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