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