utils/TableGen/GlobalISelEmitter.cpp

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