contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

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