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

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