contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

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