contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

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