utils/TableGen/GlobalISelEmitter.cpp

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