contrib/llvm-project/llvm/utils/TableGen/GlobalISelEmitter.cpp

   1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// This tablegen backend emits code for use by the GlobalISel instruction
  11 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
  12 ///
  13 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
  14 /// backend, filters out the ones that are unsupported, maps
  15 /// SelectionDAG-specific constructs to their GlobalISel counterpart
  16 /// (when applicable: MVT to LLT;  SDNode to generic Instruction).
  17 ///
  18 /// Not all patterns are supported: pass the tablegen invocation
  19 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
  20 /// as well as why.
  21 ///
  22 /// The generated file defines a single method:
  23 ///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
  24 /// intended to be used in InstructionSelector::select as the first-step
  25 /// selector for the patterns that don't require complex C++.
  26 ///
  27 /// FIXME: We'll probably want to eventually define a base
  28 /// "TargetGenInstructionSelector" class.
  29 ///
  30 //===----------------------------------------------------------------------===//
  31
  32 #include "CodeGenDAGPatterns.h"
  33 #include "SubtargetFeatureInfo.h"
  34 #include "llvm/ADT/Optional.h"
  35 #include "llvm/ADT/SmallSet.h"
  36 #include "llvm/ADT/Statistic.h"
  37 #include "llvm/Support/CodeGenCoverage.h"
  38 #include "llvm/Support/CommandLine.h"
  39 #include "llvm/Support/Error.h"
  40 #include "llvm/Support/LowLevelTypeImpl.h"
  41 #include "llvm/Support/MachineValueType.h"
  42 #include "llvm/Support/ScopedPrinter.h"
  43 #include "llvm/TableGen/Error.h"
  44 #include "llvm/TableGen/Record.h"
  45 #include "llvm/TableGen/TableGenBackend.h"
  46 #include <numeric>
  47 #include <string>
  48 using namespace llvm;
  49
  50 #define DEBUG_TYPE "gisel-emitter"
  51
  52 STATISTIC(NumPatternTotal, "Total number of patterns");
  53 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
  54 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
  55 STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
  56 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
  57
  58 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
  59
  60 static cl::opt<bool> WarnOnSkippedPatterns(
  61     "warn-on-skipped-patterns",
  62     cl::desc("Explain why a pattern was skipped for inclusion "
  63              "in the GlobalISel selector"),
  64     cl::init(false), cl::cat(GlobalISelEmitterCat));
  65
  66 static cl::opt<bool> GenerateCoverage(
  67     "instrument-gisel-coverage",
  68     cl::desc("Generate coverage instrumentation for GlobalISel"),
  69     cl::init(false), cl::cat(GlobalISelEmitterCat));
  70
  71 static cl::opt<std::string> UseCoverageFile(
  72     "gisel-coverage-file", cl::init(""),
  73     cl::desc("Specify file to retrieve coverage information from"),
  74     cl::cat(GlobalISelEmitterCat));
  75
  76 static cl::opt<bool> OptimizeMatchTable(
  77     "optimize-match-table",
  78     cl::desc("Generate an optimized version of the match table"),
  79     cl::init(true), cl::cat(GlobalISelEmitterCat));
  80
  81 namespace {
  82 //===- Helper functions ---------------------------------------------------===//
  83
  84 /// Get the name of the enum value used to number the predicate function.
  85 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
  86   if (Predicate.hasGISelPredicateCode())
  87     return "GIPFP_MI_" + Predicate.getFnName();
  88   return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
  89          Predicate.getFnName();
  90 }
  91
  92 /// Get the opcode used to check this predicate.
  93 std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
  94   return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
  95 }
  96
  97 /// This class stands in for LLT wherever we want to tablegen-erate an
  98 /// equivalent at compiler run-time.
  99 class LLTCodeGen {
 100 private:
 101   LLT Ty;
 102
 103 public:
 104   LLTCodeGen() = default;
 105   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 106
 107   std::string getCxxEnumValue() const {
 108     std::string Str;
 109     raw_string_ostream OS(Str);
 110
 111     emitCxxEnumValue(OS);
 112     return OS.str();
 113   }
 114
 115   void emitCxxEnumValue(raw_ostream &OS) const {
 116     if (Ty.isScalar()) {
 117       OS << "GILLT_s" << Ty.getSizeInBits();
 118       return;
 119     }
 120     if (Ty.isVector()) {
 121       OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
 122       return;
 123     }
 124     if (Ty.isPointer()) {
 125       OS << "GILLT_p" << Ty.getAddressSpace();
 126       if (Ty.getSizeInBits() > 0)
 127         OS << "s" << Ty.getSizeInBits();
 128       return;
 129     }
 130     llvm_unreachable("Unhandled LLT");
 131   }
 132
 133   void emitCxxConstructorCall(raw_ostream &OS) const {
 134     if (Ty.isScalar()) {
 135       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
 136       return;
 137     }
 138     if (Ty.isVector()) {
 139       OS << "LLT::vector(" << Ty.getNumElements() << ", "
 140          << Ty.getScalarSizeInBits() << ")";
 141       return;
 142     }
 143     if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
 144       OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
 145          << Ty.getSizeInBits() << ")";
 146       return;
 147     }
 148     llvm_unreachable("Unhandled LLT");
 149   }
 150
 151   const LLT &get() const { return Ty; }
 152
 153   /// This ordering is used for std::unique() and llvm::sort(). There's no
 154   /// particular logic behind the order but either A < B or B < A must be
 155   /// true if A != B.
 156   bool operator<(const LLTCodeGen &Other) const {
 157     if (Ty.isValid() != Other.Ty.isValid())
 158       return Ty.isValid() < Other.Ty.isValid();
 159     if (!Ty.isValid())
 160       return false;
 161
 162     if (Ty.isVector() != Other.Ty.isVector())
 163       return Ty.isVector() < Other.Ty.isVector();
 164     if (Ty.isScalar() != Other.Ty.isScalar())
 165       return Ty.isScalar() < Other.Ty.isScalar();
 166     if (Ty.isPointer() != Other.Ty.isPointer())
 167       return Ty.isPointer() < Other.Ty.isPointer();
 168
 169     if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
 170       return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
 171
 172     if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
 173       return Ty.getNumElements() < Other.Ty.getNumElements();
 174
 175     return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
 176   }
 177
 178   bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
 179 };
 180
 181 // Track all types that are used so we can emit the corresponding enum.
 182 std::set<LLTCodeGen> KnownTypes;
 183
 184 class InstructionMatcher;
 185 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
 186 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
 187 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
 188   MVT VT(SVT);
 189
 190   if (VT.isVector() && VT.getVectorNumElements() != 1)
 191     return LLTCodeGen(
 192         LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
 193
 194   if (VT.isInteger() || VT.isFloatingPoint())
 195     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
 196   return None;
 197 }
 198
 199 static std::string explainPredicates(const TreePatternNode *N) {
 200   std::string Explanation = "";
 201   StringRef Separator = "";
 202   for (const TreePredicateCall &Call : N->getPredicateCalls()) {
 203     const TreePredicateFn &P = Call.Fn;
 204     Explanation +=
 205         (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
 206     Separator = ", ";
 207
 208     if (P.isAlwaysTrue())
 209       Explanation += " always-true";
 210     if (P.isImmediatePattern())
 211       Explanation += " immediate";
 212
 213     if (P.isUnindexed())
 214       Explanation += " unindexed";
 215
 216     if (P.isNonExtLoad())
 217       Explanation += " non-extload";
 218     if (P.isAnyExtLoad())
 219       Explanation += " extload";
 220     if (P.isSignExtLoad())
 221       Explanation += " sextload";
 222     if (P.isZeroExtLoad())
 223       Explanation += " zextload";
 224
 225     if (P.isNonTruncStore())
 226       Explanation += " non-truncstore";
 227     if (P.isTruncStore())
 228       Explanation += " truncstore";
 229
 230     if (Record *VT = P.getMemoryVT())
 231       Explanation += (" MemVT=" + VT->getName()).str();
 232     if (Record *VT = P.getScalarMemoryVT())
 233       Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
 234
 235     if (ListInit *AddrSpaces = P.getAddressSpaces()) {
 236       raw_string_ostream OS(Explanation);
 237       OS << " AddressSpaces=[";
 238
 239       StringRef AddrSpaceSeparator;
 240       for (Init *Val : AddrSpaces->getValues()) {
 241         IntInit *IntVal = dyn_cast<IntInit>(Val);
 242         if (!IntVal)
 243           continue;
 244
 245         OS << AddrSpaceSeparator << IntVal->getValue();
 246         AddrSpaceSeparator = ", ";
 247       }
 248
 249       OS << ']';
 250     }
 251
 252     int64_t MinAlign = P.getMinAlignment();
 253     if (MinAlign > 0)
 254       Explanation += " MinAlign=" + utostr(MinAlign);
 255
 256     if (P.isAtomicOrderingMonotonic())
 257       Explanation += " monotonic";
 258     if (P.isAtomicOrderingAcquire())
 259       Explanation += " acquire";
 260     if (P.isAtomicOrderingRelease())
 261       Explanation += " release";
 262     if (P.isAtomicOrderingAcquireRelease())
 263       Explanation += " acq_rel";
 264     if (P.isAtomicOrderingSequentiallyConsistent())
 265       Explanation += " seq_cst";
 266     if (P.isAtomicOrderingAcquireOrStronger())
 267       Explanation += " >=acquire";
 268     if (P.isAtomicOrderingWeakerThanAcquire())
 269       Explanation += " <acquire";
 270     if (P.isAtomicOrderingReleaseOrStronger())
 271       Explanation += " >=release";
 272     if (P.isAtomicOrderingWeakerThanRelease())
 273       Explanation += " <release";
 274   }
 275   return Explanation;
 276 }
 277
 278 std::string explainOperator(Record *Operator) {
 279   if (Operator->isSubClassOf("SDNode"))
 280     return (" (" + Operator->getValueAsString("Opcode") + ")").str();
 281
 282   if (Operator->isSubClassOf("Intrinsic"))
 283     return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
 284
 285   if (Operator->isSubClassOf("ComplexPattern"))
 286     return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
 287             ")")
 288         .str();
 289
 290   if (Operator->isSubClassOf("SDNodeXForm"))
 291     return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
 292             ")")
 293         .str();
 294
 295   return (" (Operator " + Operator->getName() + " not understood)").str();
 296 }
 297
 298 /// Helper function to let the emitter report skip reason error messages.
 299 static Error failedImport(const Twine &Reason) {
 300   return make_error<StringError>(Reason, inconvertibleErrorCode());
 301 }
 302
 303 static Error isTrivialOperatorNode(const TreePatternNode *N) {
 304   std::string Explanation = "";
 305   std::string Separator = "";
 306
 307   bool HasUnsupportedPredicate = false;
 308   for (const TreePredicateCall &Call : N->getPredicateCalls()) {
 309     const TreePredicateFn &Predicate = Call.Fn;
 310
 311     if (Predicate.isAlwaysTrue())
 312       continue;
 313
 314     if (Predicate.isImmediatePattern())
 315       continue;
 316
 317     if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
 318         Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
 319       continue;
 320
 321     if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
 322       continue;
 323
 324     if (Predicate.isLoad() && Predicate.getMemoryVT())
 325       continue;
 326
 327     if (Predicate.isLoad() || Predicate.isStore()) {
 328       if (Predicate.isUnindexed())
 329         continue;
 330     }
 331
 332     if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
 333       const ListInit *AddrSpaces = Predicate.getAddressSpaces();
 334       if (AddrSpaces && !AddrSpaces->empty())
 335         continue;
 336
 337       if (Predicate.getMinAlignment() > 0)
 338         continue;
 339     }
 340
 341     if (Predicate.isAtomic() && Predicate.getMemoryVT())
 342       continue;
 343
 344     if (Predicate.isAtomic() &&
 345         (Predicate.isAtomicOrderingMonotonic() ||
 346          Predicate.isAtomicOrderingAcquire() ||
 347          Predicate.isAtomicOrderingRelease() ||
 348          Predicate.isAtomicOrderingAcquireRelease() ||
 349          Predicate.isAtomicOrderingSequentiallyConsistent() ||
 350          Predicate.isAtomicOrderingAcquireOrStronger() ||
 351          Predicate.isAtomicOrderingWeakerThanAcquire() ||
 352          Predicate.isAtomicOrderingReleaseOrStronger() ||
 353          Predicate.isAtomicOrderingWeakerThanRelease()))
 354       continue;
 355
 356     if (Predicate.hasGISelPredicateCode())
 357       continue;
 358
 359     HasUnsupportedPredicate = true;
 360     Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
 361     Separator = ", ";
 362     Explanation += (Separator + "first-failing:" +
 363                     Predicate.getOrigPatFragRecord()->getRecord()->getName())
 364                        .str();
 365     break;
 366   }
 367
 368   if (!HasUnsupportedPredicate)
 369     return Error::success();
 370
 371   return failedImport(Explanation);
 372 }
 373
 374 static Record *getInitValueAsRegClass(Init *V) {
 375   if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
 376     if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
 377       return VDefInit->getDef()->getValueAsDef("RegClass");
 378     if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
 379       return VDefInit->getDef();
 380   }
 381   return nullptr;
 382 }
 383
 384 std::string
 385 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
 386   std::string Name = "GIFBS";
 387   for (const auto &Feature : FeatureBitset)
 388     Name += ("_" + Feature->getName()).str();
 389   return Name;
 390 }
 391
 392 //===- MatchTable Helpers -------------------------------------------------===//
 393
 394 class MatchTable;
 395
 396 /// A record to be stored in a MatchTable.
 397 ///
 398 /// This class represents any and all output that may be required to emit the
 399 /// MatchTable. Instances  are most often configured to represent an opcode or
 400 /// value that will be emitted to the table with some formatting but it can also
 401 /// represent commas, comments, and other formatting instructions.
 402 struct MatchTableRecord {
 403   enum RecordFlagsBits {
 404     MTRF_None = 0x0,
 405     /// Causes EmitStr to be formatted as comment when emitted.
 406     MTRF_Comment = 0x1,
 407     /// Causes the record value to be followed by a comma when emitted.
 408     MTRF_CommaFollows = 0x2,
 409     /// Causes the record value to be followed by a line break when emitted.
 410     MTRF_LineBreakFollows = 0x4,
 411     /// Indicates that the record defines a label and causes an additional
 412     /// comment to be emitted containing the index of the label.
 413     MTRF_Label = 0x8,
 414     /// Causes the record to be emitted as the index of the label specified by
 415     /// LabelID along with a comment indicating where that label is.
 416     MTRF_JumpTarget = 0x10,
 417     /// Causes the formatter to add a level of indentation before emitting the
 418     /// record.
 419     MTRF_Indent = 0x20,
 420     /// Causes the formatter to remove a level of indentation after emitting the
 421     /// record.
 422     MTRF_Outdent = 0x40,
 423   };
 424
 425   /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
 426   /// reference or define.
 427   unsigned LabelID;
 428   /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
 429   /// value, a label name.
 430   std::string EmitStr;
 431
 432 private:
 433   /// The number of MatchTable elements described by this record. Comments are 0
 434   /// while values are typically 1. Values >1 may occur when we need to emit
 435   /// values that exceed the size of a MatchTable element.
 436   unsigned NumElements;
 437
 438 public:
 439   /// A bitfield of RecordFlagsBits flags.
 440   unsigned Flags;
 441
 442   /// The actual run-time value, if known
 443   int64_t RawValue;
 444
 445   MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
 446                    unsigned NumElements, unsigned Flags,
 447                    int64_t RawValue = std::numeric_limits<int64_t>::min())
 448       : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
 449         EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
 450         RawValue(RawValue) {
 451     assert((!LabelID_.hasValue() || LabelID != ~0u) &&
 452            "This value is reserved for non-labels");
 453   }
 454   MatchTableRecord(const MatchTableRecord &Other) = default;
 455   MatchTableRecord(MatchTableRecord &&Other) = default;
 456
 457   /// Useful if a Match Table Record gets optimized out
 458   void turnIntoComment() {
 459     Flags |= MTRF_Comment;
 460     Flags &= ~MTRF_CommaFollows;
 461     NumElements = 0;
 462   }
 463
 464   /// For Jump Table generation purposes
 465   bool operator<(const MatchTableRecord &Other) const {
 466     return RawValue < Other.RawValue;
 467   }
 468   int64_t getRawValue() const { return RawValue; }
 469
 470   void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
 471             const MatchTable &Table) const;
 472   unsigned size() const { return NumElements; }
 473 };
 474
 475 class Matcher;
 476
 477 /// Holds the contents of a generated MatchTable to enable formatting and the
 478 /// necessary index tracking needed to support GIM_Try.
 479 class MatchTable {
 480   /// An unique identifier for the table. The generated table will be named
 481   /// MatchTable${ID}.
 482   unsigned ID;
 483   /// The records that make up the table. Also includes comments describing the
 484   /// values being emitted and line breaks to format it.
 485   std::vector<MatchTableRecord> Contents;
 486   /// The currently defined labels.
 487   DenseMap<unsigned, unsigned> LabelMap;
 488   /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
 489   unsigned CurrentSize = 0;
 490   /// A unique identifier for a MatchTable label.
 491   unsigned CurrentLabelID = 0;
 492   /// Determines if the table should be instrumented for rule coverage tracking.
 493   bool IsWithCoverage;
 494
 495 public:
 496   static MatchTableRecord LineBreak;
 497   static MatchTableRecord Comment(StringRef Comment) {
 498     return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
 499   }
 500   static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
 501     unsigned ExtraFlags = 0;
 502     if (IndentAdjust > 0)
 503       ExtraFlags |= MatchTableRecord::MTRF_Indent;
 504     if (IndentAdjust < 0)
 505       ExtraFlags |= MatchTableRecord::MTRF_Outdent;
 506
 507     return MatchTableRecord(None, Opcode, 1,
 508                             MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
 509   }
 510   static MatchTableRecord NamedValue(StringRef NamedValue) {
 511     return MatchTableRecord(None, NamedValue, 1,
 512                             MatchTableRecord::MTRF_CommaFollows);
 513   }
 514   static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
 515     return MatchTableRecord(None, NamedValue, 1,
 516                             MatchTableRecord::MTRF_CommaFollows, RawValue);
 517   }
 518   static MatchTableRecord NamedValue(StringRef Namespace,
 519                                      StringRef NamedValue) {
 520     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
 521                             MatchTableRecord::MTRF_CommaFollows);
 522   }
 523   static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
 524                                      int64_t RawValue) {
 525     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
 526                             MatchTableRecord::MTRF_CommaFollows, RawValue);
 527   }
 528   static MatchTableRecord IntValue(int64_t IntValue) {
 529     return MatchTableRecord(None, llvm::to_string(IntValue), 1,
 530                             MatchTableRecord::MTRF_CommaFollows);
 531   }
 532   static MatchTableRecord Label(unsigned LabelID) {
 533     return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
 534                             MatchTableRecord::MTRF_Label |
 535                                 MatchTableRecord::MTRF_Comment |
 536                                 MatchTableRecord::MTRF_LineBreakFollows);
 537   }
 538   static MatchTableRecord JumpTarget(unsigned LabelID) {
 539     return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
 540                             MatchTableRecord::MTRF_JumpTarget |
 541                                 MatchTableRecord::MTRF_Comment |
 542                                 MatchTableRecord::MTRF_CommaFollows);
 543   }
 544
 545   static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
 546
 547   MatchTable(bool WithCoverage, unsigned ID = 0)
 548       : ID(ID), IsWithCoverage(WithCoverage) {}
 549
 550   bool isWithCoverage() const { return IsWithCoverage; }
 551
 552   void push_back(const MatchTableRecord &Value) {
 553     if (Value.Flags & MatchTableRecord::MTRF_Label)
 554       defineLabel(Value.LabelID);
 555     Contents.push_back(Value);
 556     CurrentSize += Value.size();
 557   }
 558
 559   unsigned allocateLabelID() { return CurrentLabelID++; }
 560
 561   void defineLabel(unsigned LabelID) {
 562     LabelMap.insert(std::make_pair(LabelID, CurrentSize));
 563   }
 564
 565   unsigned getLabelIndex(unsigned LabelID) const {
 566     const auto I = LabelMap.find(LabelID);
 567     assert(I != LabelMap.end() && "Use of undeclared label");
 568     return I->second;
 569   }
 570
 571   void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
 572
 573   void emitDeclaration(raw_ostream &OS) const {
 574     unsigned Indentation = 4;
 575     OS << "  constexpr static int64_t MatchTable" << ID << "[] = {";
 576     LineBreak.emit(OS, true, *this);
 577     OS << std::string(Indentation, ' ');
 578
 579     for (auto I = Contents.begin(), E = Contents.end(); I != E;
 580          ++I) {
 581       bool LineBreakIsNext = false;
 582       const auto &NextI = std::next(I);
 583
 584       if (NextI != E) {
 585         if (NextI->EmitStr == "" &&
 586             NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
 587           LineBreakIsNext = true;
 588       }
 589
 590       if (I->Flags & MatchTableRecord::MTRF_Indent)
 591         Indentation += 2;
 592
 593       I->emit(OS, LineBreakIsNext, *this);
 594       if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
 595         OS << std::string(Indentation, ' ');
 596
 597       if (I->Flags & MatchTableRecord::MTRF_Outdent)
 598         Indentation -= 2;
 599     }
 600     OS << "};\n";
 601   }
 602 };
 603
 604 MatchTableRecord MatchTable::LineBreak = {
 605     None, "" /* Emit String */, 0 /* Elements */,
 606     MatchTableRecord::MTRF_LineBreakFollows};
 607
 608 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
 609                             const MatchTable &Table) const {
 610   bool UseLineComment =
 611       LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
 612   if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
 613     UseLineComment = false;
 614
 615   if (Flags & MTRF_Comment)
 616     OS << (UseLineComment ? "// " : "/*");
 617
 618   OS << EmitStr;
 619   if (Flags & MTRF_Label)
 620     OS << ": @" << Table.getLabelIndex(LabelID);
 621
 622   if ((Flags & MTRF_Comment) && !UseLineComment)
 623     OS << "*/";
 624
 625   if (Flags & MTRF_JumpTarget) {
 626     if (Flags & MTRF_Comment)
 627       OS << " ";
 628     OS << Table.getLabelIndex(LabelID);
 629   }
 630
 631   if (Flags & MTRF_CommaFollows) {
 632     OS << ",";
 633     if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
 634       OS << " ";
 635   }
 636
 637   if (Flags & MTRF_LineBreakFollows)
 638     OS << "\n";
 639 }
 640
 641 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
 642   Table.push_back(Value);
 643   return Table;
 644 }
 645
 646 //===- Matchers -----------------------------------------------------------===//
 647
 648 class OperandMatcher;
 649 class MatchAction;
 650 class PredicateMatcher;
 651 class RuleMatcher;
 652
 653 class Matcher {
 654 public:
 655   virtual ~Matcher() = default;
 656   virtual void optimize() {}
 657   virtual void emit(MatchTable &Table) = 0;
 658
 659   virtual bool hasFirstCondition() const = 0;
 660   virtual const PredicateMatcher &getFirstCondition() const = 0;
 661   virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
 662 };
 663
 664 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
 665                                   bool WithCoverage) {
 666   MatchTable Table(WithCoverage);
 667   for (Matcher *Rule : Rules)
 668     Rule->emit(Table);
 669
 670   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 671 }
 672
 673 class GroupMatcher final : public Matcher {
 674   /// Conditions that form a common prefix of all the matchers contained.
 675   SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
 676
 677   /// All the nested matchers, sharing a common prefix.
 678   std::vector<Matcher *> Matchers;
 679
 680   /// An owning collection for any auxiliary matchers created while optimizing
 681   /// nested matchers contained.
 682   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
 683
 684 public:
 685   /// Add a matcher to the collection of nested matchers if it meets the
 686   /// requirements, and return true. If it doesn't, do nothing and return false.
 687   ///
 688   /// Expected to preserve its argument, so it could be moved out later on.
 689   bool addMatcher(Matcher &Candidate);
 690
 691   /// Mark the matcher as fully-built and ensure any invariants expected by both
 692   /// optimize() and emit(...) methods. Generally, both sequences of calls
 693   /// are expected to lead to a sensible result:
 694   ///
 695   /// addMatcher(...)*; finalize(); optimize(); emit(...); and
 696   /// addMatcher(...)*; finalize(); emit(...);
 697   ///
 698   /// or generally
 699   ///
 700   /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
 701   ///
 702   /// Multiple calls to optimize() are expected to be handled gracefully, though
 703   /// optimize() is not expected to be idempotent. Multiple calls to finalize()
 704   /// aren't generally supported. emit(...) is expected to be non-mutating and
 705   /// producing the exact same results upon repeated calls.
 706   ///
 707   /// addMatcher() calls after the finalize() call are not supported.
 708   ///
 709   /// finalize() and optimize() are both allowed to mutate the contained
 710   /// matchers, so moving them out after finalize() is not supported.
 711   void finalize();
 712   void optimize() override;
 713   void emit(MatchTable &Table) override;
 714
 715   /// Could be used to move out the matchers added previously, unless finalize()
 716   /// has been already called. If any of the matchers are moved out, the group
 717   /// becomes safe to destroy, but not safe to re-use for anything else.
 718   iterator_range<std::vector<Matcher *>::iterator> matchers() {
 719     return make_range(Matchers.begin(), Matchers.end());
 720   }
 721   size_t size() const { return Matchers.size(); }
 722   bool empty() const { return Matchers.empty(); }
 723
 724   std::unique_ptr<PredicateMatcher> popFirstCondition() override {
 725     assert(!Conditions.empty() &&
 726            "Trying to pop a condition from a condition-less group");
 727     std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
 728     Conditions.erase(Conditions.begin());
 729     return P;
 730   }
 731   const PredicateMatcher &getFirstCondition() const override {
 732     assert(!Conditions.empty() &&
 733            "Trying to get a condition from a condition-less group");
 734     return *Conditions.front();
 735   }
 736   bool hasFirstCondition() const override { return !Conditions.empty(); }
 737
 738 private:
 739   /// See if a candidate matcher could be added to this group solely by
 740   /// analyzing its first condition.
 741   bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
 742 };
 743
 744 class SwitchMatcher : public Matcher {
 745   /// All the nested matchers, representing distinct switch-cases. The first
 746   /// conditions (as Matcher::getFirstCondition() reports) of all the nested
 747   /// matchers must share the same type and path to a value they check, in other
 748   /// words, be isIdenticalDownToValue, but have different values they check
 749   /// against.
 750   std::vector<Matcher *> Matchers;
 751
 752   /// The representative condition, with a type and a path (InsnVarID and OpIdx
 753   /// in most cases)  shared by all the matchers contained.
 754   std::unique_ptr<PredicateMatcher> Condition = nullptr;
 755
 756   /// Temporary set used to check that the case values don't repeat within the
 757   /// same switch.
 758   std::set<MatchTableRecord> Values;
 759
 760   /// An owning collection for any auxiliary matchers created while optimizing
 761   /// nested matchers contained.
 762   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
 763
 764 public:
 765   bool addMatcher(Matcher &Candidate);
 766
 767   void finalize();
 768   void emit(MatchTable &Table) override;
 769
 770   iterator_range<std::vector<Matcher *>::iterator> matchers() {
 771     return make_range(Matchers.begin(), Matchers.end());
 772   }
 773   size_t size() const { return Matchers.size(); }
 774   bool empty() const { return Matchers.empty(); }
 775
 776   std::unique_ptr<PredicateMatcher> popFirstCondition() override {
 777     // SwitchMatcher doesn't have a common first condition for its cases, as all
 778     // the cases only share a kind of a value (a type and a path to it) they
 779     // match, but deliberately differ in the actual value they match.
 780     llvm_unreachable("Trying to pop a condition from a condition-less group");
 781   }
 782   const PredicateMatcher &getFirstCondition() const override {
 783     llvm_unreachable("Trying to pop a condition from a condition-less group");
 784   }
 785   bool hasFirstCondition() const override { return false; }
 786
 787 private:
 788   /// See if the predicate type has a Switch-implementation for it.
 789   static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
 790
 791   bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
 792
 793   /// emit()-helper
 794   static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
 795                                            MatchTable &Table);
 796 };
 797
 798 /// Generates code to check that a match rule matches.
 799 class RuleMatcher : public Matcher {
 800 public:
 801   using ActionList = std::list<std::unique_ptr<MatchAction>>;
 802   using action_iterator = ActionList::iterator;
 803
 804 protected:
 805   /// A list of matchers that all need to succeed for the current rule to match.
 806   /// FIXME: This currently supports a single match position but could be
 807   /// extended to support multiple positions to support div/rem fusion or
 808   /// load-multiple instructions.
 809   using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
 810   MatchersTy Matchers;
 811
 812   /// A list of actions that need to be taken when all predicates in this rule
 813   /// have succeeded.
 814   ActionList Actions;
 815
 816   using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
 817
 818   /// A map of instruction matchers to the local variables
 819   DefinedInsnVariablesMap InsnVariableIDs;
 820
 821   using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
 822
 823   // The set of instruction matchers that have not yet been claimed for mutation
 824   // by a BuildMI.
 825   MutatableInsnSet MutatableInsns;
 826
 827   /// A map of named operands defined by the matchers that may be referenced by
 828   /// the renderers.
 829   StringMap<OperandMatcher *> DefinedOperands;
 830
 831   /// A map of anonymous physical register operands defined by the matchers that
 832   /// may be referenced by the renderers.
 833   DenseMap<Record *, OperandMatcher *> PhysRegOperands;
 834
 835   /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
 836   unsigned NextInsnVarID;
 837
 838   /// ID for the next output instruction allocated with allocateOutputInsnID()
 839   unsigned NextOutputInsnID;
 840
 841   /// ID for the next temporary register ID allocated with allocateTempRegID()
 842   unsigned NextTempRegID;
 843
 844   std::vector<Record *> RequiredFeatures;
 845   std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
 846
 847   ArrayRef<SMLoc> SrcLoc;
 848
 849   typedef std::tuple<Record *, unsigned, unsigned>
 850       DefinedComplexPatternSubOperand;
 851   typedef StringMap<DefinedComplexPatternSubOperand>
 852       DefinedComplexPatternSubOperandMap;
 853   /// A map of Symbolic Names to ComplexPattern sub-operands.
 854   DefinedComplexPatternSubOperandMap ComplexSubOperands;
 855
 856   uint64_t RuleID;
 857   static uint64_t NextRuleID;
 858
 859 public:
 860   RuleMatcher(ArrayRef<SMLoc> SrcLoc)
 861       : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
 862         DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
 863         NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
 864         RuleID(NextRuleID++) {}
 865   RuleMatcher(RuleMatcher &&Other) = default;
 866   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 867
 868   uint64_t getRuleID() const { return RuleID; }
 869
 870   InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
 871   void addRequiredFeature(Record *Feature);
 872   const std::vector<Record *> &getRequiredFeatures() const;
 873
 874   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 875   template <class Kind, class... Args>
 876   action_iterator insertAction(action_iterator InsertPt, Args &&... args);
 877
 878   /// Define an instruction without emitting any code to do so.
 879   unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
 880
 881   unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
 882   DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
 883     return InsnVariableIDs.begin();
 884   }
 885   DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
 886     return InsnVariableIDs.end();
 887   }
 888   iterator_range<typename DefinedInsnVariablesMap::const_iterator>
 889   defined_insn_vars() const {
 890     return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
 891   }
 892
 893   MutatableInsnSet::const_iterator mutatable_insns_begin() const {
 894     return MutatableInsns.begin();
 895   }
 896   MutatableInsnSet::const_iterator mutatable_insns_end() const {
 897     return MutatableInsns.end();
 898   }
 899   iterator_range<typename MutatableInsnSet::const_iterator>
 900   mutatable_insns() const {
 901     return make_range(mutatable_insns_begin(), mutatable_insns_end());
 902   }
 903   void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
 904     bool R = MutatableInsns.erase(InsnMatcher);
 905     assert(R && "Reserving a mutatable insn that isn't available");
 906     (void)R;
 907   }
 908
 909   action_iterator actions_begin() { return Actions.begin(); }
 910   action_iterator actions_end() { return Actions.end(); }
 911   iterator_range<action_iterator> actions() {
 912     return make_range(actions_begin(), actions_end());
 913   }
 914
 915   void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
 916
 917   void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
 918
 919   Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
 920                                 unsigned RendererID, unsigned SubOperandID) {
 921     if (ComplexSubOperands.count(SymbolicName))
 922       return failedImport(
 923           "Complex suboperand referenced more than once (Operand: " +
 924           SymbolicName + ")");
 925
 926     ComplexSubOperands[SymbolicName] =
 927         std::make_tuple(ComplexPattern, RendererID, SubOperandID);
 928
 929     return Error::success();
 930   }
 931
 932   Optional<DefinedComplexPatternSubOperand>
 933   getComplexSubOperand(StringRef SymbolicName) const {
 934     const auto &I = ComplexSubOperands.find(SymbolicName);
 935     if (I == ComplexSubOperands.end())
 936       return None;
 937     return I->second;
 938   }
 939
 940   InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
 941   const OperandMatcher &getOperandMatcher(StringRef Name) const;
 942   const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
 943
 944   void optimize() override;
 945   void emit(MatchTable &Table) override;
 946
 947   /// Compare the priority of this object and B.
 948   ///
 949   /// Returns true if this object is more important than B.
 950   bool isHigherPriorityThan(const RuleMatcher &B) const;
 951
 952   /// Report the maximum number of temporary operands needed by the rule
 953   /// matcher.
 954   unsigned countRendererFns() const;
 955
 956   std::unique_ptr<PredicateMatcher> popFirstCondition() override;
 957   const PredicateMatcher &getFirstCondition() const override;
 958   LLTCodeGen getFirstConditionAsRootType();
 959   bool hasFirstCondition() const override;
 960   unsigned getNumOperands() const;
 961   StringRef getOpcode() const;
 962
 963   // FIXME: Remove this as soon as possible
 964   InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
 965
 966   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
 967   unsigned allocateTempRegID() { return NextTempRegID++; }
 968
 969   iterator_range<MatchersTy::iterator> insnmatchers() {
 970     return make_range(Matchers.begin(), Matchers.end());
 971   }
 972   bool insnmatchers_empty() const { return Matchers.empty(); }
 973   void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
 974 };
 975
 976 uint64_t RuleMatcher::NextRuleID = 0;
 977
 978 using action_iterator = RuleMatcher::action_iterator;
 979
 980 template <class PredicateTy> class PredicateListMatcher {
 981 private:
 982   /// Template instantiations should specialize this to return a string to use
 983   /// for the comment emitted when there are no predicates.
 984   std::string getNoPredicateComment() const;
 985
 986 protected:
 987   using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
 988   PredicatesTy Predicates;
 989
 990   /// Track if the list of predicates was manipulated by one of the optimization
 991   /// methods.
 992   bool Optimized = false;
 993
 994 public:
 995   /// Construct a new predicate and add it to the matcher.
 996   template <class Kind, class... Args>
 997   Optional<Kind *> addPredicate(Args &&... args);
 998
 999   typename PredicatesTy::iterator predicates_begin() {
1000     return Predicates.begin();
1001   }
1002   typename PredicatesTy::iterator predicates_end() {
1003     return Predicates.end();
1004   }
1005   iterator_range<typename PredicatesTy::iterator> predicates() {
1006     return make_range(predicates_begin(), predicates_end());
1007   }
1008   typename PredicatesTy::size_type predicates_size() const {
1009     return Predicates.size();
1010   }
1011   bool predicates_empty() const { return Predicates.empty(); }
1012
1013   std::unique_ptr<PredicateTy> predicates_pop_front() {
1014     std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1015     Predicates.pop_front();
1016     Optimized = true;
1017     return Front;
1018   }
1019
1020   void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1021     Predicates.push_front(std::move(Predicate));
1022   }
1023
1024   void eraseNullPredicates() {
1025     const auto NewEnd =
1026         std::stable_partition(Predicates.begin(), Predicates.end(),
1027                               std::logical_not<std::unique_ptr<PredicateTy>>());
1028     if (NewEnd != Predicates.begin()) {
1029       Predicates.erase(Predicates.begin(), NewEnd);
1030       Optimized = true;
1031     }
1032   }
1033
1034   /// Emit MatchTable opcodes that tests whether all the predicates are met.
1035   template <class... Args>
1036   void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1037     if (Predicates.empty() && !Optimized) {
1038       Table << MatchTable::Comment(getNoPredicateComment())
1039             << MatchTable::LineBreak;
1040       return;
1041     }
1042
1043     for (const auto &Predicate : predicates())
1044       Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1045   }
1046
1047   /// Provide a function to avoid emitting certain predicates. This is used to
1048   /// defer some predicate checks until after others
1049   using PredicateFilterFunc = std::function<bool(const PredicateTy&)>;
1050
1051   /// Emit MatchTable opcodes for predicates which satisfy \p
1052   /// ShouldEmitPredicate. This should be called multiple times to ensure all
1053   /// predicates are eventually added to the match table.
1054   template <class... Args>
1055   void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
1056                                         MatchTable &Table, Args &&... args) {
1057     if (Predicates.empty() && !Optimized) {
1058       Table << MatchTable::Comment(getNoPredicateComment())
1059             << MatchTable::LineBreak;
1060       return;
1061     }
1062
1063     for (const auto &Predicate : predicates()) {
1064       if (ShouldEmitPredicate(*Predicate))
1065         Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1066     }
1067   }
1068 };
1069
1070 class PredicateMatcher {
1071 public:
1072   /// This enum is used for RTTI and also defines the priority that is given to
1073   /// the predicate when generating the matcher code. Kinds with higher priority
1074   /// must be tested first.
1075   ///
1076   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1077   /// but OPM_Int must have priority over OPM_RegBank since constant integers
1078   /// are represented by a virtual register defined by a G_CONSTANT instruction.
1079   ///
1080   /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1081   /// are currently not compared between each other.
1082   enum PredicateKind {
1083     IPM_Opcode,
1084     IPM_NumOperands,
1085     IPM_ImmPredicate,
1086     IPM_Imm,
1087     IPM_AtomicOrderingMMO,
1088     IPM_MemoryLLTSize,
1089     IPM_MemoryVsLLTSize,
1090     IPM_MemoryAddressSpace,
1091     IPM_MemoryAlignment,
1092     IPM_GenericPredicate,
1093     OPM_SameOperand,
1094     OPM_ComplexPattern,
1095     OPM_IntrinsicID,
1096     OPM_CmpPredicate,
1097     OPM_Instruction,
1098     OPM_Int,
1099     OPM_LiteralInt,
1100     OPM_LLT,
1101     OPM_PointerToAny,
1102     OPM_RegBank,
1103     OPM_MBB,
1104   };
1105
1106 protected:
1107   PredicateKind Kind;
1108   unsigned InsnVarID;
1109   unsigned OpIdx;
1110
1111 public:
1112   PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1113       : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1114
1115   unsigned getInsnVarID() const { return InsnVarID; }
1116   unsigned getOpIdx() const { return OpIdx; }
1117
1118   virtual ~PredicateMatcher() = default;
1119   /// Emit MatchTable opcodes that check the predicate for the given operand.
1120   virtual void emitPredicateOpcodes(MatchTable &Table,
1121                                     RuleMatcher &Rule) const = 0;
1122
1123   PredicateKind getKind() const { return Kind; }
1124
1125   bool dependsOnOperands() const {
1126     // Custom predicates really depend on the context pattern of the
1127     // instruction, not just the individual instruction. This therefore
1128     // implicitly depends on all other pattern constraints.
1129     return Kind == IPM_GenericPredicate;
1130   }
1131
1132   virtual bool isIdentical(const PredicateMatcher &B) const {
1133     return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1134            OpIdx == B.OpIdx;
1135   }
1136
1137   virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1138     return hasValue() && PredicateMatcher::isIdentical(B);
1139   }
1140
1141   virtual MatchTableRecord getValue() const {
1142     assert(hasValue() && "Can not get a value of a value-less predicate!");
1143     llvm_unreachable("Not implemented yet");
1144   }
1145   virtual bool hasValue() const { return false; }
1146
1147   /// Report the maximum number of temporary operands needed by the predicate
1148   /// matcher.
1149   virtual unsigned countRendererFns() const { return 0; }
1150 };
1151
1152 /// Generates code to check a predicate of an operand.
1153 ///
1154 /// Typical predicates include:
1155 /// * Operand is a particular register.
1156 /// * Operand is assigned a particular register bank.
1157 /// * Operand is an MBB.
1158 class OperandPredicateMatcher : public PredicateMatcher {
1159 public:
1160   OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1161                           unsigned OpIdx)
1162       : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
1163   virtual ~OperandPredicateMatcher() {}
1164
1165   /// Compare the priority of this object and B.
1166   ///
1167   /// Returns true if this object is more important than B.
1168   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1169 };
1170
1171 template <>
1172 std::string
1173 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1174   return "No operand predicates";
1175 }
1176
1177 /// Generates code to check that a register operand is defined by the same exact
1178 /// one as another.
1179 class SameOperandMatcher : public OperandPredicateMatcher {
1180   std::string MatchingName;
1181
1182 public:
1183   SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1184       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1185         MatchingName(MatchingName) {}
1186
1187   static bool classof(const PredicateMatcher *P) {
1188     return P->getKind() == OPM_SameOperand;
1189   }
1190
1191   void emitPredicateOpcodes(MatchTable &Table,
1192                             RuleMatcher &Rule) const override;
1193
1194   bool isIdentical(const PredicateMatcher &B) const override {
1195     return OperandPredicateMatcher::isIdentical(B) &&
1196            MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1197   }
1198 };
1199
1200 /// Generates code to check that an operand is a particular LLT.
1201 class LLTOperandMatcher : public OperandPredicateMatcher {
1202 protected:
1203   LLTCodeGen Ty;
1204
1205 public:
1206   static std::map<LLTCodeGen, unsigned> TypeIDValues;
1207
1208   static void initTypeIDValuesMap() {
1209     TypeIDValues.clear();
1210
1211     unsigned ID = 0;
1212     for (const LLTCodeGen &LLTy : KnownTypes)
1213       TypeIDValues[LLTy] = ID++;
1214   }
1215
1216   LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1217       : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1218     KnownTypes.insert(Ty);
1219   }
1220
1221   static bool classof(const PredicateMatcher *P) {
1222     return P->getKind() == OPM_LLT;
1223   }
1224   bool isIdentical(const PredicateMatcher &B) const override {
1225     return OperandPredicateMatcher::isIdentical(B) &&
1226            Ty == cast<LLTOperandMatcher>(&B)->Ty;
1227   }
1228   MatchTableRecord getValue() const override {
1229     const auto VI = TypeIDValues.find(Ty);
1230     if (VI == TypeIDValues.end())
1231       return MatchTable::NamedValue(getTy().getCxxEnumValue());
1232     return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1233   }
1234   bool hasValue() const override {
1235     if (TypeIDValues.size() != KnownTypes.size())
1236       initTypeIDValuesMap();
1237     return TypeIDValues.count(Ty);
1238   }
1239
1240   LLTCodeGen getTy() const { return Ty; }
1241
1242   void emitPredicateOpcodes(MatchTable &Table,
1243                             RuleMatcher &Rule) const override {
1244     Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1245           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1246           << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1247           << getValue() << MatchTable::LineBreak;
1248   }
1249 };
1250
1251 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1252
1253 /// Generates code to check that an operand is a pointer to any address space.
1254 ///
1255 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1256 /// result, iN is used to describe a pointer of N bits to any address space and
1257 /// PatFrag predicates are typically used to constrain the address space. There's
1258 /// no reliable means to derive the missing type information from the pattern so
1259 /// imported rules must test the components of a pointer separately.
1260 ///
1261 /// If SizeInBits is zero, then the pointer size will be obtained from the
1262 /// subtarget.
1263 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1264 protected:
1265   unsigned SizeInBits;
1266
1267 public:
1268   PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1269                              unsigned SizeInBits)
1270       : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1271         SizeInBits(SizeInBits) {}
1272
1273   static bool classof(const OperandPredicateMatcher *P) {
1274     return P->getKind() == OPM_PointerToAny;
1275   }
1276
1277   void emitPredicateOpcodes(MatchTable &Table,
1278                             RuleMatcher &Rule) const override {
1279     Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1280           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1281           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1282           << MatchTable::Comment("SizeInBits")
1283           << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1284   }
1285 };
1286
1287 /// Generates code to check that an operand is a particular target constant.
1288 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1289 protected:
1290   const OperandMatcher &Operand;
1291   const Record &TheDef;
1292
1293   unsigned getAllocatedTemporariesBaseID() const;
1294
1295 public:
1296   bool isIdentical(const PredicateMatcher &B) const override { return false; }
1297
1298   ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1299                                const OperandMatcher &Operand,
1300                                const Record &TheDef)
1301       : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1302         Operand(Operand), TheDef(TheDef) {}
1303
1304   static bool classof(const PredicateMatcher *P) {
1305     return P->getKind() == OPM_ComplexPattern;
1306   }
1307
1308   void emitPredicateOpcodes(MatchTable &Table,
1309                             RuleMatcher &Rule) const override {
1310     unsigned ID = getAllocatedTemporariesBaseID();
1311     Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1312           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1313           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1314           << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1315           << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1316           << MatchTable::LineBreak;
1317   }
1318
1319   unsigned countRendererFns() const override {
1320     return 1;
1321   }
1322 };
1323
1324 /// Generates code to check that an operand is in a particular register bank.
1325 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1326 protected:
1327   const CodeGenRegisterClass &RC;
1328
1329 public:
1330   RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1331                              const CodeGenRegisterClass &RC)
1332       : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1333
1334   bool isIdentical(const PredicateMatcher &B) const override {
1335     return OperandPredicateMatcher::isIdentical(B) &&
1336            RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1337   }
1338
1339   static bool classof(const PredicateMatcher *P) {
1340     return P->getKind() == OPM_RegBank;
1341   }
1342
1343   void emitPredicateOpcodes(MatchTable &Table,
1344                             RuleMatcher &Rule) const override {
1345     Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1346           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1347           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1348           << MatchTable::Comment("RC")
1349           << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1350           << MatchTable::LineBreak;
1351   }
1352 };
1353
1354 /// Generates code to check that an operand is a basic block.
1355 class MBBOperandMatcher : public OperandPredicateMatcher {
1356 public:
1357   MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1358       : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1359
1360   static bool classof(const PredicateMatcher *P) {
1361     return P->getKind() == OPM_MBB;
1362   }
1363
1364   void emitPredicateOpcodes(MatchTable &Table,
1365                             RuleMatcher &Rule) const override {
1366     Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1367           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1368           << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1369   }
1370 };
1371
1372 class ImmOperandMatcher : public OperandPredicateMatcher {
1373 public:
1374   ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1375       : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1376
1377   static bool classof(const PredicateMatcher *P) {
1378     return P->getKind() == IPM_Imm;
1379   }
1380
1381   void emitPredicateOpcodes(MatchTable &Table,
1382                             RuleMatcher &Rule) const override {
1383     Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1384           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1385           << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1386   }
1387 };
1388
1389 /// Generates code to check that an operand is a G_CONSTANT with a particular
1390 /// int.
1391 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1392 protected:
1393   int64_t Value;
1394
1395 public:
1396   ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1397       : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1398
1399   bool isIdentical(const PredicateMatcher &B) const override {
1400     return OperandPredicateMatcher::isIdentical(B) &&
1401            Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1402   }
1403
1404   static bool classof(const PredicateMatcher *P) {
1405     return P->getKind() == OPM_Int;
1406   }
1407
1408   void emitPredicateOpcodes(MatchTable &Table,
1409                             RuleMatcher &Rule) const override {
1410     Table << MatchTable::Opcode("GIM_CheckConstantInt")
1411           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1412           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1413           << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1414   }
1415 };
1416
1417 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1418 /// MO.isCImm() is true).
1419 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1420 protected:
1421   int64_t Value;
1422
1423 public:
1424   LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1425       : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1426         Value(Value) {}
1427
1428   bool isIdentical(const PredicateMatcher &B) const override {
1429     return OperandPredicateMatcher::isIdentical(B) &&
1430            Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1431   }
1432
1433   static bool classof(const PredicateMatcher *P) {
1434     return P->getKind() == OPM_LiteralInt;
1435   }
1436
1437   void emitPredicateOpcodes(MatchTable &Table,
1438                             RuleMatcher &Rule) const override {
1439     Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1440           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1441           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1442           << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1443   }
1444 };
1445
1446 /// Generates code to check that an operand is an CmpInst predicate
1447 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1448 protected:
1449   std::string PredName;
1450
1451 public:
1452   CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1453                              std::string P)
1454     : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1455
1456   bool isIdentical(const PredicateMatcher &B) const override {
1457     return OperandPredicateMatcher::isIdentical(B) &&
1458            PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1459   }
1460
1461   static bool classof(const PredicateMatcher *P) {
1462     return P->getKind() == OPM_CmpPredicate;
1463   }
1464
1465   void emitPredicateOpcodes(MatchTable &Table,
1466                             RuleMatcher &Rule) const override {
1467     Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1468           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1469           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1470           << MatchTable::Comment("Predicate")
1471           << MatchTable::NamedValue("CmpInst", PredName)
1472           << MatchTable::LineBreak;
1473   }
1474 };
1475
1476 /// Generates code to check that an operand is an intrinsic ID.
1477 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1478 protected:
1479   const CodeGenIntrinsic *II;
1480
1481 public:
1482   IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1483                             const CodeGenIntrinsic *II)
1484       : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1485
1486   bool isIdentical(const PredicateMatcher &B) const override {
1487     return OperandPredicateMatcher::isIdentical(B) &&
1488            II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1489   }
1490
1491   static bool classof(const PredicateMatcher *P) {
1492     return P->getKind() == OPM_IntrinsicID;
1493   }
1494
1495   void emitPredicateOpcodes(MatchTable &Table,
1496                             RuleMatcher &Rule) const override {
1497     Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1498           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1499           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1500           << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1501           << MatchTable::LineBreak;
1502   }
1503 };
1504
1505 /// Generates code to check that a set of predicates match for a particular
1506 /// operand.
1507 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1508 protected:
1509   InstructionMatcher &Insn;
1510   unsigned OpIdx;
1511   std::string SymbolicName;
1512
1513   /// The index of the first temporary variable allocated to this operand. The
1514   /// number of allocated temporaries can be found with
1515   /// countRendererFns().
1516   unsigned AllocatedTemporariesBaseID;
1517
1518 public:
1519   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1520                  const std::string &SymbolicName,
1521                  unsigned AllocatedTemporariesBaseID)
1522       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1523         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1524
1525   bool hasSymbolicName() const { return !SymbolicName.empty(); }
1526   const StringRef getSymbolicName() const { return SymbolicName; }
1527   void setSymbolicName(StringRef Name) {
1528     assert(SymbolicName.empty() && "Operand already has a symbolic name");
1529     SymbolicName = std::string(Name);
1530   }
1531
1532   /// Construct a new operand predicate and add it to the matcher.
1533   template <class Kind, class... Args>
1534   Optional<Kind *> addPredicate(Args &&... args) {
1535     if (isSameAsAnotherOperand())
1536       return None;
1537     Predicates.emplace_back(std::make_unique<Kind>(
1538         getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1539     return static_cast<Kind *>(Predicates.back().get());
1540   }
1541
1542   unsigned getOpIdx() const { return OpIdx; }
1543   unsigned getInsnVarID() const;
1544
1545   std::string getOperandExpr(unsigned InsnVarID) const {
1546     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1547            llvm::to_string(OpIdx) + ")";
1548   }
1549
1550   InstructionMatcher &getInstructionMatcher() const { return Insn; }
1551
1552   Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1553                               bool OperandIsAPointer);
1554
1555   /// Emit MatchTable opcodes that test whether the instruction named in
1556   /// InsnVarID matches all the predicates and all the operands.
1557   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1558     if (!Optimized) {
1559       std::string Comment;
1560       raw_string_ostream CommentOS(Comment);
1561       CommentOS << "MIs[" << getInsnVarID() << "] ";
1562       if (SymbolicName.empty())
1563         CommentOS << "Operand " << OpIdx;
1564       else
1565         CommentOS << SymbolicName;
1566       Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1567     }
1568
1569     emitPredicateListOpcodes(Table, Rule);
1570   }
1571
1572   /// Compare the priority of this object and B.
1573   ///
1574   /// Returns true if this object is more important than B.
1575   bool isHigherPriorityThan(OperandMatcher &B) {
1576     // Operand matchers involving more predicates have higher priority.
1577     if (predicates_size() > B.predicates_size())
1578       return true;
1579     if (predicates_size() < B.predicates_size())
1580       return false;
1581
1582     // This assumes that predicates are added in a consistent order.
1583     for (auto &&Predicate : zip(predicates(), B.predicates())) {
1584       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1585         return true;
1586       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1587         return false;
1588     }
1589
1590     return false;
1591   };
1592
1593   /// Report the maximum number of temporary operands needed by the operand
1594   /// matcher.
1595   unsigned countRendererFns() {
1596     return std::accumulate(
1597         predicates().begin(), predicates().end(), 0,
1598         [](unsigned A,
1599            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1600           return A + Predicate->countRendererFns();
1601         });
1602   }
1603
1604   unsigned getAllocatedTemporariesBaseID() const {
1605     return AllocatedTemporariesBaseID;
1606   }
1607
1608   bool isSameAsAnotherOperand() {
1609     for (const auto &Predicate : predicates())
1610       if (isa<SameOperandMatcher>(Predicate))
1611         return true;
1612     return false;
1613   }
1614 };
1615
1616 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1617                                             bool OperandIsAPointer) {
1618   if (!VTy.isMachineValueType())
1619     return failedImport("unsupported typeset");
1620
1621   if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1622     addPredicate<PointerToAnyOperandMatcher>(0);
1623     return Error::success();
1624   }
1625
1626   auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1627   if (!OpTyOrNone)
1628     return failedImport("unsupported type");
1629
1630   if (OperandIsAPointer)
1631     addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1632   else if (VTy.isPointer())
1633     addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1634                                                  OpTyOrNone->get().getSizeInBits()));
1635   else
1636     addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1637   return Error::success();
1638 }
1639
1640 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1641   return Operand.getAllocatedTemporariesBaseID();
1642 }
1643
1644 /// Generates code to check a predicate on an instruction.
1645 ///
1646 /// Typical predicates include:
1647 /// * The opcode of the instruction is a particular value.
1648 /// * The nsw/nuw flag is/isn't set.
1649 class InstructionPredicateMatcher : public PredicateMatcher {
1650 public:
1651   InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1652       : PredicateMatcher(Kind, InsnVarID) {}
1653   virtual ~InstructionPredicateMatcher() {}
1654
1655   /// Compare the priority of this object and B.
1656   ///
1657   /// Returns true if this object is more important than B.
1658   virtual bool
1659   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1660     return Kind < B.Kind;
1661   };
1662 };
1663
1664 template <>
1665 std::string
1666 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1667   return "No instruction predicates";
1668 }
1669
1670 /// Generates code to check the opcode of an instruction.
1671 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1672 protected:
1673   const CodeGenInstruction *I;
1674
1675   static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1676
1677 public:
1678   static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1679     OpcodeValues.clear();
1680
1681     unsigned OpcodeValue = 0;
1682     for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1683       OpcodeValues[I] = OpcodeValue++;
1684   }
1685
1686   InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1687       : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1688
1689   static bool classof(const PredicateMatcher *P) {
1690     return P->getKind() == IPM_Opcode;
1691   }
1692
1693   bool isIdentical(const PredicateMatcher &B) const override {
1694     return InstructionPredicateMatcher::isIdentical(B) &&
1695            I == cast<InstructionOpcodeMatcher>(&B)->I;
1696   }
1697   MatchTableRecord getValue() const override {
1698     const auto VI = OpcodeValues.find(I);
1699     if (VI != OpcodeValues.end())
1700       return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1701                                     VI->second);
1702     return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1703   }
1704   bool hasValue() const override { return OpcodeValues.count(I); }
1705
1706   void emitPredicateOpcodes(MatchTable &Table,
1707                             RuleMatcher &Rule) const override {
1708     Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1709           << MatchTable::IntValue(InsnVarID) << getValue()
1710           << MatchTable::LineBreak;
1711   }
1712
1713   /// Compare the priority of this object and B.
1714   ///
1715   /// Returns true if this object is more important than B.
1716   bool
1717   isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1718     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1719       return true;
1720     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1721       return false;
1722
1723     // Prioritize opcodes for cosmetic reasons in the generated source. Although
1724     // this is cosmetic at the moment, we may want to drive a similar ordering
1725     // using instruction frequency information to improve compile time.
1726     if (const InstructionOpcodeMatcher *BO =
1727             dyn_cast<InstructionOpcodeMatcher>(&B))
1728       return I->TheDef->getName() < BO->I->TheDef->getName();
1729
1730     return false;
1731   };
1732
1733   bool isConstantInstruction() const {
1734     return I->TheDef->getName() == "G_CONSTANT";
1735   }
1736
1737   StringRef getOpcode() const { return I->TheDef->getName(); }
1738   bool isVariadicNumOperands() const { return I->Operands.isVariadic; }
1739
1740   StringRef getOperandType(unsigned OpIdx) const {
1741     return I->Operands[OpIdx].OperandType;
1742   }
1743 };
1744
1745 DenseMap<const CodeGenInstruction *, unsigned>
1746     InstructionOpcodeMatcher::OpcodeValues;
1747
1748 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1749   unsigned NumOperands = 0;
1750
1751 public:
1752   InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1753       : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1754         NumOperands(NumOperands) {}
1755
1756   static bool classof(const PredicateMatcher *P) {
1757     return P->getKind() == IPM_NumOperands;
1758   }
1759
1760   bool isIdentical(const PredicateMatcher &B) const override {
1761     return InstructionPredicateMatcher::isIdentical(B) &&
1762            NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1763   }
1764
1765   void emitPredicateOpcodes(MatchTable &Table,
1766                             RuleMatcher &Rule) const override {
1767     Table << MatchTable::Opcode("GIM_CheckNumOperands")
1768           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1769           << MatchTable::Comment("Expected")
1770           << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1771   }
1772 };
1773
1774 /// Generates code to check that this instruction is a constant whose value
1775 /// meets an immediate predicate.
1776 ///
1777 /// Immediates are slightly odd since they are typically used like an operand
1778 /// but are represented as an operator internally. We typically write simm8:$src
1779 /// in a tablegen pattern, but this is just syntactic sugar for
1780 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1781 /// that will be matched and the predicate (which is attached to the imm
1782 /// operator) that will be tested. In SelectionDAG this describes a
1783 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1784 ///
1785 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1786 /// this representation, the immediate could be tested with an
1787 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1788 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1789 /// there are two implementation issues with producing that matcher
1790 /// configuration from the SelectionDAG pattern:
1791 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1792 ///   were we to sink the immediate predicate to the operand we would have to
1793 ///   have two partial implementations of PatFrag support, one for immediates
1794 ///   and one for non-immediates.
1795 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1796 ///   created yet. If we were to sink the predicate to the OperandMatcher we
1797 ///   would also have to complicate (or duplicate) the code that descends and
1798 ///   creates matchers for the subtree.
1799 /// Overall, it's simpler to handle it in the place it was found.
1800 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1801 protected:
1802   TreePredicateFn Predicate;
1803
1804 public:
1805   InstructionImmPredicateMatcher(unsigned InsnVarID,
1806                                  const TreePredicateFn &Predicate)
1807       : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1808         Predicate(Predicate) {}
1809
1810   bool isIdentical(const PredicateMatcher &B) const override {
1811     return InstructionPredicateMatcher::isIdentical(B) &&
1812            Predicate.getOrigPatFragRecord() ==
1813                cast<InstructionImmPredicateMatcher>(&B)
1814                    ->Predicate.getOrigPatFragRecord();
1815   }
1816
1817   static bool classof(const PredicateMatcher *P) {
1818     return P->getKind() == IPM_ImmPredicate;
1819   }
1820
1821   void emitPredicateOpcodes(MatchTable &Table,
1822                             RuleMatcher &Rule) const override {
1823     Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1824           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1825           << MatchTable::Comment("Predicate")
1826           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1827           << MatchTable::LineBreak;
1828   }
1829 };
1830
1831 /// Generates code to check that a memory instruction has a atomic ordering
1832 /// MachineMemoryOperand.
1833 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1834 public:
1835   enum AOComparator {
1836     AO_Exactly,
1837     AO_OrStronger,
1838     AO_WeakerThan,
1839   };
1840
1841 protected:
1842   StringRef Order;
1843   AOComparator Comparator;
1844
1845 public:
1846   AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1847                                     AOComparator Comparator = AO_Exactly)
1848       : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1849         Order(Order), Comparator(Comparator) {}
1850
1851   static bool classof(const PredicateMatcher *P) {
1852     return P->getKind() == IPM_AtomicOrderingMMO;
1853   }
1854
1855   bool isIdentical(const PredicateMatcher &B) const override {
1856     if (!InstructionPredicateMatcher::isIdentical(B))
1857       return false;
1858     const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1859     return Order == R.Order && Comparator == R.Comparator;
1860   }
1861
1862   void emitPredicateOpcodes(MatchTable &Table,
1863                             RuleMatcher &Rule) const override {
1864     StringRef Opcode = "GIM_CheckAtomicOrdering";
1865
1866     if (Comparator == AO_OrStronger)
1867       Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1868     if (Comparator == AO_WeakerThan)
1869       Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1870
1871     Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1872           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1873           << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1874           << MatchTable::LineBreak;
1875   }
1876 };
1877
1878 /// Generates code to check that the size of an MMO is exactly N bytes.
1879 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1880 protected:
1881   unsigned MMOIdx;
1882   uint64_t Size;
1883
1884 public:
1885   MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1886       : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1887         MMOIdx(MMOIdx), Size(Size) {}
1888
1889   static bool classof(const PredicateMatcher *P) {
1890     return P->getKind() == IPM_MemoryLLTSize;
1891   }
1892   bool isIdentical(const PredicateMatcher &B) const override {
1893     return InstructionPredicateMatcher::isIdentical(B) &&
1894            MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1895            Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1896   }
1897
1898   void emitPredicateOpcodes(MatchTable &Table,
1899                             RuleMatcher &Rule) const override {
1900     Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1901           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1902           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1903           << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1904           << MatchTable::LineBreak;
1905   }
1906 };
1907
1908 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1909 protected:
1910   unsigned MMOIdx;
1911   SmallVector<unsigned, 4> AddrSpaces;
1912
1913 public:
1914   MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1915                                      ArrayRef<unsigned> AddrSpaces)
1916       : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1917         MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1918
1919   static bool classof(const PredicateMatcher *P) {
1920     return P->getKind() == IPM_MemoryAddressSpace;
1921   }
1922   bool isIdentical(const PredicateMatcher &B) const override {
1923     if (!InstructionPredicateMatcher::isIdentical(B))
1924       return false;
1925     auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1926     return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1927   }
1928
1929   void emitPredicateOpcodes(MatchTable &Table,
1930                             RuleMatcher &Rule) const override {
1931     Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1932           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1933           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1934         // Encode number of address spaces to expect.
1935           << MatchTable::Comment("NumAddrSpace")
1936           << MatchTable::IntValue(AddrSpaces.size());
1937     for (unsigned AS : AddrSpaces)
1938       Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
1939
1940     Table << MatchTable::LineBreak;
1941   }
1942 };
1943
1944 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
1945 protected:
1946   unsigned MMOIdx;
1947   int MinAlign;
1948
1949 public:
1950   MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1951                                   int MinAlign)
1952       : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
1953         MMOIdx(MMOIdx), MinAlign(MinAlign) {
1954     assert(MinAlign > 0);
1955   }
1956
1957   static bool classof(const PredicateMatcher *P) {
1958     return P->getKind() == IPM_MemoryAlignment;
1959   }
1960
1961   bool isIdentical(const PredicateMatcher &B) const override {
1962     if (!InstructionPredicateMatcher::isIdentical(B))
1963       return false;
1964     auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1965     return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1966   }
1967
1968   void emitPredicateOpcodes(MatchTable &Table,
1969                             RuleMatcher &Rule) const override {
1970     Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1971           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1972           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1973           << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
1974           << MatchTable::LineBreak;
1975   }
1976 };
1977
1978 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1979 /// greater than a given LLT.
1980 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1981 public:
1982   enum RelationKind {
1983     GreaterThan,
1984     EqualTo,
1985     LessThan,
1986   };
1987
1988 protected:
1989   unsigned MMOIdx;
1990   RelationKind Relation;
1991   unsigned OpIdx;
1992
1993 public:
1994   MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1995                                   enum RelationKind Relation,
1996                                   unsigned OpIdx)
1997       : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1998         MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1999
2000   static bool classof(const PredicateMatcher *P) {
2001     return P->getKind() == IPM_MemoryVsLLTSize;
2002   }
2003   bool isIdentical(const PredicateMatcher &B) const override {
2004     return InstructionPredicateMatcher::isIdentical(B) &&
2005            MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
2006            Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
2007            OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
2008   }
2009
2010   void emitPredicateOpcodes(MatchTable &Table,
2011                             RuleMatcher &Rule) const override {
2012     Table << MatchTable::Opcode(Relation == EqualTo
2013                                     ? "GIM_CheckMemorySizeEqualToLLT"
2014                                     : Relation == GreaterThan
2015                                           ? "GIM_CheckMemorySizeGreaterThanLLT"
2016                                           : "GIM_CheckMemorySizeLessThanLLT")
2017           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2018           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2019           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2020           << MatchTable::LineBreak;
2021   }
2022 };
2023
2024 /// Generates code to check an arbitrary C++ instruction predicate.
2025 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
2026 protected:
2027   TreePredicateFn Predicate;
2028
2029 public:
2030   GenericInstructionPredicateMatcher(unsigned InsnVarID,
2031                                      TreePredicateFn Predicate)
2032       : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2033         Predicate(Predicate) {}
2034
2035   static bool classof(const InstructionPredicateMatcher *P) {
2036     return P->getKind() == IPM_GenericPredicate;
2037   }
2038   bool isIdentical(const PredicateMatcher &B) const override {
2039     return InstructionPredicateMatcher::isIdentical(B) &&
2040            Predicate ==
2041                static_cast<const GenericInstructionPredicateMatcher &>(B)
2042                    .Predicate;
2043   }
2044   void emitPredicateOpcodes(MatchTable &Table,
2045                             RuleMatcher &Rule) const override {
2046     Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2047           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2048           << MatchTable::Comment("FnId")
2049           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2050           << MatchTable::LineBreak;
2051   }
2052 };
2053
2054 /// Generates code to check that a set of predicates and operands match for a
2055 /// particular instruction.
2056 ///
2057 /// Typical predicates include:
2058 /// * Has a specific opcode.
2059 /// * Has an nsw/nuw flag or doesn't.
2060 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2061 protected:
2062   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2063
2064   RuleMatcher &Rule;
2065
2066   /// The operands to match. All rendered operands must be present even if the
2067   /// condition is always true.
2068   OperandVec Operands;
2069   bool NumOperandsCheck = true;
2070
2071   std::string SymbolicName;
2072   unsigned InsnVarID;
2073
2074   /// PhysRegInputs - List list has an entry for each explicitly specified
2075   /// physreg input to the pattern.  The first elt is the Register node, the
2076   /// second is the recorded slot number the input pattern match saved it in.
2077   SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2078
2079 public:
2080   InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
2081       : Rule(Rule), SymbolicName(SymbolicName) {
2082     // We create a new instruction matcher.
2083     // Get a new ID for that instruction.
2084     InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2085   }
2086
2087   /// Construct a new instruction predicate and add it to the matcher.
2088   template <class Kind, class... Args>
2089   Optional<Kind *> addPredicate(Args &&... args) {
2090     Predicates.emplace_back(
2091         std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2092     return static_cast<Kind *>(Predicates.back().get());
2093   }
2094
2095   RuleMatcher &getRuleMatcher() const { return Rule; }
2096
2097   unsigned getInsnVarID() const { return InsnVarID; }
2098
2099   /// Add an operand to the matcher.
2100   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2101                              unsigned AllocatedTemporariesBaseID) {
2102     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2103                                              AllocatedTemporariesBaseID));
2104     if (!SymbolicName.empty())
2105       Rule.defineOperand(SymbolicName, *Operands.back());
2106
2107     return *Operands.back();
2108   }
2109
2110   OperandMatcher &getOperand(unsigned OpIdx) {
2111     auto I = std::find_if(Operands.begin(), Operands.end(),
2112                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2113                             return X->getOpIdx() == OpIdx;
2114                           });
2115     if (I != Operands.end())
2116       return **I;
2117     llvm_unreachable("Failed to lookup operand");
2118   }
2119
2120   OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2121                                   unsigned TempOpIdx) {
2122     assert(SymbolicName.empty());
2123     OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2124     Operands.emplace_back(OM);
2125     Rule.definePhysRegOperand(Reg, *OM);
2126     PhysRegInputs.emplace_back(Reg, OpIdx);
2127     return *OM;
2128   }
2129
2130   ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2131     return PhysRegInputs;
2132   }
2133
2134   StringRef getSymbolicName() const { return SymbolicName; }
2135   unsigned getNumOperands() const { return Operands.size(); }
2136   OperandVec::iterator operands_begin() { return Operands.begin(); }
2137   OperandVec::iterator operands_end() { return Operands.end(); }
2138   iterator_range<OperandVec::iterator> operands() {
2139     return make_range(operands_begin(), operands_end());
2140   }
2141   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
2142   OperandVec::const_iterator operands_end() const { return Operands.end(); }
2143   iterator_range<OperandVec::const_iterator> operands() const {
2144     return make_range(operands_begin(), operands_end());
2145   }
2146   bool operands_empty() const { return Operands.empty(); }
2147
2148   void pop_front() { Operands.erase(Operands.begin()); }
2149
2150   void optimize();
2151
2152   /// Emit MatchTable opcodes that test whether the instruction named in
2153   /// InsnVarName matches all the predicates and all the operands.
2154   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2155     if (NumOperandsCheck)
2156       InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2157           .emitPredicateOpcodes(Table, Rule);
2158
2159     // First emit all instruction level predicates need to be verified before we
2160     // can verify operands.
2161     emitFilteredPredicateListOpcodes(
2162       [](const PredicateMatcher &P) {
2163         return !P.dependsOnOperands();
2164       }, Table, Rule);
2165
2166     // Emit all operand constraints.
2167     for (const auto &Operand : Operands)
2168       Operand->emitPredicateOpcodes(Table, Rule);
2169
2170     // All of the tablegen defined predicates should now be matched. Now emit
2171     // any custom predicates that rely on all generated checks.
2172     emitFilteredPredicateListOpcodes(
2173       [](const PredicateMatcher &P) {
2174         return P.dependsOnOperands();
2175       }, Table, Rule);
2176   }
2177
2178   /// Compare the priority of this object and B.
2179   ///
2180   /// Returns true if this object is more important than B.
2181   bool isHigherPriorityThan(InstructionMatcher &B) {
2182     // Instruction matchers involving more operands have higher priority.
2183     if (Operands.size() > B.Operands.size())
2184       return true;
2185     if (Operands.size() < B.Operands.size())
2186       return false;
2187
2188     for (auto &&P : zip(predicates(), B.predicates())) {
2189       auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2190       auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2191       if (L->isHigherPriorityThan(*R))
2192         return true;
2193       if (R->isHigherPriorityThan(*L))
2194         return false;
2195     }
2196
2197     for (auto Operand : zip(Operands, B.Operands)) {
2198       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2199         return true;
2200       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2201         return false;
2202     }
2203
2204     return false;
2205   };
2206
2207   /// Report the maximum number of temporary operands needed by the instruction
2208   /// matcher.
2209   unsigned countRendererFns() {
2210     return std::accumulate(
2211                predicates().begin(), predicates().end(), 0,
2212                [](unsigned A,
2213                   const std::unique_ptr<PredicateMatcher> &Predicate) {
2214                  return A + Predicate->countRendererFns();
2215                }) +
2216            std::accumulate(
2217                Operands.begin(), Operands.end(), 0,
2218                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2219                  return A + Operand->countRendererFns();
2220                });
2221   }
2222
2223   InstructionOpcodeMatcher &getOpcodeMatcher() {
2224     for (auto &P : predicates())
2225       if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2226         return *OpMatcher;
2227     llvm_unreachable("Didn't find an opcode matcher");
2228   }
2229
2230   bool isConstantInstruction() {
2231     return getOpcodeMatcher().isConstantInstruction();
2232   }
2233
2234   StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2235 };
2236
2237 StringRef RuleMatcher::getOpcode() const {
2238   return Matchers.front()->getOpcode();
2239 }
2240
2241 unsigned RuleMatcher::getNumOperands() const {
2242   return Matchers.front()->getNumOperands();
2243 }
2244
2245 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2246   InstructionMatcher &InsnMatcher = *Matchers.front();
2247   if (!InsnMatcher.predicates_empty())
2248     if (const auto *TM =
2249             dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2250       if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2251         return TM->getTy();
2252   return {};
2253 }
2254
2255 /// Generates code to check that the operand is a register defined by an
2256 /// instruction that matches the given instruction matcher.
2257 ///
2258 /// For example, the pattern:
2259 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2260 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2261 /// the:
2262 ///   (G_ADD $src1, $src2)
2263 /// subpattern.
2264 class InstructionOperandMatcher : public OperandPredicateMatcher {
2265 protected:
2266   std::unique_ptr<InstructionMatcher> InsnMatcher;
2267
2268 public:
2269   InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2270                             RuleMatcher &Rule, StringRef SymbolicName)
2271       : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2272         InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2273
2274   static bool classof(const PredicateMatcher *P) {
2275     return P->getKind() == OPM_Instruction;
2276   }
2277
2278   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2279
2280   void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2281     const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2282     Table << MatchTable::Opcode("GIM_RecordInsn")
2283           << MatchTable::Comment("DefineMI")
2284           << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2285           << MatchTable::IntValue(getInsnVarID())
2286           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2287           << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2288           << MatchTable::LineBreak;
2289   }
2290
2291   void emitPredicateOpcodes(MatchTable &Table,
2292                             RuleMatcher &Rule) const override {
2293     emitCaptureOpcodes(Table, Rule);
2294     InsnMatcher->emitPredicateOpcodes(Table, Rule);
2295   }
2296
2297   bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2298     if (OperandPredicateMatcher::isHigherPriorityThan(B))
2299       return true;
2300     if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2301       return false;
2302
2303     if (const InstructionOperandMatcher *BP =
2304             dyn_cast<InstructionOperandMatcher>(&B))
2305       if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2306         return true;
2307     return false;
2308   }
2309 };
2310
2311 void InstructionMatcher::optimize() {
2312   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2313   const auto &OpcMatcher = getOpcodeMatcher();
2314
2315   Stash.push_back(predicates_pop_front());
2316   if (Stash.back().get() == &OpcMatcher) {
2317     if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
2318       Stash.emplace_back(
2319           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2320     NumOperandsCheck = false;
2321
2322     for (auto &OM : Operands)
2323       for (auto &OP : OM->predicates())
2324         if (isa<IntrinsicIDOperandMatcher>(OP)) {
2325           Stash.push_back(std::move(OP));
2326           OM->eraseNullPredicates();
2327           break;
2328         }
2329   }
2330
2331   if (InsnVarID > 0) {
2332     assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2333     for (auto &OP : Operands[0]->predicates())
2334       OP.reset();
2335     Operands[0]->eraseNullPredicates();
2336   }
2337   for (auto &OM : Operands) {
2338     for (auto &OP : OM->predicates())
2339       if (isa<LLTOperandMatcher>(OP))
2340         Stash.push_back(std::move(OP));
2341     OM->eraseNullPredicates();
2342   }
2343   while (!Stash.empty())
2344     prependPredicate(Stash.pop_back_val());
2345 }
2346
2347 //===- Actions ------------------------------------------------------------===//
2348 class OperandRenderer {
2349 public:
2350   enum RendererKind {
2351     OR_Copy,
2352     OR_CopyOrAddZeroReg,
2353     OR_CopySubReg,
2354     OR_CopyPhysReg,
2355     OR_CopyConstantAsImm,
2356     OR_CopyFConstantAsFPImm,
2357     OR_Imm,
2358     OR_SubRegIndex,
2359     OR_Register,
2360     OR_TempRegister,
2361     OR_ComplexPattern,
2362     OR_Custom,
2363     OR_CustomOperand
2364   };
2365
2366 protected:
2367   RendererKind Kind;
2368
2369 public:
2370   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2371   virtual ~OperandRenderer() {}
2372
2373   RendererKind getKind() const { return Kind; }
2374
2375   virtual void emitRenderOpcodes(MatchTable &Table,
2376                                  RuleMatcher &Rule) const = 0;
2377 };
2378
2379 /// A CopyRenderer emits code to copy a single operand from an existing
2380 /// instruction to the one being built.
2381 class CopyRenderer : public OperandRenderer {
2382 protected:
2383   unsigned NewInsnID;
2384   /// The name of the operand.
2385   const StringRef SymbolicName;
2386
2387 public:
2388   CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2389       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2390         SymbolicName(SymbolicName) {
2391     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2392   }
2393
2394   static bool classof(const OperandRenderer *R) {
2395     return R->getKind() == OR_Copy;
2396   }
2397
2398   const StringRef getSymbolicName() const { return SymbolicName; }
2399
2400   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2401     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2402     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2403     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2404           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2405           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2406           << MatchTable::IntValue(Operand.getOpIdx())
2407           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2408   }
2409 };
2410
2411 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2412 /// register.
2413 class CopyPhysRegRenderer : public OperandRenderer {
2414 protected:
2415   unsigned NewInsnID;
2416   Record *PhysReg;
2417
2418 public:
2419   CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2420       : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2421         PhysReg(Reg) {
2422     assert(PhysReg);
2423   }
2424
2425   static bool classof(const OperandRenderer *R) {
2426     return R->getKind() == OR_CopyPhysReg;
2427   }
2428
2429   Record *getPhysReg() const { return PhysReg; }
2430
2431   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2432     const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2433     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2434     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2435           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2436           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2437           << MatchTable::IntValue(Operand.getOpIdx())
2438           << MatchTable::Comment(PhysReg->getName())
2439           << MatchTable::LineBreak;
2440   }
2441 };
2442
2443 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2444 /// existing instruction to the one being built. If the operand turns out to be
2445 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2446 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2447 protected:
2448   unsigned NewInsnID;
2449   /// The name of the operand.
2450   const StringRef SymbolicName;
2451   const Record *ZeroRegisterDef;
2452
2453 public:
2454   CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2455                            StringRef SymbolicName, Record *ZeroRegisterDef)
2456       : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2457         SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2458     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2459   }
2460
2461   static bool classof(const OperandRenderer *R) {
2462     return R->getKind() == OR_CopyOrAddZeroReg;
2463   }
2464
2465   const StringRef getSymbolicName() const { return SymbolicName; }
2466
2467   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2468     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2469     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2470     Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2471           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2472           << MatchTable::Comment("OldInsnID")
2473           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2474           << MatchTable::IntValue(Operand.getOpIdx())
2475           << MatchTable::NamedValue(
2476                  (ZeroRegisterDef->getValue("Namespace")
2477                       ? ZeroRegisterDef->getValueAsString("Namespace")
2478                       : ""),
2479                  ZeroRegisterDef->getName())
2480           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2481   }
2482 };
2483
2484 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2485 /// an extended immediate operand.
2486 class CopyConstantAsImmRenderer : public OperandRenderer {
2487 protected:
2488   unsigned NewInsnID;
2489   /// The name of the operand.
2490   const std::string SymbolicName;
2491   bool Signed;
2492
2493 public:
2494   CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2495       : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2496         SymbolicName(SymbolicName), Signed(true) {}
2497
2498   static bool classof(const OperandRenderer *R) {
2499     return R->getKind() == OR_CopyConstantAsImm;
2500   }
2501
2502   const StringRef getSymbolicName() const { return SymbolicName; }
2503
2504   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2505     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2506     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2507     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2508                                        : "GIR_CopyConstantAsUImm")
2509           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2510           << MatchTable::Comment("OldInsnID")
2511           << MatchTable::IntValue(OldInsnVarID)
2512           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2513   }
2514 };
2515
2516 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2517 /// instruction to an extended immediate operand.
2518 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2519 protected:
2520   unsigned NewInsnID;
2521   /// The name of the operand.
2522   const std::string SymbolicName;
2523
2524 public:
2525   CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2526       : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2527         SymbolicName(SymbolicName) {}
2528
2529   static bool classof(const OperandRenderer *R) {
2530     return R->getKind() == OR_CopyFConstantAsFPImm;
2531   }
2532
2533   const StringRef getSymbolicName() const { return SymbolicName; }
2534
2535   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2536     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2537     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2538     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2539           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2540           << MatchTable::Comment("OldInsnID")
2541           << MatchTable::IntValue(OldInsnVarID)
2542           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2543   }
2544 };
2545
2546 /// A CopySubRegRenderer emits code to copy a single register operand from an
2547 /// existing instruction to the one being built and indicate that only a
2548 /// subregister should be copied.
2549 class CopySubRegRenderer : public OperandRenderer {
2550 protected:
2551   unsigned NewInsnID;
2552   /// The name of the operand.
2553   const StringRef SymbolicName;
2554   /// The subregister to extract.
2555   const CodeGenSubRegIndex *SubReg;
2556
2557 public:
2558   CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2559                      const CodeGenSubRegIndex *SubReg)
2560       : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2561         SymbolicName(SymbolicName), SubReg(SubReg) {}
2562
2563   static bool classof(const OperandRenderer *R) {
2564     return R->getKind() == OR_CopySubReg;
2565   }
2566
2567   const StringRef getSymbolicName() const { return SymbolicName; }
2568
2569   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2570     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2571     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2572     Table << MatchTable::Opcode("GIR_CopySubReg")
2573           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2574           << MatchTable::Comment("OldInsnID")
2575           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2576           << MatchTable::IntValue(Operand.getOpIdx())
2577           << MatchTable::Comment("SubRegIdx")
2578           << MatchTable::IntValue(SubReg->EnumValue)
2579           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2580   }
2581 };
2582
2583 /// Adds a specific physical register to the instruction being built.
2584 /// This is typically useful for WZR/XZR on AArch64.
2585 class AddRegisterRenderer : public OperandRenderer {
2586 protected:
2587   unsigned InsnID;
2588   const Record *RegisterDef;
2589   bool IsDef;
2590
2591 public:
2592   AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef,
2593                       bool IsDef = false)
2594       : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2595         IsDef(IsDef) {}
2596
2597   static bool classof(const OperandRenderer *R) {
2598     return R->getKind() == OR_Register;
2599   }
2600
2601   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2602     Table << MatchTable::Opcode("GIR_AddRegister")
2603           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2604           << MatchTable::NamedValue(
2605                  (RegisterDef->getValue("Namespace")
2606                       ? RegisterDef->getValueAsString("Namespace")
2607                       : ""),
2608                  RegisterDef->getName())
2609           << MatchTable::Comment("AddRegisterRegFlags");
2610
2611     // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2612     // really needed for a physical register reference. We can pack the
2613     // register and flags in a single field.
2614     if (IsDef)
2615       Table << MatchTable::NamedValue("RegState::Define");
2616     else
2617       Table << MatchTable::IntValue(0);
2618     Table << MatchTable::LineBreak;
2619   }
2620 };
2621
2622 /// Adds a specific temporary virtual register to the instruction being built.
2623 /// This is used to chain instructions together when emitting multiple
2624 /// instructions.
2625 class TempRegRenderer : public OperandRenderer {
2626 protected:
2627   unsigned InsnID;
2628   unsigned TempRegID;
2629   const CodeGenSubRegIndex *SubRegIdx;
2630   bool IsDef;
2631
2632 public:
2633   TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false,
2634                   const CodeGenSubRegIndex *SubReg = nullptr)
2635       : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2636         SubRegIdx(SubReg), IsDef(IsDef) {}
2637
2638   static bool classof(const OperandRenderer *R) {
2639     return R->getKind() == OR_TempRegister;
2640   }
2641
2642   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2643     if (SubRegIdx) {
2644       assert(!IsDef);
2645       Table << MatchTable::Opcode("GIR_AddTempSubRegister");
2646     } else
2647       Table << MatchTable::Opcode("GIR_AddTempRegister");
2648
2649     Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2650           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2651           << MatchTable::Comment("TempRegFlags");
2652
2653     if (IsDef)
2654       Table << MatchTable::NamedValue("RegState::Define");
2655     else
2656       Table << MatchTable::IntValue(0);
2657
2658     if (SubRegIdx)
2659       Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName());
2660     Table << MatchTable::LineBreak;
2661   }
2662 };
2663
2664 /// Adds a specific immediate to the instruction being built.
2665 class ImmRenderer : public OperandRenderer {
2666 protected:
2667   unsigned InsnID;
2668   int64_t Imm;
2669
2670 public:
2671   ImmRenderer(unsigned InsnID, int64_t Imm)
2672       : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2673
2674   static bool classof(const OperandRenderer *R) {
2675     return R->getKind() == OR_Imm;
2676   }
2677
2678   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2679     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2680           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2681           << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2682   }
2683 };
2684
2685 /// Adds an enum value for a subreg index to the instruction being built.
2686 class SubRegIndexRenderer : public OperandRenderer {
2687 protected:
2688   unsigned InsnID;
2689   const CodeGenSubRegIndex *SubRegIdx;
2690
2691 public:
2692   SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2693       : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2694
2695   static bool classof(const OperandRenderer *R) {
2696     return R->getKind() == OR_SubRegIndex;
2697   }
2698
2699   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2700     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2701           << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2702           << MatchTable::IntValue(SubRegIdx->EnumValue)
2703           << MatchTable::LineBreak;
2704   }
2705 };
2706
2707 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2708 /// matcher function.
2709 class RenderComplexPatternOperand : public OperandRenderer {
2710 private:
2711   unsigned InsnID;
2712   const Record &TheDef;
2713   /// The name of the operand.
2714   const StringRef SymbolicName;
2715   /// The renderer number. This must be unique within a rule since it's used to
2716   /// identify a temporary variable to hold the renderer function.
2717   unsigned RendererID;
2718   /// When provided, this is the suboperand of the ComplexPattern operand to
2719   /// render. Otherwise all the suboperands will be rendered.
2720   Optional<unsigned> SubOperand;
2721
2722   unsigned getNumOperands() const {
2723     return TheDef.getValueAsDag("Operands")->getNumArgs();
2724   }
2725
2726 public:
2727   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2728                               StringRef SymbolicName, unsigned RendererID,
2729                               Optional<unsigned> SubOperand = None)
2730       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2731         SymbolicName(SymbolicName), RendererID(RendererID),
2732         SubOperand(SubOperand) {}
2733
2734   static bool classof(const OperandRenderer *R) {
2735     return R->getKind() == OR_ComplexPattern;
2736   }
2737
2738   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2739     Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2740                                                       : "GIR_ComplexRenderer")
2741           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2742           << MatchTable::Comment("RendererID")
2743           << MatchTable::IntValue(RendererID);
2744     if (SubOperand.hasValue())
2745       Table << MatchTable::Comment("SubOperand")
2746             << MatchTable::IntValue(SubOperand.getValue());
2747     Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2748   }
2749 };
2750
2751 class CustomRenderer : public OperandRenderer {
2752 protected:
2753   unsigned InsnID;
2754   const Record &Renderer;
2755   /// The name of the operand.
2756   const std::string SymbolicName;
2757
2758 public:
2759   CustomRenderer(unsigned InsnID, const Record &Renderer,
2760                  StringRef SymbolicName)
2761       : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2762         SymbolicName(SymbolicName) {}
2763
2764   static bool classof(const OperandRenderer *R) {
2765     return R->getKind() == OR_Custom;
2766   }
2767
2768   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2769     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2770     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2771     Table << MatchTable::Opcode("GIR_CustomRenderer")
2772           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2773           << MatchTable::Comment("OldInsnID")
2774           << MatchTable::IntValue(OldInsnVarID)
2775           << MatchTable::Comment("Renderer")
2776           << MatchTable::NamedValue(
2777                  "GICR_" + Renderer.getValueAsString("RendererFn").str())
2778           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2779   }
2780 };
2781
2782 class CustomOperandRenderer : public OperandRenderer {
2783 protected:
2784   unsigned InsnID;
2785   const Record &Renderer;
2786   /// The name of the operand.
2787   const std::string SymbolicName;
2788
2789 public:
2790   CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2791                         StringRef SymbolicName)
2792       : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2793         SymbolicName(SymbolicName) {}
2794
2795   static bool classof(const OperandRenderer *R) {
2796     return R->getKind() == OR_CustomOperand;
2797   }
2798
2799   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2800     const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2801     Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2802           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2803           << MatchTable::Comment("OldInsnID")
2804           << MatchTable::IntValue(OpdMatcher.getInsnVarID())
2805           << MatchTable::Comment("OpIdx")
2806           << MatchTable::IntValue(OpdMatcher.getOpIdx())
2807           << MatchTable::Comment("OperandRenderer")
2808           << MatchTable::NamedValue(
2809             "GICR_" + Renderer.getValueAsString("RendererFn").str())
2810           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2811   }
2812 };
2813
2814 /// An action taken when all Matcher predicates succeeded for a parent rule.
2815 ///
2816 /// Typical actions include:
2817 /// * Changing the opcode of an instruction.
2818 /// * Adding an operand to an instruction.
2819 class MatchAction {
2820 public:
2821   virtual ~MatchAction() {}
2822
2823   /// Emit the MatchTable opcodes to implement the action.
2824   virtual void emitActionOpcodes(MatchTable &Table,
2825                                  RuleMatcher &Rule) const = 0;
2826 };
2827
2828 /// Generates a comment describing the matched rule being acted upon.
2829 class DebugCommentAction : public MatchAction {
2830 private:
2831   std::string S;
2832
2833 public:
2834   DebugCommentAction(StringRef S) : S(std::string(S)) {}
2835
2836   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2837     Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2838   }
2839 };
2840
2841 /// Generates code to build an instruction or mutate an existing instruction
2842 /// into the desired instruction when this is possible.
2843 class BuildMIAction : public MatchAction {
2844 private:
2845   unsigned InsnID;
2846   const CodeGenInstruction *I;
2847   InstructionMatcher *Matched;
2848   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2849
2850   /// True if the instruction can be built solely by mutating the opcode.
2851   bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2852     if (!Insn)
2853       return false;
2854
2855     if (OperandRenderers.size() != Insn->getNumOperands())
2856       return false;
2857
2858     for (const auto &Renderer : enumerate(OperandRenderers)) {
2859       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2860         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2861         if (Insn != &OM.getInstructionMatcher() ||
2862             OM.getOpIdx() != Renderer.index())
2863           return false;
2864       } else
2865         return false;
2866     }
2867
2868     return true;
2869   }
2870
2871 public:
2872   BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2873       : InsnID(InsnID), I(I), Matched(nullptr) {}
2874
2875   unsigned getInsnID() const { return InsnID; }
2876   const CodeGenInstruction *getCGI() const { return I; }
2877
2878   void chooseInsnToMutate(RuleMatcher &Rule) {
2879     for (auto *MutateCandidate : Rule.mutatable_insns()) {
2880       if (canMutate(Rule, MutateCandidate)) {
2881         // Take the first one we're offered that we're able to mutate.
2882         Rule.reserveInsnMatcherForMutation(MutateCandidate);
2883         Matched = MutateCandidate;
2884         return;
2885       }
2886     }
2887   }
2888
2889   template <class Kind, class... Args>
2890   Kind &addRenderer(Args&&... args) {
2891     OperandRenderers.emplace_back(
2892         std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2893     return *static_cast<Kind *>(OperandRenderers.back().get());
2894   }
2895
2896   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2897     if (Matched) {
2898       assert(canMutate(Rule, Matched) &&
2899              "Arranged to mutate an insn that isn't mutatable");
2900
2901       unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2902       Table << MatchTable::Opcode("GIR_MutateOpcode")
2903             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2904             << MatchTable::Comment("RecycleInsnID")
2905             << MatchTable::IntValue(RecycleInsnID)
2906             << MatchTable::Comment("Opcode")
2907             << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2908             << MatchTable::LineBreak;
2909
2910       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2911         for (auto Def : I->ImplicitDefs) {
2912           auto Namespace = Def->getValue("Namespace")
2913                                ? Def->getValueAsString("Namespace")
2914                                : "";
2915           Table << MatchTable::Opcode("GIR_AddImplicitDef")
2916                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2917                 << MatchTable::NamedValue(Namespace, Def->getName())
2918                 << MatchTable::LineBreak;
2919         }
2920         for (auto Use : I->ImplicitUses) {
2921           auto Namespace = Use->getValue("Namespace")
2922                                ? Use->getValueAsString("Namespace")
2923                                : "";
2924           Table << MatchTable::Opcode("GIR_AddImplicitUse")
2925                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2926                 << MatchTable::NamedValue(Namespace, Use->getName())
2927                 << MatchTable::LineBreak;
2928         }
2929       }
2930       return;
2931     }
2932
2933     // TODO: Simple permutation looks like it could be almost as common as
2934     //       mutation due to commutative operations.
2935
2936     Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2937           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2938           << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2939           << MatchTable::LineBreak;
2940     for (const auto &Renderer : OperandRenderers)
2941       Renderer->emitRenderOpcodes(Table, Rule);
2942
2943     if (I->mayLoad || I->mayStore) {
2944       Table << MatchTable::Opcode("GIR_MergeMemOperands")
2945             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2946             << MatchTable::Comment("MergeInsnID's");
2947       // Emit the ID's for all the instructions that are matched by this rule.
2948       // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2949       //       some other means of having a memoperand. Also limit this to
2950       //       emitted instructions that expect to have a memoperand too. For
2951       //       example, (G_SEXT (G_LOAD x)) that results in separate load and
2952       //       sign-extend instructions shouldn't put the memoperand on the
2953       //       sign-extend since it has no effect there.
2954       std::vector<unsigned> MergeInsnIDs;
2955       for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2956         MergeInsnIDs.push_back(IDMatcherPair.second);
2957       llvm::sort(MergeInsnIDs);
2958       for (const auto &MergeInsnID : MergeInsnIDs)
2959         Table << MatchTable::IntValue(MergeInsnID);
2960       Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2961             << MatchTable::LineBreak;
2962     }
2963
2964     // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2965     //        better for combines. Particularly when there are multiple match
2966     //        roots.
2967     if (InsnID == 0)
2968       Table << MatchTable::Opcode("GIR_EraseFromParent")
2969             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2970             << MatchTable::LineBreak;
2971   }
2972 };
2973
2974 /// Generates code to constrain the operands of an output instruction to the
2975 /// register classes specified by the definition of that instruction.
2976 class ConstrainOperandsToDefinitionAction : public MatchAction {
2977   unsigned InsnID;
2978
2979 public:
2980   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2981
2982   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2983     Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2984           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2985           << MatchTable::LineBreak;
2986   }
2987 };
2988
2989 /// Generates code to constrain the specified operand of an output instruction
2990 /// to the specified register class.
2991 class ConstrainOperandToRegClassAction : public MatchAction {
2992   unsigned InsnID;
2993   unsigned OpIdx;
2994   const CodeGenRegisterClass &RC;
2995
2996 public:
2997   ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2998                                    const CodeGenRegisterClass &RC)
2999       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
3000
3001   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3002     Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
3003           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3004           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
3005           << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
3006           << MatchTable::LineBreak;
3007   }
3008 };
3009
3010 /// Generates code to create a temporary register which can be used to chain
3011 /// instructions together.
3012 class MakeTempRegisterAction : public MatchAction {
3013 private:
3014   LLTCodeGen Ty;
3015   unsigned TempRegID;
3016
3017 public:
3018   MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
3019       : Ty(Ty), TempRegID(TempRegID) {
3020     KnownTypes.insert(Ty);
3021   }
3022
3023   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3024     Table << MatchTable::Opcode("GIR_MakeTempReg")
3025           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
3026           << MatchTable::Comment("TypeID")
3027           << MatchTable::NamedValue(Ty.getCxxEnumValue())
3028           << MatchTable::LineBreak;
3029   }
3030 };
3031
3032 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
3033   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
3034   MutatableInsns.insert(Matchers.back().get());
3035   return *Matchers.back();
3036 }
3037
3038 void RuleMatcher::addRequiredFeature(Record *Feature) {
3039   RequiredFeatures.push_back(Feature);
3040 }
3041
3042 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
3043   return RequiredFeatures;
3044 }
3045
3046 // Emplaces an action of the specified Kind at the end of the action list.
3047 //
3048 // Returns a reference to the newly created action.
3049 //
3050 // Like std::vector::emplace_back(), may invalidate all iterators if the new
3051 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
3052 // iterator.
3053 template <class Kind, class... Args>
3054 Kind &RuleMatcher::addAction(Args &&... args) {
3055   Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
3056   return *static_cast<Kind *>(Actions.back().get());
3057 }
3058
3059 // Emplaces an action of the specified Kind before the given insertion point.
3060 //
3061 // Returns an iterator pointing at the newly created instruction.
3062 //
3063 // Like std::vector::insert(), may invalidate all iterators if the new size
3064 // exceeds the capacity. Otherwise, only invalidates the iterators from the
3065 // insertion point onwards.
3066 template <class Kind, class... Args>
3067 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
3068                                           Args &&... args) {
3069   return Actions.emplace(InsertPt,
3070                          std::make_unique<Kind>(std::forward<Args>(args)...));
3071 }
3072
3073 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
3074   unsigned NewInsnVarID = NextInsnVarID++;
3075   InsnVariableIDs[&Matcher] = NewInsnVarID;
3076   return NewInsnVarID;
3077 }
3078
3079 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
3080   const auto &I = InsnVariableIDs.find(&InsnMatcher);
3081   if (I != InsnVariableIDs.end())
3082     return I->second;
3083   llvm_unreachable("Matched Insn was not captured in a local variable");
3084 }
3085
3086 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3087   if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3088     DefinedOperands[SymbolicName] = &OM;
3089     return;
3090   }
3091
3092   // If the operand is already defined, then we must ensure both references in
3093   // the matcher have the exact same node.
3094   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3095 }
3096
3097 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3098   if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3099     PhysRegOperands[Reg] = &OM;
3100     return;
3101   }
3102 }
3103
3104 InstructionMatcher &
3105 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3106   for (const auto &I : InsnVariableIDs)
3107     if (I.first->getSymbolicName() == SymbolicName)
3108       return *I.first;
3109   llvm_unreachable(
3110       ("Failed to lookup instruction " + SymbolicName).str().c_str());
3111 }
3112
3113 const OperandMatcher &
3114 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3115   const auto &I = PhysRegOperands.find(Reg);
3116
3117   if (I == PhysRegOperands.end()) {
3118     PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3119                     " was not declared in matcher");
3120   }
3121
3122   return *I->second;
3123 }
3124
3125 const OperandMatcher &
3126 RuleMatcher::getOperandMatcher(StringRef Name) const {
3127   const auto &I = DefinedOperands.find(Name);
3128
3129   if (I == DefinedOperands.end())
3130     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3131
3132   return *I->second;
3133 }
3134
3135 void RuleMatcher::emit(MatchTable &Table) {
3136   if (Matchers.empty())
3137     llvm_unreachable("Unexpected empty matcher!");
3138
3139   // The representation supports rules that require multiple roots such as:
3140   //    %ptr(p0) = ...
3141   //    %elt0(s32) = G_LOAD %ptr
3142   //    %1(p0) = G_ADD %ptr, 4
3143   //    %elt1(s32) = G_LOAD p0 %1
3144   // which could be usefully folded into:
3145   //    %ptr(p0) = ...
3146   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3147   // on some targets but we don't need to make use of that yet.
3148   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3149
3150   unsigned LabelID = Table.allocateLabelID();
3151   Table << MatchTable::Opcode("GIM_Try", +1)
3152         << MatchTable::Comment("On fail goto")
3153         << MatchTable::JumpTarget(LabelID)
3154         << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3155         << MatchTable::LineBreak;
3156
3157   if (!RequiredFeatures.empty()) {
3158     Table << MatchTable::Opcode("GIM_CheckFeatures")
3159           << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3160           << MatchTable::LineBreak;
3161   }
3162
3163   Matchers.front()->emitPredicateOpcodes(Table, *this);
3164
3165   // We must also check if it's safe to fold the matched instructions.
3166   if (InsnVariableIDs.size() >= 2) {
3167     // Invert the map to create stable ordering (by var names)
3168     SmallVector<unsigned, 2> InsnIDs;
3169     for (const auto &Pair : InsnVariableIDs) {
3170       // Skip the root node since it isn't moving anywhere. Everything else is
3171       // sinking to meet it.
3172       if (Pair.first == Matchers.front().get())
3173         continue;
3174
3175       InsnIDs.push_back(Pair.second);
3176     }
3177     llvm::sort(InsnIDs);
3178
3179     for (const auto &InsnID : InsnIDs) {
3180       // Reject the difficult cases until we have a more accurate check.
3181       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3182             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3183             << MatchTable::LineBreak;
3184
3185       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3186       //        account for unsafe cases.
3187       //
3188       //        Example:
3189       //          MI1--> %0 = ...
3190       //                 %1 = ... %0
3191       //          MI0--> %2 = ... %0
3192       //          It's not safe to erase MI1. We currently handle this by not
3193       //          erasing %0 (even when it's dead).
3194       //
3195       //        Example:
3196       //          MI1--> %0 = load volatile @a
3197       //                 %1 = load volatile @a
3198       //          MI0--> %2 = ... %0
3199       //          It's not safe to sink %0's def past %1. We currently handle
3200       //          this by rejecting all loads.
3201       //
3202       //        Example:
3203       //          MI1--> %0 = load @a
3204       //                 %1 = store @a
3205       //          MI0--> %2 = ... %0
3206       //          It's not safe to sink %0's def past %1. We currently handle
3207       //          this by rejecting all loads.
3208       //
3209       //        Example:
3210       //                   G_CONDBR %cond, @BB1
3211       //                 BB0:
3212       //          MI1-->   %0 = load @a
3213       //                   G_BR @BB1
3214       //                 BB1:
3215       //          MI0-->   %2 = ... %0
3216       //          It's not always safe to sink %0 across control flow. In this
3217       //          case it may introduce a memory fault. We currentl handle this
3218       //          by rejecting all loads.
3219     }
3220   }
3221
3222   for (const auto &PM : EpilogueMatchers)
3223     PM->emitPredicateOpcodes(Table, *this);
3224
3225   for (const auto &MA : Actions)
3226     MA->emitActionOpcodes(Table, *this);
3227
3228   if (Table.isWithCoverage())
3229     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3230           << MatchTable::LineBreak;
3231   else
3232     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3233           << MatchTable::LineBreak;
3234
3235   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3236         << MatchTable::Label(LabelID);
3237   ++NumPatternEmitted;
3238 }
3239
3240 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3241   // Rules involving more match roots have higher priority.
3242   if (Matchers.size() > B.Matchers.size())
3243     return true;
3244   if (Matchers.size() < B.Matchers.size())
3245     return false;
3246
3247   for (auto Matcher : zip(Matchers, B.Matchers)) {
3248     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3249       return true;
3250     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3251       return false;
3252   }
3253
3254   return false;
3255 }
3256
3257 unsigned RuleMatcher::countRendererFns() const {
3258   return std::accumulate(
3259       Matchers.begin(), Matchers.end(), 0,
3260       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3261         return A + Matcher->countRendererFns();
3262       });
3263 }
3264
3265 bool OperandPredicateMatcher::isHigherPriorityThan(
3266     const OperandPredicateMatcher &B) const {
3267   // Generally speaking, an instruction is more important than an Int or a
3268   // LiteralInt because it can cover more nodes but theres an exception to
3269   // this. G_CONSTANT's are less important than either of those two because they
3270   // are more permissive.
3271
3272   const InstructionOperandMatcher *AOM =
3273       dyn_cast<InstructionOperandMatcher>(this);
3274   const InstructionOperandMatcher *BOM =
3275       dyn_cast<InstructionOperandMatcher>(&B);
3276   bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3277   bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3278
3279   if (AOM && BOM) {
3280     // The relative priorities between a G_CONSTANT and any other instruction
3281     // don't actually matter but this code is needed to ensure a strict weak
3282     // ordering. This is particularly important on Windows where the rules will
3283     // be incorrectly sorted without it.
3284     if (AIsConstantInsn != BIsConstantInsn)
3285       return AIsConstantInsn < BIsConstantInsn;
3286     return false;
3287   }
3288
3289   if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3290     return false;
3291   if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3292     return true;
3293
3294   return Kind < B.Kind;
3295 }
3296
3297 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3298                                               RuleMatcher &Rule) const {
3299   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3300   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3301   assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3302
3303   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3304         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3305         << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3306         << MatchTable::Comment("OtherMI")
3307         << MatchTable::IntValue(OtherInsnVarID)
3308         << MatchTable::Comment("OtherOpIdx")
3309         << MatchTable::IntValue(OtherOM.getOpIdx())
3310         << MatchTable::LineBreak;
3311 }
3312
3313 //===- GlobalISelEmitter class --------------------------------------------===//
3314
3315 static Expected<LLTCodeGen> getInstResultType(const TreePatternNode *Dst) {
3316   ArrayRef<TypeSetByHwMode> ChildTypes = Dst->getExtTypes();
3317   if (ChildTypes.size() != 1)
3318     return failedImport("Dst pattern child has multiple results");
3319
3320   Optional<LLTCodeGen> MaybeOpTy;
3321   if (ChildTypes.front().isMachineValueType()) {
3322     MaybeOpTy =
3323       MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3324   }
3325
3326   if (!MaybeOpTy)
3327     return failedImport("Dst operand has an unsupported type");
3328   return *MaybeOpTy;
3329 }
3330
3331 class GlobalISelEmitter {
3332 public:
3333   explicit GlobalISelEmitter(RecordKeeper &RK);
3334   void run(raw_ostream &OS);
3335
3336 private:
3337   const RecordKeeper &RK;
3338   const CodeGenDAGPatterns CGP;
3339   const CodeGenTarget &Target;
3340   CodeGenRegBank &CGRegs;
3341
3342   /// Keep track of the equivalence between SDNodes and Instruction by mapping
3343   /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3344   /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3345   /// This is defined using 'GINodeEquiv' in the target description.
3346   DenseMap<Record *, Record *> NodeEquivs;
3347
3348   /// Keep track of the equivalence between ComplexPattern's and
3349   /// GIComplexOperandMatcher. Map entries are specified by subclassing
3350   /// GIComplexPatternEquiv.
3351   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3352
3353   /// Keep track of the equivalence between SDNodeXForm's and
3354   /// GICustomOperandRenderer. Map entries are specified by subclassing
3355   /// GISDNodeXFormEquiv.
3356   DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3357
3358   /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3359   /// This adds compatibility for RuleMatchers to use this for ordering rules.
3360   DenseMap<uint64_t, int> RuleMatcherScores;
3361
3362   // Map of predicates to their subtarget features.
3363   SubtargetFeatureInfoMap SubtargetFeatures;
3364
3365   // Rule coverage information.
3366   Optional<CodeGenCoverage> RuleCoverage;
3367
3368   void gatherOpcodeValues();
3369   void gatherTypeIDValues();
3370   void gatherNodeEquivs();
3371
3372   Record *findNodeEquiv(Record *N) const;
3373   const CodeGenInstruction *getEquivNode(Record &Equiv,
3374                                          const TreePatternNode *N) const;
3375
3376   Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3377   Expected<InstructionMatcher &>
3378   createAndImportSelDAGMatcher(RuleMatcher &Rule,
3379                                InstructionMatcher &InsnMatcher,
3380                                const TreePatternNode *Src, unsigned &TempOpIdx);
3381   Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3382                                            unsigned &TempOpIdx) const;
3383   Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3384                            const TreePatternNode *SrcChild,
3385                            bool OperandIsAPointer, bool OperandIsImmArg,
3386                            unsigned OpIdx, unsigned &TempOpIdx);
3387
3388   Expected<BuildMIAction &> createAndImportInstructionRenderer(
3389       RuleMatcher &M, InstructionMatcher &InsnMatcher,
3390       const TreePatternNode *Src, const TreePatternNode *Dst);
3391   Expected<action_iterator> createAndImportSubInstructionRenderer(
3392       action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3393       unsigned TempReg);
3394   Expected<action_iterator>
3395   createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3396                             const TreePatternNode *Dst);
3397   void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3398
3399   Expected<action_iterator>
3400   importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3401                              BuildMIAction &DstMIBuilder,
3402                              const llvm::TreePatternNode *Dst);
3403   Expected<action_iterator>
3404   importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3405                             BuildMIAction &DstMIBuilder,
3406                             TreePatternNode *DstChild);
3407   Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3408                                       BuildMIAction &DstMIBuilder,
3409                                       DagInit *DefaultOps) const;
3410   Error
3411   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3412                              const std::vector<Record *> &ImplicitDefs) const;
3413
3414   void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3415                            StringRef TypeIdentifier, StringRef ArgType,
3416                            StringRef ArgName, StringRef AdditionalDeclarations,
3417                            std::function<bool(const Record *R)> Filter);
3418   void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3419                            StringRef ArgType,
3420                            std::function<bool(const Record *R)> Filter);
3421   void emitMIPredicateFns(raw_ostream &OS);
3422
3423   /// Analyze pattern \p P, returning a matcher for it if possible.
3424   /// Otherwise, return an Error explaining why we don't support it.
3425   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3426
3427   void declareSubtargetFeature(Record *Predicate);
3428
3429   MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3430                              bool WithCoverage);
3431
3432   /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3433   /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3434   /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3435   /// If no register class is found, return None.
3436   Optional<const CodeGenRegisterClass *>
3437   inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3438                                  TreePatternNode *SuperRegNode,
3439                                  TreePatternNode *SubRegIdxNode);
3440   Optional<CodeGenSubRegIndex *>
3441   inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3442
3443   /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3444   /// Return None if no such class exists.
3445   Optional<const CodeGenRegisterClass *>
3446   inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3447                           TreePatternNode *SubRegIdxNode);
3448
3449   /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3450   Optional<const CodeGenRegisterClass *>
3451   getRegClassFromLeaf(TreePatternNode *Leaf);
3452
3453   /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3454   /// otherwise.
3455   Optional<const CodeGenRegisterClass *>
3456   inferRegClassFromPattern(TreePatternNode *N);
3457
3458 public:
3459   /// Takes a sequence of \p Rules and group them based on the predicates
3460   /// they share. \p MatcherStorage is used as a memory container
3461   /// for the group that are created as part of this process.
3462   ///
3463   /// What this optimization does looks like if GroupT = GroupMatcher:
3464   /// Output without optimization:
3465   /// \verbatim
3466   /// # R1
3467   ///  # predicate A
3468   ///  # predicate B
3469   ///  ...
3470   /// # R2
3471   ///  # predicate A // <-- effectively this is going to be checked twice.
3472   ///                //     Once in R1 and once in R2.
3473   ///  # predicate C
3474   /// \endverbatim
3475   /// Output with optimization:
3476   /// \verbatim
3477   /// # Group1_2
3478   ///  # predicate A // <-- Check is now shared.
3479   ///  # R1
3480   ///   # predicate B
3481   ///  # R2
3482   ///   # predicate C
3483   /// \endverbatim
3484   template <class GroupT>
3485   static std::vector<Matcher *> optimizeRules(
3486       ArrayRef<Matcher *> Rules,
3487       std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3488 };
3489
3490 void GlobalISelEmitter::gatherOpcodeValues() {
3491   InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3492 }
3493
3494 void GlobalISelEmitter::gatherTypeIDValues() {
3495   LLTOperandMatcher::initTypeIDValuesMap();
3496 }
3497
3498 void GlobalISelEmitter::gatherNodeEquivs() {
3499   assert(NodeEquivs.empty());
3500   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3501     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3502
3503   assert(ComplexPatternEquivs.empty());
3504   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3505     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3506     if (!SelDAGEquiv)
3507       continue;
3508     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3509  }
3510
3511  assert(SDNodeXFormEquivs.empty());
3512  for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3513    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3514    if (!SelDAGEquiv)
3515      continue;
3516    SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3517  }
3518 }
3519
3520 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3521   return NodeEquivs.lookup(N);
3522 }
3523
3524 const CodeGenInstruction *
3525 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3526   if (N->getNumChildren() >= 1) {
3527     // setcc operation maps to two different G_* instructions based on the type.
3528     if (!Equiv.isValueUnset("IfFloatingPoint") &&
3529         MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3530       return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3531   }
3532
3533   for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3534     const TreePredicateFn &Predicate = Call.Fn;
3535     if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3536         Predicate.isSignExtLoad())
3537       return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3538     if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3539         Predicate.isZeroExtLoad())
3540       return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3541   }
3542
3543   return &Target.getInstruction(Equiv.getValueAsDef("I"));
3544 }
3545
3546 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3547     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3548       CGRegs(Target.getRegBank()) {}
3549
3550 //===- Emitter ------------------------------------------------------------===//
3551
3552 Error
3553 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3554                                         ArrayRef<Predicate> Predicates) {
3555   for (const Predicate &P : Predicates) {
3556     if (!P.Def || P.getCondString().empty())
3557       continue;
3558     declareSubtargetFeature(P.Def);
3559     M.addRequiredFeature(P.Def);
3560   }
3561
3562   return Error::success();
3563 }
3564
3565 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3566     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3567     const TreePatternNode *Src, unsigned &TempOpIdx) {
3568   Record *SrcGIEquivOrNull = nullptr;
3569   const CodeGenInstruction *SrcGIOrNull = nullptr;
3570
3571   // Start with the defined operands (i.e., the results of the root operator).
3572   if (Src->getExtTypes().size() > 1)
3573     return failedImport("Src pattern has multiple results");
3574
3575   if (Src->isLeaf()) {
3576     Init *SrcInit = Src->getLeafValue();
3577     if (isa<IntInit>(SrcInit)) {
3578       InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3579           &Target.getInstruction(RK.getDef("G_CONSTANT")));
3580     } else
3581       return failedImport(
3582           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3583   } else {
3584     SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3585     if (!SrcGIEquivOrNull)
3586       return failedImport("Pattern operator lacks an equivalent Instruction" +
3587                           explainOperator(Src->getOperator()));
3588     SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3589
3590     // The operators look good: match the opcode
3591     InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3592   }
3593
3594   unsigned OpIdx = 0;
3595   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3596     // Results don't have a name unless they are the root node. The caller will
3597     // set the name if appropriate.
3598     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3599     if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3600       return failedImport(toString(std::move(Error)) +
3601                           " for result of Src pattern operator");
3602   }
3603
3604   for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3605     const TreePredicateFn &Predicate = Call.Fn;
3606     if (Predicate.isAlwaysTrue())
3607       continue;
3608
3609     if (Predicate.isImmediatePattern()) {
3610       InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3611       continue;
3612     }
3613
3614     // An address space check is needed in all contexts if there is one.
3615     if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3616       if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3617         SmallVector<unsigned, 4> ParsedAddrSpaces;
3618
3619         for (Init *Val : AddrSpaces->getValues()) {
3620           IntInit *IntVal = dyn_cast<IntInit>(Val);
3621           if (!IntVal)
3622             return failedImport("Address space is not an integer");
3623           ParsedAddrSpaces.push_back(IntVal->getValue());
3624         }
3625
3626         if (!ParsedAddrSpaces.empty()) {
3627           InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3628             0, ParsedAddrSpaces);
3629         }
3630       }
3631
3632       int64_t MinAlign = Predicate.getMinAlignment();
3633       if (MinAlign > 0)
3634         InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3635     }
3636
3637     // G_LOAD is used for both non-extending and any-extending loads.
3638     if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3639       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3640           0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3641       continue;
3642     }
3643     if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3644       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3645           0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3646       continue;
3647     }
3648
3649     if (Predicate.isStore()) {
3650       if (Predicate.isTruncStore()) {
3651         // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3652         InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3653             0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3654         continue;
3655       }
3656       if (Predicate.isNonTruncStore()) {
3657         // We need to check the sizes match here otherwise we could incorrectly
3658         // match truncating stores with non-truncating ones.
3659         InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3660             0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3661       }
3662     }
3663
3664     // No check required. We already did it by swapping the opcode.
3665     if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3666         Predicate.isSignExtLoad())
3667       continue;
3668
3669     // No check required. We already did it by swapping the opcode.
3670     if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3671         Predicate.isZeroExtLoad())
3672       continue;
3673
3674     // No check required. G_STORE by itself is a non-extending store.
3675     if (Predicate.isNonTruncStore())
3676       continue;
3677
3678     if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3679       if (Predicate.getMemoryVT() != nullptr) {
3680         Optional<LLTCodeGen> MemTyOrNone =
3681             MVTToLLT(getValueType(Predicate.getMemoryVT()));
3682
3683         if (!MemTyOrNone)
3684           return failedImport("MemVT could not be converted to LLT");
3685
3686         // MMO's work in bytes so we must take care of unusual types like i1
3687         // don't round down.
3688         unsigned MemSizeInBits =
3689             llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3690
3691         InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3692             0, MemSizeInBits / 8);
3693         continue;
3694       }
3695     }
3696
3697     if (Predicate.isLoad() || Predicate.isStore()) {
3698       // No check required. A G_LOAD/G_STORE is an unindexed load.
3699       if (Predicate.isUnindexed())
3700         continue;
3701     }
3702
3703     if (Predicate.isAtomic()) {
3704       if (Predicate.isAtomicOrderingMonotonic()) {
3705         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3706             "Monotonic");
3707         continue;
3708       }
3709       if (Predicate.isAtomicOrderingAcquire()) {
3710         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3711         continue;
3712       }
3713       if (Predicate.isAtomicOrderingRelease()) {
3714         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3715         continue;
3716       }
3717       if (Predicate.isAtomicOrderingAcquireRelease()) {
3718         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3719             "AcquireRelease");
3720         continue;
3721       }
3722       if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3723         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3724             "SequentiallyConsistent");
3725         continue;
3726       }
3727
3728       if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3729         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3730             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3731         continue;
3732       }
3733       if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3734         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3735             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3736         continue;
3737       }
3738
3739       if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3740         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3741             "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3742         continue;
3743       }
3744       if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3745         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3746             "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3747         continue;
3748       }
3749     }
3750
3751     if (Predicate.hasGISelPredicateCode()) {
3752       InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3753       continue;
3754     }
3755
3756     return failedImport("Src pattern child has predicate (" +
3757                         explainPredicates(Src) + ")");
3758   }
3759   if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3760     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3761   else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
3762     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3763       "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3764   }
3765
3766   if (Src->isLeaf()) {
3767     Init *SrcInit = Src->getLeafValue();
3768     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3769       OperandMatcher &OM =
3770           InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3771       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3772     } else
3773       return failedImport(
3774           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3775   } else {
3776     assert(SrcGIOrNull &&
3777            "Expected to have already found an equivalent Instruction");
3778     if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3779         SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3780       // imm/fpimm still have operands but we don't need to do anything with it
3781       // here since we don't support ImmLeaf predicates yet. However, we still
3782       // need to note the hidden operand to get GIM_CheckNumOperands correct.
3783       InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3784       return InsnMatcher;
3785     }
3786
3787     // Special case because the operand order is changed from setcc. The
3788     // predicate operand needs to be swapped from the last operand to the first
3789     // source.
3790
3791     unsigned NumChildren = Src->getNumChildren();
3792     bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
3793
3794     if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
3795       TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
3796       if (SrcChild->isLeaf()) {
3797         DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
3798         Record *CCDef = DI ? DI->getDef() : nullptr;
3799         if (!CCDef || !CCDef->isSubClassOf("CondCode"))
3800           return failedImport("Unable to handle CondCode");
3801
3802         OperandMatcher &OM =
3803           InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3804         StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
3805                                       CCDef->getValueAsString("ICmpPredicate");
3806
3807         if (!PredType.empty()) {
3808           OM.addPredicate<CmpPredicateOperandMatcher>(std::string(PredType));
3809           // Process the other 2 operands normally.
3810           --NumChildren;
3811         }
3812       }
3813     }
3814
3815     // Match the used operands (i.e. the children of the operator).
3816     bool IsIntrinsic =
3817         SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3818         SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
3819     const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
3820     if (IsIntrinsic && !II)
3821       return failedImport("Expected IntInit containing intrinsic ID)");
3822
3823     for (unsigned i = 0; i != NumChildren; ++i) {
3824       TreePatternNode *SrcChild = Src->getChild(i);
3825
3826       // We need to determine the meaning of a literal integer based on the
3827       // context. If this is a field required to be an immediate (such as an
3828       // immarg intrinsic argument), the required predicates are different than
3829       // a constant which may be materialized in a register. If we have an
3830       // argument that is required to be an immediate, we should not emit an LLT
3831       // type check, and should not be looking for a G_CONSTANT defined
3832       // register.
3833       bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
3834
3835       // SelectionDAG allows pointers to be represented with iN since it doesn't
3836       // distinguish between pointers and integers but they are different types in GlobalISel.
3837       // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3838       //
3839       bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3840
3841       if (IsIntrinsic) {
3842         // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3843         // following the defs is an intrinsic ID.
3844         if (i == 0) {
3845           OperandMatcher &OM =
3846               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3847           OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3848           continue;
3849         }
3850
3851         // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
3852         //
3853         // Note that we have to look at the i-1th parameter, because we don't
3854         // have the intrinsic ID in the intrinsic's parameter list.
3855         OperandIsAPointer |= II->isParamAPointer(i - 1);
3856         OperandIsImmArg |= II->isParamImmArg(i - 1);
3857       }
3858
3859       if (auto Error =
3860               importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3861                                  OperandIsImmArg, OpIdx++, TempOpIdx))
3862         return std::move(Error);
3863     }
3864   }
3865
3866   return InsnMatcher;
3867 }
3868
3869 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3870     OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3871   const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3872   if (ComplexPattern == ComplexPatternEquivs.end())
3873     return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3874                         ") not mapped to GlobalISel");
3875
3876   OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3877   TempOpIdx++;
3878   return Error::success();
3879 }
3880
3881 // Get the name to use for a pattern operand. For an anonymous physical register
3882 // input, this should use the register name.
3883 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
3884                                  Record *&PhysReg) {
3885   StringRef SrcChildName = SrcChild->getName();
3886   if (SrcChildName.empty() && SrcChild->isLeaf()) {
3887     if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3888       auto *ChildRec = ChildDefInit->getDef();
3889       if (ChildRec->isSubClassOf("Register")) {
3890         SrcChildName = ChildRec->getName();
3891         PhysReg = ChildRec;
3892       }
3893     }
3894   }
3895
3896   return SrcChildName;
3897 }
3898
3899 Error GlobalISelEmitter::importChildMatcher(
3900     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3901     const TreePatternNode *SrcChild, bool OperandIsAPointer,
3902     bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
3903
3904   Record *PhysReg = nullptr;
3905   StringRef SrcChildName = getSrcChildName(SrcChild, PhysReg);
3906
3907   OperandMatcher &OM =
3908       PhysReg
3909           ? InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx)
3910           : InsnMatcher.addOperand(OpIdx, std::string(SrcChildName), TempOpIdx);
3911   if (OM.isSameAsAnotherOperand())
3912     return Error::success();
3913
3914   ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3915   if (ChildTypes.size() != 1)
3916     return failedImport("Src pattern child has multiple results");
3917
3918   // Check MBB's before the type check since they are not a known type.
3919   if (!SrcChild->isLeaf()) {
3920     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3921       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3922       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3923         OM.addPredicate<MBBOperandMatcher>();
3924         return Error::success();
3925       }
3926       if (SrcChild->getOperator()->getName() == "timm") {
3927         OM.addPredicate<ImmOperandMatcher>();
3928         return Error::success();
3929       }
3930     }
3931   }
3932
3933   // Immediate arguments have no meaningful type to check as they don't have
3934   // registers.
3935   if (!OperandIsImmArg) {
3936     if (auto Error =
3937             OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3938       return failedImport(toString(std::move(Error)) + " for Src operand (" +
3939                           to_string(*SrcChild) + ")");
3940   }
3941
3942   // Check for nested instructions.
3943   if (!SrcChild->isLeaf()) {
3944     if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3945       // When a ComplexPattern is used as an operator, it should do the same
3946       // thing as when used as a leaf. However, the children of the operator
3947       // name the sub-operands that make up the complex operand and we must
3948       // prepare to reference them in the renderer too.
3949       unsigned RendererID = TempOpIdx;
3950       if (auto Error = importComplexPatternOperandMatcher(
3951               OM, SrcChild->getOperator(), TempOpIdx))
3952         return Error;
3953
3954       for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3955         auto *SubOperand = SrcChild->getChild(i);
3956         if (!SubOperand->getName().empty()) {
3957           if (auto Error = Rule.defineComplexSubOperand(SubOperand->getName(),
3958                                                         SrcChild->getOperator(),
3959                                                         RendererID, i))
3960             return Error;
3961         }
3962       }
3963
3964       return Error::success();
3965     }
3966
3967     auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3968         InsnMatcher.getRuleMatcher(), SrcChild->getName());
3969     if (!MaybeInsnOperand.hasValue()) {
3970       // This isn't strictly true. If the user were to provide exactly the same
3971       // matchers as the original operand then we could allow it. However, it's
3972       // simpler to not permit the redundant specification.
3973       return failedImport("Nested instruction cannot be the same as another operand");
3974     }
3975
3976     // Map the node to a gMIR instruction.
3977     InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3978     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3979         Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3980     if (auto Error = InsnMatcherOrError.takeError())
3981       return Error;
3982
3983     return Error::success();
3984   }
3985
3986   if (SrcChild->hasAnyPredicate())
3987     return failedImport("Src pattern child has unsupported predicate");
3988
3989   // Check for constant immediates.
3990   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3991     if (OperandIsImmArg) {
3992       // Checks for argument directly in operand list
3993       OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
3994     } else {
3995       // Checks for materialized constant
3996       OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3997     }
3998     return Error::success();
3999   }
4000
4001   // Check for def's like register classes or ComplexPattern's.
4002   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4003     auto *ChildRec = ChildDefInit->getDef();
4004
4005     // Check for register classes.
4006     if (ChildRec->isSubClassOf("RegisterClass") ||
4007         ChildRec->isSubClassOf("RegisterOperand")) {
4008       OM.addPredicate<RegisterBankOperandMatcher>(
4009           Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
4010       return Error::success();
4011     }
4012
4013     if (ChildRec->isSubClassOf("Register")) {
4014       // This just be emitted as a copy to the specific register.
4015       ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
4016       const CodeGenRegisterClass *RC
4017         = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
4018       if (!RC) {
4019         return failedImport(
4020           "Could not determine physical register class of pattern source");
4021       }
4022
4023       OM.addPredicate<RegisterBankOperandMatcher>(*RC);
4024       return Error::success();
4025     }
4026
4027     // Check for ValueType.
4028     if (ChildRec->isSubClassOf("ValueType")) {
4029       // We already added a type check as standard practice so this doesn't need
4030       // to do anything.
4031       return Error::success();
4032     }
4033
4034     // Check for ComplexPattern's.
4035     if (ChildRec->isSubClassOf("ComplexPattern"))
4036       return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
4037
4038     if (ChildRec->isSubClassOf("ImmLeaf")) {
4039       return failedImport(
4040           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
4041     }
4042
4043     // Place holder for SRCVALUE nodes. Nothing to do here.
4044     if (ChildRec->getName() == "srcvalue")
4045       return Error::success();
4046
4047     return failedImport(
4048         "Src pattern child def is an unsupported tablegen class");
4049   }
4050
4051   return failedImport("Src pattern child is an unsupported kind");
4052 }
4053
4054 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
4055     action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
4056     TreePatternNode *DstChild) {
4057
4058   const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
4059   if (SubOperand.hasValue()) {
4060     DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4061         *std::get<0>(*SubOperand), DstChild->getName(),
4062         std::get<1>(*SubOperand), std::get<2>(*SubOperand));
4063     return InsertPt;
4064   }
4065
4066   if (!DstChild->isLeaf()) {
4067     if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
4068       auto Child = DstChild->getChild(0);
4069       auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
4070       if (I != SDNodeXFormEquivs.end()) {
4071         Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
4072         if (XFormOpc->getName() == "timm") {
4073           // If this is a TargetConstant, there won't be a corresponding
4074           // instruction to transform. Instead, this will refer directly to an
4075           // operand in an instruction's operand list.
4076           DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
4077                                                           Child->getName());
4078         } else {
4079           DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
4080                                                    Child->getName());
4081         }
4082
4083         return InsertPt;
4084       }
4085       return failedImport("SDNodeXForm " + Child->getName() +
4086                           " has no custom renderer");
4087     }
4088
4089     // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
4090     // inline, but in MI it's just another operand.
4091     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
4092       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
4093       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4094         DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4095         return InsertPt;
4096       }
4097     }
4098
4099     // Similarly, imm is an operator in TreePatternNode's view but must be
4100     // rendered as operands.
4101     // FIXME: The target should be able to choose sign-extended when appropriate
4102     //        (e.g. on Mips).
4103     if (DstChild->getOperator()->getName() == "timm") {
4104       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4105       return InsertPt;
4106     } else if (DstChild->getOperator()->getName() == "imm") {
4107       DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
4108       return InsertPt;
4109     } else if (DstChild->getOperator()->getName() == "fpimm") {
4110       DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
4111           DstChild->getName());
4112       return InsertPt;
4113     }
4114
4115     if (DstChild->getOperator()->isSubClassOf("Instruction")) {
4116       auto OpTy = getInstResultType(DstChild);
4117       if (!OpTy)
4118         return OpTy.takeError();
4119
4120       unsigned TempRegID = Rule.allocateTempRegID();
4121       InsertPt = Rule.insertAction<MakeTempRegisterAction>(
4122           InsertPt, *OpTy, TempRegID);
4123       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4124
4125       auto InsertPtOrError = createAndImportSubInstructionRenderer(
4126           ++InsertPt, Rule, DstChild, TempRegID);
4127       if (auto Error = InsertPtOrError.takeError())
4128         return std::move(Error);
4129       return InsertPtOrError.get();
4130     }
4131
4132     return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4133   }
4134
4135   // It could be a specific immediate in which case we should just check for
4136   // that immediate.
4137   if (const IntInit *ChildIntInit =
4138           dyn_cast<IntInit>(DstChild->getLeafValue())) {
4139     DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4140     return InsertPt;
4141   }
4142
4143   // Otherwise, we're looking for a bog-standard RegisterClass operand.
4144   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4145     auto *ChildRec = ChildDefInit->getDef();
4146
4147     ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4148     if (ChildTypes.size() != 1)
4149       return failedImport("Dst pattern child has multiple results");
4150
4151     Optional<LLTCodeGen> OpTyOrNone = None;
4152     if (ChildTypes.front().isMachineValueType())
4153       OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4154     if (!OpTyOrNone)
4155       return failedImport("Dst operand has an unsupported type");
4156
4157     if (ChildRec->isSubClassOf("Register")) {
4158       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
4159       return InsertPt;
4160     }
4161
4162     if (ChildRec->isSubClassOf("RegisterClass") ||
4163         ChildRec->isSubClassOf("RegisterOperand") ||
4164         ChildRec->isSubClassOf("ValueType")) {
4165       if (ChildRec->isSubClassOf("RegisterOperand") &&
4166           !ChildRec->isValueUnset("GIZeroRegister")) {
4167         DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4168             DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4169         return InsertPt;
4170       }
4171
4172       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4173       return InsertPt;
4174     }
4175
4176     if (ChildRec->isSubClassOf("SubRegIndex")) {
4177       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4178       DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4179       return InsertPt;
4180     }
4181
4182     if (ChildRec->isSubClassOf("ComplexPattern")) {
4183       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4184       if (ComplexPattern == ComplexPatternEquivs.end())
4185         return failedImport(
4186             "SelectionDAG ComplexPattern not mapped to GlobalISel");
4187
4188       const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4189       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4190           *ComplexPattern->second, DstChild->getName(),
4191           OM.getAllocatedTemporariesBaseID());
4192       return InsertPt;
4193     }
4194
4195     return failedImport(
4196         "Dst pattern child def is an unsupported tablegen class");
4197   }
4198
4199   return failedImport("Dst pattern child is an unsupported kind");
4200 }
4201
4202 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4203     RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4204     const TreePatternNode *Dst) {
4205   auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4206   if (auto Error = InsertPtOrError.takeError())
4207     return std::move(Error);
4208
4209   action_iterator InsertPt = InsertPtOrError.get();
4210   BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4211
4212   for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4213     InsertPt = M.insertAction<BuildMIAction>(
4214         InsertPt, M.allocateOutputInsnID(),
4215         &Target.getInstruction(RK.getDef("COPY")));
4216     BuildMIAction &CopyToPhysRegMIBuilder =
4217         *static_cast<BuildMIAction *>(InsertPt->get());
4218     CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(PhysInput.first,
4219                                                             true);
4220     CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4221   }
4222
4223   importExplicitDefRenderers(DstMIBuilder);
4224
4225   if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4226                        .takeError())
4227     return std::move(Error);
4228
4229   return DstMIBuilder;
4230 }
4231
4232 Expected<action_iterator>
4233 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4234     const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4235     unsigned TempRegID) {
4236   auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4237
4238   // TODO: Assert there's exactly one result.
4239
4240   if (auto Error = InsertPtOrError.takeError())
4241     return std::move(Error);
4242
4243   BuildMIAction &DstMIBuilder =
4244       *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4245
4246   // Assign the result to TempReg.
4247   DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4248
4249   InsertPtOrError =
4250       importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4251   if (auto Error = InsertPtOrError.takeError())
4252     return std::move(Error);
4253
4254   // We need to make sure that when we import an INSERT_SUBREG as a
4255   // subinstruction that it ends up being constrained to the correct super
4256   // register and subregister classes.
4257   auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4258   if (OpName == "INSERT_SUBREG") {
4259     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4260     if (!SubClass)
4261       return failedImport(
4262           "Cannot infer register class from INSERT_SUBREG operand #1");
4263     Optional<const CodeGenRegisterClass *> SuperClass =
4264         inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4265                                        Dst->getChild(2));
4266     if (!SuperClass)
4267       return failedImport(
4268           "Cannot infer register class for INSERT_SUBREG operand #0");
4269     // The destination and the super register source of an INSERT_SUBREG must
4270     // be the same register class.
4271     M.insertAction<ConstrainOperandToRegClassAction>(
4272         InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4273     M.insertAction<ConstrainOperandToRegClassAction>(
4274         InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4275     M.insertAction<ConstrainOperandToRegClassAction>(
4276         InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4277     return InsertPtOrError.get();
4278   }
4279
4280   if (OpName == "EXTRACT_SUBREG") {
4281     // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4282     // instructions, the result register class is controlled by the
4283     // subregisters of the operand. As a result, we must constrain the result
4284     // class rather than check that it's already the right one.
4285     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4286     if (!SuperClass)
4287       return failedImport(
4288         "Cannot infer register class from EXTRACT_SUBREG operand #0");
4289
4290     auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4291     if (!SubIdx)
4292       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4293
4294     const auto SrcRCDstRCPair =
4295       (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4296     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4297     M.insertAction<ConstrainOperandToRegClassAction>(
4298       InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4299     M.insertAction<ConstrainOperandToRegClassAction>(
4300       InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4301
4302     // We're done with this pattern!  It's eligible for GISel emission; return
4303     // it.
4304     return InsertPtOrError.get();
4305   }
4306
4307   // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4308   // subinstruction.
4309   if (OpName == "SUBREG_TO_REG") {
4310     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4311     if (!SubClass)
4312       return failedImport(
4313         "Cannot infer register class from SUBREG_TO_REG child #1");
4314     auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4315                                               Dst->getChild(2));
4316     if (!SuperClass)
4317       return failedImport(
4318         "Cannot infer register class for SUBREG_TO_REG operand #0");
4319     M.insertAction<ConstrainOperandToRegClassAction>(
4320       InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4321     M.insertAction<ConstrainOperandToRegClassAction>(
4322       InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4323     return InsertPtOrError.get();
4324   }
4325
4326   if (OpName == "REG_SEQUENCE") {
4327     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4328     M.insertAction<ConstrainOperandToRegClassAction>(
4329       InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4330
4331     unsigned Num = Dst->getNumChildren();
4332     for (unsigned I = 1; I != Num; I += 2) {
4333       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4334
4335       auto SubIdx = inferSubRegIndexForNode(SubRegChild);
4336       if (!SubIdx)
4337         return failedImport("REG_SEQUENCE child is not a subreg index");
4338
4339       const auto SrcRCDstRCPair =
4340         (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4341       assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4342       M.insertAction<ConstrainOperandToRegClassAction>(
4343         InsertPt, DstMIBuilder.getInsnID(), I, *SrcRCDstRCPair->second);
4344     }
4345
4346     return InsertPtOrError.get();
4347   }
4348
4349   M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4350                                                       DstMIBuilder.getInsnID());
4351   return InsertPtOrError.get();
4352 }
4353
4354 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4355     action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4356   Record *DstOp = Dst->getOperator();
4357   if (!DstOp->isSubClassOf("Instruction")) {
4358     if (DstOp->isSubClassOf("ValueType"))
4359       return failedImport(
4360           "Pattern operator isn't an instruction (it's a ValueType)");
4361     return failedImport("Pattern operator isn't an instruction");
4362   }
4363   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4364
4365   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4366   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4367   StringRef Name = DstI->TheDef->getName();
4368   if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4369     DstI = &Target.getInstruction(RK.getDef("COPY"));
4370
4371   return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4372                                        DstI);
4373 }
4374
4375 void GlobalISelEmitter::importExplicitDefRenderers(
4376     BuildMIAction &DstMIBuilder) {
4377   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4378   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
4379     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
4380     DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4381   }
4382 }
4383
4384 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4385     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4386     const llvm::TreePatternNode *Dst) {
4387   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4388   CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4389
4390   StringRef Name = OrigDstI->TheDef->getName();
4391   unsigned ExpectedDstINumUses = Dst->getNumChildren();
4392
4393   // EXTRACT_SUBREG needs to use a subregister COPY.
4394   if (Name == "EXTRACT_SUBREG") {
4395     DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4396     if (!SubRegInit)
4397       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4398
4399     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4400     TreePatternNode *ValChild = Dst->getChild(0);
4401     if (!ValChild->isLeaf()) {
4402       // We really have to handle the source instruction, and then insert a
4403       // copy from the subregister.
4404       auto ExtractSrcTy = getInstResultType(ValChild);
4405       if (!ExtractSrcTy)
4406         return ExtractSrcTy.takeError();
4407
4408       unsigned TempRegID = M.allocateTempRegID();
4409       InsertPt = M.insertAction<MakeTempRegisterAction>(
4410         InsertPt, *ExtractSrcTy, TempRegID);
4411
4412       auto InsertPtOrError = createAndImportSubInstructionRenderer(
4413         ++InsertPt, M, ValChild, TempRegID);
4414       if (auto Error = InsertPtOrError.takeError())
4415         return std::move(Error);
4416
4417       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, false, SubIdx);
4418       return InsertPt;
4419     }
4420
4421     // If this is a source operand, this is just a subregister copy.
4422     Record *RCDef = getInitValueAsRegClass(ValChild->getLeafValue());
4423     if (!RCDef)
4424       return failedImport("EXTRACT_SUBREG child #0 could not "
4425                           "be coerced to a register class");
4426
4427     CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4428
4429     const auto SrcRCDstRCPair =
4430       RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4431     if (SrcRCDstRCPair.hasValue()) {
4432       assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4433       if (SrcRCDstRCPair->first != RC)
4434         return failedImport("EXTRACT_SUBREG requires an additional COPY");
4435     }
4436
4437     DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4438                                                  SubIdx);
4439     return InsertPt;
4440   }
4441
4442   if (Name == "REG_SEQUENCE") {
4443     if (!Dst->getChild(0)->isLeaf())
4444       return failedImport("REG_SEQUENCE child #0 is not a leaf");
4445
4446     Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4447     if (!RCDef)
4448       return failedImport("REG_SEQUENCE child #0 could not "
4449                           "be coerced to a register class");
4450
4451     if ((ExpectedDstINumUses - 1) % 2 != 0)
4452       return failedImport("Malformed REG_SEQUENCE");
4453
4454     for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4455       TreePatternNode *ValChild = Dst->getChild(I);
4456       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4457
4458       if (DefInit *SubRegInit =
4459               dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4460         CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4461
4462         auto InsertPtOrError =
4463             importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4464         if (auto Error = InsertPtOrError.takeError())
4465           return std::move(Error);
4466         InsertPt = InsertPtOrError.get();
4467         DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4468       }
4469     }
4470
4471     return InsertPt;
4472   }
4473
4474   // Render the explicit uses.
4475   unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4476   if (Name == "COPY_TO_REGCLASS") {
4477     DstINumUses--; // Ignore the class constraint.
4478     ExpectedDstINumUses--;
4479   }
4480
4481   // NumResults - This is the number of results produced by the instruction in
4482   // the "outs" list.
4483   unsigned NumResults = OrigDstI->Operands.NumDefs;
4484
4485   // Number of operands we know the output instruction must have. If it is
4486   // variadic, we could have more operands.
4487   unsigned NumFixedOperands = DstI->Operands.size();
4488
4489   // Loop over all of the fixed operands of the instruction pattern, emitting
4490   // code to fill them all in. The node 'N' usually has number children equal to
4491   // the number of input operands of the instruction.  However, in cases where
4492   // there are predicate operands for an instruction, we need to fill in the
4493   // 'execute always' values. Match up the node operands to the instruction
4494   // operands to do this.
4495   unsigned Child = 0;
4496
4497   // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
4498   // number of operands at the end of the list which have default values.
4499   // Those can come from the pattern if it provides enough arguments, or be
4500   // filled in with the default if the pattern hasn't provided them. But any
4501   // operand with a default value _before_ the last mandatory one will be
4502   // filled in with their defaults unconditionally.
4503   unsigned NonOverridableOperands = NumFixedOperands;
4504   while (NonOverridableOperands > NumResults &&
4505          CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
4506     --NonOverridableOperands;
4507
4508   unsigned NumDefaultOps = 0;
4509   for (unsigned I = 0; I != DstINumUses; ++I) {
4510     unsigned InstOpNo = DstI->Operands.NumDefs + I;
4511
4512     // Determine what to emit for this operand.
4513     Record *OperandNode = DstI->Operands[InstOpNo].Rec;
4514
4515     // If the operand has default values, introduce them now.
4516     if (CGP.operandHasDefault(OperandNode) &&
4517         (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
4518       // This is a predicate or optional def operand which the pattern has not
4519       // overridden, or which we aren't letting it override; emit the 'default
4520       // ops' operands.
4521
4522       const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
4523       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4524       if (auto Error = importDefaultOperandRenderers(
4525             InsertPt, M, DstMIBuilder, DefaultOps))
4526         return std::move(Error);
4527       ++NumDefaultOps;
4528       continue;
4529     }
4530
4531     auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4532                                                      Dst->getChild(Child));
4533     if (auto Error = InsertPtOrError.takeError())
4534       return std::move(Error);
4535     InsertPt = InsertPtOrError.get();
4536     ++Child;
4537   }
4538
4539   if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4540     return failedImport("Expected " + llvm::to_string(DstINumUses) +
4541                         " used operands but found " +
4542                         llvm::to_string(ExpectedDstINumUses) +
4543                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
4544                         " default ones");
4545
4546   return InsertPt;
4547 }
4548
4549 Error GlobalISelEmitter::importDefaultOperandRenderers(
4550     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4551     DagInit *DefaultOps) const {
4552   for (const auto *DefaultOp : DefaultOps->getArgs()) {
4553     Optional<LLTCodeGen> OpTyOrNone = None;
4554
4555     // Look through ValueType operators.
4556     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4557       if (const DefInit *DefaultDagOperator =
4558               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4559         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4560           OpTyOrNone = MVTToLLT(getValueType(
4561                                   DefaultDagOperator->getDef()));
4562           DefaultOp = DefaultDagOp->getArg(0);
4563         }
4564       }
4565     }
4566
4567     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4568       auto Def = DefaultDefOp->getDef();
4569       if (Def->getName() == "undef_tied_input") {
4570         unsigned TempRegID = M.allocateTempRegID();
4571         M.insertAction<MakeTempRegisterAction>(
4572           InsertPt, OpTyOrNone.getValue(), TempRegID);
4573         InsertPt = M.insertAction<BuildMIAction>(
4574           InsertPt, M.allocateOutputInsnID(),
4575           &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4576         BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4577           InsertPt->get());
4578         IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4579         DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4580       } else {
4581         DstMIBuilder.addRenderer<AddRegisterRenderer>(Def);
4582       }
4583       continue;
4584     }
4585
4586     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4587       DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4588       continue;
4589     }
4590
4591     return failedImport("Could not add default op");
4592   }
4593
4594   return Error::success();
4595 }
4596
4597 Error GlobalISelEmitter::importImplicitDefRenderers(
4598     BuildMIAction &DstMIBuilder,
4599     const std::vector<Record *> &ImplicitDefs) const {
4600   if (!ImplicitDefs.empty())
4601     return failedImport("Pattern defines a physical register");
4602   return Error::success();
4603 }
4604
4605 Optional<const CodeGenRegisterClass *>
4606 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4607   assert(Leaf && "Expected node?");
4608   assert(Leaf->isLeaf() && "Expected leaf?");
4609   Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4610   if (!RCRec)
4611     return None;
4612   CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4613   if (!RC)
4614     return None;
4615   return RC;
4616 }
4617
4618 Optional<const CodeGenRegisterClass *>
4619 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4620   if (!N)
4621     return None;
4622
4623   if (N->isLeaf())
4624     return getRegClassFromLeaf(N);
4625
4626   // We don't have a leaf node, so we have to try and infer something. Check
4627   // that we have an instruction that we an infer something from.
4628
4629   // Only handle things that produce a single type.
4630   if (N->getNumTypes() != 1)
4631     return None;
4632   Record *OpRec = N->getOperator();
4633
4634   // We only want instructions.
4635   if (!OpRec->isSubClassOf("Instruction"))
4636     return None;
4637
4638   // Don't want to try and infer things when there could potentially be more
4639   // than one candidate register class.
4640   auto &Inst = Target.getInstruction(OpRec);
4641   if (Inst.Operands.NumDefs > 1)
4642     return None;
4643
4644   // Handle any special-case instructions which we can safely infer register
4645   // classes from.
4646   StringRef InstName = Inst.TheDef->getName();
4647   bool IsRegSequence = InstName == "REG_SEQUENCE";
4648   if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
4649     // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
4650     // has the desired register class as the first child.
4651     TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
4652     if (!RCChild->isLeaf())
4653       return None;
4654     return getRegClassFromLeaf(RCChild);
4655   }
4656
4657   // Handle destination record types that we can safely infer a register class
4658   // from.
4659   const auto &DstIOperand = Inst.Operands[0];
4660   Record *DstIOpRec = DstIOperand.Rec;
4661   if (DstIOpRec->isSubClassOf("RegisterOperand")) {
4662     DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4663     const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4664     return &RC;
4665   }
4666
4667   if (DstIOpRec->isSubClassOf("RegisterClass")) {
4668     const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4669     return &RC;
4670   }
4671
4672   return None;
4673 }
4674
4675 Optional<const CodeGenRegisterClass *>
4676 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
4677                                            TreePatternNode *SubRegIdxNode) {
4678   assert(SubRegIdxNode && "Expected subregister index node!");
4679   // We need a ValueTypeByHwMode for getSuperRegForSubReg.
4680   if (!Ty.isValueTypeByHwMode(false))
4681     return None;
4682   if (!SubRegIdxNode->isLeaf())
4683     return None;
4684   DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4685   if (!SubRegInit)
4686     return None;
4687   CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4688
4689   // Use the information we found above to find a minimal register class which
4690   // supports the subregister and type we want.
4691   auto RC =
4692       Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx);
4693   if (!RC)
4694     return None;
4695   return *RC;
4696 }
4697
4698 Optional<const CodeGenRegisterClass *>
4699 GlobalISelEmitter::inferSuperRegisterClassForNode(
4700     const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
4701     TreePatternNode *SubRegIdxNode) {
4702   assert(SuperRegNode && "Expected super register node!");
4703   // Check if we already have a defined register class for the super register
4704   // node. If we do, then we should preserve that rather than inferring anything
4705   // from the subregister index node. We can assume that whoever wrote the
4706   // pattern in the first place made sure that the super register and
4707   // subregister are compatible.
4708   if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
4709           inferRegClassFromPattern(SuperRegNode))
4710     return *SuperRegisterClass;
4711   return inferSuperRegisterClass(Ty, SubRegIdxNode);
4712 }
4713
4714 Optional<CodeGenSubRegIndex *>
4715 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
4716   if (!SubRegIdxNode->isLeaf())
4717     return None;
4718
4719   DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4720   if (!SubRegInit)
4721     return None;
4722   return CGRegs.getSubRegIdx(SubRegInit->getDef());
4723 }
4724
4725 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
4726   // Keep track of the matchers and actions to emit.
4727   int Score = P.getPatternComplexity(CGP);
4728   RuleMatcher M(P.getSrcRecord()->getLoc());
4729   RuleMatcherScores[M.getRuleID()] = Score;
4730   M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
4731                                   "  =>  " +
4732                                   llvm::to_string(*P.getDstPattern()));
4733
4734   if (auto Error = importRulePredicates(M, P.getPredicates()))
4735     return std::move(Error);
4736
4737   // Next, analyze the pattern operators.
4738   TreePatternNode *Src = P.getSrcPattern();
4739   TreePatternNode *Dst = P.getDstPattern();
4740
4741   // If the root of either pattern isn't a simple operator, ignore it.
4742   if (auto Err = isTrivialOperatorNode(Dst))
4743     return failedImport("Dst pattern root isn't a trivial operator (" +
4744                         toString(std::move(Err)) + ")");
4745   if (auto Err = isTrivialOperatorNode(Src))
4746     return failedImport("Src pattern root isn't a trivial operator (" +
4747                         toString(std::move(Err)) + ")");
4748
4749   // The different predicates and matchers created during
4750   // addInstructionMatcher use the RuleMatcher M to set up their
4751   // instruction ID (InsnVarID) that are going to be used when
4752   // M is going to be emitted.
4753   // However, the code doing the emission still relies on the IDs
4754   // returned during that process by the RuleMatcher when issuing
4755   // the recordInsn opcodes.
4756   // Because of that:
4757   // 1. The order in which we created the predicates
4758   //    and such must be the same as the order in which we emit them,
4759   //    and
4760   // 2. We need to reset the generation of the IDs in M somewhere between
4761   //    addInstructionMatcher and emit
4762   //
4763   // FIXME: Long term, we don't want to have to rely on this implicit
4764   // naming being the same. One possible solution would be to have
4765   // explicit operator for operation capture and reference those.
4766   // The plus side is that it would expose opportunities to share
4767   // the capture accross rules. The downside is that it would
4768   // introduce a dependency between predicates (captures must happen
4769   // before their first use.)
4770   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
4771   unsigned TempOpIdx = 0;
4772   auto InsnMatcherOrError =
4773       createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
4774   if (auto Error = InsnMatcherOrError.takeError())
4775     return std::move(Error);
4776   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
4777
4778   if (Dst->isLeaf()) {
4779     Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
4780
4781     const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
4782     if (RCDef) {
4783       // We need to replace the def and all its uses with the specified
4784       // operand. However, we must also insert COPY's wherever needed.
4785       // For now, emit a copy and let the register allocator clean up.
4786       auto &DstI = Target.getInstruction(RK.getDef("COPY"));
4787       const auto &DstIOperand = DstI.Operands[0];
4788
4789       OperandMatcher &OM0 = InsnMatcher.getOperand(0);
4790       OM0.setSymbolicName(DstIOperand.Name);
4791       M.defineOperand(OM0.getSymbolicName(), OM0);
4792       OM0.addPredicate<RegisterBankOperandMatcher>(RC);
4793
4794       auto &DstMIBuilder =
4795           M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
4796       DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4797       DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
4798       M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
4799
4800       // We're done with this pattern!  It's eligible for GISel emission; return
4801       // it.
4802       ++NumPatternImported;
4803       return std::move(M);
4804     }
4805
4806     return failedImport("Dst pattern root isn't a known leaf");
4807   }
4808
4809   // Start with the defined operands (i.e., the results of the root operator).
4810   Record *DstOp = Dst->getOperator();
4811   if (!DstOp->isSubClassOf("Instruction"))
4812     return failedImport("Pattern operator isn't an instruction");
4813
4814   auto &DstI = Target.getInstruction(DstOp);
4815   StringRef DstIName = DstI.TheDef->getName();
4816
4817   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
4818     return failedImport("Src pattern results and dst MI defs are different (" +
4819                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
4820                         to_string(DstI.Operands.NumDefs) + " def(s))");
4821
4822   // The root of the match also has constraints on the register bank so that it
4823   // matches the result instruction.
4824   unsigned OpIdx = 0;
4825   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
4826     (void)VTy;
4827
4828     const auto &DstIOperand = DstI.Operands[OpIdx];
4829     Record *DstIOpRec = DstIOperand.Rec;
4830     if (DstIName == "COPY_TO_REGCLASS") {
4831       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4832
4833       if (DstIOpRec == nullptr)
4834         return failedImport(
4835             "COPY_TO_REGCLASS operand #1 isn't a register class");
4836     } else if (DstIName == "REG_SEQUENCE") {
4837       DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4838       if (DstIOpRec == nullptr)
4839         return failedImport("REG_SEQUENCE operand #0 isn't a register class");
4840     } else if (DstIName == "EXTRACT_SUBREG") {
4841       auto InferredClass = inferRegClassFromPattern(Dst->getChild(0));
4842       if (!InferredClass)
4843         return failedImport("Could not infer class for EXTRACT_SUBREG operand #0");
4844
4845       // We can assume that a subregister is in the same bank as it's super
4846       // register.
4847       DstIOpRec = (*InferredClass)->getDef();
4848     } else if (DstIName == "INSERT_SUBREG") {
4849       auto MaybeSuperClass = inferSuperRegisterClassForNode(
4850           VTy, Dst->getChild(0), Dst->getChild(2));
4851       if (!MaybeSuperClass)
4852         return failedImport(
4853             "Cannot infer register class for INSERT_SUBREG operand #0");
4854       // Move to the next pattern here, because the register class we found
4855       // doesn't necessarily have a record associated with it. So, we can't
4856       // set DstIOpRec using this.
4857       OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4858       OM.setSymbolicName(DstIOperand.Name);
4859       M.defineOperand(OM.getSymbolicName(), OM);
4860       OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
4861       ++OpIdx;
4862       continue;
4863     } else if (DstIName == "SUBREG_TO_REG") {
4864       auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
4865       if (!MaybeRegClass)
4866         return failedImport(
4867             "Cannot infer register class for SUBREG_TO_REG operand #0");
4868       OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4869       OM.setSymbolicName(DstIOperand.Name);
4870       M.defineOperand(OM.getSymbolicName(), OM);
4871       OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
4872       ++OpIdx;
4873       continue;
4874     } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
4875       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4876     else if (!DstIOpRec->isSubClassOf("RegisterClass"))
4877       return failedImport("Dst MI def isn't a register class" +
4878                           to_string(*Dst));
4879
4880     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4881     OM.setSymbolicName(DstIOperand.Name);
4882     M.defineOperand(OM.getSymbolicName(), OM);
4883     OM.addPredicate<RegisterBankOperandMatcher>(
4884         Target.getRegisterClass(DstIOpRec));
4885     ++OpIdx;
4886   }
4887
4888   auto DstMIBuilderOrError =
4889       createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
4890   if (auto Error = DstMIBuilderOrError.takeError())
4891     return std::move(Error);
4892   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
4893
4894   // Render the implicit defs.
4895   // These are only added to the root of the result.
4896   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
4897     return std::move(Error);
4898
4899   DstMIBuilder.chooseInsnToMutate(M);
4900
4901   // Constrain the registers to classes. This is normally derived from the
4902   // emitted instruction but a few instructions require special handling.
4903   if (DstIName == "COPY_TO_REGCLASS") {
4904     // COPY_TO_REGCLASS does not provide operand constraints itself but the
4905     // result is constrained to the class given by the second child.
4906     Record *DstIOpRec =
4907         getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4908
4909     if (DstIOpRec == nullptr)
4910       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
4911
4912     M.addAction<ConstrainOperandToRegClassAction>(
4913         0, 0, Target.getRegisterClass(DstIOpRec));
4914
4915     // We're done with this pattern!  It's eligible for GISel emission; return
4916     // it.
4917     ++NumPatternImported;
4918     return std::move(M);
4919   }
4920
4921   if (DstIName == "EXTRACT_SUBREG") {
4922     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4923     if (!SuperClass)
4924       return failedImport(
4925         "Cannot infer register class from EXTRACT_SUBREG operand #0");
4926
4927     auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4928     if (!SubIdx)
4929       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4930
4931     // It would be nice to leave this constraint implicit but we're required
4932     // to pick a register class so constrain the result to a register class
4933     // that can hold the correct MVT.
4934     //
4935     // FIXME: This may introduce an extra copy if the chosen class doesn't
4936     //        actually contain the subregisters.
4937     assert(Src->getExtTypes().size() == 1 &&
4938              "Expected Src of EXTRACT_SUBREG to have one result type");
4939
4940     const auto SrcRCDstRCPair =
4941       (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4942     if (!SrcRCDstRCPair) {
4943       return failedImport("subreg index is incompatible "
4944                           "with inferred reg class");
4945     }
4946
4947     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4948     M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4949     M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4950
4951     // We're done with this pattern!  It's eligible for GISel emission; return
4952     // it.
4953     ++NumPatternImported;
4954     return std::move(M);
4955   }
4956
4957   if (DstIName == "INSERT_SUBREG") {
4958     assert(Src->getExtTypes().size() == 1 &&
4959            "Expected Src of INSERT_SUBREG to have one result type");
4960     // We need to constrain the destination, a super regsister source, and a
4961     // subregister source.
4962     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4963     if (!SubClass)
4964       return failedImport(
4965           "Cannot infer register class from INSERT_SUBREG operand #1");
4966     auto SuperClass = inferSuperRegisterClassForNode(
4967         Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
4968     if (!SuperClass)
4969       return failedImport(
4970           "Cannot infer register class for INSERT_SUBREG operand #0");
4971     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4972     M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
4973     M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4974     ++NumPatternImported;
4975     return std::move(M);
4976   }
4977
4978   if (DstIName == "SUBREG_TO_REG") {
4979     // We need to constrain the destination and subregister source.
4980     assert(Src->getExtTypes().size() == 1 &&
4981            "Expected Src of SUBREG_TO_REG to have one result type");
4982
4983     // Attempt to infer the subregister source from the first child. If it has
4984     // an explicitly given register class, we'll use that. Otherwise, we will
4985     // fail.
4986     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4987     if (!SubClass)
4988       return failedImport(
4989           "Cannot infer register class from SUBREG_TO_REG child #1");
4990     // We don't have a child to look at that might have a super register node.
4991     auto SuperClass =
4992         inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
4993     if (!SuperClass)
4994       return failedImport(
4995           "Cannot infer register class for SUBREG_TO_REG operand #0");
4996     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4997     M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4998     ++NumPatternImported;
4999     return std::move(M);
5000   }
5001
5002   if (DstIName == "REG_SEQUENCE") {
5003     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5004
5005     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5006
5007     unsigned Num = Dst->getNumChildren();
5008     for (unsigned I = 1; I != Num; I += 2) {
5009       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
5010
5011       auto SubIdx = inferSubRegIndexForNode(SubRegChild);
5012       if (!SubIdx)
5013         return failedImport("REG_SEQUENCE child is not a subreg index");
5014
5015       const auto SrcRCDstRCPair =
5016         (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5017
5018       M.addAction<ConstrainOperandToRegClassAction>(0, I,
5019                                                     *SrcRCDstRCPair->second);
5020     }
5021
5022     ++NumPatternImported;
5023     return std::move(M);
5024   }
5025
5026   M.addAction<ConstrainOperandsToDefinitionAction>(0);
5027
5028   // We're done with this pattern!  It's eligible for GISel emission; return it.
5029   ++NumPatternImported;
5030   return std::move(M);
5031 }
5032
5033 // Emit imm predicate table and an enum to reference them with.
5034 // The 'Predicate_' part of the name is redundant but eliminating it is more
5035 // trouble than it's worth.
5036 void GlobalISelEmitter::emitCxxPredicateFns(
5037     raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
5038     StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
5039     std::function<bool(const Record *R)> Filter) {
5040   std::vector<const Record *> MatchedRecords;
5041   const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
5042   std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
5043                [&](Record *Record) {
5044                  return !Record->getValueAsString(CodeFieldName).empty() &&
5045                         Filter(Record);
5046                });
5047
5048   if (!MatchedRecords.empty()) {
5049     OS << "// PatFrag predicates.\n"
5050        << "enum {\n";
5051     std::string EnumeratorSeparator =
5052         (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
5053     for (const auto *Record : MatchedRecords) {
5054       OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
5055          << EnumeratorSeparator;
5056       EnumeratorSeparator = ",\n";
5057     }
5058     OS << "};\n";
5059   }
5060
5061   OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
5062      << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
5063      << ArgName << ") const {\n"
5064      << AdditionalDeclarations;
5065   if (!AdditionalDeclarations.empty())
5066     OS << "\n";
5067   if (!MatchedRecords.empty())
5068     OS << "  switch (PredicateID) {\n";
5069   for (const auto *Record : MatchedRecords) {
5070     OS << "  case GIPFP_" << TypeIdentifier << "_Predicate_"
5071        << Record->getName() << ": {\n"
5072        << "    " << Record->getValueAsString(CodeFieldName) << "\n"
5073        << "    llvm_unreachable(\"" << CodeFieldName
5074        << " should have returned\");\n"
5075        << "    return false;\n"
5076        << "  }\n";
5077   }
5078   if (!MatchedRecords.empty())
5079     OS << "  }\n";
5080   OS << "  llvm_unreachable(\"Unknown predicate\");\n"
5081      << "  return false;\n"
5082      << "}\n";
5083 }
5084
5085 void GlobalISelEmitter::emitImmPredicateFns(
5086     raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
5087     std::function<bool(const Record *R)> Filter) {
5088   return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
5089                              "Imm", "", Filter);
5090 }
5091
5092 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
5093   return emitCxxPredicateFns(
5094       OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
5095       "  const MachineFunction &MF = *MI.getParent()->getParent();\n"
5096       "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5097       "  (void)MRI;",
5098       [](const Record *R) { return true; });
5099 }
5100
5101 template <class GroupT>
5102 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
5103     ArrayRef<Matcher *> Rules,
5104     std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
5105
5106   std::vector<Matcher *> OptRules;
5107   std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
5108   assert(CurrentGroup->empty() && "Newly created group isn't empty!");
5109   unsigned NumGroups = 0;
5110
5111   auto ProcessCurrentGroup = [&]() {
5112     if (CurrentGroup->empty())
5113       // An empty group is good to be reused:
5114       return;
5115
5116     // If the group isn't large enough to provide any benefit, move all the
5117     // added rules out of it and make sure to re-create the group to properly
5118     // re-initialize it:
5119     if (CurrentGroup->size() < 2)
5120       for (Matcher *M : CurrentGroup->matchers())
5121         OptRules.push_back(M);
5122     else {
5123       CurrentGroup->finalize();
5124       OptRules.push_back(CurrentGroup.get());
5125       MatcherStorage.emplace_back(std::move(CurrentGroup));
5126       ++NumGroups;
5127     }
5128     CurrentGroup = std::make_unique<GroupT>();
5129   };
5130   for (Matcher *Rule : Rules) {
5131     // Greedily add as many matchers as possible to the current group:
5132     if (CurrentGroup->addMatcher(*Rule))
5133       continue;
5134
5135     ProcessCurrentGroup();
5136     assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
5137
5138     // Try to add the pending matcher to a newly created empty group:
5139     if (!CurrentGroup->addMatcher(*Rule))
5140       // If we couldn't add the matcher to an empty group, that group type
5141       // doesn't support that kind of matchers at all, so just skip it:
5142       OptRules.push_back(Rule);
5143   }
5144   ProcessCurrentGroup();
5145
5146   LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
5147   assert(CurrentGroup->empty() && "The last group wasn't properly processed");
5148   return OptRules;
5149 }
5150
5151 MatchTable
5152 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
5153                                    bool Optimize, bool WithCoverage) {
5154   std::vector<Matcher *> InputRules;
5155   for (Matcher &Rule : Rules)
5156     InputRules.push_back(&Rule);
5157
5158   if (!Optimize)
5159     return MatchTable::buildTable(InputRules, WithCoverage);
5160
5161   unsigned CurrentOrdering = 0;
5162   StringMap<unsigned> OpcodeOrder;
5163   for (RuleMatcher &Rule : Rules) {
5164     const StringRef Opcode = Rule.getOpcode();
5165     assert(!Opcode.empty() && "Didn't expect an undefined opcode");
5166     if (OpcodeOrder.count(Opcode) == 0)
5167       OpcodeOrder[Opcode] = CurrentOrdering++;
5168   }
5169
5170   std::stable_sort(InputRules.begin(), InputRules.end(),
5171                    [&OpcodeOrder](const Matcher *A, const Matcher *B) {
5172                      auto *L = static_cast<const RuleMatcher *>(A);
5173                      auto *R = static_cast<const RuleMatcher *>(B);
5174                      return std::make_tuple(OpcodeOrder[L->getOpcode()],
5175                                             L->getNumOperands()) <
5176                             std::make_tuple(OpcodeOrder[R->getOpcode()],
5177                                             R->getNumOperands());
5178                    });
5179
5180   for (Matcher *Rule : InputRules)
5181     Rule->optimize();
5182
5183   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
5184   std::vector<Matcher *> OptRules =
5185       optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
5186
5187   for (Matcher *Rule : OptRules)
5188     Rule->optimize();
5189
5190   OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
5191
5192   return MatchTable::buildTable(OptRules, WithCoverage);
5193 }
5194
5195 void GroupMatcher::optimize() {
5196   // Make sure we only sort by a specific predicate within a range of rules that
5197   // all have that predicate checked against a specific value (not a wildcard):
5198   auto F = Matchers.begin();
5199   auto T = F;
5200   auto E = Matchers.end();
5201   while (T != E) {
5202     while (T != E) {
5203       auto *R = static_cast<RuleMatcher *>(*T);
5204       if (!R->getFirstConditionAsRootType().get().isValid())
5205         break;
5206       ++T;
5207     }
5208     std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
5209       auto *L = static_cast<RuleMatcher *>(A);
5210       auto *R = static_cast<RuleMatcher *>(B);
5211       return L->getFirstConditionAsRootType() <
5212              R->getFirstConditionAsRootType();
5213     });
5214     if (T != E)
5215       F = ++T;
5216   }
5217   GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
5218       .swap(Matchers);
5219   GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
5220       .swap(Matchers);
5221 }
5222
5223 void GlobalISelEmitter::run(raw_ostream &OS) {
5224   if (!UseCoverageFile.empty()) {
5225     RuleCoverage = CodeGenCoverage();
5226     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5227     if (!RuleCoverageBufOrErr) {
5228       PrintWarning(SMLoc(), "Missing rule coverage data");
5229       RuleCoverage = None;
5230     } else {
5231       if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5232         PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5233         RuleCoverage = None;
5234       }
5235     }
5236   }
5237
5238   // Track the run-time opcode values
5239   gatherOpcodeValues();
5240   // Track the run-time LLT ID values
5241   gatherTypeIDValues();
5242
5243   // Track the GINodeEquiv definitions.
5244   gatherNodeEquivs();
5245
5246   emitSourceFileHeader(("Global Instruction Selector for the " +
5247                        Target.getName() + " target").str(), OS);
5248   std::vector<RuleMatcher> Rules;
5249   // Look through the SelectionDAG patterns we found, possibly emitting some.
5250   for (const PatternToMatch &Pat : CGP.ptms()) {
5251     ++NumPatternTotal;
5252
5253     auto MatcherOrErr = runOnPattern(Pat);
5254
5255     // The pattern analysis can fail, indicating an unsupported pattern.
5256     // Report that if we've been asked to do so.
5257     if (auto Err = MatcherOrErr.takeError()) {
5258       if (WarnOnSkippedPatterns) {
5259         PrintWarning(Pat.getSrcRecord()->getLoc(),
5260                      "Skipped pattern: " + toString(std::move(Err)));
5261       } else {
5262         consumeError(std::move(Err));
5263       }
5264       ++NumPatternImportsSkipped;
5265       continue;
5266     }
5267
5268     if (RuleCoverage) {
5269       if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5270         ++NumPatternsTested;
5271       else
5272         PrintWarning(Pat.getSrcRecord()->getLoc(),
5273                      "Pattern is not covered by a test");
5274     }
5275     Rules.push_back(std::move(MatcherOrErr.get()));
5276   }
5277
5278   // Comparison function to order records by name.
5279   auto orderByName = [](const Record *A, const Record *B) {
5280     return A->getName() < B->getName();
5281   };
5282
5283   std::vector<Record *> ComplexPredicates =
5284       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5285   llvm::sort(ComplexPredicates, orderByName);
5286
5287   std::vector<Record *> CustomRendererFns =
5288       RK.getAllDerivedDefinitions("GICustomOperandRenderer");
5289   llvm::sort(CustomRendererFns, orderByName);
5290
5291   unsigned MaxTemporaries = 0;
5292   for (const auto &Rule : Rules)
5293     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5294
5295   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5296      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5297      << ";\n"
5298      << "using PredicateBitset = "
5299         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5300      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5301
5302   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5303      << "  mutable MatcherState State;\n"
5304      << "  typedef "
5305         "ComplexRendererFns("
5306      << Target.getName()
5307      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5308
5309      << "  typedef void(" << Target.getName()
5310      << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5311         "MachineInstr&, int) "
5312         "const;\n"
5313      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5314         "CustomRendererFn> "
5315         "ISelInfo;\n";
5316   OS << "  static " << Target.getName()
5317      << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5318      << "  static " << Target.getName()
5319      << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5320      << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5321         "override;\n"
5322      << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5323         "const override;\n"
5324      << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5325         "&Imm) const override;\n"
5326      << "  const int64_t *getMatchTable() const override;\n"
5327      << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
5328         "const override;\n"
5329      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5330
5331   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5332      << ", State(" << MaxTemporaries << "),\n"
5333      << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5334      << ", ComplexPredicateFns, CustomRenderers)\n"
5335      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5336
5337   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5338   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5339                                                            OS);
5340
5341   // Separate subtarget features by how often they must be recomputed.
5342   SubtargetFeatureInfoMap ModuleFeatures;
5343   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5344                std::inserter(ModuleFeatures, ModuleFeatures.end()),
5345                [](const SubtargetFeatureInfoMap::value_type &X) {
5346                  return !X.second.mustRecomputePerFunction();
5347                });
5348   SubtargetFeatureInfoMap FunctionFeatures;
5349   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5350                std::inserter(FunctionFeatures, FunctionFeatures.end()),
5351                [](const SubtargetFeatureInfoMap::value_type &X) {
5352                  return X.second.mustRecomputePerFunction();
5353                });
5354
5355   SubtargetFeatureInfo::emitComputeAvailableFeatures(
5356     Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5357       ModuleFeatures, OS);
5358
5359
5360   OS << "void " << Target.getName() << "InstructionSelector"
5361     "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
5362     "  AvailableFunctionFeatures = computeAvailableFunctionFeatures("
5363     "(const " << Target.getName() << "Subtarget*)&MF.getSubtarget(), &MF);\n"
5364     "}\n";
5365
5366   if (Target.getName() == "X86" || Target.getName() == "AArch64") {
5367     // TODO: Implement PGSO.
5368     OS << "static bool shouldOptForSize(const MachineFunction *MF) {\n";
5369     OS << "    return MF->getFunction().hasOptSize();\n";
5370     OS << "}\n\n";
5371   }
5372
5373   SubtargetFeatureInfo::emitComputeAvailableFeatures(
5374       Target.getName(), "InstructionSelector",
5375       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5376       "const MachineFunction *MF");
5377
5378   // Emit a table containing the LLT objects needed by the matcher and an enum
5379   // for the matcher to reference them with.
5380   std::vector<LLTCodeGen> TypeObjects;
5381   for (const auto &Ty : KnownTypes)
5382     TypeObjects.push_back(Ty);
5383   llvm::sort(TypeObjects);
5384   OS << "// LLT Objects.\n"
5385      << "enum {\n";
5386   for (const auto &TypeObject : TypeObjects) {
5387     OS << "  ";
5388     TypeObject.emitCxxEnumValue(OS);
5389     OS << ",\n";
5390   }
5391   OS << "};\n";
5392   OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5393      << "const static LLT TypeObjects[] = {\n";
5394   for (const auto &TypeObject : TypeObjects) {
5395     OS << "  ";
5396     TypeObject.emitCxxConstructorCall(OS);
5397     OS << ",\n";
5398   }
5399   OS << "};\n\n";
5400
5401   // Emit a table containing the PredicateBitsets objects needed by the matcher
5402   // and an enum for the matcher to reference them with.
5403   std::vector<std::vector<Record *>> FeatureBitsets;
5404   for (auto &Rule : Rules)
5405     FeatureBitsets.push_back(Rule.getRequiredFeatures());
5406   llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5407                                  const std::vector<Record *> &B) {
5408     if (A.size() < B.size())
5409       return true;
5410     if (A.size() > B.size())
5411       return false;
5412     for (auto Pair : zip(A, B)) {
5413       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5414         return true;
5415       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5416         return false;
5417     }
5418     return false;
5419   });
5420   FeatureBitsets.erase(
5421       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5422       FeatureBitsets.end());
5423   OS << "// Feature bitsets.\n"
5424      << "enum {\n"
5425      << "  GIFBS_Invalid,\n";
5426   for (const auto &FeatureBitset : FeatureBitsets) {
5427     if (FeatureBitset.empty())
5428       continue;
5429     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5430   }
5431   OS << "};\n"
5432      << "const static PredicateBitset FeatureBitsets[] {\n"
5433      << "  {}, // GIFBS_Invalid\n";
5434   for (const auto &FeatureBitset : FeatureBitsets) {
5435     if (FeatureBitset.empty())
5436       continue;
5437     OS << "  {";
5438     for (const auto &Feature : FeatureBitset) {
5439       const auto &I = SubtargetFeatures.find(Feature);
5440       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5441       OS << I->second.getEnumBitName() << ", ";
5442     }
5443     OS << "},\n";
5444   }
5445   OS << "};\n\n";
5446
5447   // Emit complex predicate table and an enum to reference them with.
5448   OS << "// ComplexPattern predicates.\n"
5449      << "enum {\n"
5450      << "  GICP_Invalid,\n";
5451   for (const auto &Record : ComplexPredicates)
5452     OS << "  GICP_" << Record->getName() << ",\n";
5453   OS << "};\n"
5454      << "// See constructor for table contents\n\n";
5455
5456   emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5457     bool Unset;
5458     return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5459            !R->getValueAsBit("IsAPInt");
5460   });
5461   emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5462     bool Unset;
5463     return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5464   });
5465   emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5466     return R->getValueAsBit("IsAPInt");
5467   });
5468   emitMIPredicateFns(OS);
5469   OS << "\n";
5470
5471   OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5472      << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5473      << "  nullptr, // GICP_Invalid\n";
5474   for (const auto &Record : ComplexPredicates)
5475     OS << "  &" << Target.getName()
5476        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5477        << ", // " << Record->getName() << "\n";
5478   OS << "};\n\n";
5479
5480   OS << "// Custom renderers.\n"
5481      << "enum {\n"
5482      << "  GICR_Invalid,\n";
5483   for (const auto &Record : CustomRendererFns)
5484     OS << "  GICR_" << Record->getValueAsString("RendererFn") << ", \n";
5485   OS << "};\n";
5486
5487   OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5488      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5489      << "  nullptr, // GICR_Invalid\n";
5490   for (const auto &Record : CustomRendererFns)
5491     OS << "  &" << Target.getName()
5492        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
5493        << ", // " << Record->getName() << "\n";
5494   OS << "};\n\n";
5495
5496   llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5497     int ScoreA = RuleMatcherScores[A.getRuleID()];
5498     int ScoreB = RuleMatcherScores[B.getRuleID()];
5499     if (ScoreA > ScoreB)
5500       return true;
5501     if (ScoreB > ScoreA)
5502       return false;
5503     if (A.isHigherPriorityThan(B)) {
5504       assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5505                                            "and less important at "
5506                                            "the same time");
5507       return true;
5508     }
5509     return false;
5510   });
5511
5512   OS << "bool " << Target.getName()
5513      << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5514         "&CoverageInfo) const {\n"
5515      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
5516      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5517      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5518      << "  NewMIVector OutMIs;\n"
5519      << "  State.MIs.clear();\n"
5520      << "  State.MIs.push_back(&I);\n\n"
5521      << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5522      << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5523      << ", CoverageInfo)) {\n"
5524      << "    return true;\n"
5525      << "  }\n\n"
5526      << "  return false;\n"
5527      << "}\n\n";
5528
5529   const MatchTable Table =
5530       buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5531   OS << "const int64_t *" << Target.getName()
5532      << "InstructionSelector::getMatchTable() const {\n";
5533   Table.emitDeclaration(OS);
5534   OS << "  return ";
5535   Table.emitUse(OS);
5536   OS << ";\n}\n";
5537   OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5538
5539   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5540      << "PredicateBitset AvailableModuleFeatures;\n"
5541      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5542      << "PredicateBitset getAvailableFeatures() const {\n"
5543      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5544      << "}\n"
5545      << "PredicateBitset\n"
5546      << "computeAvailableModuleFeatures(const " << Target.getName()
5547      << "Subtarget *Subtarget) const;\n"
5548      << "PredicateBitset\n"
5549      << "computeAvailableFunctionFeatures(const " << Target.getName()
5550      << "Subtarget *Subtarget,\n"
5551      << "                                 const MachineFunction *MF) const;\n"
5552      << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
5553      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5554
5555   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5556      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5557      << "AvailableFunctionFeatures()\n"
5558      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5559 }
5560
5561 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5562   if (SubtargetFeatures.count(Predicate) == 0)
5563     SubtargetFeatures.emplace(
5564         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5565 }
5566
5567 void RuleMatcher::optimize() {
5568   for (auto &Item : InsnVariableIDs) {
5569     InstructionMatcher &InsnMatcher = *Item.first;
5570     for (auto &OM : InsnMatcher.operands()) {
5571       // Complex Patterns are usually expensive and they relatively rarely fail
5572       // on their own: more often we end up throwing away all the work done by a
5573       // matching part of a complex pattern because some other part of the
5574       // enclosing pattern didn't match. All of this makes it beneficial to
5575       // delay complex patterns until the very end of the rule matching,
5576       // especially for targets having lots of complex patterns.
5577       for (auto &OP : OM->predicates())
5578         if (isa<ComplexPatternOperandMatcher>(OP))
5579           EpilogueMatchers.emplace_back(std::move(OP));
5580       OM->eraseNullPredicates();
5581     }
5582     InsnMatcher.optimize();
5583   }
5584   llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5585                                   const std::unique_ptr<PredicateMatcher> &R) {
5586     return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5587            std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5588   });
5589 }
5590
5591 bool RuleMatcher::hasFirstCondition() const {
5592   if (insnmatchers_empty())
5593     return false;
5594   InstructionMatcher &Matcher = insnmatchers_front();
5595   if (!Matcher.predicates_empty())
5596     return true;
5597   for (auto &OM : Matcher.operands())
5598     for (auto &OP : OM->predicates())
5599       if (!isa<InstructionOperandMatcher>(OP))
5600         return true;
5601   return false;
5602 }
5603
5604 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5605   assert(!insnmatchers_empty() &&
5606          "Trying to get a condition from an empty RuleMatcher");
5607
5608   InstructionMatcher &Matcher = insnmatchers_front();
5609   if (!Matcher.predicates_empty())
5610     return **Matcher.predicates_begin();
5611   // If there is no more predicate on the instruction itself, look at its
5612   // operands.
5613   for (auto &OM : Matcher.operands())
5614     for (auto &OP : OM->predicates())
5615       if (!isa<InstructionOperandMatcher>(OP))
5616         return *OP;
5617
5618   llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5619                    "no conditions");
5620 }
5621
5622 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5623   assert(!insnmatchers_empty() &&
5624          "Trying to pop a condition from an empty RuleMatcher");
5625
5626   InstructionMatcher &Matcher = insnmatchers_front();
5627   if (!Matcher.predicates_empty())
5628     return Matcher.predicates_pop_front();
5629   // If there is no more predicate on the instruction itself, look at its
5630   // operands.
5631   for (auto &OM : Matcher.operands())
5632     for (auto &OP : OM->predicates())
5633       if (!isa<InstructionOperandMatcher>(OP)) {
5634         std::unique_ptr<PredicateMatcher> Result = std::move(OP);
5635         OM->eraseNullPredicates();
5636         return Result;
5637       }
5638
5639   llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
5640                    "no conditions");
5641 }
5642
5643 bool GroupMatcher::candidateConditionMatches(
5644     const PredicateMatcher &Predicate) const {
5645
5646   if (empty()) {
5647     // Sharing predicates for nested instructions is not supported yet as we
5648     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5649     // only work on the original root instruction (InsnVarID == 0):
5650     if (Predicate.getInsnVarID() != 0)
5651       return false;
5652     // ... otherwise an empty group can handle any predicate with no specific
5653     // requirements:
5654     return true;
5655   }
5656
5657   const Matcher &Representative = **Matchers.begin();
5658   const auto &RepresentativeCondition = Representative.getFirstCondition();
5659   // ... if not empty, the group can only accomodate matchers with the exact
5660   // same first condition:
5661   return Predicate.isIdentical(RepresentativeCondition);
5662 }
5663
5664 bool GroupMatcher::addMatcher(Matcher &Candidate) {
5665   if (!Candidate.hasFirstCondition())
5666     return false;
5667
5668   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5669   if (!candidateConditionMatches(Predicate))
5670     return false;
5671
5672   Matchers.push_back(&Candidate);
5673   return true;
5674 }
5675
5676 void GroupMatcher::finalize() {
5677   assert(Conditions.empty() && "Already finalized?");
5678   if (empty())
5679     return;
5680
5681   Matcher &FirstRule = **Matchers.begin();
5682   for (;;) {
5683     // All the checks are expected to succeed during the first iteration:
5684     for (const auto &Rule : Matchers)
5685       if (!Rule->hasFirstCondition())
5686         return;
5687     const auto &FirstCondition = FirstRule.getFirstCondition();
5688     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5689       if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
5690         return;
5691
5692     Conditions.push_back(FirstRule.popFirstCondition());
5693     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5694       Matchers[I]->popFirstCondition();
5695   }
5696 }
5697
5698 void GroupMatcher::emit(MatchTable &Table) {
5699   unsigned LabelID = ~0U;
5700   if (!Conditions.empty()) {
5701     LabelID = Table.allocateLabelID();
5702     Table << MatchTable::Opcode("GIM_Try", +1)
5703           << MatchTable::Comment("On fail goto")
5704           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
5705   }
5706   for (auto &Condition : Conditions)
5707     Condition->emitPredicateOpcodes(
5708         Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
5709
5710   for (const auto &M : Matchers)
5711     M->emit(Table);
5712
5713   // Exit the group
5714   if (!Conditions.empty())
5715     Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
5716           << MatchTable::Label(LabelID);
5717 }
5718
5719 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
5720   return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
5721 }
5722
5723 bool SwitchMatcher::candidateConditionMatches(
5724     const PredicateMatcher &Predicate) const {
5725
5726   if (empty()) {
5727     // Sharing predicates for nested instructions is not supported yet as we
5728     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5729     // only work on the original root instruction (InsnVarID == 0):
5730     if (Predicate.getInsnVarID() != 0)
5731       return false;
5732     // ... while an attempt to add even a root matcher to an empty SwitchMatcher
5733     // could fail as not all the types of conditions are supported:
5734     if (!isSupportedPredicateType(Predicate))
5735       return false;
5736     // ... or the condition might not have a proper implementation of
5737     // getValue() / isIdenticalDownToValue() yet:
5738     if (!Predicate.hasValue())
5739       return false;
5740     // ... otherwise an empty Switch can accomodate the condition with no
5741     // further requirements:
5742     return true;
5743   }
5744
5745   const Matcher &CaseRepresentative = **Matchers.begin();
5746   const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
5747   // Switch-cases must share the same kind of condition and path to the value it
5748   // checks:
5749   if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
5750     return false;
5751
5752   const auto Value = Predicate.getValue();
5753   // ... but be unique with respect to the actual value they check:
5754   return Values.count(Value) == 0;
5755 }
5756
5757 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
5758   if (!Candidate.hasFirstCondition())
5759     return false;
5760
5761   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5762   if (!candidateConditionMatches(Predicate))
5763     return false;
5764   const auto Value = Predicate.getValue();
5765   Values.insert(Value);
5766
5767   Matchers.push_back(&Candidate);
5768   return true;
5769 }
5770
5771 void SwitchMatcher::finalize() {
5772   assert(Condition == nullptr && "Already finalized");
5773   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5774   if (empty())
5775     return;
5776
5777   std::stable_sort(Matchers.begin(), Matchers.end(),
5778                    [](const Matcher *L, const Matcher *R) {
5779                      return L->getFirstCondition().getValue() <
5780                             R->getFirstCondition().getValue();
5781                    });
5782   Condition = Matchers[0]->popFirstCondition();
5783   for (unsigned I = 1, E = Values.size(); I < E; ++I)
5784     Matchers[I]->popFirstCondition();
5785 }
5786
5787 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
5788                                                  MatchTable &Table) {
5789   assert(isSupportedPredicateType(P) && "Predicate type is not supported");
5790
5791   if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
5792     Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
5793           << MatchTable::IntValue(Condition->getInsnVarID());
5794     return;
5795   }
5796   if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
5797     Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
5798           << MatchTable::IntValue(Condition->getInsnVarID())
5799           << MatchTable::Comment("Op")
5800           << MatchTable::IntValue(Condition->getOpIdx());
5801     return;
5802   }
5803
5804   llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
5805                    "predicate type that is claimed to be supported");
5806 }
5807
5808 void SwitchMatcher::emit(MatchTable &Table) {
5809   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5810   if (empty())
5811     return;
5812   assert(Condition != nullptr &&
5813          "Broken SwitchMatcher, hasn't been finalized?");
5814
5815   std::vector<unsigned> LabelIDs(Values.size());
5816   std::generate(LabelIDs.begin(), LabelIDs.end(),
5817                 [&Table]() { return Table.allocateLabelID(); });
5818   const unsigned Default = Table.allocateLabelID();
5819
5820   const int64_t LowerBound = Values.begin()->getRawValue();
5821   const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
5822
5823   emitPredicateSpecificOpcodes(*Condition, Table);
5824
5825   Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
5826         << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
5827         << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
5828
5829   int64_t J = LowerBound;
5830   auto VI = Values.begin();
5831   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5832     auto V = *VI++;
5833     while (J++ < V.getRawValue())
5834       Table << MatchTable::IntValue(0);
5835     V.turnIntoComment();
5836     Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
5837   }
5838   Table << MatchTable::LineBreak;
5839
5840   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5841     Table << MatchTable::Label(LabelIDs[I]);
5842     Matchers[I]->emit(Table);
5843     Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
5844   }
5845   Table << MatchTable::Label(Default);
5846 }
5847
5848 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
5849
5850 } // end anonymous namespace
5851
5852 //===----------------------------------------------------------------------===//
5853
5854 namespace llvm {
5855 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
5856   GlobalISelEmitter(RK).run(OS);
5857 }
5858 } // End llvm namespace