llvm/utils/TableGen/GlobalISelMatchTable.cpp

   1 //===- GlobalISelMatchTable.cpp -------------------------------------------===//
   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 #include "GlobalISelMatchTable.h"
  10 #include "CodeGenInstruction.h"
  11 #include "CodeGenRegisters.h"
  12 #include "llvm/ADT/Statistic.h"
  13 #include "llvm/Support/Debug.h"
  14 #include "llvm/Support/LEB128.h"
  15 #include "llvm/Support/ScopedPrinter.h"
  16 #include "llvm/Support/raw_ostream.h"
  17 #include "llvm/TableGen/Error.h"
  18
  19 #define DEBUG_TYPE "gi-match-table"
  20
  21 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
  22
  23 namespace llvm {
  24 namespace gi {
  25
  26 namespace {
  27
  28 Error failUnsupported(const Twine &Reason) {
  29   return make_error<StringError>(Reason, inconvertibleErrorCode());
  30 }
  31
  32 /// Get the name of the enum value used to number the predicate function.
  33 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
  34   if (Predicate.hasGISelPredicateCode())
  35     return "GICXXPred_MI_" + Predicate.getFnName();
  36   return "GICXXPred_" + Predicate.getImmTypeIdentifier().str() + "_" +
  37          Predicate.getFnName();
  38 }
  39
  40 std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
  41   return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
  42 }
  43
  44 // GIMT_Encode2/4/8
  45 constexpr StringLiteral EncodeMacroName = "GIMT_Encode";
  46
  47 } // namespace
  48
  49 //===- Helpers ------------------------------------------------------------===//
  50
  51 void emitEncodingMacrosDef(raw_ostream &OS) {
  52   OS << "#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__\n"
  53      << "#define " << EncodeMacroName << "2(Val)"
  54      << " uint8_t(Val), uint8_t((uint16_t)Val >> 8)\n"
  55      << "#define " << EncodeMacroName << "4(Val)"
  56      << " uint8_t(Val), uint8_t((uint32_t)Val >> 8), "
  57         "uint8_t((uint32_t)Val >> 16), uint8_t((uint32_t)Val >> 24)\n"
  58      << "#define " << EncodeMacroName << "8(Val)"
  59      << " uint8_t(Val), uint8_t((uint64_t)Val >> 8), "
  60         "uint8_t((uint64_t)Val >> 16), uint8_t((uint64_t)Val >> 24),  "
  61         "uint8_t((uint64_t)Val >> 32), uint8_t((uint64_t)Val >> 40), "
  62         "uint8_t((uint64_t)Val >> 48), uint8_t((uint64_t)Val >> 56)\n"
  63      << "#else\n"
  64      << "#define " << EncodeMacroName << "2(Val)"
  65      << " uint8_t((uint16_t)Val >> 8), uint8_t(Val)\n"
  66      << "#define " << EncodeMacroName << "4(Val)"
  67      << " uint8_t((uint32_t)Val >> 24), uint8_t((uint32_t)Val >> 16), "
  68         "uint8_t((uint32_t)Val >> 8), uint8_t(Val)\n"
  69      << "#define " << EncodeMacroName << "8(Val)"
  70      << " uint8_t((uint64_t)Val >> 56), uint8_t((uint64_t)Val >> 48), "
  71         "uint8_t((uint64_t)Val >> 40), uint8_t((uint64_t)Val >> 32),  "
  72         "uint8_t((uint64_t)Val >> 24), uint8_t((uint64_t)Val >> 16), "
  73         "uint8_t((uint64_t)Val >> 8), uint8_t(Val)\n"
  74      << "#endif\n";
  75 }
  76
  77 void emitEncodingMacrosUndef(raw_ostream &OS) {
  78   OS << "#undef " << EncodeMacroName << "2\n"
  79      << "#undef " << EncodeMacroName << "4\n"
  80      << "#undef " << EncodeMacroName << "8\n";
  81 }
  82
  83 std::string getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset,
  84                                     int HwModeIdx) {
  85   std::string Name = "GIFBS";
  86   for (const auto &Feature : FeatureBitset)
  87     Name += ("_" + Feature->getName()).str();
  88   if (HwModeIdx >= 0)
  89     Name += ("_HwMode" + std::to_string(HwModeIdx));
  90   return Name;
  91 }
  92
  93 template <class GroupT>
  94 std::vector<Matcher *>
  95 optimizeRules(ArrayRef<Matcher *> Rules,
  96               std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
  97
  98   std::vector<Matcher *> OptRules;
  99   std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
 100   assert(CurrentGroup->empty() && "Newly created group isn't empty!");
 101   unsigned NumGroups = 0;
 102
 103   auto ProcessCurrentGroup = [&]() {
 104     if (CurrentGroup->empty())
 105       // An empty group is good to be reused:
 106       return;
 107
 108     // If the group isn't large enough to provide any benefit, move all the
 109     // added rules out of it and make sure to re-create the group to properly
 110     // re-initialize it:
 111     if (CurrentGroup->size() < 2)
 112       append_range(OptRules, CurrentGroup->matchers());
 113     else {
 114       CurrentGroup->finalize();
 115       OptRules.push_back(CurrentGroup.get());
 116       MatcherStorage.emplace_back(std::move(CurrentGroup));
 117       ++NumGroups;
 118     }
 119     CurrentGroup = std::make_unique<GroupT>();
 120   };
 121   for (Matcher *Rule : Rules) {
 122     // Greedily add as many matchers as possible to the current group:
 123     if (CurrentGroup->addMatcher(*Rule))
 124       continue;
 125
 126     ProcessCurrentGroup();
 127     assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
 128
 129     // Try to add the pending matcher to a newly created empty group:
 130     if (!CurrentGroup->addMatcher(*Rule))
 131       // If we couldn't add the matcher to an empty group, that group type
 132       // doesn't support that kind of matchers at all, so just skip it:
 133       OptRules.push_back(Rule);
 134   }
 135   ProcessCurrentGroup();
 136
 137   LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
 138   (void)NumGroups;
 139   assert(CurrentGroup->empty() && "The last group wasn't properly processed");
 140   return OptRules;
 141 }
 142
 143 template std::vector<Matcher *> optimizeRules<GroupMatcher>(
 144     ArrayRef<Matcher *> Rules,
 145     std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
 146
 147 template std::vector<Matcher *> optimizeRules<SwitchMatcher>(
 148     ArrayRef<Matcher *> Rules,
 149     std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
 150
 151 static std::string getEncodedEmitStr(StringRef NamedValue, unsigned NumBytes) {
 152   if (NumBytes == 2 || NumBytes == 4 || NumBytes == 8)
 153     return (EncodeMacroName + Twine(NumBytes) + "(" + NamedValue + ")").str();
 154   llvm_unreachable("Unsupported number of bytes!");
 155 }
 156
 157 //===- Global Data --------------------------------------------------------===//
 158
 159 std::set<LLTCodeGen> KnownTypes;
 160
 161 //===- MatchTableRecord ---------------------------------------------------===//
 162
 163 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
 164                             const MatchTable &Table) const {
 165   bool UseLineComment =
 166       LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
 167   if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
 168     UseLineComment = false;
 169
 170   if (Flags & MTRF_Comment)
 171     OS << (UseLineComment ? "// " : "/*");
 172
 173   if (NumElements > 1 && !(Flags & (MTRF_PreEncoded | MTRF_Comment)))
 174     OS << getEncodedEmitStr(EmitStr, NumElements);
 175   else
 176     OS << EmitStr;
 177
 178   if (Flags & MTRF_Label)
 179     OS << ": @" << Table.getLabelIndex(LabelID);
 180
 181   if ((Flags & MTRF_Comment) && !UseLineComment)
 182     OS << "*/";
 183
 184   if (Flags & MTRF_JumpTarget) {
 185     if (Flags & MTRF_Comment)
 186       OS << " ";
 187     // TODO: Could encode this AOT to speed up build of generated file
 188     OS << getEncodedEmitStr(llvm::to_string(Table.getLabelIndex(LabelID)),
 189                             NumElements);
 190   }
 191
 192   if (Flags & MTRF_CommaFollows) {
 193     OS << ",";
 194     if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
 195       OS << " ";
 196   }
 197
 198   if (Flags & MTRF_LineBreakFollows)
 199     OS << "\n";
 200 }
 201
 202 //===- MatchTable ---------------------------------------------------------===//
 203
 204 MatchTableRecord MatchTable::LineBreak = {
 205     std::nullopt, "" /* Emit String */, 0 /* Elements */,
 206     MatchTableRecord::MTRF_LineBreakFollows};
 207
 208 MatchTableRecord MatchTable::Comment(StringRef Comment) {
 209   return MatchTableRecord(std::nullopt, Comment, 0,
 210                           MatchTableRecord::MTRF_Comment);
 211 }
 212
 213 MatchTableRecord MatchTable::Opcode(StringRef Opcode, int IndentAdjust) {
 214   unsigned ExtraFlags = 0;
 215   if (IndentAdjust > 0)
 216     ExtraFlags |= MatchTableRecord::MTRF_Indent;
 217   if (IndentAdjust < 0)
 218     ExtraFlags |= MatchTableRecord::MTRF_Outdent;
 219
 220   return MatchTableRecord(std::nullopt, Opcode, 1,
 221                           MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
 222 }
 223
 224 MatchTableRecord MatchTable::NamedValue(unsigned NumBytes,
 225                                         StringRef NamedValue) {
 226   return MatchTableRecord(std::nullopt, NamedValue, NumBytes,
 227                           MatchTableRecord::MTRF_CommaFollows);
 228 }
 229
 230 MatchTableRecord MatchTable::NamedValue(unsigned NumBytes, StringRef NamedValue,
 231                                         int64_t RawValue) {
 232   return MatchTableRecord(std::nullopt, NamedValue, NumBytes,
 233                           MatchTableRecord::MTRF_CommaFollows, RawValue);
 234 }
 235
 236 MatchTableRecord MatchTable::NamedValue(unsigned NumBytes, StringRef Namespace,
 237                                         StringRef NamedValue) {
 238   return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(),
 239                           NumBytes, MatchTableRecord::MTRF_CommaFollows);
 240 }
 241
 242 MatchTableRecord MatchTable::NamedValue(unsigned NumBytes, StringRef Namespace,
 243                                         StringRef NamedValue,
 244                                         int64_t RawValue) {
 245   return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(),
 246                           NumBytes, MatchTableRecord::MTRF_CommaFollows,
 247                           RawValue);
 248 }
 249
 250 MatchTableRecord MatchTable::IntValue(unsigned NumBytes, int64_t IntValue) {
 251   assert(isUIntN(NumBytes * 8, IntValue) || isIntN(NumBytes * 8, IntValue));
 252   auto Str = llvm::to_string(IntValue);
 253   if (NumBytes == 1 && IntValue < 0)
 254     Str = "uint8_t(" + Str + ")";
 255   // TODO: Could optimize this directly to save the compiler some work when
 256   // building the file
 257   return MatchTableRecord(std::nullopt, Str, NumBytes,
 258                           MatchTableRecord::MTRF_CommaFollows);
 259 }
 260
 261 MatchTableRecord MatchTable::ULEB128Value(uint64_t IntValue) {
 262   uint8_t Buffer[10];
 263   unsigned Len = encodeULEB128(IntValue, Buffer);
 264
 265   // Simple case (most common)
 266   if (Len == 1) {
 267     return MatchTableRecord(std::nullopt, llvm::to_string((unsigned)Buffer[0]),
 268                             1, MatchTableRecord::MTRF_CommaFollows);
 269   }
 270
 271   // Print it as, e.g. /* -123456 (*/, 0xC0, 0xBB, 0x78 /*)*/
 272   std::string Str;
 273   raw_string_ostream OS(Str);
 274   OS << "/* " << llvm::to_string(IntValue) << "(*/";
 275   for (unsigned K = 0; K < Len; ++K) {
 276     if (K)
 277       OS << ", ";
 278     OS << "0x" << llvm::toHex({Buffer[K]});
 279   }
 280   OS << "/*)*/";
 281   return MatchTableRecord(std::nullopt, Str, Len,
 282                           MatchTableRecord::MTRF_CommaFollows |
 283                               MatchTableRecord::MTRF_PreEncoded);
 284 }
 285
 286 MatchTableRecord MatchTable::Label(unsigned LabelID) {
 287   return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
 288                           MatchTableRecord::MTRF_Label |
 289                               MatchTableRecord::MTRF_Comment |
 290                               MatchTableRecord::MTRF_LineBreakFollows);
 291 }
 292
 293 MatchTableRecord MatchTable::JumpTarget(unsigned LabelID) {
 294   return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 4,
 295                           MatchTableRecord::MTRF_JumpTarget |
 296                               MatchTableRecord::MTRF_Comment |
 297                               MatchTableRecord::MTRF_CommaFollows);
 298 }
 299
 300 void MatchTable::emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
 301
 302 void MatchTable::emitDeclaration(raw_ostream &OS) const {
 303   unsigned Indentation = 4;
 304   OS << "  constexpr static uint8_t MatchTable" << ID << "[] = {";
 305   LineBreak.emit(OS, true, *this);
 306   OS << std::string(Indentation, ' ');
 307
 308   for (auto I = Contents.begin(), E = Contents.end(); I != E; ++I) {
 309     bool LineBreakIsNext = false;
 310     const auto &NextI = std::next(I);
 311
 312     if (NextI != E) {
 313       if (NextI->EmitStr == "" &&
 314           NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
 315         LineBreakIsNext = true;
 316     }
 317
 318     if (I->Flags & MatchTableRecord::MTRF_Indent)
 319       Indentation += 2;
 320
 321     I->emit(OS, LineBreakIsNext, *this);
 322     if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
 323       OS << std::string(Indentation, ' ');
 324
 325     if (I->Flags & MatchTableRecord::MTRF_Outdent)
 326       Indentation -= 2;
 327   }
 328   OS << "}; // Size: " << CurrentSize << " bytes\n";
 329 }
 330
 331 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,
 332                                   bool IsCombiner) {
 333   MatchTable Table(WithCoverage, IsCombiner);
 334   for (Matcher *Rule : Rules)
 335     Rule->emit(Table);
 336
 337   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 338 }
 339
 340 //===- LLTCodeGen ---------------------------------------------------------===//
 341
 342 std::string LLTCodeGen::getCxxEnumValue() const {
 343   std::string Str;
 344   raw_string_ostream OS(Str);
 345
 346   emitCxxEnumValue(OS);
 347   return Str;
 348 }
 349
 350 void LLTCodeGen::emitCxxEnumValue(raw_ostream &OS) const {
 351   if (Ty.isScalar()) {
 352     OS << "GILLT_s" << Ty.getSizeInBits();
 353     return;
 354   }
 355   if (Ty.isVector()) {
 356     OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v")
 357        << Ty.getElementCount().getKnownMinValue() << "s"
 358        << Ty.getScalarSizeInBits();
 359     return;
 360   }
 361   if (Ty.isPointer()) {
 362     OS << "GILLT_p" << Ty.getAddressSpace();
 363     if (Ty.getSizeInBits() > 0)
 364       OS << "s" << Ty.getSizeInBits();
 365     return;
 366   }
 367   llvm_unreachable("Unhandled LLT");
 368 }
 369
 370 void LLTCodeGen::emitCxxConstructorCall(raw_ostream &OS) const {
 371   if (Ty.isScalar()) {
 372     OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
 373     return;
 374   }
 375   if (Ty.isVector()) {
 376     OS << "LLT::vector("
 377        << (Ty.isScalable() ? "ElementCount::getScalable("
 378                            : "ElementCount::getFixed(")
 379        << Ty.getElementCount().getKnownMinValue() << "), "
 380        << Ty.getScalarSizeInBits() << ")";
 381     return;
 382   }
 383   if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
 384     OS << "LLT::pointer(" << Ty.getAddressSpace() << ", " << Ty.getSizeInBits()
 385        << ")";
 386     return;
 387   }
 388   llvm_unreachable("Unhandled LLT");
 389 }
 390
 391 /// This ordering is used for std::unique() and llvm::sort(). There's no
 392 /// particular logic behind the order but either A < B or B < A must be
 393 /// true if A != B.
 394 bool LLTCodeGen::operator<(const LLTCodeGen &Other) const {
 395   if (Ty.isValid() != Other.Ty.isValid())
 396     return Ty.isValid() < Other.Ty.isValid();
 397   if (!Ty.isValid())
 398     return false;
 399
 400   if (Ty.isVector() != Other.Ty.isVector())
 401     return Ty.isVector() < Other.Ty.isVector();
 402   if (Ty.isScalar() != Other.Ty.isScalar())
 403     return Ty.isScalar() < Other.Ty.isScalar();
 404   if (Ty.isPointer() != Other.Ty.isPointer())
 405     return Ty.isPointer() < Other.Ty.isPointer();
 406
 407   if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
 408     return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
 409
 410   if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount())
 411     return std::make_tuple(Ty.isScalable(),
 412                            Ty.getElementCount().getKnownMinValue()) <
 413            std::make_tuple(Other.Ty.isScalable(),
 414                            Other.Ty.getElementCount().getKnownMinValue());
 415
 416   assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) &&
 417          "Unexpected mismatch of scalable property");
 418   return Ty.isVector()
 419              ? std::make_tuple(Ty.isScalable(),
 420                                Ty.getSizeInBits().getKnownMinValue()) <
 421                    std::make_tuple(Other.Ty.isScalable(),
 422                                    Other.Ty.getSizeInBits().getKnownMinValue())
 423              : Ty.getSizeInBits().getFixedValue() <
 424                    Other.Ty.getSizeInBits().getFixedValue();
 425 }
 426
 427 //===- LLTCodeGen Helpers -------------------------------------------------===//
 428
 429 std::optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
 430   MVT VT(SVT);
 431
 432   if (VT.isVector() && !VT.getVectorElementCount().isScalar())
 433     return LLTCodeGen(
 434         LLT::vector(VT.getVectorElementCount(), VT.getScalarSizeInBits()));
 435
 436   if (VT.isInteger() || VT.isFloatingPoint())
 437     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
 438
 439   return std::nullopt;
 440 }
 441
 442 //===- Matcher ------------------------------------------------------------===//
 443
 444 void Matcher::optimize() {}
 445
 446 Matcher::~Matcher() {}
 447
 448 //===- GroupMatcher -------------------------------------------------------===//
 449
 450 bool GroupMatcher::candidateConditionMatches(
 451     const PredicateMatcher &Predicate) const {
 452
 453   if (empty()) {
 454     // Sharing predicates for nested instructions is not supported yet as we
 455     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
 456     // only work on the original root instruction (InsnVarID == 0):
 457     if (Predicate.getInsnVarID() != 0)
 458       return false;
 459     // ... otherwise an empty group can handle any predicate with no specific
 460     // requirements:
 461     return true;
 462   }
 463
 464   const Matcher &Representative = **Matchers.begin();
 465   const auto &RepresentativeCondition = Representative.getFirstCondition();
 466   // ... if not empty, the group can only accomodate matchers with the exact
 467   // same first condition:
 468   return Predicate.isIdentical(RepresentativeCondition);
 469 }
 470
 471 bool GroupMatcher::addMatcher(Matcher &Candidate) {
 472   if (!Candidate.hasFirstCondition())
 473     return false;
 474
 475   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
 476   if (!candidateConditionMatches(Predicate))
 477     return false;
 478
 479   Matchers.push_back(&Candidate);
 480   return true;
 481 }
 482
 483 void GroupMatcher::finalize() {
 484   assert(Conditions.empty() && "Already finalized?");
 485   if (empty())
 486     return;
 487
 488   Matcher &FirstRule = **Matchers.begin();
 489   for (;;) {
 490     // All the checks are expected to succeed during the first iteration:
 491     for (const auto &Rule : Matchers)
 492       if (!Rule->hasFirstCondition())
 493         return;
 494     const auto &FirstCondition = FirstRule.getFirstCondition();
 495     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
 496       if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
 497         return;
 498
 499     Conditions.push_back(FirstRule.popFirstCondition());
 500     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
 501       Matchers[I]->popFirstCondition();
 502   }
 503 }
 504
 505 void GroupMatcher::emit(MatchTable &Table) {
 506   unsigned LabelID = ~0U;
 507   if (!Conditions.empty()) {
 508     LabelID = Table.allocateLabelID();
 509     Table << MatchTable::Opcode("GIM_Try", +1)
 510           << MatchTable::Comment("On fail goto")
 511           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
 512   }
 513   for (auto &Condition : Conditions)
 514     Condition->emitPredicateOpcodes(
 515         Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
 516
 517   for (const auto &M : Matchers)
 518     M->emit(Table);
 519
 520   // Exit the group
 521   if (!Conditions.empty())
 522     Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
 523           << MatchTable::Label(LabelID);
 524 }
 525
 526 void GroupMatcher::optimize() {
 527   // Make sure we only sort by a specific predicate within a range of rules that
 528   // all have that predicate checked against a specific value (not a wildcard):
 529   auto F = Matchers.begin();
 530   auto T = F;
 531   auto E = Matchers.end();
 532   while (T != E) {
 533     while (T != E) {
 534       auto *R = static_cast<RuleMatcher *>(*T);
 535       if (!R->getFirstConditionAsRootType().get().isValid())
 536         break;
 537       ++T;
 538     }
 539     std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
 540       auto *L = static_cast<RuleMatcher *>(A);
 541       auto *R = static_cast<RuleMatcher *>(B);
 542       return L->getFirstConditionAsRootType() <
 543              R->getFirstConditionAsRootType();
 544     });
 545     if (T != E)
 546       F = ++T;
 547   }
 548   optimizeRules<GroupMatcher>(Matchers, MatcherStorage).swap(Matchers);
 549   optimizeRules<SwitchMatcher>(Matchers, MatcherStorage).swap(Matchers);
 550 }
 551
 552 //===- SwitchMatcher ------------------------------------------------------===//
 553
 554 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
 555   return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
 556 }
 557
 558 bool SwitchMatcher::candidateConditionMatches(
 559     const PredicateMatcher &Predicate) const {
 560
 561   if (empty()) {
 562     // Sharing predicates for nested instructions is not supported yet as we
 563     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
 564     // only work on the original root instruction (InsnVarID == 0):
 565     if (Predicate.getInsnVarID() != 0)
 566       return false;
 567     // ... while an attempt to add even a root matcher to an empty SwitchMatcher
 568     // could fail as not all the types of conditions are supported:
 569     if (!isSupportedPredicateType(Predicate))
 570       return false;
 571     // ... or the condition might not have a proper implementation of
 572     // getValue() / isIdenticalDownToValue() yet:
 573     if (!Predicate.hasValue())
 574       return false;
 575     // ... otherwise an empty Switch can accomodate the condition with no
 576     // further requirements:
 577     return true;
 578   }
 579
 580   const Matcher &CaseRepresentative = **Matchers.begin();
 581   const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
 582   // Switch-cases must share the same kind of condition and path to the value it
 583   // checks:
 584   if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
 585     return false;
 586
 587   const auto Value = Predicate.getValue();
 588   // ... but be unique with respect to the actual value they check:
 589   return Values.count(Value) == 0;
 590 }
 591
 592 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
 593   if (!Candidate.hasFirstCondition())
 594     return false;
 595
 596   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
 597   if (!candidateConditionMatches(Predicate))
 598     return false;
 599   const auto Value = Predicate.getValue();
 600   Values.insert(Value);
 601
 602   Matchers.push_back(&Candidate);
 603   return true;
 604 }
 605
 606 void SwitchMatcher::finalize() {
 607   assert(Condition == nullptr && "Already finalized");
 608   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
 609   if (empty())
 610     return;
 611
 612   llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) {
 613     return L->getFirstCondition().getValue() <
 614            R->getFirstCondition().getValue();
 615   });
 616   Condition = Matchers[0]->popFirstCondition();
 617   for (unsigned I = 1, E = Values.size(); I < E; ++I)
 618     Matchers[I]->popFirstCondition();
 619 }
 620
 621 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
 622                                                  MatchTable &Table) {
 623   assert(isSupportedPredicateType(P) && "Predicate type is not supported");
 624
 625   if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
 626     Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
 627           << MatchTable::ULEB128Value(Condition->getInsnVarID());
 628     return;
 629   }
 630   if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
 631     Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
 632           << MatchTable::ULEB128Value(Condition->getInsnVarID())
 633           << MatchTable::Comment("Op")
 634           << MatchTable::ULEB128Value(Condition->getOpIdx());
 635     return;
 636   }
 637
 638   llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
 639                    "predicate type that is claimed to be supported");
 640 }
 641
 642 void SwitchMatcher::emit(MatchTable &Table) {
 643   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
 644   if (empty())
 645     return;
 646   assert(Condition != nullptr &&
 647          "Broken SwitchMatcher, hasn't been finalized?");
 648
 649   std::vector<unsigned> LabelIDs(Values.size());
 650   std::generate(LabelIDs.begin(), LabelIDs.end(),
 651                 [&Table]() { return Table.allocateLabelID(); });
 652   const unsigned Default = Table.allocateLabelID();
 653
 654   const int64_t LowerBound = Values.begin()->getRawValue();
 655   const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
 656
 657   emitPredicateSpecificOpcodes(*Condition, Table);
 658
 659   Table << MatchTable::Comment("[") << MatchTable::IntValue(2, LowerBound)
 660         << MatchTable::IntValue(2, UpperBound) << MatchTable::Comment(")")
 661         << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
 662
 663   int64_t J = LowerBound;
 664   auto VI = Values.begin();
 665   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
 666     auto V = *VI++;
 667     while (J++ < V.getRawValue())
 668       Table << MatchTable::IntValue(4, 0);
 669     V.turnIntoComment();
 670     Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
 671   }
 672   Table << MatchTable::LineBreak;
 673
 674   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
 675     Table << MatchTable::Label(LabelIDs[I]);
 676     Matchers[I]->emit(Table);
 677     Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 678   }
 679   Table << MatchTable::Label(Default);
 680 }
 681
 682 //===- RuleMatcher --------------------------------------------------------===//
 683
 684 uint64_t RuleMatcher::NextRuleID = 0;
 685
 686 StringRef RuleMatcher::getOpcode() const {
 687   return Matchers.front()->getOpcode();
 688 }
 689
 690 unsigned RuleMatcher::getNumOperands() const {
 691   return Matchers.front()->getNumOperands();
 692 }
 693
 694 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
 695   InstructionMatcher &InsnMatcher = *Matchers.front();
 696   if (!InsnMatcher.predicates_empty())
 697     if (const auto *TM =
 698             dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
 699       if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
 700         return TM->getTy();
 701   return {};
 702 }
 703
 704 void RuleMatcher::optimize() {
 705   for (auto &Item : InsnVariableIDs) {
 706     InstructionMatcher &InsnMatcher = *Item.first;
 707     for (auto &OM : InsnMatcher.operands()) {
 708       // Complex Patterns are usually expensive and they relatively rarely fail
 709       // on their own: more often we end up throwing away all the work done by a
 710       // matching part of a complex pattern because some other part of the
 711       // enclosing pattern didn't match. All of this makes it beneficial to
 712       // delay complex patterns until the very end of the rule matching,
 713       // especially for targets having lots of complex patterns.
 714       for (auto &OP : OM->predicates())
 715         if (isa<ComplexPatternOperandMatcher>(OP))
 716           EpilogueMatchers.emplace_back(std::move(OP));
 717       OM->eraseNullPredicates();
 718     }
 719     InsnMatcher.optimize();
 720   }
 721   llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
 722                                   const std::unique_ptr<PredicateMatcher> &R) {
 723     return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
 724            std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
 725   });
 726 }
 727
 728 bool RuleMatcher::hasFirstCondition() const {
 729   if (insnmatchers_empty())
 730     return false;
 731   InstructionMatcher &Matcher = insnmatchers_front();
 732   if (!Matcher.predicates_empty())
 733     return true;
 734   for (auto &OM : Matcher.operands())
 735     for (auto &OP : OM->predicates())
 736       if (!isa<InstructionOperandMatcher>(OP))
 737         return true;
 738   return false;
 739 }
 740
 741 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
 742   assert(!insnmatchers_empty() &&
 743          "Trying to get a condition from an empty RuleMatcher");
 744
 745   InstructionMatcher &Matcher = insnmatchers_front();
 746   if (!Matcher.predicates_empty())
 747     return **Matcher.predicates_begin();
 748   // If there is no more predicate on the instruction itself, look at its
 749   // operands.
 750   for (auto &OM : Matcher.operands())
 751     for (auto &OP : OM->predicates())
 752       if (!isa<InstructionOperandMatcher>(OP))
 753         return *OP;
 754
 755   llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
 756                    "no conditions");
 757 }
 758
 759 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
 760   assert(!insnmatchers_empty() &&
 761          "Trying to pop a condition from an empty RuleMatcher");
 762
 763   InstructionMatcher &Matcher = insnmatchers_front();
 764   if (!Matcher.predicates_empty())
 765     return Matcher.predicates_pop_front();
 766   // If there is no more predicate on the instruction itself, look at its
 767   // operands.
 768   for (auto &OM : Matcher.operands())
 769     for (auto &OP : OM->predicates())
 770       if (!isa<InstructionOperandMatcher>(OP)) {
 771         std::unique_ptr<PredicateMatcher> Result = std::move(OP);
 772         OM->eraseNullPredicates();
 773         return Result;
 774       }
 775
 776   llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
 777                    "no conditions");
 778 }
 779
 780 GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R,
 781                                         StringRef FlagName,
 782                                         GISelFlags FlagBit) {
 783   // If the value of a flag is unset, ignore it.
 784   // If it's set, it always takes precedence over the existing value so
 785   // clear/set the corresponding bit.
 786   bool Unset = false;
 787   bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset);
 788   if (!Unset)
 789     return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit);
 790   return CurFlags;
 791 }
 792
 793 SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) {
 794   if (!R || !R->isSubClassOf("GISelFlags"))
 795     return {Flags, Flags};
 796
 797   assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) &&
 798          "GISelFlags is only expected on Pattern/PatFrags!");
 799
 800   GISelFlags NewFlags =
 801       updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies);
 802   return {Flags, NewFlags};
 803 }
 804
 805 Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName,
 806                                            Record *ComplexPattern,
 807                                            unsigned RendererID,
 808                                            unsigned SubOperandID,
 809                                            StringRef ParentSymbolicName) {
 810   std::string ParentName(ParentSymbolicName);
 811   if (ComplexSubOperands.count(SymbolicName)) {
 812     const std::string &RecordedParentName =
 813         ComplexSubOperandsParentName[SymbolicName];
 814     if (RecordedParentName != ParentName)
 815       return failUnsupported("Error: Complex suboperand " + SymbolicName +
 816                              " referenced by different operands: " +
 817                              RecordedParentName + " and " + ParentName + ".");
 818     // Complex suboperand referenced more than once from same the operand is
 819     // used to generate 'same operand check'. Emitting of
 820     // GIR_ComplexSubOperandRenderer for them is already handled.
 821     return Error::success();
 822   }
 823
 824   ComplexSubOperands[SymbolicName] =
 825       std::make_tuple(ComplexPattern, RendererID, SubOperandID);
 826   ComplexSubOperandsParentName[SymbolicName] = ParentName;
 827
 828   return Error::success();
 829 }
 830
 831 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
 832   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
 833   MutatableInsns.insert(Matchers.back().get());
 834   return *Matchers.back();
 835 }
 836
 837 void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {
 838   RequiredSimplePredicates.push_back(PredName.str());
 839 }
 840
 841 const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {
 842   return RequiredSimplePredicates;
 843 }
 844
 845 void RuleMatcher::addRequiredFeature(Record *Feature) {
 846   RequiredFeatures.push_back(Feature);
 847 }
 848
 849 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
 850   return RequiredFeatures;
 851 }
 852
 853 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
 854   unsigned NewInsnVarID = NextInsnVarID++;
 855   InsnVariableIDs[&Matcher] = NewInsnVarID;
 856   return NewInsnVarID;
 857 }
 858
 859 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
 860   const auto &I = InsnVariableIDs.find(&InsnMatcher);
 861   if (I != InsnVariableIDs.end())
 862     return I->second;
 863   llvm_unreachable("Matched Insn was not captured in a local variable");
 864 }
 865
 866 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
 867   if (!DefinedOperands.contains(SymbolicName)) {
 868     DefinedOperands[SymbolicName] = &OM;
 869     return;
 870   }
 871
 872   // If the operand is already defined, then we must ensure both references in
 873   // the matcher have the exact same node.
 874   RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher();
 875   OM.addPredicate<SameOperandMatcher>(
 876       OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(),
 877       RM.getGISelFlags());
 878 }
 879
 880 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
 881   if (!PhysRegOperands.contains(Reg)) {
 882     PhysRegOperands[Reg] = &OM;
 883     return;
 884   }
 885 }
 886
 887 InstructionMatcher &
 888 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
 889   for (const auto &I : InsnVariableIDs)
 890     if (I.first->getSymbolicName() == SymbolicName)
 891       return *I.first;
 892   llvm_unreachable(
 893       ("Failed to lookup instruction " + SymbolicName).str().c_str());
 894 }
 895
 896 const OperandMatcher &RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
 897   const auto &I = PhysRegOperands.find(Reg);
 898
 899   if (I == PhysRegOperands.end()) {
 900     PrintFatalError(SrcLoc, "Register " + Reg->getName() +
 901                                 " was not declared in matcher");
 902   }
 903
 904   return *I->second;
 905 }
 906
 907 OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) {
 908   const auto &I = DefinedOperands.find(Name);
 909
 910   if (I == DefinedOperands.end())
 911     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
 912
 913   return *I->second;
 914 }
 915
 916 const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const {
 917   const auto &I = DefinedOperands.find(Name);
 918
 919   if (I == DefinedOperands.end())
 920     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
 921
 922   return *I->second;
 923 }
 924
 925 void RuleMatcher::emit(MatchTable &Table) {
 926   if (Matchers.empty())
 927     llvm_unreachable("Unexpected empty matcher!");
 928
 929   // The representation supports rules that require multiple roots such as:
 930   //    %ptr(p0) = ...
 931   //    %elt0(s32) = G_LOAD %ptr
 932   //    %1(p0) = G_ADD %ptr, 4
 933   //    %elt1(s32) = G_LOAD p0 %1
 934   // which could be usefully folded into:
 935   //    %ptr(p0) = ...
 936   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
 937   // on some targets but we don't need to make use of that yet.
 938   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
 939
 940   unsigned LabelID = Table.allocateLabelID();
 941   Table << MatchTable::Opcode("GIM_Try", +1)
 942         << MatchTable::Comment("On fail goto")
 943         << MatchTable::JumpTarget(LabelID)
 944         << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
 945         << MatchTable::LineBreak;
 946
 947   if (!RequiredFeatures.empty() || HwModeIdx >= 0) {
 948     Table << MatchTable::Opcode("GIM_CheckFeatures")
 949           << MatchTable::NamedValue(
 950                  2, getNameForFeatureBitset(RequiredFeatures, HwModeIdx))
 951           << MatchTable::LineBreak;
 952   }
 953
 954   if (!RequiredSimplePredicates.empty()) {
 955     for (const auto &Pred : RequiredSimplePredicates) {
 956       Table << MatchTable::Opcode("GIM_CheckSimplePredicate")
 957             << MatchTable::NamedValue(2, Pred) << MatchTable::LineBreak;
 958     }
 959   }
 960
 961   Matchers.front()->emitPredicateOpcodes(Table, *this);
 962
 963   // Check if it's safe to replace registers.
 964   for (const auto &MA : Actions)
 965     MA->emitAdditionalPredicates(Table, *this);
 966
 967   // We must also check if it's safe to fold the matched instructions.
 968   if (InsnVariableIDs.size() >= 2) {
 969     // Invert the map to create stable ordering (by var names)
 970     SmallVector<unsigned, 2> InsnIDs;
 971     for (const auto &Pair : InsnVariableIDs) {
 972       // Skip the root node since it isn't moving anywhere. Everything else is
 973       // sinking to meet it.
 974       if (Pair.first == Matchers.front().get())
 975         continue;
 976
 977       InsnIDs.push_back(Pair.second);
 978     }
 979     llvm::sort(InsnIDs);
 980
 981     for (const auto &InsnID : InsnIDs) {
 982       // Reject the difficult cases until we have a more accurate check.
 983       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
 984             << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
 985             << MatchTable::LineBreak;
 986
 987       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
 988       //        account for unsafe cases.
 989       //
 990       //        Example:
 991       //          MI1--> %0 = ...
 992       //                 %1 = ... %0
 993       //          MI0--> %2 = ... %0
 994       //          It's not safe to erase MI1. We currently handle this by not
 995       //          erasing %0 (even when it's dead).
 996       //
 997       //        Example:
 998       //          MI1--> %0 = load volatile @a
 999       //                 %1 = load volatile @a
1000       //          MI0--> %2 = ... %0
1001       //          It's not safe to sink %0's def past %1. We currently handle
1002       //          this by rejecting all loads.
1003       //
1004       //        Example:
1005       //          MI1--> %0 = load @a
1006       //                 %1 = store @a
1007       //          MI0--> %2 = ... %0
1008       //          It's not safe to sink %0's def past %1. We currently handle
1009       //          this by rejecting all loads.
1010       //
1011       //        Example:
1012       //                   G_CONDBR %cond, @BB1
1013       //                 BB0:
1014       //          MI1-->   %0 = load @a
1015       //                   G_BR @BB1
1016       //                 BB1:
1017       //          MI0-->   %2 = ... %0
1018       //          It's not always safe to sink %0 across control flow. In this
1019       //          case it may introduce a memory fault. We currentl handle
1020       //          this by rejecting all loads.
1021     }
1022   }
1023
1024   for (const auto &PM : EpilogueMatchers)
1025     PM->emitPredicateOpcodes(Table, *this);
1026
1027   for (const auto &MA : Actions)
1028     MA->emitActionOpcodes(Table, *this);
1029
1030   assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&
1031          "Combiner tables don't support coverage!");
1032   if (Table.isWithCoverage())
1033     Table << MatchTable::Opcode("GIR_Coverage")
1034           << MatchTable::IntValue(4, RuleID) << MatchTable::LineBreak;
1035   else if (!Table.isCombiner())
1036     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
1037           << MatchTable::LineBreak;
1038
1039   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
1040         << MatchTable::Label(LabelID);
1041   ++NumPatternEmitted;
1042 }
1043
1044 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1045   // Rules involving more match roots have higher priority.
1046   if (Matchers.size() > B.Matchers.size())
1047     return true;
1048   if (Matchers.size() < B.Matchers.size())
1049     return false;
1050
1051   for (auto Matcher : zip(Matchers, B.Matchers)) {
1052     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1053       return true;
1054     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1055       return false;
1056   }
1057
1058   return false;
1059 }
1060
1061 unsigned RuleMatcher::countRendererFns() const {
1062   return std::accumulate(
1063       Matchers.begin(), Matchers.end(), 0,
1064       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1065         return A + Matcher->countRendererFns();
1066       });
1067 }
1068
1069 //===- PredicateMatcher ---------------------------------------------------===//
1070
1071 PredicateMatcher::~PredicateMatcher() {}
1072
1073 //===- OperandPredicateMatcher --------------------------------------------===//
1074
1075 OperandPredicateMatcher::~OperandPredicateMatcher() {}
1076
1077 bool OperandPredicateMatcher::isHigherPriorityThan(
1078     const OperandPredicateMatcher &B) const {
1079   // Generally speaking, an instruction is more important than an Int or a
1080   // LiteralInt because it can cover more nodes but theres an exception to
1081   // this. G_CONSTANT's are less important than either of those two because they
1082   // are more permissive.
1083
1084   const InstructionOperandMatcher *AOM =
1085       dyn_cast<InstructionOperandMatcher>(this);
1086   const InstructionOperandMatcher *BOM =
1087       dyn_cast<InstructionOperandMatcher>(&B);
1088   bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
1089   bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
1090
1091   if (AOM && BOM) {
1092     // The relative priorities between a G_CONSTANT and any other instruction
1093     // don't actually matter but this code is needed to ensure a strict weak
1094     // ordering. This is particularly important on Windows where the rules will
1095     // be incorrectly sorted without it.
1096     if (AIsConstantInsn != BIsConstantInsn)
1097       return AIsConstantInsn < BIsConstantInsn;
1098     return false;
1099   }
1100
1101   if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
1102     return false;
1103   if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
1104     return true;
1105
1106   return Kind < B.Kind;
1107 }
1108
1109 //===- SameOperandMatcher -------------------------------------------------===//
1110
1111 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1112                                               RuleMatcher &Rule) const {
1113   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
1114   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
1115   assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
1116   const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1117   Table << MatchTable::Opcode(IgnoreCopies
1118                                   ? "GIM_CheckIsSameOperandIgnoreCopies"
1119                                   : "GIM_CheckIsSameOperand")
1120         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1121         << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
1122         << MatchTable::Comment("OtherMI")
1123         << MatchTable::ULEB128Value(OtherInsnVarID)
1124         << MatchTable::Comment("OtherOpIdx")
1125         << MatchTable::ULEB128Value(OtherOM.getOpIdx())
1126         << MatchTable::LineBreak;
1127 }
1128
1129 //===- LLTOperandMatcher --------------------------------------------------===//
1130
1131 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1132
1133 MatchTableRecord LLTOperandMatcher::getValue() const {
1134   const auto VI = TypeIDValues.find(Ty);
1135   if (VI == TypeIDValues.end())
1136     return MatchTable::NamedValue(1, getTy().getCxxEnumValue());
1137   return MatchTable::NamedValue(1, getTy().getCxxEnumValue(), VI->second);
1138 }
1139
1140 bool LLTOperandMatcher::hasValue() const {
1141   if (TypeIDValues.size() != KnownTypes.size())
1142     initTypeIDValuesMap();
1143   return TypeIDValues.count(Ty);
1144 }
1145
1146 void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1147                                              RuleMatcher &Rule) const {
1148   Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1149         << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1150         << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("Type")
1151         << getValue() << MatchTable::LineBreak;
1152 }
1153
1154 //===- PointerToAnyOperandMatcher -----------------------------------------===//
1155
1156 void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1157                                                       RuleMatcher &Rule) const {
1158   Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1159         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1160         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1161         << MatchTable::Comment("SizeInBits")
1162         << MatchTable::ULEB128Value(SizeInBits) << MatchTable::LineBreak;
1163 }
1164
1165 //===- RecordNamedOperandMatcher ------------------------------------------===//
1166
1167 void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1168                                                      RuleMatcher &Rule) const {
1169   Table << MatchTable::Opcode("GIM_RecordNamedOperand")
1170         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1171         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1172         << MatchTable::Comment("StoreIdx") << MatchTable::ULEB128Value(StoreIdx)
1173         << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;
1174 }
1175
1176 //===- RecordRegisterType ------------------------------------------===//
1177
1178 void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table,
1179                                               RuleMatcher &Rule) const {
1180   assert(Idx < 0 && "Temp types always have negative indexes!");
1181   Table << MatchTable::Opcode("GIM_RecordRegType") << MatchTable::Comment("MI")
1182         << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1183         << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("TempTypeIdx")
1184         << MatchTable::IntValue(1, Idx) << MatchTable::LineBreak;
1185 }
1186
1187 //===- ComplexPatternOperandMatcher ---------------------------------------===//
1188
1189 void ComplexPatternOperandMatcher::emitPredicateOpcodes(
1190     MatchTable &Table, RuleMatcher &Rule) const {
1191   unsigned ID = getAllocatedTemporariesBaseID();
1192   Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1193         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1194         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1195         << MatchTable::Comment("Renderer") << MatchTable::IntValue(2, ID)
1196         << MatchTable::NamedValue(2, ("GICP_" + TheDef.getName()).str())
1197         << MatchTable::LineBreak;
1198 }
1199
1200 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1201   return Operand.getAllocatedTemporariesBaseID();
1202 }
1203
1204 //===- RegisterBankOperandMatcher -----------------------------------------===//
1205
1206 bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const {
1207   return OperandPredicateMatcher::isIdentical(B) &&
1208          RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1209 }
1210
1211 void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1212                                                       RuleMatcher &Rule) const {
1213   Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1214         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1215         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1216         << MatchTable::Comment("RC")
1217         << MatchTable::NamedValue(2, RC.getQualifiedIdName())
1218         << MatchTable::LineBreak;
1219 }
1220
1221 //===- MBBOperandMatcher --------------------------------------------------===//
1222
1223 void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1224                                              RuleMatcher &Rule) const {
1225   Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1226         << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1227         << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
1228 }
1229
1230 //===- ImmOperandMatcher --------------------------------------------------===//
1231
1232 void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1233                                              RuleMatcher &Rule) const {
1234   Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1235         << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1236         << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
1237 }
1238
1239 //===- ConstantIntOperandMatcher ------------------------------------------===//
1240
1241 void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1242                                                      RuleMatcher &Rule) const {
1243   const bool IsInt8 = isInt<8>(Value);
1244   Table << MatchTable::Opcode(IsInt8 ? "GIM_CheckConstantInt8"
1245                                      : "GIM_CheckConstantInt")
1246         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1247         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1248         << MatchTable::IntValue(IsInt8 ? 1 : 8, Value) << MatchTable::LineBreak;
1249 }
1250
1251 //===- LiteralIntOperandMatcher -------------------------------------------===//
1252
1253 void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1254                                                     RuleMatcher &Rule) const {
1255   Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1256         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1257         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1258         << MatchTable::IntValue(8, Value) << MatchTable::LineBreak;
1259 }
1260
1261 //===- CmpPredicateOperandMatcher -----------------------------------------===//
1262
1263 void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1264                                                       RuleMatcher &Rule) const {
1265   Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1266         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1267         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1268         << MatchTable::Comment("Predicate")
1269         << MatchTable::NamedValue(2, "CmpInst", PredName)
1270         << MatchTable::LineBreak;
1271 }
1272
1273 //===- IntrinsicIDOperandMatcher ------------------------------------------===//
1274
1275 void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1276                                                      RuleMatcher &Rule) const {
1277   Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1278         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1279         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1280         << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName)
1281         << MatchTable::LineBreak;
1282 }
1283
1284 //===- OperandImmPredicateMatcher -----------------------------------------===//
1285
1286 void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1287                                                       RuleMatcher &Rule) const {
1288   Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
1289         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1290         << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)
1291         << MatchTable::Comment("Predicate")
1292         << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
1293         << MatchTable::LineBreak;
1294 }
1295
1296 //===- OperandMatcher -----------------------------------------------------===//
1297
1298 std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const {
1299   return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1300          llvm::to_string(OpIdx) + ")";
1301 }
1302
1303 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
1304
1305 TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) {
1306   if (TTIdx >= 0) {
1307     // Temp type index not assigned yet, so assign one and add the necessary
1308     // predicate.
1309     TTIdx = Rule.getNextTempTypeIdx();
1310     assert(TTIdx < 0);
1311     addPredicate<RecordRegisterType>(TTIdx);
1312     return TTIdx;
1313   }
1314   return TTIdx;
1315 }
1316
1317 void OperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1318                                           RuleMatcher &Rule) {
1319   if (!Optimized) {
1320     std::string Comment;
1321     raw_string_ostream CommentOS(Comment);
1322     CommentOS << "MIs[" << getInsnVarID() << "] ";
1323     if (SymbolicName.empty())
1324       CommentOS << "Operand " << OpIdx;
1325     else
1326       CommentOS << SymbolicName;
1327     Table << MatchTable::Comment(Comment) << MatchTable::LineBreak;
1328   }
1329
1330   emitPredicateListOpcodes(Table, Rule);
1331 }
1332
1333 bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) {
1334   // Operand matchers involving more predicates have higher priority.
1335   if (predicates_size() > B.predicates_size())
1336     return true;
1337   if (predicates_size() < B.predicates_size())
1338     return false;
1339
1340   // This assumes that predicates are added in a consistent order.
1341   for (auto &&Predicate : zip(predicates(), B.predicates())) {
1342     if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1343       return true;
1344     if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1345       return false;
1346   }
1347
1348   return false;
1349 }
1350
1351 unsigned OperandMatcher::countRendererFns() {
1352   return std::accumulate(
1353       predicates().begin(), predicates().end(), 0,
1354       [](unsigned A,
1355          const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1356         return A + Predicate->countRendererFns();
1357       });
1358 }
1359
1360 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1361                                             bool OperandIsAPointer) {
1362   if (!VTy.isMachineValueType())
1363     return failUnsupported("unsupported typeset");
1364
1365   if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1366     addPredicate<PointerToAnyOperandMatcher>(0);
1367     return Error::success();
1368   }
1369
1370   auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1371   if (!OpTyOrNone)
1372     return failUnsupported("unsupported type");
1373
1374   if (OperandIsAPointer)
1375     addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1376   else if (VTy.isPointer())
1377     addPredicate<LLTOperandMatcher>(
1378         LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits()));
1379   else
1380     addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1381   return Error::success();
1382 }
1383
1384 //===- InstructionOpcodeMatcher -------------------------------------------===//
1385
1386 DenseMap<const CodeGenInstruction *, unsigned>
1387     InstructionOpcodeMatcher::OpcodeValues;
1388
1389 MatchTableRecord
1390 InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const {
1391   const auto VI = OpcodeValues.find(I);
1392   if (VI != OpcodeValues.end())
1393     return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(),
1394                                   VI->second);
1395   return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName());
1396 }
1397
1398 void InstructionOpcodeMatcher::initOpcodeValuesMap(
1399     const CodeGenTarget &Target) {
1400   OpcodeValues.clear();
1401
1402   unsigned OpcodeValue = 0;
1403   for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1404     OpcodeValues[I] = OpcodeValue++;
1405 }
1406
1407 MatchTableRecord InstructionOpcodeMatcher::getValue() const {
1408   assert(Insts.size() == 1);
1409
1410   const CodeGenInstruction *I = Insts[0];
1411   const auto VI = OpcodeValues.find(I);
1412   if (VI != OpcodeValues.end())
1413     return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(),
1414                                   VI->second);
1415   return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName());
1416 }
1417
1418 void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table,
1419                                                     RuleMatcher &Rule) const {
1420   StringRef CheckType =
1421       Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
1422   Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
1423         << MatchTable::ULEB128Value(InsnVarID);
1424
1425   for (const CodeGenInstruction *I : Insts)
1426     Table << getInstValue(I);
1427   Table << MatchTable::LineBreak;
1428 }
1429
1430 bool InstructionOpcodeMatcher::isHigherPriorityThan(
1431     const InstructionPredicateMatcher &B) const {
1432   if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1433     return true;
1434   if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1435     return false;
1436
1437   // Prioritize opcodes for cosmetic reasons in the generated source. Although
1438   // this is cosmetic at the moment, we may want to drive a similar ordering
1439   // using instruction frequency information to improve compile time.
1440   if (const InstructionOpcodeMatcher *BO =
1441           dyn_cast<InstructionOpcodeMatcher>(&B))
1442     return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName();
1443
1444   return false;
1445 }
1446
1447 bool InstructionOpcodeMatcher::isConstantInstruction() const {
1448   return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT";
1449 }
1450
1451 StringRef InstructionOpcodeMatcher::getOpcode() const {
1452   return Insts[0]->TheDef->getName();
1453 }
1454
1455 bool InstructionOpcodeMatcher::isVariadicNumOperands() const {
1456   // If one is variadic, they all should be.
1457   return Insts[0]->Operands.isVariadic;
1458 }
1459
1460 StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const {
1461   // Types expected to be uniform for all alternatives.
1462   return Insts[0]->Operands[OpIdx].OperandType;
1463 }
1464
1465 //===- InstructionNumOperandsMatcher --------------------------------------===//
1466
1467 void InstructionNumOperandsMatcher::emitPredicateOpcodes(
1468     MatchTable &Table, RuleMatcher &Rule) const {
1469   Table << MatchTable::Opcode("GIM_CheckNumOperands")
1470         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1471         << MatchTable::Comment("Expected")
1472         << MatchTable::ULEB128Value(NumOperands) << MatchTable::LineBreak;
1473 }
1474
1475 //===- InstructionImmPredicateMatcher -------------------------------------===//
1476
1477 bool InstructionImmPredicateMatcher::isIdentical(
1478     const PredicateMatcher &B) const {
1479   return InstructionPredicateMatcher::isIdentical(B) &&
1480          Predicate.getOrigPatFragRecord() ==
1481              cast<InstructionImmPredicateMatcher>(&B)
1482                  ->Predicate.getOrigPatFragRecord();
1483 }
1484
1485 void InstructionImmPredicateMatcher::emitPredicateOpcodes(
1486     MatchTable &Table, RuleMatcher &Rule) const {
1487   Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
1488         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1489         << MatchTable::Comment("Predicate")
1490         << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
1491         << MatchTable::LineBreak;
1492 }
1493
1494 //===- AtomicOrderingMMOPredicateMatcher ----------------------------------===//
1495
1496 bool AtomicOrderingMMOPredicateMatcher::isIdentical(
1497     const PredicateMatcher &B) const {
1498   if (!InstructionPredicateMatcher::isIdentical(B))
1499     return false;
1500   const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1501   return Order == R.Order && Comparator == R.Comparator;
1502 }
1503
1504 void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes(
1505     MatchTable &Table, RuleMatcher &Rule) const {
1506   StringRef Opcode = "GIM_CheckAtomicOrdering";
1507
1508   if (Comparator == AO_OrStronger)
1509     Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1510   if (Comparator == AO_WeakerThan)
1511     Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1512
1513   Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1514         << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Order")
1515         << MatchTable::NamedValue(1,
1516                                   ("(uint8_t)AtomicOrdering::" + Order).str())
1517         << MatchTable::LineBreak;
1518 }
1519
1520 //===- MemorySizePredicateMatcher -----------------------------------------===//
1521
1522 void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1523                                                       RuleMatcher &Rule) const {
1524   Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1525         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1526         << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1527         << MatchTable::Comment("Size") << MatchTable::IntValue(4, Size)
1528         << MatchTable::LineBreak;
1529 }
1530
1531 //===- MemoryAddressSpacePredicateMatcher ---------------------------------===//
1532
1533 bool MemoryAddressSpacePredicateMatcher::isIdentical(
1534     const PredicateMatcher &B) const {
1535   if (!InstructionPredicateMatcher::isIdentical(B))
1536     return false;
1537   auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1538   return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1539 }
1540
1541 void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes(
1542     MatchTable &Table, RuleMatcher &Rule) const {
1543   Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1544         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1545         << MatchTable::Comment("MMO")
1546         << MatchTable::ULEB128Value(MMOIdx)
1547         // Encode number of address spaces to expect.
1548         << MatchTable::Comment("NumAddrSpace")
1549         << MatchTable::ULEB128Value(AddrSpaces.size());
1550   for (unsigned AS : AddrSpaces)
1551     Table << MatchTable::Comment("AddrSpace") << MatchTable::ULEB128Value(AS);
1552
1553   Table << MatchTable::LineBreak;
1554 }
1555
1556 //===- MemoryAlignmentPredicateMatcher ------------------------------------===//
1557
1558 bool MemoryAlignmentPredicateMatcher::isIdentical(
1559     const PredicateMatcher &B) const {
1560   if (!InstructionPredicateMatcher::isIdentical(B))
1561     return false;
1562   auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1563   return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1564 }
1565
1566 void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes(
1567     MatchTable &Table, RuleMatcher &Rule) const {
1568   Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1569         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1570         << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1571         << MatchTable::Comment("MinAlign") << MatchTable::ULEB128Value(MinAlign)
1572         << MatchTable::LineBreak;
1573 }
1574
1575 //===- MemoryVsLLTSizePredicateMatcher ------------------------------------===//
1576
1577 bool MemoryVsLLTSizePredicateMatcher::isIdentical(
1578     const PredicateMatcher &B) const {
1579   return InstructionPredicateMatcher::isIdentical(B) &&
1580          MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1581          Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1582          OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1583 }
1584
1585 void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes(
1586     MatchTable &Table, RuleMatcher &Rule) const {
1587   Table << MatchTable::Opcode(
1588                Relation == EqualTo       ? "GIM_CheckMemorySizeEqualToLLT"
1589                : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT"
1590                                          : "GIM_CheckMemorySizeLessThanLLT")
1591         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1592         << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1593         << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
1594         << MatchTable::LineBreak;
1595 }
1596
1597 //===- VectorSplatImmPredicateMatcher -------------------------------------===//
1598
1599 void VectorSplatImmPredicateMatcher::emitPredicateOpcodes(
1600     MatchTable &Table, RuleMatcher &Rule) const {
1601   if (Kind == AllOnes)
1602     Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");
1603   else
1604     Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");
1605
1606   Table << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);
1607   Table << MatchTable::LineBreak;
1608 }
1609
1610 //===- GenericInstructionPredicateMatcher ---------------------------------===//
1611
1612 GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(
1613     unsigned InsnVarID, TreePredicateFn Predicate)
1614     : GenericInstructionPredicateMatcher(InsnVarID,
1615                                          getEnumNameForPredicate(Predicate)) {}
1616
1617 bool GenericInstructionPredicateMatcher::isIdentical(
1618     const PredicateMatcher &B) const {
1619   return InstructionPredicateMatcher::isIdentical(B) &&
1620          EnumVal ==
1621              static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;
1622 }
1623 void GenericInstructionPredicateMatcher::emitPredicateOpcodes(
1624     MatchTable &Table, RuleMatcher &Rule) const {
1625   Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
1626         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1627         << MatchTable::Comment("FnId") << MatchTable::NamedValue(2, EnumVal)
1628         << MatchTable::LineBreak;
1629 }
1630
1631 //===- MIFlagsInstructionPredicateMatcher ---------------------------------===//
1632
1633 bool MIFlagsInstructionPredicateMatcher::isIdentical(
1634     const PredicateMatcher &B) const {
1635   if (!InstructionPredicateMatcher::isIdentical(B))
1636     return false;
1637   const auto &Other =
1638       static_cast<const MIFlagsInstructionPredicateMatcher &>(B);
1639   return Flags == Other.Flags && CheckNot == Other.CheckNot;
1640 }
1641
1642 void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes(
1643     MatchTable &Table, RuleMatcher &Rule) const {
1644   Table << MatchTable::Opcode(CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags")
1645         << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1646         << MatchTable::NamedValue(4, join(Flags, " | "))
1647         << MatchTable::LineBreak;
1648 }
1649
1650 //===- InstructionMatcher -------------------------------------------------===//
1651
1652 OperandMatcher &
1653 InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,
1654                                unsigned AllocatedTemporariesBaseID) {
1655   Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
1656                                            AllocatedTemporariesBaseID));
1657   if (!SymbolicName.empty())
1658     Rule.defineOperand(SymbolicName, *Operands.back());
1659
1660   return *Operands.back();
1661 }
1662
1663 OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) {
1664   auto I = llvm::find_if(Operands,
1665                          [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1666                            return X->getOpIdx() == OpIdx;
1667                          });
1668   if (I != Operands.end())
1669     return **I;
1670   llvm_unreachable("Failed to lookup operand");
1671 }
1672
1673 OperandMatcher &InstructionMatcher::addPhysRegInput(Record *Reg, unsigned OpIdx,
1674                                                     unsigned TempOpIdx) {
1675   assert(SymbolicName.empty());
1676   OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
1677   Operands.emplace_back(OM);
1678   Rule.definePhysRegOperand(Reg, *OM);
1679   PhysRegInputs.emplace_back(Reg, OpIdx);
1680   return *OM;
1681 }
1682
1683 void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table,
1684                                               RuleMatcher &Rule) {
1685   if (NumOperandsCheck)
1686     InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
1687         .emitPredicateOpcodes(Table, Rule);
1688
1689   // First emit all instruction level predicates need to be verified before we
1690   // can verify operands.
1691   emitFilteredPredicateListOpcodes(
1692       [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table,
1693       Rule);
1694
1695   // Emit all operand constraints.
1696   for (const auto &Operand : Operands)
1697     Operand->emitPredicateOpcodes(Table, Rule);
1698
1699   // All of the tablegen defined predicates should now be matched. Now emit
1700   // any custom predicates that rely on all generated checks.
1701   emitFilteredPredicateListOpcodes(
1702       [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table,
1703       Rule);
1704 }
1705
1706 bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) {
1707   // Instruction matchers involving more operands have higher priority.
1708   if (Operands.size() > B.Operands.size())
1709     return true;
1710   if (Operands.size() < B.Operands.size())
1711     return false;
1712
1713   for (auto &&P : zip(predicates(), B.predicates())) {
1714     auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
1715     auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
1716     if (L->isHigherPriorityThan(*R))
1717       return true;
1718     if (R->isHigherPriorityThan(*L))
1719       return false;
1720   }
1721
1722   for (auto Operand : zip(Operands, B.Operands)) {
1723     if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
1724       return true;
1725     if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
1726       return false;
1727   }
1728
1729   return false;
1730 }
1731
1732 unsigned InstructionMatcher::countRendererFns() {
1733   return std::accumulate(
1734              predicates().begin(), predicates().end(), 0,
1735              [](unsigned A,
1736                 const std::unique_ptr<PredicateMatcher> &Predicate) {
1737                return A + Predicate->countRendererFns();
1738              }) +
1739          std::accumulate(
1740              Operands.begin(), Operands.end(), 0,
1741              [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
1742                return A + Operand->countRendererFns();
1743              });
1744 }
1745
1746 void InstructionMatcher::optimize() {
1747   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
1748   const auto &OpcMatcher = getOpcodeMatcher();
1749
1750   Stash.push_back(predicates_pop_front());
1751   if (Stash.back().get() == &OpcMatcher) {
1752     if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands() &&
1753         getNumOperands() != 0)
1754       Stash.emplace_back(
1755           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
1756     NumOperandsCheck = false;
1757
1758     for (auto &OM : Operands)
1759       for (auto &OP : OM->predicates())
1760         if (isa<IntrinsicIDOperandMatcher>(OP)) {
1761           Stash.push_back(std::move(OP));
1762           OM->eraseNullPredicates();
1763           break;
1764         }
1765   }
1766
1767   if (InsnVarID > 0) {
1768     assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
1769     for (auto &OP : Operands[0]->predicates())
1770       OP.reset();
1771     Operands[0]->eraseNullPredicates();
1772   }
1773   for (auto &OM : Operands) {
1774     for (auto &OP : OM->predicates())
1775       if (isa<LLTOperandMatcher>(OP))
1776         Stash.push_back(std::move(OP));
1777     OM->eraseNullPredicates();
1778   }
1779   while (!Stash.empty())
1780     prependPredicate(Stash.pop_back_val());
1781 }
1782
1783 //===- InstructionOperandMatcher ------------------------------------------===//
1784
1785 void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table,
1786                                                    RuleMatcher &Rule) const {
1787   const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
1788   const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1789   Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies"
1790                                            : "GIM_RecordInsn")
1791         << MatchTable::Comment("DefineMI")
1792         << MatchTable::ULEB128Value(NewInsnVarID) << MatchTable::Comment("MI")
1793         << MatchTable::ULEB128Value(getInsnVarID())
1794         << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(getOpIdx())
1795         << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
1796         << MatchTable::LineBreak;
1797 }
1798
1799 bool InstructionOperandMatcher::isHigherPriorityThan(
1800     const OperandPredicateMatcher &B) const {
1801   if (OperandPredicateMatcher::isHigherPriorityThan(B))
1802     return true;
1803   if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
1804     return false;
1805
1806   if (const InstructionOperandMatcher *BP =
1807           dyn_cast<InstructionOperandMatcher>(&B))
1808     if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
1809       return true;
1810   return false;
1811 }
1812
1813 //===- OperandRenderer ----------------------------------------------------===//
1814
1815 OperandRenderer::~OperandRenderer() {}
1816
1817 //===- CopyRenderer -------------------------------------------------------===//
1818
1819 void CopyRenderer::emitRenderOpcodes(MatchTable &Table,
1820                                      RuleMatcher &Rule) const {
1821   const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1822   unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1823   Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
1824         << MatchTable::ULEB128Value(NewInsnID)
1825         << MatchTable::Comment("OldInsnID")
1826         << MatchTable::ULEB128Value(OldInsnVarID)
1827         << MatchTable::Comment("OpIdx")
1828         << MatchTable::ULEB128Value(Operand.getOpIdx())
1829         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1830 }
1831
1832 //===- CopyPhysRegRenderer ------------------------------------------------===//
1833
1834 void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table,
1835                                             RuleMatcher &Rule) const {
1836   const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
1837   unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1838   Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
1839         << MatchTable::ULEB128Value(NewInsnID)
1840         << MatchTable::Comment("OldInsnID")
1841         << MatchTable::ULEB128Value(OldInsnVarID)
1842         << MatchTable::Comment("OpIdx")
1843         << MatchTable::ULEB128Value(Operand.getOpIdx())
1844         << MatchTable::Comment(PhysReg->getName()) << MatchTable::LineBreak;
1845 }
1846
1847 //===- CopyOrAddZeroRegRenderer -------------------------------------------===//
1848
1849 void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table,
1850                                                  RuleMatcher &Rule) const {
1851   const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1852   unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1853   Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
1854         << MatchTable::Comment("NewInsnID")
1855         << MatchTable::ULEB128Value(NewInsnID)
1856         << MatchTable::Comment("OldInsnID")
1857         << MatchTable::ULEB128Value(OldInsnVarID)
1858         << MatchTable::Comment("OpIdx")
1859         << MatchTable::ULEB128Value(Operand.getOpIdx())
1860         << MatchTable::NamedValue(
1861                2,
1862                (ZeroRegisterDef->getValue("Namespace")
1863                     ? ZeroRegisterDef->getValueAsString("Namespace")
1864                     : ""),
1865                ZeroRegisterDef->getName())
1866         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1867 }
1868
1869 //===- CopyConstantAsImmRenderer ------------------------------------------===//
1870
1871 void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table,
1872                                                   RuleMatcher &Rule) const {
1873   InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
1874   unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
1875   Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
1876                                      : "GIR_CopyConstantAsUImm")
1877         << MatchTable::Comment("NewInsnID")
1878         << MatchTable::ULEB128Value(NewInsnID)
1879         << MatchTable::Comment("OldInsnID")
1880         << MatchTable::ULEB128Value(OldInsnVarID)
1881         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1882 }
1883
1884 //===- CopyFConstantAsFPImmRenderer ---------------------------------------===//
1885
1886 void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table,
1887                                                      RuleMatcher &Rule) const {
1888   InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
1889   unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
1890   Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
1891         << MatchTable::Comment("NewInsnID")
1892         << MatchTable::ULEB128Value(NewInsnID)
1893         << MatchTable::Comment("OldInsnID")
1894         << MatchTable::ULEB128Value(OldInsnVarID)
1895         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1896 }
1897
1898 //===- CopySubRegRenderer -------------------------------------------------===//
1899
1900 void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table,
1901                                            RuleMatcher &Rule) const {
1902   const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1903   unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1904   Table << MatchTable::Opcode("GIR_CopySubReg")
1905         << MatchTable::Comment("NewInsnID")
1906         << MatchTable::ULEB128Value(NewInsnID)
1907         << MatchTable::Comment("OldInsnID")
1908         << MatchTable::ULEB128Value(OldInsnVarID)
1909         << MatchTable::Comment("OpIdx")
1910         << MatchTable::ULEB128Value(Operand.getOpIdx())
1911         << MatchTable::Comment("SubRegIdx")
1912         << MatchTable::IntValue(2, SubReg->EnumValue)
1913         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1914 }
1915
1916 //===- AddRegisterRenderer ------------------------------------------------===//
1917
1918 void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table,
1919                                             RuleMatcher &Rule) const {
1920   Table << MatchTable::Opcode("GIR_AddRegister")
1921         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID);
1922   if (RegisterDef->getName() != "zero_reg") {
1923     Table << MatchTable::NamedValue(
1924         2,
1925         (RegisterDef->getValue("Namespace")
1926              ? RegisterDef->getValueAsString("Namespace")
1927              : ""),
1928         RegisterDef->getName());
1929   } else {
1930     Table << MatchTable::NamedValue(2, Target.getRegNamespace(), "NoRegister");
1931   }
1932   Table << MatchTable::Comment("AddRegisterRegFlags");
1933
1934   // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
1935   // really needed for a physical register reference. We can pack the
1936   // register and flags in a single field.
1937   if (IsDef)
1938     Table << MatchTable::NamedValue(2, "RegState::Define");
1939   else
1940     Table << MatchTable::IntValue(2, 0);
1941   Table << MatchTable::LineBreak;
1942 }
1943
1944 //===- TempRegRenderer ----------------------------------------------------===//
1945
1946 void TempRegRenderer::emitRenderOpcodes(MatchTable &Table,
1947                                         RuleMatcher &Rule) const {
1948   const bool NeedsFlags = (SubRegIdx || IsDef);
1949   if (SubRegIdx) {
1950     assert(!IsDef);
1951     Table << MatchTable::Opcode("GIR_AddTempSubRegister");
1952   } else
1953     Table << MatchTable::Opcode(NeedsFlags ? "GIR_AddTempRegister"
1954                                            : "GIR_AddSimpleTempRegister");
1955
1956   Table << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
1957         << MatchTable::Comment("TempRegID")
1958         << MatchTable::ULEB128Value(TempRegID);
1959
1960   if (!NeedsFlags) {
1961     Table << MatchTable::LineBreak;
1962     return;
1963   }
1964
1965   Table << MatchTable::Comment("TempRegFlags");
1966   if (IsDef) {
1967     SmallString<32> RegFlags;
1968     RegFlags += "RegState::Define";
1969     if (IsDead)
1970       RegFlags += "|RegState::Dead";
1971     Table << MatchTable::NamedValue(2, RegFlags);
1972   } else
1973     Table << MatchTable::IntValue(2, 0);
1974
1975   if (SubRegIdx)
1976     Table << MatchTable::NamedValue(2, SubRegIdx->getQualifiedName());
1977   Table << MatchTable::LineBreak;
1978 }
1979
1980 //===- ImmRenderer --------------------------------------------------------===//
1981
1982 void ImmRenderer::emitAddImm(MatchTable &Table, RuleMatcher &RM,
1983                              unsigned InsnID, int64_t Imm, StringRef ImmName) {
1984   const bool IsInt8 = isInt<8>(Imm);
1985
1986   Table << MatchTable::Opcode(IsInt8 ? "GIR_AddImm8" : "GIR_AddImm")
1987         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
1988         << MatchTable::Comment(ImmName)
1989         << MatchTable::IntValue(IsInt8 ? 1 : 8, Imm) << MatchTable::LineBreak;
1990 }
1991
1992 void ImmRenderer::emitRenderOpcodes(MatchTable &Table,
1993                                     RuleMatcher &Rule) const {
1994   if (CImmLLT) {
1995     assert(Table.isCombiner() &&
1996            "ConstantInt immediate are only for combiners!");
1997     Table << MatchTable::Opcode("GIR_AddCImm") << MatchTable::Comment("InsnID")
1998           << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Type")
1999           << *CImmLLT << MatchTable::Comment("Imm")
2000           << MatchTable::IntValue(8, Imm) << MatchTable::LineBreak;
2001   } else
2002     emitAddImm(Table, Rule, InsnID, Imm);
2003 }
2004
2005 //===- SubRegIndexRenderer ------------------------------------------------===//
2006
2007 void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table,
2008                                             RuleMatcher &Rule) const {
2009   ImmRenderer::emitAddImm(Table, Rule, InsnID, SubRegIdx->EnumValue,
2010                           "SubRegIndex");
2011 }
2012
2013 //===- RenderComplexPatternOperand ----------------------------------------===//
2014
2015 void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table,
2016                                                     RuleMatcher &Rule) const {
2017   Table << MatchTable::Opcode(
2018                SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer"
2019                                     : "GIR_ComplexSubOperandRenderer")
2020                           : "GIR_ComplexRenderer")
2021         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2022         << MatchTable::Comment("RendererID")
2023         << MatchTable::IntValue(2, RendererID);
2024   if (SubOperand)
2025     Table << MatchTable::Comment("SubOperand")
2026           << MatchTable::ULEB128Value(*SubOperand);
2027   if (SubReg)
2028     Table << MatchTable::Comment("SubRegIdx")
2029           << MatchTable::IntValue(2, SubReg->EnumValue);
2030   Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2031 }
2032
2033 //===- CustomRenderer -----------------------------------------------------===//
2034
2035 void CustomRenderer::emitRenderOpcodes(MatchTable &Table,
2036                                        RuleMatcher &Rule) const {
2037   InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2038   unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2039   Table << MatchTable::Opcode("GIR_CustomRenderer")
2040         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2041         << MatchTable::Comment("OldInsnID")
2042         << MatchTable::ULEB128Value(OldInsnVarID)
2043         << MatchTable::Comment("Renderer")
2044         << MatchTable::NamedValue(
2045                2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
2046         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2047 }
2048
2049 //===- CustomOperandRenderer ----------------------------------------------===//
2050
2051 void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table,
2052                                               RuleMatcher &Rule) const {
2053   const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2054   Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2055         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2056         << MatchTable::Comment("OldInsnID")
2057         << MatchTable::ULEB128Value(OpdMatcher.getInsnVarID())
2058         << MatchTable::Comment("OpIdx")
2059         << MatchTable::ULEB128Value(OpdMatcher.getOpIdx())
2060         << MatchTable::Comment("OperandRenderer")
2061         << MatchTable::NamedValue(
2062                2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
2063         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2064 }
2065
2066 //===- CustomCXXAction ----------------------------------------------------===//
2067
2068 void CustomCXXAction::emitActionOpcodes(MatchTable &Table,
2069                                         RuleMatcher &Rule) const {
2070   Table << MatchTable::Opcode("GIR_CustomAction")
2071         << MatchTable::NamedValue(2, FnEnumName) << MatchTable::LineBreak;
2072 }
2073
2074 //===- BuildMIAction ------------------------------------------------------===//
2075
2076 bool BuildMIAction::canMutate(RuleMatcher &Rule,
2077                               const InstructionMatcher *Insn) const {
2078   if (!Insn)
2079     return false;
2080
2081   if (OperandRenderers.size() != Insn->getNumOperands())
2082     return false;
2083
2084   for (const auto &Renderer : enumerate(OperandRenderers)) {
2085     if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2086       const OperandMatcher &OM =
2087           Rule.getOperandMatcher(Copy->getSymbolicName());
2088       if (Insn != &OM.getInstructionMatcher() ||
2089           OM.getOpIdx() != Renderer.index())
2090         return false;
2091     } else
2092       return false;
2093   }
2094
2095   return true;
2096 }
2097
2098 void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) {
2099   for (auto *MutateCandidate : Rule.mutatable_insns()) {
2100     if (canMutate(Rule, MutateCandidate)) {
2101       // Take the first one we're offered that we're able to mutate.
2102       Rule.reserveInsnMatcherForMutation(MutateCandidate);
2103       Matched = MutateCandidate;
2104       return;
2105     }
2106   }
2107 }
2108
2109 void BuildMIAction::emitActionOpcodes(MatchTable &Table,
2110                                       RuleMatcher &Rule) const {
2111   const auto AddMIFlags = [&]() {
2112     for (const InstructionMatcher *IM : CopiedFlags) {
2113       Table << MatchTable::Opcode("GIR_CopyMIFlags")
2114             << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2115             << MatchTable::Comment("OldInsnID")
2116             << MatchTable::ULEB128Value(IM->getInsnVarID())
2117             << MatchTable::LineBreak;
2118     }
2119
2120     if (!SetFlags.empty()) {
2121       Table << MatchTable::Opcode("GIR_SetMIFlags")
2122             << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2123             << MatchTable::NamedValue(4, join(SetFlags, " | "))
2124             << MatchTable::LineBreak;
2125     }
2126
2127     if (!UnsetFlags.empty()) {
2128       Table << MatchTable::Opcode("GIR_UnsetMIFlags")
2129             << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2130             << MatchTable::NamedValue(4, join(UnsetFlags, " | "))
2131             << MatchTable::LineBreak;
2132     }
2133   };
2134
2135   if (Matched) {
2136     assert(canMutate(Rule, Matched) &&
2137            "Arranged to mutate an insn that isn't mutatable");
2138
2139     unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2140     Table << MatchTable::Opcode("GIR_MutateOpcode")
2141           << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2142           << MatchTable::Comment("RecycleInsnID")
2143           << MatchTable::ULEB128Value(RecycleInsnID)
2144           << MatchTable::Comment("Opcode")
2145           << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName())
2146           << MatchTable::LineBreak;
2147
2148     if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2149       for (auto *Def : I->ImplicitDefs) {
2150         auto Namespace = Def->getValue("Namespace")
2151                              ? Def->getValueAsString("Namespace")
2152                              : "";
2153         const bool IsDead = DeadImplicitDefs.contains(Def);
2154         Table << MatchTable::Opcode("GIR_AddImplicitDef")
2155               << MatchTable::Comment("InsnID")
2156               << MatchTable::ULEB128Value(InsnID)
2157               << MatchTable::NamedValue(2, Namespace, Def->getName())
2158               << (IsDead ? MatchTable::NamedValue(2, "RegState", "Dead")
2159                          : MatchTable::IntValue(2, 0))
2160               << MatchTable::LineBreak;
2161       }
2162       for (auto *Use : I->ImplicitUses) {
2163         auto Namespace = Use->getValue("Namespace")
2164                              ? Use->getValueAsString("Namespace")
2165                              : "";
2166         Table << MatchTable::Opcode("GIR_AddImplicitUse")
2167               << MatchTable::Comment("InsnID")
2168               << MatchTable::ULEB128Value(InsnID)
2169               << MatchTable::NamedValue(2, Namespace, Use->getName())
2170               << MatchTable::LineBreak;
2171       }
2172     }
2173
2174     AddMIFlags();
2175
2176     // Mark the mutated instruction as erased.
2177     Rule.tryEraseInsnID(RecycleInsnID);
2178     return;
2179   }
2180
2181   // TODO: Simple permutation looks like it could be almost as common as
2182   //       mutation due to commutative operations.
2183
2184   Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2185         << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Opcode")
2186         << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName())
2187         << MatchTable::LineBreak;
2188   for (const auto &Renderer : OperandRenderers)
2189     Renderer->emitRenderOpcodes(Table, Rule);
2190
2191   for (auto [OpIdx, Def] : enumerate(I->ImplicitDefs)) {
2192     auto Namespace =
2193         Def->getValue("Namespace") ? Def->getValueAsString("Namespace") : "";
2194     if (DeadImplicitDefs.contains(Def)) {
2195       Table
2196           << MatchTable::Opcode("GIR_SetImplicitDefDead")
2197           << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2198           << MatchTable::Comment(
2199                  ("OpIdx for " + Namespace + "::" + Def->getName() + "").str())
2200           << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
2201     }
2202   }
2203
2204   if (I->mayLoad || I->mayStore) {
2205     // Emit the ID's for all the instructions that are matched by this rule.
2206     // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2207     //       some other means of having a memoperand. Also limit this to
2208     //       emitted instructions that expect to have a memoperand too. For
2209     //       example, (G_SEXT (G_LOAD x)) that results in separate load and
2210     //       sign-extend instructions shouldn't put the memoperand on the
2211     //       sign-extend since it has no effect there.
2212
2213     std::vector<unsigned> MergeInsnIDs;
2214     for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2215       MergeInsnIDs.push_back(IDMatcherPair.second);
2216     llvm::sort(MergeInsnIDs);
2217
2218     Table << MatchTable::Opcode("GIR_MergeMemOperands")
2219           << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2220           << MatchTable::Comment("NumInsns")
2221           << MatchTable::IntValue(1, MergeInsnIDs.size())
2222           << MatchTable::Comment("MergeInsnID's");
2223     for (const auto &MergeInsnID : MergeInsnIDs)
2224       Table << MatchTable::ULEB128Value(MergeInsnID);
2225     Table << MatchTable::LineBreak;
2226   }
2227
2228   AddMIFlags();
2229 }
2230
2231 //===- BuildConstantAction ------------------------------------------------===//
2232
2233 void BuildConstantAction::emitActionOpcodes(MatchTable &Table,
2234                                             RuleMatcher &Rule) const {
2235   Table << MatchTable::Opcode("GIR_BuildConstant")
2236         << MatchTable::Comment("TempRegID")
2237         << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("Val")
2238         << MatchTable::IntValue(8, Val) << MatchTable::LineBreak;
2239 }
2240
2241 //===- EraseInstAction ----------------------------------------------------===//
2242
2243 void EraseInstAction::emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
2244                                         unsigned InsnID) {
2245   // Avoid erasing the same inst twice.
2246   if (!Rule.tryEraseInsnID(InsnID))
2247     return;
2248
2249   Table << MatchTable::Opcode("GIR_EraseFromParent")
2250         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2251         << MatchTable::LineBreak;
2252 }
2253
2254 void EraseInstAction::emitActionOpcodes(MatchTable &Table,
2255                                         RuleMatcher &Rule) const {
2256   emitActionOpcodes(Table, Rule, InsnID);
2257 }
2258
2259 //===- ReplaceRegAction ---------------------------------------------------===//
2260
2261 void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table,
2262                                                 RuleMatcher &Rule) const {
2263   if (TempRegID != (unsigned)-1)
2264     return;
2265
2266   Table << MatchTable::Opcode("GIM_CheckCanReplaceReg")
2267         << MatchTable::Comment("OldInsnID")
2268         << MatchTable::ULEB128Value(OldInsnID)
2269         << MatchTable::Comment("OldOpIdx") << MatchTable::ULEB128Value(OldOpIdx)
2270         << MatchTable::Comment("NewInsnId")
2271         << MatchTable::ULEB128Value(NewInsnId)
2272         << MatchTable::Comment("NewOpIdx") << MatchTable::ULEB128Value(NewOpIdx)
2273         << MatchTable::LineBreak;
2274 }
2275
2276 void ReplaceRegAction::emitActionOpcodes(MatchTable &Table,
2277                                          RuleMatcher &Rule) const {
2278   if (TempRegID != (unsigned)-1) {
2279     Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg")
2280           << MatchTable::Comment("OldInsnID")
2281           << MatchTable::ULEB128Value(OldInsnID)
2282           << MatchTable::Comment("OldOpIdx")
2283           << MatchTable::ULEB128Value(OldOpIdx)
2284           << MatchTable::Comment("TempRegID")
2285           << MatchTable::ULEB128Value(TempRegID) << MatchTable::LineBreak;
2286   } else {
2287     Table << MatchTable::Opcode("GIR_ReplaceReg")
2288           << MatchTable::Comment("OldInsnID")
2289           << MatchTable::ULEB128Value(OldInsnID)
2290           << MatchTable::Comment("OldOpIdx")
2291           << MatchTable::ULEB128Value(OldOpIdx)
2292           << MatchTable::Comment("NewInsnId")
2293           << MatchTable::ULEB128Value(NewInsnId)
2294           << MatchTable::Comment("NewOpIdx")
2295           << MatchTable::ULEB128Value(NewOpIdx) << MatchTable::LineBreak;
2296   }
2297 }
2298
2299 //===- ConstrainOperandToRegClassAction -----------------------------------===//
2300
2301 void ConstrainOperandToRegClassAction::emitActionOpcodes(
2302     MatchTable &Table, RuleMatcher &Rule) const {
2303   Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2304         << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2305         << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
2306         << MatchTable::NamedValue(2, RC.getQualifiedIdName())
2307         << MatchTable::LineBreak;
2308 }
2309
2310 //===- MakeTempRegisterAction ---------------------------------------------===//
2311
2312 void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table,
2313                                                RuleMatcher &Rule) const {
2314   Table << MatchTable::Opcode("GIR_MakeTempReg")
2315         << MatchTable::Comment("TempRegID")
2316         << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("TypeID")
2317         << Ty << MatchTable::LineBreak;
2318 }
2319
2320 } // namespace gi
2321 } // namespace llvm