llvm/utils/TableGen/GlobalISelEmitter.cpp

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