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   bool isIdentical(const PredicateMatcher &B) const override {
1841     return InstructionPredicateMatcher::isIdentical(B) &&
1842            Predicate ==
1843                static_cast<const GenericInstructionPredicateMatcher &>(B)
1844                    .Predicate;
1845   }
1846   void emitPredicateOpcodes(MatchTable &Table,
1847                             RuleMatcher &Rule) const override {
1848     Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
1849           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1850           << MatchTable::Comment("FnId")
1851           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1852           << MatchTable::LineBreak;
1853   }
1854 };
1855
1856 /// Generates code to check that a set of predicates and operands match for a
1857 /// particular instruction.
1858 ///
1859 /// Typical predicates include:
1860 /// * Has a specific opcode.
1861 /// * Has an nsw/nuw flag or doesn't.
1862 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
1863 protected:
1864   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
1865
1866   RuleMatcher &Rule;
1867
1868   /// The operands to match. All rendered operands must be present even if the
1869   /// condition is always true.
1870   OperandVec Operands;
1871   bool NumOperandsCheck = true;
1872
1873   std::string SymbolicName;
1874   unsigned InsnVarID;
1875
1876 public:
1877   InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
1878       : Rule(Rule), SymbolicName(SymbolicName) {
1879     // We create a new instruction matcher.
1880     // Get a new ID for that instruction.
1881     InsnVarID = Rule.implicitlyDefineInsnVar(*this);
1882   }
1883
1884   /// Construct a new instruction predicate and add it to the matcher.
1885   template <class Kind, class... Args>
1886   Optional<Kind *> addPredicate(Args &&... args) {
1887     Predicates.emplace_back(
1888         llvm::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
1889     return static_cast<Kind *>(Predicates.back().get());
1890   }
1891
1892   RuleMatcher &getRuleMatcher() const { return Rule; }
1893
1894   unsigned getInsnVarID() const { return InsnVarID; }
1895
1896   /// Add an operand to the matcher.
1897   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
1898                              unsigned AllocatedTemporariesBaseID) {
1899     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
1900                                              AllocatedTemporariesBaseID));
1901     if (!SymbolicName.empty())
1902       Rule.defineOperand(SymbolicName, *Operands.back());
1903
1904     return *Operands.back();
1905   }
1906
1907   OperandMatcher &getOperand(unsigned OpIdx) {
1908     auto I = std::find_if(Operands.begin(), Operands.end(),
1909                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1910                             return X->getOpIdx() == OpIdx;
1911                           });
1912     if (I != Operands.end())
1913       return **I;
1914     llvm_unreachable("Failed to lookup operand");
1915   }
1916
1917   StringRef getSymbolicName() const { return SymbolicName; }
1918   unsigned getNumOperands() const { return Operands.size(); }
1919   OperandVec::iterator operands_begin() { return Operands.begin(); }
1920   OperandVec::iterator operands_end() { return Operands.end(); }
1921   iterator_range<OperandVec::iterator> operands() {
1922     return make_range(operands_begin(), operands_end());
1923   }
1924   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
1925   OperandVec::const_iterator operands_end() const { return Operands.end(); }
1926   iterator_range<OperandVec::const_iterator> operands() const {
1927     return make_range(operands_begin(), operands_end());
1928   }
1929   bool operands_empty() const { return Operands.empty(); }
1930
1931   void pop_front() { Operands.erase(Operands.begin()); }
1932
1933   void optimize();
1934
1935   /// Emit MatchTable opcodes that test whether the instruction named in
1936   /// InsnVarName matches all the predicates and all the operands.
1937   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1938     if (NumOperandsCheck)
1939       InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
1940           .emitPredicateOpcodes(Table, Rule);
1941
1942     emitPredicateListOpcodes(Table, Rule);
1943
1944     for (const auto &Operand : Operands)
1945       Operand->emitPredicateOpcodes(Table, Rule);
1946   }
1947
1948   /// Compare the priority of this object and B.
1949   ///
1950   /// Returns true if this object is more important than B.
1951   bool isHigherPriorityThan(InstructionMatcher &B) {
1952     // Instruction matchers involving more operands have higher priority.
1953     if (Operands.size() > B.Operands.size())
1954       return true;
1955     if (Operands.size() < B.Operands.size())
1956       return false;
1957
1958     for (auto &&P : zip(predicates(), B.predicates())) {
1959       auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
1960       auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
1961       if (L->isHigherPriorityThan(*R))
1962         return true;
1963       if (R->isHigherPriorityThan(*L))
1964         return false;
1965     }
1966
1967     for (const auto &Operand : zip(Operands, B.Operands)) {
1968       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
1969         return true;
1970       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
1971         return false;
1972     }
1973
1974     return false;
1975   };
1976
1977   /// Report the maximum number of temporary operands needed by the instruction
1978   /// matcher.
1979   unsigned countRendererFns() {
1980     return std::accumulate(
1981                predicates().begin(), predicates().end(), 0,
1982                [](unsigned A,
1983                   const std::unique_ptr<PredicateMatcher> &Predicate) {
1984                  return A + Predicate->countRendererFns();
1985                }) +
1986            std::accumulate(
1987                Operands.begin(), Operands.end(), 0,
1988                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
1989                  return A + Operand->countRendererFns();
1990                });
1991   }
1992
1993   InstructionOpcodeMatcher &getOpcodeMatcher() {
1994     for (auto &P : predicates())
1995       if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
1996         return *OpMatcher;
1997     llvm_unreachable("Didn't find an opcode matcher");
1998   }
1999
2000   bool isConstantInstruction() {
2001     return getOpcodeMatcher().isConstantInstruction();
2002   }
2003
2004   StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2005 };
2006
2007 StringRef RuleMatcher::getOpcode() const {
2008   return Matchers.front()->getOpcode();
2009 }
2010
2011 unsigned RuleMatcher::getNumOperands() const {
2012   return Matchers.front()->getNumOperands();
2013 }
2014
2015 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2016   InstructionMatcher &InsnMatcher = *Matchers.front();
2017   if (!InsnMatcher.predicates_empty())
2018     if (const auto *TM =
2019             dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2020       if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2021         return TM->getTy();
2022   return {};
2023 }
2024
2025 /// Generates code to check that the operand is a register defined by an
2026 /// instruction that matches the given instruction matcher.
2027 ///
2028 /// For example, the pattern:
2029 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2030 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2031 /// the:
2032 ///   (G_ADD $src1, $src2)
2033 /// subpattern.
2034 class InstructionOperandMatcher : public OperandPredicateMatcher {
2035 protected:
2036   std::unique_ptr<InstructionMatcher> InsnMatcher;
2037
2038 public:
2039   InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2040                             RuleMatcher &Rule, StringRef SymbolicName)
2041       : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2042         InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2043
2044   static bool classof(const PredicateMatcher *P) {
2045     return P->getKind() == OPM_Instruction;
2046   }
2047
2048   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2049
2050   void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2051     const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2052     Table << MatchTable::Opcode("GIM_RecordInsn")
2053           << MatchTable::Comment("DefineMI")
2054           << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2055           << MatchTable::IntValue(getInsnVarID())
2056           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2057           << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2058           << MatchTable::LineBreak;
2059   }
2060
2061   void emitPredicateOpcodes(MatchTable &Table,
2062                             RuleMatcher &Rule) const override {
2063     emitCaptureOpcodes(Table, Rule);
2064     InsnMatcher->emitPredicateOpcodes(Table, Rule);
2065   }
2066
2067   bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2068     if (OperandPredicateMatcher::isHigherPriorityThan(B))
2069       return true;
2070     if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2071       return false;
2072
2073     if (const InstructionOperandMatcher *BP =
2074             dyn_cast<InstructionOperandMatcher>(&B))
2075       if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2076         return true;
2077     return false;
2078   }
2079 };
2080
2081 void InstructionMatcher::optimize() {
2082   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2083   const auto &OpcMatcher = getOpcodeMatcher();
2084
2085   Stash.push_back(predicates_pop_front());
2086   if (Stash.back().get() == &OpcMatcher) {
2087     if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands())
2088       Stash.emplace_back(
2089           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2090     NumOperandsCheck = false;
2091
2092     for (auto &OM : Operands)
2093       for (auto &OP : OM->predicates())
2094         if (isa<IntrinsicIDOperandMatcher>(OP)) {
2095           Stash.push_back(std::move(OP));
2096           OM->eraseNullPredicates();
2097           break;
2098         }
2099   }
2100
2101   if (InsnVarID > 0) {
2102     assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2103     for (auto &OP : Operands[0]->predicates())
2104       OP.reset();
2105     Operands[0]->eraseNullPredicates();
2106   }
2107   for (auto &OM : Operands) {
2108     for (auto &OP : OM->predicates())
2109       if (isa<LLTOperandMatcher>(OP))
2110         Stash.push_back(std::move(OP));
2111     OM->eraseNullPredicates();
2112   }
2113   while (!Stash.empty())
2114     prependPredicate(Stash.pop_back_val());
2115 }
2116
2117 //===- Actions ------------------------------------------------------------===//
2118 class OperandRenderer {
2119 public:
2120   enum RendererKind {
2121     OR_Copy,
2122     OR_CopyOrAddZeroReg,
2123     OR_CopySubReg,
2124     OR_CopyConstantAsImm,
2125     OR_CopyFConstantAsFPImm,
2126     OR_Imm,
2127     OR_Register,
2128     OR_TempRegister,
2129     OR_ComplexPattern,
2130     OR_Custom
2131   };
2132
2133 protected:
2134   RendererKind Kind;
2135
2136 public:
2137   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2138   virtual ~OperandRenderer() {}
2139
2140   RendererKind getKind() const { return Kind; }
2141
2142   virtual void emitRenderOpcodes(MatchTable &Table,
2143                                  RuleMatcher &Rule) const = 0;
2144 };
2145
2146 /// A CopyRenderer emits code to copy a single operand from an existing
2147 /// instruction to the one being built.
2148 class CopyRenderer : public OperandRenderer {
2149 protected:
2150   unsigned NewInsnID;
2151   /// The name of the operand.
2152   const StringRef SymbolicName;
2153
2154 public:
2155   CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2156       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2157         SymbolicName(SymbolicName) {
2158     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2159   }
2160
2161   static bool classof(const OperandRenderer *R) {
2162     return R->getKind() == OR_Copy;
2163   }
2164
2165   const StringRef getSymbolicName() const { return SymbolicName; }
2166
2167   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2168     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2169     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2170     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2171           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2172           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2173           << MatchTable::IntValue(Operand.getOpIdx())
2174           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2175   }
2176 };
2177
2178 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2179 /// existing instruction to the one being built. If the operand turns out to be
2180 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2181 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2182 protected:
2183   unsigned NewInsnID;
2184   /// The name of the operand.
2185   const StringRef SymbolicName;
2186   const Record *ZeroRegisterDef;
2187
2188 public:
2189   CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2190                            StringRef SymbolicName, Record *ZeroRegisterDef)
2191       : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2192         SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2193     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2194   }
2195
2196   static bool classof(const OperandRenderer *R) {
2197     return R->getKind() == OR_CopyOrAddZeroReg;
2198   }
2199
2200   const StringRef getSymbolicName() const { return SymbolicName; }
2201
2202   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2203     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2204     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2205     Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2206           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2207           << MatchTable::Comment("OldInsnID")
2208           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2209           << MatchTable::IntValue(Operand.getOpIdx())
2210           << MatchTable::NamedValue(
2211                  (ZeroRegisterDef->getValue("Namespace")
2212                       ? ZeroRegisterDef->getValueAsString("Namespace")
2213                       : ""),
2214                  ZeroRegisterDef->getName())
2215           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2216   }
2217 };
2218
2219 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2220 /// an extended immediate operand.
2221 class CopyConstantAsImmRenderer : public OperandRenderer {
2222 protected:
2223   unsigned NewInsnID;
2224   /// The name of the operand.
2225   const std::string SymbolicName;
2226   bool Signed;
2227
2228 public:
2229   CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2230       : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2231         SymbolicName(SymbolicName), Signed(true) {}
2232
2233   static bool classof(const OperandRenderer *R) {
2234     return R->getKind() == OR_CopyConstantAsImm;
2235   }
2236
2237   const StringRef getSymbolicName() const { return SymbolicName; }
2238
2239   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2240     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2241     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2242     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2243                                        : "GIR_CopyConstantAsUImm")
2244           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2245           << MatchTable::Comment("OldInsnID")
2246           << MatchTable::IntValue(OldInsnVarID)
2247           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2248   }
2249 };
2250
2251 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2252 /// instruction to an extended immediate operand.
2253 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2254 protected:
2255   unsigned NewInsnID;
2256   /// The name of the operand.
2257   const std::string SymbolicName;
2258
2259 public:
2260   CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2261       : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2262         SymbolicName(SymbolicName) {}
2263
2264   static bool classof(const OperandRenderer *R) {
2265     return R->getKind() == OR_CopyFConstantAsFPImm;
2266   }
2267
2268   const StringRef getSymbolicName() const { return SymbolicName; }
2269
2270   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2271     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2272     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2273     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2274           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2275           << MatchTable::Comment("OldInsnID")
2276           << MatchTable::IntValue(OldInsnVarID)
2277           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2278   }
2279 };
2280
2281 /// A CopySubRegRenderer emits code to copy a single register operand from an
2282 /// existing instruction to the one being built and indicate that only a
2283 /// subregister should be copied.
2284 class CopySubRegRenderer : public OperandRenderer {
2285 protected:
2286   unsigned NewInsnID;
2287   /// The name of the operand.
2288   const StringRef SymbolicName;
2289   /// The subregister to extract.
2290   const CodeGenSubRegIndex *SubReg;
2291
2292 public:
2293   CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2294                      const CodeGenSubRegIndex *SubReg)
2295       : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2296         SymbolicName(SymbolicName), SubReg(SubReg) {}
2297
2298   static bool classof(const OperandRenderer *R) {
2299     return R->getKind() == OR_CopySubReg;
2300   }
2301
2302   const StringRef getSymbolicName() const { return SymbolicName; }
2303
2304   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2305     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2306     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2307     Table << MatchTable::Opcode("GIR_CopySubReg")
2308           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2309           << MatchTable::Comment("OldInsnID")
2310           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2311           << MatchTable::IntValue(Operand.getOpIdx())
2312           << MatchTable::Comment("SubRegIdx")
2313           << MatchTable::IntValue(SubReg->EnumValue)
2314           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2315   }
2316 };
2317
2318 /// Adds a specific physical register to the instruction being built.
2319 /// This is typically useful for WZR/XZR on AArch64.
2320 class AddRegisterRenderer : public OperandRenderer {
2321 protected:
2322   unsigned InsnID;
2323   const Record *RegisterDef;
2324
2325 public:
2326   AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
2327       : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
2328   }
2329
2330   static bool classof(const OperandRenderer *R) {
2331     return R->getKind() == OR_Register;
2332   }
2333
2334   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2335     Table << MatchTable::Opcode("GIR_AddRegister")
2336           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2337           << MatchTable::NamedValue(
2338                  (RegisterDef->getValue("Namespace")
2339                       ? RegisterDef->getValueAsString("Namespace")
2340                       : ""),
2341                  RegisterDef->getName())
2342           << MatchTable::LineBreak;
2343   }
2344 };
2345
2346 /// Adds a specific temporary virtual register to the instruction being built.
2347 /// This is used to chain instructions together when emitting multiple
2348 /// instructions.
2349 class TempRegRenderer : public OperandRenderer {
2350 protected:
2351   unsigned InsnID;
2352   unsigned TempRegID;
2353   bool IsDef;
2354
2355 public:
2356   TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
2357       : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2358         IsDef(IsDef) {}
2359
2360   static bool classof(const OperandRenderer *R) {
2361     return R->getKind() == OR_TempRegister;
2362   }
2363
2364   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2365     Table << MatchTable::Opcode("GIR_AddTempRegister")
2366           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2367           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2368           << MatchTable::Comment("TempRegFlags");
2369     if (IsDef)
2370       Table << MatchTable::NamedValue("RegState::Define");
2371     else
2372       Table << MatchTable::IntValue(0);
2373     Table << MatchTable::LineBreak;
2374   }
2375 };
2376
2377 /// Adds a specific immediate to the instruction being built.
2378 class ImmRenderer : public OperandRenderer {
2379 protected:
2380   unsigned InsnID;
2381   int64_t Imm;
2382
2383 public:
2384   ImmRenderer(unsigned InsnID, int64_t Imm)
2385       : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2386
2387   static bool classof(const OperandRenderer *R) {
2388     return R->getKind() == OR_Imm;
2389   }
2390
2391   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2392     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2393           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2394           << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2395   }
2396 };
2397
2398 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2399 /// matcher function.
2400 class RenderComplexPatternOperand : public OperandRenderer {
2401 private:
2402   unsigned InsnID;
2403   const Record &TheDef;
2404   /// The name of the operand.
2405   const StringRef SymbolicName;
2406   /// The renderer number. This must be unique within a rule since it's used to
2407   /// identify a temporary variable to hold the renderer function.
2408   unsigned RendererID;
2409   /// When provided, this is the suboperand of the ComplexPattern operand to
2410   /// render. Otherwise all the suboperands will be rendered.
2411   Optional<unsigned> SubOperand;
2412
2413   unsigned getNumOperands() const {
2414     return TheDef.getValueAsDag("Operands")->getNumArgs();
2415   }
2416
2417 public:
2418   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2419                               StringRef SymbolicName, unsigned RendererID,
2420                               Optional<unsigned> SubOperand = None)
2421       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2422         SymbolicName(SymbolicName), RendererID(RendererID),
2423         SubOperand(SubOperand) {}
2424
2425   static bool classof(const OperandRenderer *R) {
2426     return R->getKind() == OR_ComplexPattern;
2427   }
2428
2429   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2430     Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2431                                                       : "GIR_ComplexRenderer")
2432           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2433           << MatchTable::Comment("RendererID")
2434           << MatchTable::IntValue(RendererID);
2435     if (SubOperand.hasValue())
2436       Table << MatchTable::Comment("SubOperand")
2437             << MatchTable::IntValue(SubOperand.getValue());
2438     Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2439   }
2440 };
2441
2442 class CustomRenderer : public OperandRenderer {
2443 protected:
2444   unsigned InsnID;
2445   const Record &Renderer;
2446   /// The name of the operand.
2447   const std::string SymbolicName;
2448
2449 public:
2450   CustomRenderer(unsigned InsnID, const Record &Renderer,
2451                  StringRef SymbolicName)
2452       : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2453         SymbolicName(SymbolicName) {}
2454
2455   static bool classof(const OperandRenderer *R) {
2456     return R->getKind() == OR_Custom;
2457   }
2458
2459   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2460     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2461     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2462     Table << MatchTable::Opcode("GIR_CustomRenderer")
2463           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2464           << MatchTable::Comment("OldInsnID")
2465           << MatchTable::IntValue(OldInsnVarID)
2466           << MatchTable::Comment("Renderer")
2467           << MatchTable::NamedValue(
2468                  "GICR_" + Renderer.getValueAsString("RendererFn").str())
2469           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2470   }
2471 };
2472
2473 /// An action taken when all Matcher predicates succeeded for a parent rule.
2474 ///
2475 /// Typical actions include:
2476 /// * Changing the opcode of an instruction.
2477 /// * Adding an operand to an instruction.
2478 class MatchAction {
2479 public:
2480   virtual ~MatchAction() {}
2481
2482   /// Emit the MatchTable opcodes to implement the action.
2483   virtual void emitActionOpcodes(MatchTable &Table,
2484                                  RuleMatcher &Rule) const = 0;
2485 };
2486
2487 /// Generates a comment describing the matched rule being acted upon.
2488 class DebugCommentAction : public MatchAction {
2489 private:
2490   std::string S;
2491
2492 public:
2493   DebugCommentAction(StringRef S) : S(S) {}
2494
2495   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2496     Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2497   }
2498 };
2499
2500 /// Generates code to build an instruction or mutate an existing instruction
2501 /// into the desired instruction when this is possible.
2502 class BuildMIAction : public MatchAction {
2503 private:
2504   unsigned InsnID;
2505   const CodeGenInstruction *I;
2506   InstructionMatcher *Matched;
2507   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2508
2509   /// True if the instruction can be built solely by mutating the opcode.
2510   bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2511     if (!Insn)
2512       return false;
2513
2514     if (OperandRenderers.size() != Insn->getNumOperands())
2515       return false;
2516
2517     for (const auto &Renderer : enumerate(OperandRenderers)) {
2518       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2519         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2520         if (Insn != &OM.getInstructionMatcher() ||
2521             OM.getOpIdx() != Renderer.index())
2522           return false;
2523       } else
2524         return false;
2525     }
2526
2527     return true;
2528   }
2529
2530 public:
2531   BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2532       : InsnID(InsnID), I(I), Matched(nullptr) {}
2533
2534   unsigned getInsnID() const { return InsnID; }
2535   const CodeGenInstruction *getCGI() const { return I; }
2536
2537   void chooseInsnToMutate(RuleMatcher &Rule) {
2538     for (auto *MutateCandidate : Rule.mutatable_insns()) {
2539       if (canMutate(Rule, MutateCandidate)) {
2540         // Take the first one we're offered that we're able to mutate.
2541         Rule.reserveInsnMatcherForMutation(MutateCandidate);
2542         Matched = MutateCandidate;
2543         return;
2544       }
2545     }
2546   }
2547
2548   template <class Kind, class... Args>
2549   Kind &addRenderer(Args&&... args) {
2550     OperandRenderers.emplace_back(
2551         llvm::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2552     return *static_cast<Kind *>(OperandRenderers.back().get());
2553   }
2554
2555   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2556     if (Matched) {
2557       assert(canMutate(Rule, Matched) &&
2558              "Arranged to mutate an insn that isn't mutatable");
2559
2560       unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2561       Table << MatchTable::Opcode("GIR_MutateOpcode")
2562             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2563             << MatchTable::Comment("RecycleInsnID")
2564             << MatchTable::IntValue(RecycleInsnID)
2565             << MatchTable::Comment("Opcode")
2566             << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2567             << MatchTable::LineBreak;
2568
2569       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2570         for (auto Def : I->ImplicitDefs) {
2571           auto Namespace = Def->getValue("Namespace")
2572                                ? Def->getValueAsString("Namespace")
2573                                : "";
2574           Table << MatchTable::Opcode("GIR_AddImplicitDef")
2575                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2576                 << MatchTable::NamedValue(Namespace, Def->getName())
2577                 << MatchTable::LineBreak;
2578         }
2579         for (auto Use : I->ImplicitUses) {
2580           auto Namespace = Use->getValue("Namespace")
2581                                ? Use->getValueAsString("Namespace")
2582                                : "";
2583           Table << MatchTable::Opcode("GIR_AddImplicitUse")
2584                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2585                 << MatchTable::NamedValue(Namespace, Use->getName())
2586                 << MatchTable::LineBreak;
2587         }
2588       }
2589       return;
2590     }
2591
2592     // TODO: Simple permutation looks like it could be almost as common as
2593     //       mutation due to commutative operations.
2594
2595     Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2596           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2597           << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2598           << MatchTable::LineBreak;
2599     for (const auto &Renderer : OperandRenderers)
2600       Renderer->emitRenderOpcodes(Table, Rule);
2601
2602     if (I->mayLoad || I->mayStore) {
2603       Table << MatchTable::Opcode("GIR_MergeMemOperands")
2604             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2605             << MatchTable::Comment("MergeInsnID's");
2606       // Emit the ID's for all the instructions that are matched by this rule.
2607       // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2608       //       some other means of having a memoperand. Also limit this to
2609       //       emitted instructions that expect to have a memoperand too. For
2610       //       example, (G_SEXT (G_LOAD x)) that results in separate load and
2611       //       sign-extend instructions shouldn't put the memoperand on the
2612       //       sign-extend since it has no effect there.
2613       std::vector<unsigned> MergeInsnIDs;
2614       for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2615         MergeInsnIDs.push_back(IDMatcherPair.second);
2616       llvm::sort(MergeInsnIDs);
2617       for (const auto &MergeInsnID : MergeInsnIDs)
2618         Table << MatchTable::IntValue(MergeInsnID);
2619       Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2620             << MatchTable::LineBreak;
2621     }
2622
2623     // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2624     //        better for combines. Particularly when there are multiple match
2625     //        roots.
2626     if (InsnID == 0)
2627       Table << MatchTable::Opcode("GIR_EraseFromParent")
2628             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2629             << MatchTable::LineBreak;
2630   }
2631 };
2632
2633 /// Generates code to constrain the operands of an output instruction to the
2634 /// register classes specified by the definition of that instruction.
2635 class ConstrainOperandsToDefinitionAction : public MatchAction {
2636   unsigned InsnID;
2637
2638 public:
2639   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2640
2641   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2642     Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2643           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2644           << MatchTable::LineBreak;
2645   }
2646 };
2647
2648 /// Generates code to constrain the specified operand of an output instruction
2649 /// to the specified register class.
2650 class ConstrainOperandToRegClassAction : public MatchAction {
2651   unsigned InsnID;
2652   unsigned OpIdx;
2653   const CodeGenRegisterClass &RC;
2654
2655 public:
2656   ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2657                                    const CodeGenRegisterClass &RC)
2658       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
2659
2660   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2661     Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2662           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2663           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
2664           << MatchTable::Comment("RC " + RC.getName())
2665           << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
2666   }
2667 };
2668
2669 /// Generates code to create a temporary register which can be used to chain
2670 /// instructions together.
2671 class MakeTempRegisterAction : public MatchAction {
2672 private:
2673   LLTCodeGen Ty;
2674   unsigned TempRegID;
2675
2676 public:
2677   MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
2678       : Ty(Ty), TempRegID(TempRegID) {}
2679
2680   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2681     Table << MatchTable::Opcode("GIR_MakeTempReg")
2682           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2683           << MatchTable::Comment("TypeID")
2684           << MatchTable::NamedValue(Ty.getCxxEnumValue())
2685           << MatchTable::LineBreak;
2686   }
2687 };
2688
2689 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
2690   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
2691   MutatableInsns.insert(Matchers.back().get());
2692   return *Matchers.back();
2693 }
2694
2695 void RuleMatcher::addRequiredFeature(Record *Feature) {
2696   RequiredFeatures.push_back(Feature);
2697 }
2698
2699 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
2700   return RequiredFeatures;
2701 }
2702
2703 // Emplaces an action of the specified Kind at the end of the action list.
2704 //
2705 // Returns a reference to the newly created action.
2706 //
2707 // Like std::vector::emplace_back(), may invalidate all iterators if the new
2708 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
2709 // iterator.
2710 template <class Kind, class... Args>
2711 Kind &RuleMatcher::addAction(Args &&... args) {
2712   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
2713   return *static_cast<Kind *>(Actions.back().get());
2714 }
2715
2716 // Emplaces an action of the specified Kind before the given insertion point.
2717 //
2718 // Returns an iterator pointing at the newly created instruction.
2719 //
2720 // Like std::vector::insert(), may invalidate all iterators if the new size
2721 // exceeds the capacity. Otherwise, only invalidates the iterators from the
2722 // insertion point onwards.
2723 template <class Kind, class... Args>
2724 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
2725                                           Args &&... args) {
2726   return Actions.emplace(InsertPt,
2727                          llvm::make_unique<Kind>(std::forward<Args>(args)...));
2728 }
2729
2730 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
2731   unsigned NewInsnVarID = NextInsnVarID++;
2732   InsnVariableIDs[&Matcher] = NewInsnVarID;
2733   return NewInsnVarID;
2734 }
2735
2736 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
2737   const auto &I = InsnVariableIDs.find(&InsnMatcher);
2738   if (I != InsnVariableIDs.end())
2739     return I->second;
2740   llvm_unreachable("Matched Insn was not captured in a local variable");
2741 }
2742
2743 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
2744   if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
2745     DefinedOperands[SymbolicName] = &OM;
2746     return;
2747   }
2748
2749   // If the operand is already defined, then we must ensure both references in
2750   // the matcher have the exact same node.
2751   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
2752 }
2753
2754 InstructionMatcher &
2755 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
2756   for (const auto &I : InsnVariableIDs)
2757     if (I.first->getSymbolicName() == SymbolicName)
2758       return *I.first;
2759   llvm_unreachable(
2760       ("Failed to lookup instruction " + SymbolicName).str().c_str());
2761 }
2762
2763 const OperandMatcher &
2764 RuleMatcher::getOperandMatcher(StringRef Name) const {
2765   const auto &I = DefinedOperands.find(Name);
2766
2767   if (I == DefinedOperands.end())
2768     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
2769
2770   return *I->second;
2771 }
2772
2773 void RuleMatcher::emit(MatchTable &Table) {
2774   if (Matchers.empty())
2775     llvm_unreachable("Unexpected empty matcher!");
2776
2777   // The representation supports rules that require multiple roots such as:
2778   //    %ptr(p0) = ...
2779   //    %elt0(s32) = G_LOAD %ptr
2780   //    %1(p0) = G_ADD %ptr, 4
2781   //    %elt1(s32) = G_LOAD p0 %1
2782   // which could be usefully folded into:
2783   //    %ptr(p0) = ...
2784   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
2785   // on some targets but we don't need to make use of that yet.
2786   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
2787
2788   unsigned LabelID = Table.allocateLabelID();
2789   Table << MatchTable::Opcode("GIM_Try", +1)
2790         << MatchTable::Comment("On fail goto")
2791         << MatchTable::JumpTarget(LabelID)
2792         << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
2793         << MatchTable::LineBreak;
2794
2795   if (!RequiredFeatures.empty()) {
2796     Table << MatchTable::Opcode("GIM_CheckFeatures")
2797           << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
2798           << MatchTable::LineBreak;
2799   }
2800
2801   Matchers.front()->emitPredicateOpcodes(Table, *this);
2802
2803   // We must also check if it's safe to fold the matched instructions.
2804   if (InsnVariableIDs.size() >= 2) {
2805     // Invert the map to create stable ordering (by var names)
2806     SmallVector<unsigned, 2> InsnIDs;
2807     for (const auto &Pair : InsnVariableIDs) {
2808       // Skip the root node since it isn't moving anywhere. Everything else is
2809       // sinking to meet it.
2810       if (Pair.first == Matchers.front().get())
2811         continue;
2812
2813       InsnIDs.push_back(Pair.second);
2814     }
2815     llvm::sort(InsnIDs);
2816
2817     for (const auto &InsnID : InsnIDs) {
2818       // Reject the difficult cases until we have a more accurate check.
2819       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
2820             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2821             << MatchTable::LineBreak;
2822
2823       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
2824       //        account for unsafe cases.
2825       //
2826       //        Example:
2827       //          MI1--> %0 = ...
2828       //                 %1 = ... %0
2829       //          MI0--> %2 = ... %0
2830       //          It's not safe to erase MI1. We currently handle this by not
2831       //          erasing %0 (even when it's dead).
2832       //
2833       //        Example:
2834       //          MI1--> %0 = load volatile @a
2835       //                 %1 = load volatile @a
2836       //          MI0--> %2 = ... %0
2837       //          It's not safe to sink %0's def past %1. We currently handle
2838       //          this by rejecting all loads.
2839       //
2840       //        Example:
2841       //          MI1--> %0 = load @a
2842       //                 %1 = store @a
2843       //          MI0--> %2 = ... %0
2844       //          It's not safe to sink %0's def past %1. We currently handle
2845       //          this by rejecting all loads.
2846       //
2847       //        Example:
2848       //                   G_CONDBR %cond, @BB1
2849       //                 BB0:
2850       //          MI1-->   %0 = load @a
2851       //                   G_BR @BB1
2852       //                 BB1:
2853       //          MI0-->   %2 = ... %0
2854       //          It's not always safe to sink %0 across control flow. In this
2855       //          case it may introduce a memory fault. We currentl handle this
2856       //          by rejecting all loads.
2857     }
2858   }
2859
2860   for (const auto &PM : EpilogueMatchers)
2861     PM->emitPredicateOpcodes(Table, *this);
2862
2863   for (const auto &MA : Actions)
2864     MA->emitActionOpcodes(Table, *this);
2865
2866   if (Table.isWithCoverage())
2867     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
2868           << MatchTable::LineBreak;
2869   else
2870     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
2871           << MatchTable::LineBreak;
2872
2873   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
2874         << MatchTable::Label(LabelID);
2875   ++NumPatternEmitted;
2876 }
2877
2878 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
2879   // Rules involving more match roots have higher priority.
2880   if (Matchers.size() > B.Matchers.size())
2881     return true;
2882   if (Matchers.size() < B.Matchers.size())
2883     return false;
2884
2885   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
2886     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
2887       return true;
2888     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
2889       return false;
2890   }
2891
2892   return false;
2893 }
2894
2895 unsigned RuleMatcher::countRendererFns() const {
2896   return std::accumulate(
2897       Matchers.begin(), Matchers.end(), 0,
2898       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
2899         return A + Matcher->countRendererFns();
2900       });
2901 }
2902
2903 bool OperandPredicateMatcher::isHigherPriorityThan(
2904     const OperandPredicateMatcher &B) const {
2905   // Generally speaking, an instruction is more important than an Int or a
2906   // LiteralInt because it can cover more nodes but theres an exception to
2907   // this. G_CONSTANT's are less important than either of those two because they
2908   // are more permissive.
2909
2910   const InstructionOperandMatcher *AOM =
2911       dyn_cast<InstructionOperandMatcher>(this);
2912   const InstructionOperandMatcher *BOM =
2913       dyn_cast<InstructionOperandMatcher>(&B);
2914   bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
2915   bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
2916
2917   if (AOM && BOM) {
2918     // The relative priorities between a G_CONSTANT and any other instruction
2919     // don't actually matter but this code is needed to ensure a strict weak
2920     // ordering. This is particularly important on Windows where the rules will
2921     // be incorrectly sorted without it.
2922     if (AIsConstantInsn != BIsConstantInsn)
2923       return AIsConstantInsn < BIsConstantInsn;
2924     return false;
2925   }
2926
2927   if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
2928     return false;
2929   if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
2930     return true;
2931
2932   return Kind < B.Kind;
2933 }
2934
2935 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
2936                                               RuleMatcher &Rule) const {
2937   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
2938   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
2939   assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
2940
2941   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
2942         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2943         << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2944         << MatchTable::Comment("OtherMI")
2945         << MatchTable::IntValue(OtherInsnVarID)
2946         << MatchTable::Comment("OtherOpIdx")
2947         << MatchTable::IntValue(OtherOM.getOpIdx())
2948         << MatchTable::LineBreak;
2949 }
2950
2951 //===- GlobalISelEmitter class --------------------------------------------===//
2952
2953 class GlobalISelEmitter {
2954 public:
2955   explicit GlobalISelEmitter(RecordKeeper &RK);
2956   void run(raw_ostream &OS);
2957
2958 private:
2959   const RecordKeeper &RK;
2960   const CodeGenDAGPatterns CGP;
2961   const CodeGenTarget &Target;
2962   CodeGenRegBank CGRegs;
2963
2964   /// Keep track of the equivalence between SDNodes and Instruction by mapping
2965   /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
2966   /// check for attributes on the relation such as CheckMMOIsNonAtomic.
2967   /// This is defined using 'GINodeEquiv' in the target description.
2968   DenseMap<Record *, Record *> NodeEquivs;
2969
2970   /// Keep track of the equivalence between ComplexPattern's and
2971   /// GIComplexOperandMatcher. Map entries are specified by subclassing
2972   /// GIComplexPatternEquiv.
2973   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
2974
2975   /// Keep track of the equivalence between SDNodeXForm's and
2976   /// GICustomOperandRenderer. Map entries are specified by subclassing
2977   /// GISDNodeXFormEquiv.
2978   DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
2979
2980   /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
2981   /// This adds compatibility for RuleMatchers to use this for ordering rules.
2982   DenseMap<uint64_t, int> RuleMatcherScores;
2983
2984   // Map of predicates to their subtarget features.
2985   SubtargetFeatureInfoMap SubtargetFeatures;
2986
2987   // Rule coverage information.
2988   Optional<CodeGenCoverage> RuleCoverage;
2989
2990   void gatherOpcodeValues();
2991   void gatherTypeIDValues();
2992   void gatherNodeEquivs();
2993
2994   Record *findNodeEquiv(Record *N) const;
2995   const CodeGenInstruction *getEquivNode(Record &Equiv,
2996                                          const TreePatternNode *N) const;
2997
2998   Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
2999   Expected<InstructionMatcher &>
3000   createAndImportSelDAGMatcher(RuleMatcher &Rule,
3001                                InstructionMatcher &InsnMatcher,
3002                                const TreePatternNode *Src, unsigned &TempOpIdx);
3003   Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3004                                            unsigned &TempOpIdx) const;
3005   Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3006                            const TreePatternNode *SrcChild,
3007                            bool OperandIsAPointer, unsigned OpIdx,
3008                            unsigned &TempOpIdx);
3009
3010   Expected<BuildMIAction &>
3011   createAndImportInstructionRenderer(RuleMatcher &M,
3012                                      const TreePatternNode *Dst);
3013   Expected<action_iterator> createAndImportSubInstructionRenderer(
3014       action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3015       unsigned TempReg);
3016   Expected<action_iterator>
3017   createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3018                             const TreePatternNode *Dst);
3019   void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3020   Expected<action_iterator>
3021   importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3022                              BuildMIAction &DstMIBuilder,
3023                              const llvm::TreePatternNode *Dst);
3024   Expected<action_iterator>
3025   importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3026                             BuildMIAction &DstMIBuilder,
3027                             TreePatternNode *DstChild);
3028   Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
3029                                       DagInit *DefaultOps) const;
3030   Error
3031   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3032                              const std::vector<Record *> &ImplicitDefs) const;
3033
3034   void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3035                            StringRef TypeIdentifier, StringRef ArgType,
3036                            StringRef ArgName, StringRef AdditionalDeclarations,
3037                            std::function<bool(const Record *R)> Filter);
3038   void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3039                            StringRef ArgType,
3040                            std::function<bool(const Record *R)> Filter);
3041   void emitMIPredicateFns(raw_ostream &OS);
3042
3043   /// Analyze pattern \p P, returning a matcher for it if possible.
3044   /// Otherwise, return an Error explaining why we don't support it.
3045   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3046
3047   void declareSubtargetFeature(Record *Predicate);
3048
3049   MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3050                              bool WithCoverage);
3051
3052 public:
3053   /// Takes a sequence of \p Rules and group them based on the predicates
3054   /// they share. \p MatcherStorage is used as a memory container
3055   /// for the group that are created as part of this process.
3056   ///
3057   /// What this optimization does looks like if GroupT = GroupMatcher:
3058   /// Output without optimization:
3059   /// \verbatim
3060   /// # R1
3061   ///  # predicate A
3062   ///  # predicate B
3063   ///  ...
3064   /// # R2
3065   ///  # predicate A // <-- effectively this is going to be checked twice.
3066   ///                //     Once in R1 and once in R2.
3067   ///  # predicate C
3068   /// \endverbatim
3069   /// Output with optimization:
3070   /// \verbatim
3071   /// # Group1_2
3072   ///  # predicate A // <-- Check is now shared.
3073   ///  # R1
3074   ///   # predicate B
3075   ///  # R2
3076   ///   # predicate C
3077   /// \endverbatim
3078   template <class GroupT>
3079   static std::vector<Matcher *> optimizeRules(
3080       ArrayRef<Matcher *> Rules,
3081       std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3082 };
3083
3084 void GlobalISelEmitter::gatherOpcodeValues() {
3085   InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3086 }
3087
3088 void GlobalISelEmitter::gatherTypeIDValues() {
3089   LLTOperandMatcher::initTypeIDValuesMap();
3090 }
3091
3092 void GlobalISelEmitter::gatherNodeEquivs() {
3093   assert(NodeEquivs.empty());
3094   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3095     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3096
3097   assert(ComplexPatternEquivs.empty());
3098   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3099     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3100     if (!SelDAGEquiv)
3101       continue;
3102     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3103  }
3104
3105  assert(SDNodeXFormEquivs.empty());
3106  for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3107    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3108    if (!SelDAGEquiv)
3109      continue;
3110    SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3111  }
3112 }
3113
3114 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3115   return NodeEquivs.lookup(N);
3116 }
3117
3118 const CodeGenInstruction *
3119 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3120   for (const auto &Predicate : N->getPredicateFns()) {
3121     if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3122         Predicate.isSignExtLoad())
3123       return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3124     if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3125         Predicate.isZeroExtLoad())
3126       return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3127   }
3128   return &Target.getInstruction(Equiv.getValueAsDef("I"));
3129 }
3130
3131 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3132     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3133       CGRegs(RK, Target.getHwModes()) {}
3134
3135 //===- Emitter ------------------------------------------------------------===//
3136
3137 Error
3138 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3139                                         ArrayRef<Predicate> Predicates) {
3140   for (const Predicate &P : Predicates) {
3141     if (!P.Def)
3142       continue;
3143     declareSubtargetFeature(P.Def);
3144     M.addRequiredFeature(P.Def);
3145   }
3146
3147   return Error::success();
3148 }
3149
3150 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3151     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3152     const TreePatternNode *Src, unsigned &TempOpIdx) {
3153   Record *SrcGIEquivOrNull = nullptr;
3154   const CodeGenInstruction *SrcGIOrNull = nullptr;
3155
3156   // Start with the defined operands (i.e., the results of the root operator).
3157   if (Src->getExtTypes().size() > 1)
3158     return failedImport("Src pattern has multiple results");
3159
3160   if (Src->isLeaf()) {
3161     Init *SrcInit = Src->getLeafValue();
3162     if (isa<IntInit>(SrcInit)) {
3163       InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3164           &Target.getInstruction(RK.getDef("G_CONSTANT")));
3165     } else
3166       return failedImport(
3167           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3168   } else {
3169     SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3170     if (!SrcGIEquivOrNull)
3171       return failedImport("Pattern operator lacks an equivalent Instruction" +
3172                           explainOperator(Src->getOperator()));
3173     SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3174
3175     // The operators look good: match the opcode
3176     InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3177   }
3178
3179   unsigned OpIdx = 0;
3180   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3181     // Results don't have a name unless they are the root node. The caller will
3182     // set the name if appropriate.
3183     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3184     if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3185       return failedImport(toString(std::move(Error)) +
3186                           " for result of Src pattern operator");
3187   }
3188
3189   for (const auto &Predicate : Src->getPredicateFns()) {
3190     if (Predicate.isAlwaysTrue())
3191       continue;
3192
3193     if (Predicate.isImmediatePattern()) {
3194       InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3195       continue;
3196     }
3197
3198     // G_LOAD is used for both non-extending and any-extending loads.
3199     if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3200       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3201           0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3202       continue;
3203     }
3204     if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3205       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3206           0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3207       continue;
3208     }
3209
3210     // No check required. We already did it by swapping the opcode.
3211     if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3212         Predicate.isSignExtLoad())
3213       continue;
3214
3215     // No check required. We already did it by swapping the opcode.
3216     if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3217         Predicate.isZeroExtLoad())
3218       continue;
3219
3220     // No check required. G_STORE by itself is a non-extending store.
3221     if (Predicate.isNonTruncStore())
3222       continue;
3223
3224     if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3225       if (Predicate.getMemoryVT() != nullptr) {
3226         Optional<LLTCodeGen> MemTyOrNone =
3227             MVTToLLT(getValueType(Predicate.getMemoryVT()));
3228
3229         if (!MemTyOrNone)
3230           return failedImport("MemVT could not be converted to LLT");
3231
3232         // MMO's work in bytes so we must take care of unusual types like i1
3233         // don't round down.
3234         unsigned MemSizeInBits =
3235             llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3236
3237         InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3238             0, MemSizeInBits / 8);
3239         continue;
3240       }
3241     }
3242
3243     if (Predicate.isLoad() || Predicate.isStore()) {
3244       // No check required. A G_LOAD/G_STORE is an unindexed load.
3245       if (Predicate.isUnindexed())
3246         continue;
3247     }
3248
3249     if (Predicate.isAtomic()) {
3250       if (Predicate.isAtomicOrderingMonotonic()) {
3251         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3252             "Monotonic");
3253         continue;
3254       }
3255       if (Predicate.isAtomicOrderingAcquire()) {
3256         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3257         continue;
3258       }
3259       if (Predicate.isAtomicOrderingRelease()) {
3260         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3261         continue;
3262       }
3263       if (Predicate.isAtomicOrderingAcquireRelease()) {
3264         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3265             "AcquireRelease");
3266         continue;
3267       }
3268       if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3269         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3270             "SequentiallyConsistent");
3271         continue;
3272       }
3273
3274       if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3275         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3276             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3277         continue;
3278       }
3279       if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3280         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3281             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3282         continue;
3283       }
3284
3285       if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3286         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3287             "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3288         continue;
3289       }
3290       if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3291         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3292             "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3293         continue;
3294       }
3295     }
3296
3297     if (Predicate.hasGISelPredicateCode()) {
3298       InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3299       continue;
3300     }
3301
3302     return failedImport("Src pattern child has predicate (" +
3303                         explainPredicates(Src) + ")");
3304   }
3305   if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3306     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3307
3308   if (Src->isLeaf()) {
3309     Init *SrcInit = Src->getLeafValue();
3310     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3311       OperandMatcher &OM =
3312           InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3313       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3314     } else
3315       return failedImport(
3316           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3317   } else {
3318     assert(SrcGIOrNull &&
3319            "Expected to have already found an equivalent Instruction");
3320     if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3321         SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3322       // imm/fpimm still have operands but we don't need to do anything with it
3323       // here since we don't support ImmLeaf predicates yet. However, we still
3324       // need to note the hidden operand to get GIM_CheckNumOperands correct.
3325       InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3326       return InsnMatcher;
3327     }
3328
3329     // Match the used operands (i.e. the children of the operator).
3330     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
3331       TreePatternNode *SrcChild = Src->getChild(i);
3332
3333       // SelectionDAG allows pointers to be represented with iN since it doesn't
3334       // distinguish between pointers and integers but they are different types in GlobalISel.
3335       // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3336       bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3337
3338       // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3339       // following the defs is an intrinsic ID.
3340       if ((SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3341            SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS") &&
3342           i == 0) {
3343         if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
3344           OperandMatcher &OM =
3345               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3346           OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3347           continue;
3348         }
3349
3350         return failedImport("Expected IntInit containing instrinsic ID)");
3351       }
3352
3353       if (auto Error =
3354               importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3355                                  OpIdx++, TempOpIdx))
3356         return std::move(Error);
3357     }
3358   }
3359
3360   return InsnMatcher;
3361 }
3362
3363 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3364     OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3365   const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3366   if (ComplexPattern == ComplexPatternEquivs.end())
3367     return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3368                         ") not mapped to GlobalISel");
3369
3370   OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3371   TempOpIdx++;
3372   return Error::success();
3373 }
3374
3375 Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
3376                                             InstructionMatcher &InsnMatcher,
3377                                             const TreePatternNode *SrcChild,
3378                                             bool OperandIsAPointer,
3379                                             unsigned OpIdx,
3380                                             unsigned &TempOpIdx) {
3381   OperandMatcher &OM =
3382       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
3383   if (OM.isSameAsAnotherOperand())
3384     return Error::success();
3385
3386   ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3387   if (ChildTypes.size() != 1)
3388     return failedImport("Src pattern child has multiple results");
3389
3390   // Check MBB's before the type check since they are not a known type.
3391   if (!SrcChild->isLeaf()) {
3392     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3393       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3394       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3395         OM.addPredicate<MBBOperandMatcher>();
3396         return Error::success();
3397       }
3398     }
3399   }
3400
3401   if (auto Error =
3402           OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3403     return failedImport(toString(std::move(Error)) + " for Src operand (" +
3404                         to_string(*SrcChild) + ")");
3405
3406   // Check for nested instructions.
3407   if (!SrcChild->isLeaf()) {
3408     if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3409       // When a ComplexPattern is used as an operator, it should do the same
3410       // thing as when used as a leaf. However, the children of the operator
3411       // name the sub-operands that make up the complex operand and we must
3412       // prepare to reference them in the renderer too.
3413       unsigned RendererID = TempOpIdx;
3414       if (auto Error = importComplexPatternOperandMatcher(
3415               OM, SrcChild->getOperator(), TempOpIdx))
3416         return Error;
3417
3418       for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3419         auto *SubOperand = SrcChild->getChild(i);
3420         if (!SubOperand->getName().empty())
3421           Rule.defineComplexSubOperand(SubOperand->getName(),
3422                                        SrcChild->getOperator(), RendererID, i);
3423       }
3424
3425       return Error::success();
3426     }
3427
3428     auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3429         InsnMatcher.getRuleMatcher(), SrcChild->getName());
3430     if (!MaybeInsnOperand.hasValue()) {
3431       // This isn't strictly true. If the user were to provide exactly the same
3432       // matchers as the original operand then we could allow it. However, it's
3433       // simpler to not permit the redundant specification.
3434       return failedImport("Nested instruction cannot be the same as another operand");
3435     }
3436
3437     // Map the node to a gMIR instruction.
3438     InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3439     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3440         Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3441     if (auto Error = InsnMatcherOrError.takeError())
3442       return Error;
3443
3444     return Error::success();
3445   }
3446
3447   if (SrcChild->hasAnyPredicate())
3448     return failedImport("Src pattern child has unsupported predicate");
3449
3450   // Check for constant immediates.
3451   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3452     OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3453     return Error::success();
3454   }
3455
3456   // Check for def's like register classes or ComplexPattern's.
3457   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3458     auto *ChildRec = ChildDefInit->getDef();
3459
3460     // Check for register classes.
3461     if (ChildRec->isSubClassOf("RegisterClass") ||
3462         ChildRec->isSubClassOf("RegisterOperand")) {
3463       OM.addPredicate<RegisterBankOperandMatcher>(
3464           Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
3465       return Error::success();
3466     }
3467
3468     // Check for ValueType.
3469     if (ChildRec->isSubClassOf("ValueType")) {
3470       // We already added a type check as standard practice so this doesn't need
3471       // to do anything.
3472       return Error::success();
3473     }
3474
3475     // Check for ComplexPattern's.
3476     if (ChildRec->isSubClassOf("ComplexPattern"))
3477       return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
3478
3479     if (ChildRec->isSubClassOf("ImmLeaf")) {
3480       return failedImport(
3481           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
3482     }
3483
3484     return failedImport(
3485         "Src pattern child def is an unsupported tablegen class");
3486   }
3487
3488   return failedImport("Src pattern child is an unsupported kind");
3489 }
3490
3491 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
3492     action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
3493     TreePatternNode *DstChild) {
3494
3495   const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
3496   if (SubOperand.hasValue()) {
3497     DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3498         *std::get<0>(*SubOperand), DstChild->getName(),
3499         std::get<1>(*SubOperand), std::get<2>(*SubOperand));
3500     return InsertPt;
3501   }
3502
3503   if (!DstChild->isLeaf()) {
3504
3505     if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
3506       auto Child = DstChild->getChild(0);
3507       auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
3508       if (I != SDNodeXFormEquivs.end()) {
3509         DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
3510         return InsertPt;
3511       }
3512       return failedImport("SDNodeXForm " + Child->getName() +
3513                           " has no custom renderer");
3514     }
3515
3516     // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
3517     // inline, but in MI it's just another operand.
3518     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
3519       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
3520       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3521         DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3522         return InsertPt;
3523       }
3524     }
3525
3526     // Similarly, imm is an operator in TreePatternNode's view but must be
3527     // rendered as operands.
3528     // FIXME: The target should be able to choose sign-extended when appropriate
3529     //        (e.g. on Mips).
3530     if (DstChild->getOperator()->getName() == "imm") {
3531       DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
3532       return InsertPt;
3533     } else if (DstChild->getOperator()->getName() == "fpimm") {
3534       DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
3535           DstChild->getName());
3536       return InsertPt;
3537     }
3538
3539     if (DstChild->getOperator()->isSubClassOf("Instruction")) {
3540       ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3541       if (ChildTypes.size() != 1)
3542         return failedImport("Dst pattern child has multiple results");
3543
3544       Optional<LLTCodeGen> OpTyOrNone = None;
3545       if (ChildTypes.front().isMachineValueType())
3546         OpTyOrNone =
3547             MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3548       if (!OpTyOrNone)
3549         return failedImport("Dst operand has an unsupported type");
3550
3551       unsigned TempRegID = Rule.allocateTempRegID();
3552       InsertPt = Rule.insertAction<MakeTempRegisterAction>(
3553           InsertPt, OpTyOrNone.getValue(), TempRegID);
3554       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3555
3556       auto InsertPtOrError = createAndImportSubInstructionRenderer(
3557           ++InsertPt, Rule, DstChild, TempRegID);
3558       if (auto Error = InsertPtOrError.takeError())
3559         return std::move(Error);
3560       return InsertPtOrError.get();
3561     }
3562
3563     return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
3564   }
3565
3566   // It could be a specific immediate in which case we should just check for
3567   // that immediate.
3568   if (const IntInit *ChildIntInit =
3569           dyn_cast<IntInit>(DstChild->getLeafValue())) {
3570     DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
3571     return InsertPt;
3572   }
3573
3574   // Otherwise, we're looking for a bog-standard RegisterClass operand.
3575   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
3576     auto *ChildRec = ChildDefInit->getDef();
3577
3578     ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3579     if (ChildTypes.size() != 1)
3580       return failedImport("Dst pattern child has multiple results");
3581
3582     Optional<LLTCodeGen> OpTyOrNone = None;
3583     if (ChildTypes.front().isMachineValueType())
3584       OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3585     if (!OpTyOrNone)
3586       return failedImport("Dst operand has an unsupported type");
3587
3588     if (ChildRec->isSubClassOf("Register")) {
3589       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
3590       return InsertPt;
3591     }
3592
3593     if (ChildRec->isSubClassOf("RegisterClass") ||
3594         ChildRec->isSubClassOf("RegisterOperand") ||
3595         ChildRec->isSubClassOf("ValueType")) {
3596       if (ChildRec->isSubClassOf("RegisterOperand") &&
3597           !ChildRec->isValueUnset("GIZeroRegister")) {
3598         DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
3599             DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
3600         return InsertPt;
3601       }
3602
3603       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3604       return InsertPt;
3605     }
3606
3607     if (ChildRec->isSubClassOf("ComplexPattern")) {
3608       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
3609       if (ComplexPattern == ComplexPatternEquivs.end())
3610         return failedImport(
3611             "SelectionDAG ComplexPattern not mapped to GlobalISel");
3612
3613       const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
3614       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3615           *ComplexPattern->second, DstChild->getName(),
3616           OM.getAllocatedTemporariesBaseID());
3617       return InsertPt;
3618     }
3619
3620     return failedImport(
3621         "Dst pattern child def is an unsupported tablegen class");
3622   }
3623
3624   return failedImport("Dst pattern child is an unsupported kind");
3625 }
3626
3627 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
3628     RuleMatcher &M, const TreePatternNode *Dst) {
3629   auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
3630   if (auto Error = InsertPtOrError.takeError())
3631     return std::move(Error);
3632
3633   action_iterator InsertPt = InsertPtOrError.get();
3634   BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
3635
3636   importExplicitDefRenderers(DstMIBuilder);
3637
3638   if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
3639                        .takeError())
3640     return std::move(Error);
3641
3642   return DstMIBuilder;
3643 }
3644
3645 Expected<action_iterator>
3646 GlobalISelEmitter::createAndImportSubInstructionRenderer(
3647     const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3648     unsigned TempRegID) {
3649   auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
3650
3651   // TODO: Assert there's exactly one result.
3652
3653   if (auto Error = InsertPtOrError.takeError())
3654     return std::move(Error);
3655
3656   BuildMIAction &DstMIBuilder =
3657       *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
3658
3659   // Assign the result to TempReg.
3660   DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
3661
3662   InsertPtOrError =
3663       importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
3664   if (auto Error = InsertPtOrError.takeError())
3665     return std::move(Error);
3666
3667   M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
3668                                                       DstMIBuilder.getInsnID());
3669   return InsertPtOrError.get();
3670 }
3671
3672 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
3673     action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
3674   Record *DstOp = Dst->getOperator();
3675   if (!DstOp->isSubClassOf("Instruction")) {
3676     if (DstOp->isSubClassOf("ValueType"))
3677       return failedImport(
3678           "Pattern operator isn't an instruction (it's a ValueType)");
3679     return failedImport("Pattern operator isn't an instruction");
3680   }
3681   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
3682
3683   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
3684   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
3685   if (DstI->TheDef->getName() == "COPY_TO_REGCLASS")
3686     DstI = &Target.getInstruction(RK.getDef("COPY"));
3687   else if (DstI->TheDef->getName() == "EXTRACT_SUBREG")
3688     DstI = &Target.getInstruction(RK.getDef("COPY"));
3689   else if (DstI->TheDef->getName() == "REG_SEQUENCE")
3690     return failedImport("Unable to emit REG_SEQUENCE");
3691
3692   return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
3693                                        DstI);
3694 }
3695
3696 void GlobalISelEmitter::importExplicitDefRenderers(
3697     BuildMIAction &DstMIBuilder) {
3698   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3699   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
3700     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
3701     DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
3702   }
3703 }
3704
3705 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
3706     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
3707     const llvm::TreePatternNode *Dst) {
3708   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3709   CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
3710
3711   // EXTRACT_SUBREG needs to use a subregister COPY.
3712   if (OrigDstI->TheDef->getName() == "EXTRACT_SUBREG") {
3713     if (!Dst->getChild(0)->isLeaf())
3714       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
3715
3716     if (DefInit *SubRegInit =
3717             dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
3718       Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
3719       if (!RCDef)
3720         return failedImport("EXTRACT_SUBREG child #0 could not "
3721                             "be coerced to a register class");
3722
3723       CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
3724       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
3725
3726       const auto &SrcRCDstRCPair =
3727           RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
3728       if (SrcRCDstRCPair.hasValue()) {
3729         assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
3730         if (SrcRCDstRCPair->first != RC)
3731           return failedImport("EXTRACT_SUBREG requires an additional COPY");
3732       }
3733
3734       DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
3735                                                    SubIdx);
3736       return InsertPt;
3737     }
3738
3739     return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
3740   }
3741
3742   // Render the explicit uses.
3743   unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
3744   unsigned ExpectedDstINumUses = Dst->getNumChildren();
3745   if (OrigDstI->TheDef->getName() == "COPY_TO_REGCLASS") {
3746     DstINumUses--; // Ignore the class constraint.
3747     ExpectedDstINumUses--;
3748   }
3749
3750   unsigned Child = 0;
3751   unsigned NumDefaultOps = 0;
3752   for (unsigned I = 0; I != DstINumUses; ++I) {
3753     const CGIOperandList::OperandInfo &DstIOperand =
3754         DstI->Operands[DstI->Operands.NumDefs + I];
3755
3756     // If the operand has default values, introduce them now.
3757     // FIXME: Until we have a decent test case that dictates we should do
3758     // otherwise, we're going to assume that operands with default values cannot
3759     // be specified in the patterns. Therefore, adding them will not cause us to
3760     // end up with too many rendered operands.
3761     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
3762       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
3763       if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
3764         return std::move(Error);
3765       ++NumDefaultOps;
3766       continue;
3767     }
3768
3769     auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
3770                                                      Dst->getChild(Child));
3771     if (auto Error = InsertPtOrError.takeError())
3772       return std::move(Error);
3773     InsertPt = InsertPtOrError.get();
3774     ++Child;
3775   }
3776
3777   if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
3778     return failedImport("Expected " + llvm::to_string(DstINumUses) +
3779                         " used operands but found " +
3780                         llvm::to_string(ExpectedDstINumUses) +
3781                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
3782                         " default ones");
3783
3784   return InsertPt;
3785 }
3786
3787 Error GlobalISelEmitter::importDefaultOperandRenderers(
3788     BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
3789   for (const auto *DefaultOp : DefaultOps->getArgs()) {
3790     // Look through ValueType operators.
3791     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
3792       if (const DefInit *DefaultDagOperator =
3793               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
3794         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
3795           DefaultOp = DefaultDagOp->getArg(0);
3796       }
3797     }
3798
3799     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
3800       DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
3801       continue;
3802     }
3803
3804     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
3805       DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
3806       continue;
3807     }
3808
3809     return failedImport("Could not add default op");
3810   }
3811
3812   return Error::success();
3813 }
3814
3815 Error GlobalISelEmitter::importImplicitDefRenderers(
3816     BuildMIAction &DstMIBuilder,
3817     const std::vector<Record *> &ImplicitDefs) const {
3818   if (!ImplicitDefs.empty())
3819     return failedImport("Pattern defines a physical register");
3820   return Error::success();
3821 }
3822
3823 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
3824   // Keep track of the matchers and actions to emit.
3825   int Score = P.getPatternComplexity(CGP);
3826   RuleMatcher M(P.getSrcRecord()->getLoc());
3827   RuleMatcherScores[M.getRuleID()] = Score;
3828   M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
3829                                   "  =>  " +
3830                                   llvm::to_string(*P.getDstPattern()));
3831
3832   if (auto Error = importRulePredicates(M, P.getPredicates()))
3833     return std::move(Error);
3834
3835   // Next, analyze the pattern operators.
3836   TreePatternNode *Src = P.getSrcPattern();
3837   TreePatternNode *Dst = P.getDstPattern();
3838
3839   // If the root of either pattern isn't a simple operator, ignore it.
3840   if (auto Err = isTrivialOperatorNode(Dst))
3841     return failedImport("Dst pattern root isn't a trivial operator (" +
3842                         toString(std::move(Err)) + ")");
3843   if (auto Err = isTrivialOperatorNode(Src))
3844     return failedImport("Src pattern root isn't a trivial operator (" +
3845                         toString(std::move(Err)) + ")");
3846
3847   // The different predicates and matchers created during
3848   // addInstructionMatcher use the RuleMatcher M to set up their
3849   // instruction ID (InsnVarID) that are going to be used when
3850   // M is going to be emitted.
3851   // However, the code doing the emission still relies on the IDs
3852   // returned during that process by the RuleMatcher when issuing
3853   // the recordInsn opcodes.
3854   // Because of that:
3855   // 1. The order in which we created the predicates
3856   //    and such must be the same as the order in which we emit them,
3857   //    and
3858   // 2. We need to reset the generation of the IDs in M somewhere between
3859   //    addInstructionMatcher and emit
3860   //
3861   // FIXME: Long term, we don't want to have to rely on this implicit
3862   // naming being the same. One possible solution would be to have
3863   // explicit operator for operation capture and reference those.
3864   // The plus side is that it would expose opportunities to share
3865   // the capture accross rules. The downside is that it would
3866   // introduce a dependency between predicates (captures must happen
3867   // before their first use.)
3868   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
3869   unsigned TempOpIdx = 0;
3870   auto InsnMatcherOrError =
3871       createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
3872   if (auto Error = InsnMatcherOrError.takeError())
3873     return std::move(Error);
3874   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
3875
3876   if (Dst->isLeaf()) {
3877     Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
3878
3879     const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
3880     if (RCDef) {
3881       // We need to replace the def and all its uses with the specified
3882       // operand. However, we must also insert COPY's wherever needed.
3883       // For now, emit a copy and let the register allocator clean up.
3884       auto &DstI = Target.getInstruction(RK.getDef("COPY"));
3885       const auto &DstIOperand = DstI.Operands[0];
3886
3887       OperandMatcher &OM0 = InsnMatcher.getOperand(0);
3888       OM0.setSymbolicName(DstIOperand.Name);
3889       M.defineOperand(OM0.getSymbolicName(), OM0);
3890       OM0.addPredicate<RegisterBankOperandMatcher>(RC);
3891
3892       auto &DstMIBuilder =
3893           M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
3894       DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
3895       DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
3896       M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
3897
3898       // We're done with this pattern!  It's eligible for GISel emission; return
3899       // it.
3900       ++NumPatternImported;
3901       return std::move(M);
3902     }
3903
3904     return failedImport("Dst pattern root isn't a known leaf");
3905   }
3906
3907   // Start with the defined operands (i.e., the results of the root operator).
3908   Record *DstOp = Dst->getOperator();
3909   if (!DstOp->isSubClassOf("Instruction"))
3910     return failedImport("Pattern operator isn't an instruction");
3911
3912   auto &DstI = Target.getInstruction(DstOp);
3913   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
3914     return failedImport("Src pattern results and dst MI defs are different (" +
3915                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
3916                         to_string(DstI.Operands.NumDefs) + " def(s))");
3917
3918   // The root of the match also has constraints on the register bank so that it
3919   // matches the result instruction.
3920   unsigned OpIdx = 0;
3921   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3922     (void)VTy;
3923
3924     const auto &DstIOperand = DstI.Operands[OpIdx];
3925     Record *DstIOpRec = DstIOperand.Rec;
3926     if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
3927       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
3928
3929       if (DstIOpRec == nullptr)
3930         return failedImport(
3931             "COPY_TO_REGCLASS operand #1 isn't a register class");
3932     } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
3933       if (!Dst->getChild(0)->isLeaf())
3934         return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
3935
3936       // We can assume that a subregister is in the same bank as it's super
3937       // register.
3938       DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
3939
3940       if (DstIOpRec == nullptr)
3941         return failedImport(
3942             "EXTRACT_SUBREG operand #0 isn't a register class");
3943     } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
3944       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
3945     else if (!DstIOpRec->isSubClassOf("RegisterClass"))
3946       return failedImport("Dst MI def isn't a register class" +
3947                           to_string(*Dst));
3948
3949     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
3950     OM.setSymbolicName(DstIOperand.Name);
3951     M.defineOperand(OM.getSymbolicName(), OM);
3952     OM.addPredicate<RegisterBankOperandMatcher>(
3953         Target.getRegisterClass(DstIOpRec));
3954     ++OpIdx;
3955   }
3956
3957   auto DstMIBuilderOrError = createAndImportInstructionRenderer(M, Dst);
3958   if (auto Error = DstMIBuilderOrError.takeError())
3959     return std::move(Error);
3960   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
3961
3962   // Render the implicit defs.
3963   // These are only added to the root of the result.
3964   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
3965     return std::move(Error);
3966
3967   DstMIBuilder.chooseInsnToMutate(M);
3968
3969   // Constrain the registers to classes. This is normally derived from the
3970   // emitted instruction but a few instructions require special handling.
3971   if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
3972     // COPY_TO_REGCLASS does not provide operand constraints itself but the
3973     // result is constrained to the class given by the second child.
3974     Record *DstIOpRec =
3975         getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
3976
3977     if (DstIOpRec == nullptr)
3978       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
3979
3980     M.addAction<ConstrainOperandToRegClassAction>(
3981         0, 0, Target.getRegisterClass(DstIOpRec));
3982
3983     // We're done with this pattern!  It's eligible for GISel emission; return
3984     // it.
3985     ++NumPatternImported;
3986     return std::move(M);
3987   }
3988
3989   if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
3990     // EXTRACT_SUBREG selects into a subregister COPY but unlike most
3991     // instructions, the result register class is controlled by the
3992     // subregisters of the operand. As a result, we must constrain the result
3993     // class rather than check that it's already the right one.
3994     if (!Dst->getChild(0)->isLeaf())
3995       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
3996
3997     DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
3998     if (!SubRegInit)
3999       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4000
4001     // Constrain the result to the same register bank as the operand.
4002     Record *DstIOpRec =
4003         getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4004
4005     if (DstIOpRec == nullptr)
4006       return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
4007
4008     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4009     CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
4010
4011     // It would be nice to leave this constraint implicit but we're required
4012     // to pick a register class so constrain the result to a register class
4013     // that can hold the correct MVT.
4014     //
4015     // FIXME: This may introduce an extra copy if the chosen class doesn't
4016     //        actually contain the subregisters.
4017     assert(Src->getExtTypes().size() == 1 &&
4018              "Expected Src of EXTRACT_SUBREG to have one result type");
4019
4020     const auto &SrcRCDstRCPair =
4021         SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4022     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4023     M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4024     M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4025
4026     // We're done with this pattern!  It's eligible for GISel emission; return
4027     // it.
4028     ++NumPatternImported;
4029     return std::move(M);
4030   }
4031
4032   M.addAction<ConstrainOperandsToDefinitionAction>(0);
4033
4034   // We're done with this pattern!  It's eligible for GISel emission; return it.
4035   ++NumPatternImported;
4036   return std::move(M);
4037 }
4038
4039 // Emit imm predicate table and an enum to reference them with.
4040 // The 'Predicate_' part of the name is redundant but eliminating it is more
4041 // trouble than it's worth.
4042 void GlobalISelEmitter::emitCxxPredicateFns(
4043     raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
4044     StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
4045     std::function<bool(const Record *R)> Filter) {
4046   std::vector<const Record *> MatchedRecords;
4047   const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
4048   std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
4049                [&](Record *Record) {
4050                  return !Record->getValueAsString(CodeFieldName).empty() &&
4051                         Filter(Record);
4052                });
4053
4054   if (!MatchedRecords.empty()) {
4055     OS << "// PatFrag predicates.\n"
4056        << "enum {\n";
4057     std::string EnumeratorSeparator =
4058         (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
4059     for (const auto *Record : MatchedRecords) {
4060       OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
4061          << EnumeratorSeparator;
4062       EnumeratorSeparator = ",\n";
4063     }
4064     OS << "};\n";
4065   }
4066
4067   OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
4068      << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
4069      << ArgName << ") const {\n"
4070      << AdditionalDeclarations;
4071   if (!AdditionalDeclarations.empty())
4072     OS << "\n";
4073   if (!MatchedRecords.empty())
4074     OS << "  switch (PredicateID) {\n";
4075   for (const auto *Record : MatchedRecords) {
4076     OS << "  case GIPFP_" << TypeIdentifier << "_Predicate_"
4077        << Record->getName() << ": {\n"
4078        << "    " << Record->getValueAsString(CodeFieldName) << "\n"
4079        << "    llvm_unreachable(\"" << CodeFieldName
4080        << " should have returned\");\n"
4081        << "    return false;\n"
4082        << "  }\n";
4083   }
4084   if (!MatchedRecords.empty())
4085     OS << "  }\n";
4086   OS << "  llvm_unreachable(\"Unknown predicate\");\n"
4087      << "  return false;\n"
4088      << "}\n";
4089 }
4090
4091 void GlobalISelEmitter::emitImmPredicateFns(
4092     raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
4093     std::function<bool(const Record *R)> Filter) {
4094   return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
4095                              "Imm", "", Filter);
4096 }
4097
4098 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
4099   return emitCxxPredicateFns(
4100       OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
4101       "  const MachineFunction &MF = *MI.getParent()->getParent();\n"
4102       "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4103       "  (void)MRI;",
4104       [](const Record *R) { return true; });
4105 }
4106
4107 template <class GroupT>
4108 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
4109     ArrayRef<Matcher *> Rules,
4110     std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
4111
4112   std::vector<Matcher *> OptRules;
4113   std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>();
4114   assert(CurrentGroup->empty() && "Newly created group isn't empty!");
4115   unsigned NumGroups = 0;
4116
4117   auto ProcessCurrentGroup = [&]() {
4118     if (CurrentGroup->empty())
4119       // An empty group is good to be reused:
4120       return;
4121
4122     // If the group isn't large enough to provide any benefit, move all the
4123     // added rules out of it and make sure to re-create the group to properly
4124     // re-initialize it:
4125     if (CurrentGroup->size() < 2)
4126       for (Matcher *M : CurrentGroup->matchers())
4127         OptRules.push_back(M);
4128     else {
4129       CurrentGroup->finalize();
4130       OptRules.push_back(CurrentGroup.get());
4131       MatcherStorage.emplace_back(std::move(CurrentGroup));
4132       ++NumGroups;
4133     }
4134     CurrentGroup = make_unique<GroupT>();
4135   };
4136   for (Matcher *Rule : Rules) {
4137     // Greedily add as many matchers as possible to the current group:
4138     if (CurrentGroup->addMatcher(*Rule))
4139       continue;
4140
4141     ProcessCurrentGroup();
4142     assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
4143
4144     // Try to add the pending matcher to a newly created empty group:
4145     if (!CurrentGroup->addMatcher(*Rule))
4146       // If we couldn't add the matcher to an empty group, that group type
4147       // doesn't support that kind of matchers at all, so just skip it:
4148       OptRules.push_back(Rule);
4149   }
4150   ProcessCurrentGroup();
4151
4152   LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
4153   assert(CurrentGroup->empty() && "The last group wasn't properly processed");
4154   return OptRules;
4155 }
4156
4157 MatchTable
4158 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
4159                                    bool Optimize, bool WithCoverage) {
4160   std::vector<Matcher *> InputRules;
4161   for (Matcher &Rule : Rules)
4162     InputRules.push_back(&Rule);
4163
4164   if (!Optimize)
4165     return MatchTable::buildTable(InputRules, WithCoverage);
4166
4167   unsigned CurrentOrdering = 0;
4168   StringMap<unsigned> OpcodeOrder;
4169   for (RuleMatcher &Rule : Rules) {
4170     const StringRef Opcode = Rule.getOpcode();
4171     assert(!Opcode.empty() && "Didn't expect an undefined opcode");
4172     if (OpcodeOrder.count(Opcode) == 0)
4173       OpcodeOrder[Opcode] = CurrentOrdering++;
4174   }
4175
4176   std::stable_sort(InputRules.begin(), InputRules.end(),
4177                    [&OpcodeOrder](const Matcher *A, const Matcher *B) {
4178                      auto *L = static_cast<const RuleMatcher *>(A);
4179                      auto *R = static_cast<const RuleMatcher *>(B);
4180                      return std::make_tuple(OpcodeOrder[L->getOpcode()],
4181                                             L->getNumOperands()) <
4182                             std::make_tuple(OpcodeOrder[R->getOpcode()],
4183                                             R->getNumOperands());
4184                    });
4185
4186   for (Matcher *Rule : InputRules)
4187     Rule->optimize();
4188
4189   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
4190   std::vector<Matcher *> OptRules =
4191       optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
4192
4193   for (Matcher *Rule : OptRules)
4194     Rule->optimize();
4195
4196   OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
4197
4198   return MatchTable::buildTable(OptRules, WithCoverage);
4199 }
4200
4201 void GroupMatcher::optimize() {
4202   // Make sure we only sort by a specific predicate within a range of rules that
4203   // all have that predicate checked against a specific value (not a wildcard):
4204   auto F = Matchers.begin();
4205   auto T = F;
4206   auto E = Matchers.end();
4207   while (T != E) {
4208     while (T != E) {
4209       auto *R = static_cast<RuleMatcher *>(*T);
4210       if (!R->getFirstConditionAsRootType().get().isValid())
4211         break;
4212       ++T;
4213     }
4214     std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
4215       auto *L = static_cast<RuleMatcher *>(A);
4216       auto *R = static_cast<RuleMatcher *>(B);
4217       return L->getFirstConditionAsRootType() <
4218              R->getFirstConditionAsRootType();
4219     });
4220     if (T != E)
4221       F = ++T;
4222   }
4223   GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
4224       .swap(Matchers);
4225   GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
4226       .swap(Matchers);
4227 }
4228
4229 void GlobalISelEmitter::run(raw_ostream &OS) {
4230   if (!UseCoverageFile.empty()) {
4231     RuleCoverage = CodeGenCoverage();
4232     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
4233     if (!RuleCoverageBufOrErr) {
4234       PrintWarning(SMLoc(), "Missing rule coverage data");
4235       RuleCoverage = None;
4236     } else {
4237       if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
4238         PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
4239         RuleCoverage = None;
4240       }
4241     }
4242   }
4243
4244   // Track the run-time opcode values
4245   gatherOpcodeValues();
4246   // Track the run-time LLT ID values
4247   gatherTypeIDValues();
4248
4249   // Track the GINodeEquiv definitions.
4250   gatherNodeEquivs();
4251
4252   emitSourceFileHeader(("Global Instruction Selector for the " +
4253                        Target.getName() + " target").str(), OS);
4254   std::vector<RuleMatcher> Rules;
4255   // Look through the SelectionDAG patterns we found, possibly emitting some.
4256   for (const PatternToMatch &Pat : CGP.ptms()) {
4257     ++NumPatternTotal;
4258
4259     auto MatcherOrErr = runOnPattern(Pat);
4260
4261     // The pattern analysis can fail, indicating an unsupported pattern.
4262     // Report that if we've been asked to do so.
4263     if (auto Err = MatcherOrErr.takeError()) {
4264       if (WarnOnSkippedPatterns) {
4265         PrintWarning(Pat.getSrcRecord()->getLoc(),
4266                      "Skipped pattern: " + toString(std::move(Err)));
4267       } else {
4268         consumeError(std::move(Err));
4269       }
4270       ++NumPatternImportsSkipped;
4271       continue;
4272     }
4273
4274     if (RuleCoverage) {
4275       if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
4276         ++NumPatternsTested;
4277       else
4278         PrintWarning(Pat.getSrcRecord()->getLoc(),
4279                      "Pattern is not covered by a test");
4280     }
4281     Rules.push_back(std::move(MatcherOrErr.get()));
4282   }
4283
4284   // Comparison function to order records by name.
4285   auto orderByName = [](const Record *A, const Record *B) {
4286     return A->getName() < B->getName();
4287   };
4288
4289   std::vector<Record *> ComplexPredicates =
4290       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
4291   llvm::sort(ComplexPredicates, orderByName);
4292
4293   std::vector<Record *> CustomRendererFns =
4294       RK.getAllDerivedDefinitions("GICustomOperandRenderer");
4295   llvm::sort(CustomRendererFns, orderByName);
4296
4297   unsigned MaxTemporaries = 0;
4298   for (const auto &Rule : Rules)
4299     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
4300
4301   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
4302      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
4303      << ";\n"
4304      << "using PredicateBitset = "
4305         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
4306      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
4307
4308   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
4309      << "  mutable MatcherState State;\n"
4310      << "  typedef "
4311         "ComplexRendererFns("
4312      << Target.getName()
4313      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
4314
4315      << "  typedef void(" << Target.getName()
4316      << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
4317         "MachineInstr&) "
4318         "const;\n"
4319      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
4320         "CustomRendererFn> "
4321         "ISelInfo;\n";
4322   OS << "  static " << Target.getName()
4323      << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
4324      << "  static " << Target.getName()
4325      << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
4326      << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
4327         "override;\n"
4328      << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
4329         "const override;\n"
4330      << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
4331         "&Imm) const override;\n"
4332      << "  const int64_t *getMatchTable() const override;\n"
4333      << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
4334         "const override;\n"
4335      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
4336
4337   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
4338      << ", State(" << MaxTemporaries << "),\n"
4339      << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
4340      << ", ComplexPredicateFns, CustomRenderers)\n"
4341      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
4342
4343   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
4344   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
4345                                                            OS);
4346
4347   // Separate subtarget features by how often they must be recomputed.
4348   SubtargetFeatureInfoMap ModuleFeatures;
4349   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4350                std::inserter(ModuleFeatures, ModuleFeatures.end()),
4351                [](const SubtargetFeatureInfoMap::value_type &X) {
4352                  return !X.second.mustRecomputePerFunction();
4353                });
4354   SubtargetFeatureInfoMap FunctionFeatures;
4355   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4356                std::inserter(FunctionFeatures, FunctionFeatures.end()),
4357                [](const SubtargetFeatureInfoMap::value_type &X) {
4358                  return X.second.mustRecomputePerFunction();
4359                });
4360
4361   SubtargetFeatureInfo::emitComputeAvailableFeatures(
4362       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
4363       ModuleFeatures, OS);
4364   SubtargetFeatureInfo::emitComputeAvailableFeatures(
4365       Target.getName(), "InstructionSelector",
4366       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
4367       "const MachineFunction *MF");
4368
4369   // Emit a table containing the LLT objects needed by the matcher and an enum
4370   // for the matcher to reference them with.
4371   std::vector<LLTCodeGen> TypeObjects;
4372   for (const auto &Ty : KnownTypes)
4373     TypeObjects.push_back(Ty);
4374   llvm::sort(TypeObjects);
4375   OS << "// LLT Objects.\n"
4376      << "enum {\n";
4377   for (const auto &TypeObject : TypeObjects) {
4378     OS << "  ";
4379     TypeObject.emitCxxEnumValue(OS);
4380     OS << ",\n";
4381   }
4382   OS << "};\n";
4383   OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
4384      << "const static LLT TypeObjects[] = {\n";
4385   for (const auto &TypeObject : TypeObjects) {
4386     OS << "  ";
4387     TypeObject.emitCxxConstructorCall(OS);
4388     OS << ",\n";
4389   }
4390   OS << "};\n\n";
4391
4392   // Emit a table containing the PredicateBitsets objects needed by the matcher
4393   // and an enum for the matcher to reference them with.
4394   std::vector<std::vector<Record *>> FeatureBitsets;
4395   for (auto &Rule : Rules)
4396     FeatureBitsets.push_back(Rule.getRequiredFeatures());
4397   llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
4398                                  const std::vector<Record *> &B) {
4399     if (A.size() < B.size())
4400       return true;
4401     if (A.size() > B.size())
4402       return false;
4403     for (const auto &Pair : zip(A, B)) {
4404       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
4405         return true;
4406       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
4407         return false;
4408     }
4409     return false;
4410   });
4411   FeatureBitsets.erase(
4412       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
4413       FeatureBitsets.end());
4414   OS << "// Feature bitsets.\n"
4415      << "enum {\n"
4416      << "  GIFBS_Invalid,\n";
4417   for (const auto &FeatureBitset : FeatureBitsets) {
4418     if (FeatureBitset.empty())
4419       continue;
4420     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
4421   }
4422   OS << "};\n"
4423      << "const static PredicateBitset FeatureBitsets[] {\n"
4424      << "  {}, // GIFBS_Invalid\n";
4425   for (const auto &FeatureBitset : FeatureBitsets) {
4426     if (FeatureBitset.empty())
4427       continue;
4428     OS << "  {";
4429     for (const auto &Feature : FeatureBitset) {
4430       const auto &I = SubtargetFeatures.find(Feature);
4431       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
4432       OS << I->second.getEnumBitName() << ", ";
4433     }
4434     OS << "},\n";
4435   }
4436   OS << "};\n\n";
4437
4438   // Emit complex predicate table and an enum to reference them with.
4439   OS << "// ComplexPattern predicates.\n"
4440      << "enum {\n"
4441      << "  GICP_Invalid,\n";
4442   for (const auto &Record : ComplexPredicates)
4443     OS << "  GICP_" << Record->getName() << ",\n";
4444   OS << "};\n"
4445      << "// See constructor for table contents\n\n";
4446
4447   emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
4448     bool Unset;
4449     return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
4450            !R->getValueAsBit("IsAPInt");
4451   });
4452   emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
4453     bool Unset;
4454     return R->getValueAsBitOrUnset("IsAPFloat", Unset);
4455   });
4456   emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
4457     return R->getValueAsBit("IsAPInt");
4458   });
4459   emitMIPredicateFns(OS);
4460   OS << "\n";
4461
4462   OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
4463      << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
4464      << "  nullptr, // GICP_Invalid\n";
4465   for (const auto &Record : ComplexPredicates)
4466     OS << "  &" << Target.getName()
4467        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
4468        << ", // " << Record->getName() << "\n";
4469   OS << "};\n\n";
4470
4471   OS << "// Custom renderers.\n"
4472      << "enum {\n"
4473      << "  GICR_Invalid,\n";
4474   for (const auto &Record : CustomRendererFns)
4475     OS << "  GICR_" << Record->getValueAsString("RendererFn") << ", \n";
4476   OS << "};\n";
4477
4478   OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
4479      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
4480      << "  nullptr, // GICP_Invalid\n";
4481   for (const auto &Record : CustomRendererFns)
4482     OS << "  &" << Target.getName()
4483        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
4484        << ", // " << Record->getName() << "\n";
4485   OS << "};\n\n";
4486
4487   std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
4488                                                    const RuleMatcher &B) {
4489     int ScoreA = RuleMatcherScores[A.getRuleID()];
4490     int ScoreB = RuleMatcherScores[B.getRuleID()];
4491     if (ScoreA > ScoreB)
4492       return true;
4493     if (ScoreB > ScoreA)
4494       return false;
4495     if (A.isHigherPriorityThan(B)) {
4496       assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
4497                                            "and less important at "
4498                                            "the same time");
4499       return true;
4500     }
4501     return false;
4502   });
4503
4504   OS << "bool " << Target.getName()
4505      << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
4506         "&CoverageInfo) const {\n"
4507      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
4508      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4509      << "  // FIXME: This should be computed on a per-function basis rather "
4510         "than per-insn.\n"
4511      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
4512         "&MF);\n"
4513      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
4514      << "  NewMIVector OutMIs;\n"
4515      << "  State.MIs.clear();\n"
4516      << "  State.MIs.push_back(&I);\n\n"
4517      << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
4518      << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
4519      << ", CoverageInfo)) {\n"
4520      << "    return true;\n"
4521      << "  }\n\n"
4522      << "  return false;\n"
4523      << "}\n\n";
4524
4525   const MatchTable Table =
4526       buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
4527   OS << "const int64_t *" << Target.getName()
4528      << "InstructionSelector::getMatchTable() const {\n";
4529   Table.emitDeclaration(OS);
4530   OS << "  return ";
4531   Table.emitUse(OS);
4532   OS << ";\n}\n";
4533   OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
4534
4535   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
4536      << "PredicateBitset AvailableModuleFeatures;\n"
4537      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
4538      << "PredicateBitset getAvailableFeatures() const {\n"
4539      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
4540      << "}\n"
4541      << "PredicateBitset\n"
4542      << "computeAvailableModuleFeatures(const " << Target.getName()
4543      << "Subtarget *Subtarget) const;\n"
4544      << "PredicateBitset\n"
4545      << "computeAvailableFunctionFeatures(const " << Target.getName()
4546      << "Subtarget *Subtarget,\n"
4547      << "                                 const MachineFunction *MF) const;\n"
4548      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
4549
4550   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
4551      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
4552      << "AvailableFunctionFeatures()\n"
4553      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
4554 }
4555
4556 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
4557   if (SubtargetFeatures.count(Predicate) == 0)
4558     SubtargetFeatures.emplace(
4559         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
4560 }
4561
4562 void RuleMatcher::optimize() {
4563   for (auto &Item : InsnVariableIDs) {
4564     InstructionMatcher &InsnMatcher = *Item.first;
4565     for (auto &OM : InsnMatcher.operands()) {
4566       // Complex Patterns are usually expensive and they relatively rarely fail
4567       // on their own: more often we end up throwing away all the work done by a
4568       // matching part of a complex pattern because some other part of the
4569       // enclosing pattern didn't match. All of this makes it beneficial to
4570       // delay complex patterns until the very end of the rule matching,
4571       // especially for targets having lots of complex patterns.
4572       for (auto &OP : OM->predicates())
4573         if (isa<ComplexPatternOperandMatcher>(OP))
4574           EpilogueMatchers.emplace_back(std::move(OP));
4575       OM->eraseNullPredicates();
4576     }
4577     InsnMatcher.optimize();
4578   }
4579   llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
4580                                   const std::unique_ptr<PredicateMatcher> &R) {
4581     return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
4582            std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
4583   });
4584 }
4585
4586 bool RuleMatcher::hasFirstCondition() const {
4587   if (insnmatchers_empty())
4588     return false;
4589   InstructionMatcher &Matcher = insnmatchers_front();
4590   if (!Matcher.predicates_empty())
4591     return true;
4592   for (auto &OM : Matcher.operands())
4593     for (auto &OP : OM->predicates())
4594       if (!isa<InstructionOperandMatcher>(OP))
4595         return true;
4596   return false;
4597 }
4598
4599 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
4600   assert(!insnmatchers_empty() &&
4601          "Trying to get a condition from an empty RuleMatcher");
4602
4603   InstructionMatcher &Matcher = insnmatchers_front();
4604   if (!Matcher.predicates_empty())
4605     return **Matcher.predicates_begin();
4606   // If there is no more predicate on the instruction itself, look at its
4607   // operands.
4608   for (auto &OM : Matcher.operands())
4609     for (auto &OP : OM->predicates())
4610       if (!isa<InstructionOperandMatcher>(OP))
4611         return *OP;
4612
4613   llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
4614                    "no conditions");
4615 }
4616
4617 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
4618   assert(!insnmatchers_empty() &&
4619          "Trying to pop a condition from an empty RuleMatcher");
4620
4621   InstructionMatcher &Matcher = insnmatchers_front();
4622   if (!Matcher.predicates_empty())
4623     return Matcher.predicates_pop_front();
4624   // If there is no more predicate on the instruction itself, look at its
4625   // operands.
4626   for (auto &OM : Matcher.operands())
4627     for (auto &OP : OM->predicates())
4628       if (!isa<InstructionOperandMatcher>(OP)) {
4629         std::unique_ptr<PredicateMatcher> Result = std::move(OP);
4630         OM->eraseNullPredicates();
4631         return Result;
4632       }
4633
4634   llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
4635                    "no conditions");
4636 }
4637
4638 bool GroupMatcher::candidateConditionMatches(
4639     const PredicateMatcher &Predicate) const {
4640
4641   if (empty()) {
4642     // Sharing predicates for nested instructions is not supported yet as we
4643     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4644     // only work on the original root instruction (InsnVarID == 0):
4645     if (Predicate.getInsnVarID() != 0)
4646       return false;
4647     // ... otherwise an empty group can handle any predicate with no specific
4648     // requirements:
4649     return true;
4650   }
4651
4652   const Matcher &Representative = **Matchers.begin();
4653   const auto &RepresentativeCondition = Representative.getFirstCondition();
4654   // ... if not empty, the group can only accomodate matchers with the exact
4655   // same first condition:
4656   return Predicate.isIdentical(RepresentativeCondition);
4657 }
4658
4659 bool GroupMatcher::addMatcher(Matcher &Candidate) {
4660   if (!Candidate.hasFirstCondition())
4661     return false;
4662
4663   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4664   if (!candidateConditionMatches(Predicate))
4665     return false;
4666
4667   Matchers.push_back(&Candidate);
4668   return true;
4669 }
4670
4671 void GroupMatcher::finalize() {
4672   assert(Conditions.empty() && "Already finalized?");
4673   if (empty())
4674     return;
4675
4676   Matcher &FirstRule = **Matchers.begin();
4677   for (;;) {
4678     // All the checks are expected to succeed during the first iteration:
4679     for (const auto &Rule : Matchers)
4680       if (!Rule->hasFirstCondition())
4681         return;
4682     const auto &FirstCondition = FirstRule.getFirstCondition();
4683     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4684       if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
4685         return;
4686
4687     Conditions.push_back(FirstRule.popFirstCondition());
4688     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4689       Matchers[I]->popFirstCondition();
4690   }
4691 }
4692
4693 void GroupMatcher::emit(MatchTable &Table) {
4694   unsigned LabelID = ~0U;
4695   if (!Conditions.empty()) {
4696     LabelID = Table.allocateLabelID();
4697     Table << MatchTable::Opcode("GIM_Try", +1)
4698           << MatchTable::Comment("On fail goto")
4699           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
4700   }
4701   for (auto &Condition : Conditions)
4702     Condition->emitPredicateOpcodes(
4703         Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
4704
4705   for (const auto &M : Matchers)
4706     M->emit(Table);
4707
4708   // Exit the group
4709   if (!Conditions.empty())
4710     Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
4711           << MatchTable::Label(LabelID);
4712 }
4713
4714 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
4715   return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
4716 }
4717
4718 bool SwitchMatcher::candidateConditionMatches(
4719     const PredicateMatcher &Predicate) const {
4720
4721   if (empty()) {
4722     // Sharing predicates for nested instructions is not supported yet as we
4723     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4724     // only work on the original root instruction (InsnVarID == 0):
4725     if (Predicate.getInsnVarID() != 0)
4726       return false;
4727     // ... while an attempt to add even a root matcher to an empty SwitchMatcher
4728     // could fail as not all the types of conditions are supported:
4729     if (!isSupportedPredicateType(Predicate))
4730       return false;
4731     // ... or the condition might not have a proper implementation of
4732     // getValue() / isIdenticalDownToValue() yet:
4733     if (!Predicate.hasValue())
4734       return false;
4735     // ... otherwise an empty Switch can accomodate the condition with no
4736     // further requirements:
4737     return true;
4738   }
4739
4740   const Matcher &CaseRepresentative = **Matchers.begin();
4741   const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
4742   // Switch-cases must share the same kind of condition and path to the value it
4743   // checks:
4744   if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
4745     return false;
4746
4747   const auto Value = Predicate.getValue();
4748   // ... but be unique with respect to the actual value they check:
4749   return Values.count(Value) == 0;
4750 }
4751
4752 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
4753   if (!Candidate.hasFirstCondition())
4754     return false;
4755
4756   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4757   if (!candidateConditionMatches(Predicate))
4758     return false;
4759   const auto Value = Predicate.getValue();
4760   Values.insert(Value);
4761
4762   Matchers.push_back(&Candidate);
4763   return true;
4764 }
4765
4766 void SwitchMatcher::finalize() {
4767   assert(Condition == nullptr && "Already finalized");
4768   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4769   if (empty())
4770     return;
4771
4772   std::stable_sort(Matchers.begin(), Matchers.end(),
4773                    [](const Matcher *L, const Matcher *R) {
4774                      return L->getFirstCondition().getValue() <
4775                             R->getFirstCondition().getValue();
4776                    });
4777   Condition = Matchers[0]->popFirstCondition();
4778   for (unsigned I = 1, E = Values.size(); I < E; ++I)
4779     Matchers[I]->popFirstCondition();
4780 }
4781
4782 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
4783                                                  MatchTable &Table) {
4784   assert(isSupportedPredicateType(P) && "Predicate type is not supported");
4785
4786   if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
4787     Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
4788           << MatchTable::IntValue(Condition->getInsnVarID());
4789     return;
4790   }
4791   if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
4792     Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
4793           << MatchTable::IntValue(Condition->getInsnVarID())
4794           << MatchTable::Comment("Op")
4795           << MatchTable::IntValue(Condition->getOpIdx());
4796     return;
4797   }
4798
4799   llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
4800                    "predicate type that is claimed to be supported");
4801 }
4802
4803 void SwitchMatcher::emit(MatchTable &Table) {
4804   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4805   if (empty())
4806     return;
4807   assert(Condition != nullptr &&
4808          "Broken SwitchMatcher, hasn't been finalized?");
4809
4810   std::vector<unsigned> LabelIDs(Values.size());
4811   std::generate(LabelIDs.begin(), LabelIDs.end(),
4812                 [&Table]() { return Table.allocateLabelID(); });
4813   const unsigned Default = Table.allocateLabelID();
4814
4815   const int64_t LowerBound = Values.begin()->getRawValue();
4816   const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
4817
4818   emitPredicateSpecificOpcodes(*Condition, Table);
4819
4820   Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
4821         << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
4822         << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
4823
4824   int64_t J = LowerBound;
4825   auto VI = Values.begin();
4826   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4827     auto V = *VI++;
4828     while (J++ < V.getRawValue())
4829       Table << MatchTable::IntValue(0);
4830     V.turnIntoComment();
4831     Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
4832   }
4833   Table << MatchTable::LineBreak;
4834
4835   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4836     Table << MatchTable::Label(LabelIDs[I]);
4837     Matchers[I]->emit(Table);
4838     Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
4839   }
4840   Table << MatchTable::Label(Default);
4841 }
4842
4843 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
4844
4845 } // end anonymous namespace
4846
4847 //===----------------------------------------------------------------------===//
4848
4849 namespace llvm {
4850 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
4851   GlobalISelEmitter(RK).run(OS);
4852 }
4853 } // End llvm namespace