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

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