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 "Common/CodeGenInstruction.h" 11 #include "Common/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(ArrayRef<const Record *> FeatureBitset, 84 int HwModeIdx) { 85 std::string Name = "GIFBS"; 86 for (const Record *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::tuple(Ty.isScalable(), 412 Ty.getElementCount().getKnownMinValue()) < 413 std::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::tuple(Ty.isScalable(), 420 Ty.getSizeInBits().getKnownMinValue()) < 421 std::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 Matchers = optimizeRules<GroupMatcher>(Matchers, MatcherStorage); 549 Matchers = optimizeRules<SwitchMatcher>(Matchers, MatcherStorage); 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 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() { 691 InstructionMatcher &InsnMatcher = *Matchers.front(); 692 if (!InsnMatcher.predicates_empty()) 693 if (const auto *TM = 694 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin())) 695 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0) 696 return TM->getTy(); 697 return {}; 698 } 699 700 void RuleMatcher::optimize() { 701 for (auto &Item : InsnVariableIDs) { 702 InstructionMatcher &InsnMatcher = *Item.first; 703 for (auto &OM : InsnMatcher.operands()) { 704 // Complex Patterns are usually expensive and they relatively rarely fail 705 // on their own: more often we end up throwing away all the work done by a 706 // matching part of a complex pattern because some other part of the 707 // enclosing pattern didn't match. All of this makes it beneficial to 708 // delay complex patterns until the very end of the rule matching, 709 // especially for targets having lots of complex patterns. 710 for (auto &OP : OM->predicates()) 711 if (isa<ComplexPatternOperandMatcher>(OP)) 712 EpilogueMatchers.emplace_back(std::move(OP)); 713 OM->eraseNullPredicates(); 714 } 715 InsnMatcher.optimize(); 716 } 717 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L, 718 const std::unique_ptr<PredicateMatcher> &R) { 719 return std::tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) < 720 std::tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx()); 721 }); 722 723 // Deduplicate EraseInst actions, and if an EraseInst erases the root, place 724 // it at the end to favor generation of GIR_EraseRootFromParent_Done 725 DenseSet<unsigned> AlreadySeenEraseInsts; 726 auto EraseRootIt = Actions.end(); 727 auto It = Actions.begin(); 728 while (It != Actions.end()) { 729 if (const auto *EI = dyn_cast<EraseInstAction>(It->get())) { 730 unsigned InstID = EI->getInsnID(); 731 if (!AlreadySeenEraseInsts.insert(InstID).second) { 732 It = Actions.erase(It); 733 continue; 734 } 735 736 if (InstID == 0) 737 EraseRootIt = It; 738 } 739 740 ++It; 741 } 742 743 if (EraseRootIt != Actions.end()) 744 Actions.splice(Actions.end(), Actions, EraseRootIt); 745 } 746 747 bool RuleMatcher::hasFirstCondition() const { 748 if (insnmatchers_empty()) 749 return false; 750 InstructionMatcher &Matcher = insnmatchers_front(); 751 if (!Matcher.predicates_empty()) 752 return true; 753 for (auto &OM : Matcher.operands()) 754 for (auto &OP : OM->predicates()) 755 if (!isa<InstructionOperandMatcher>(OP)) 756 return true; 757 return false; 758 } 759 760 const PredicateMatcher &RuleMatcher::getFirstCondition() const { 761 assert(!insnmatchers_empty() && 762 "Trying to get a condition from an empty RuleMatcher"); 763 764 InstructionMatcher &Matcher = insnmatchers_front(); 765 if (!Matcher.predicates_empty()) 766 return **Matcher.predicates_begin(); 767 // If there is no more predicate on the instruction itself, look at its 768 // operands. 769 for (auto &OM : Matcher.operands()) 770 for (auto &OP : OM->predicates()) 771 if (!isa<InstructionOperandMatcher>(OP)) 772 return *OP; 773 774 llvm_unreachable("Trying to get a condition from an InstructionMatcher with " 775 "no conditions"); 776 } 777 778 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() { 779 assert(!insnmatchers_empty() && 780 "Trying to pop a condition from an empty RuleMatcher"); 781 782 InstructionMatcher &Matcher = insnmatchers_front(); 783 if (!Matcher.predicates_empty()) 784 return Matcher.predicates_pop_front(); 785 // If there is no more predicate on the instruction itself, look at its 786 // operands. 787 for (auto &OM : Matcher.operands()) 788 for (auto &OP : OM->predicates()) 789 if (!isa<InstructionOperandMatcher>(OP)) { 790 std::unique_ptr<PredicateMatcher> Result = std::move(OP); 791 OM->eraseNullPredicates(); 792 return Result; 793 } 794 795 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with " 796 "no conditions"); 797 } 798 799 GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R, 800 StringRef FlagName, 801 GISelFlags FlagBit) { 802 // If the value of a flag is unset, ignore it. 803 // If it's set, it always takes precedence over the existing value so 804 // clear/set the corresponding bit. 805 bool Unset = false; 806 bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset); 807 if (!Unset) 808 return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit); 809 return CurFlags; 810 } 811 812 SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) { 813 if (!R || !R->isSubClassOf("GISelFlags")) 814 return {Flags, Flags}; 815 816 assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) && 817 "GISelFlags is only expected on Pattern/PatFrags!"); 818 819 GISelFlags NewFlags = 820 updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies); 821 return {Flags, NewFlags}; 822 } 823 824 Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName, 825 const Record *ComplexPattern, 826 unsigned RendererID, 827 unsigned SubOperandID, 828 StringRef ParentSymbolicName) { 829 std::string ParentName(ParentSymbolicName); 830 if (ComplexSubOperands.count(SymbolicName)) { 831 const std::string &RecordedParentName = 832 ComplexSubOperandsParentName[SymbolicName]; 833 if (RecordedParentName != ParentName) 834 return failUnsupported("Error: Complex suboperand " + SymbolicName + 835 " referenced by different operands: " + 836 RecordedParentName + " and " + ParentName + "."); 837 // Complex suboperand referenced more than once from same the operand is 838 // used to generate 'same operand check'. Emitting of 839 // GIR_ComplexSubOperandRenderer for them is already handled. 840 return Error::success(); 841 } 842 843 ComplexSubOperands[SymbolicName] = {ComplexPattern, RendererID, SubOperandID}; 844 ComplexSubOperandsParentName[SymbolicName] = std::move(ParentName); 845 846 return Error::success(); 847 } 848 849 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) { 850 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName)); 851 MutatableInsns.insert(Matchers.back().get()); 852 return *Matchers.back(); 853 } 854 855 void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) { 856 RequiredSimplePredicates.push_back(PredName.str()); 857 } 858 859 const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() { 860 return RequiredSimplePredicates; 861 } 862 863 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) { 864 unsigned NewInsnVarID = NextInsnVarID++; 865 InsnVariableIDs[&Matcher] = NewInsnVarID; 866 return NewInsnVarID; 867 } 868 869 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const { 870 const auto &I = InsnVariableIDs.find(&InsnMatcher); 871 if (I != InsnVariableIDs.end()) 872 return I->second; 873 llvm_unreachable("Matched Insn was not captured in a local variable"); 874 } 875 876 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) { 877 if (DefinedOperands.try_emplace(SymbolicName, &OM).second) 878 return; 879 880 // If the operand is already defined, then we must ensure both references in 881 // the matcher have the exact same node. 882 RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher(); 883 OM.addPredicate<SameOperandMatcher>( 884 OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(), 885 RM.getGISelFlags()); 886 } 887 888 void RuleMatcher::definePhysRegOperand(const Record *Reg, OperandMatcher &OM) { 889 PhysRegOperands.try_emplace(Reg, &OM); 890 } 891 892 InstructionMatcher & 893 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const { 894 for (const auto &I : InsnVariableIDs) 895 if (I.first->getSymbolicName() == SymbolicName) 896 return *I.first; 897 llvm_unreachable( 898 ("Failed to lookup instruction " + SymbolicName).str().c_str()); 899 } 900 901 const OperandMatcher & 902 RuleMatcher::getPhysRegOperandMatcher(const Record *Reg) const { 903 const auto &I = PhysRegOperands.find(Reg); 904 905 if (I == PhysRegOperands.end()) { 906 PrintFatalError(SrcLoc, "Register " + Reg->getName() + 907 " was not declared in matcher"); 908 } 909 910 return *I->second; 911 } 912 913 OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) { 914 const auto &I = DefinedOperands.find(Name); 915 916 if (I == DefinedOperands.end()) 917 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher"); 918 919 return *I->second; 920 } 921 922 const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const { 923 const auto &I = DefinedOperands.find(Name); 924 925 if (I == DefinedOperands.end()) 926 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher"); 927 928 return *I->second; 929 } 930 931 void RuleMatcher::emit(MatchTable &Table) { 932 if (Matchers.empty()) 933 llvm_unreachable("Unexpected empty matcher!"); 934 935 // The representation supports rules that require multiple roots such as: 936 // %ptr(p0) = ... 937 // %elt0(s32) = G_LOAD %ptr 938 // %1(p0) = G_ADD %ptr, 4 939 // %elt1(s32) = G_LOAD p0 %1 940 // which could be usefully folded into: 941 // %ptr(p0) = ... 942 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr 943 // on some targets but we don't need to make use of that yet. 944 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); 945 946 unsigned LabelID = Table.allocateLabelID(); 947 Table << MatchTable::Opcode("GIM_Try", +1) 948 << MatchTable::Comment("On fail goto") 949 << MatchTable::JumpTarget(LabelID) 950 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str()) 951 << MatchTable::LineBreak; 952 953 if (!RequiredFeatures.empty() || HwModeIdx >= 0) { 954 Table << MatchTable::Opcode("GIM_CheckFeatures") 955 << MatchTable::NamedValue( 956 2, getNameForFeatureBitset(RequiredFeatures, HwModeIdx)) 957 << MatchTable::LineBreak; 958 } 959 960 if (!RequiredSimplePredicates.empty()) { 961 for (const auto &Pred : RequiredSimplePredicates) { 962 Table << MatchTable::Opcode("GIM_CheckSimplePredicate") 963 << MatchTable::NamedValue(2, Pred) << MatchTable::LineBreak; 964 } 965 } 966 967 Matchers.front()->emitPredicateOpcodes(Table, *this); 968 969 // Check if it's safe to replace registers. 970 for (const auto &MA : Actions) 971 MA->emitAdditionalPredicates(Table, *this); 972 973 // We must also check if it's safe to fold the matched instructions. 974 if (InsnVariableIDs.size() >= 2) { 975 976 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or 977 // account for unsafe cases. 978 // 979 // Example: 980 // MI1--> %0 = ... 981 // %1 = ... %0 982 // MI0--> %2 = ... %0 983 // It's not safe to erase MI1. We currently handle this by not 984 // erasing %0 (even when it's dead). 985 // 986 // Example: 987 // MI1--> %0 = load volatile @a 988 // %1 = load volatile @a 989 // MI0--> %2 = ... %0 990 // It's not safe to sink %0's def past %1. We currently handle 991 // this by rejecting all loads. 992 // 993 // Example: 994 // MI1--> %0 = load @a 995 // %1 = store @a 996 // MI0--> %2 = ... %0 997 // It's not safe to sink %0's def past %1. We currently handle 998 // this by rejecting all loads. 999 // 1000 // Example: 1001 // G_CONDBR %cond, @BB1 1002 // BB0: 1003 // MI1--> %0 = load @a 1004 // G_BR @BB1 1005 // BB1: 1006 // MI0--> %2 = ... %0 1007 // It's not always safe to sink %0 across control flow. In this 1008 // case it may introduce a memory fault. We currentl handle 1009 // this by rejecting all loads. 1010 1011 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold") 1012 << MatchTable::Comment("NumInsns") 1013 << MatchTable::IntValue(1, InsnVariableIDs.size() - 1) 1014 << MatchTable::LineBreak; 1015 } 1016 1017 for (const auto &PM : EpilogueMatchers) 1018 PM->emitPredicateOpcodes(Table, *this); 1019 1020 if (!CustomCXXAction.empty()) { 1021 /// Handle combiners relying on custom C++ code instead of actions. 1022 assert(Table.isCombiner() && "CustomCXXAction is only for combiners!"); 1023 // We cannot have actions other than debug comments. 1024 assert(none_of(Actions, [](auto &A) { 1025 return A->getKind() != MatchAction::AK_DebugComment; 1026 })); 1027 for (const auto &MA : Actions) 1028 MA->emitActionOpcodes(Table, *this); 1029 Table << MatchTable::Opcode("GIR_DoneWithCustomAction", -1) 1030 << MatchTable::Comment("Fn") 1031 << MatchTable::NamedValue(2, CustomCXXAction) 1032 << MatchTable::LineBreak; 1033 } else { 1034 // Emit all actions except the last one, then emit coverage and emit the 1035 // final action. 1036 // 1037 // This is because some actions, such as GIR_EraseRootFromParent_Done, also 1038 // double as a GIR_Done and terminate execution of the rule. 1039 if (!Actions.empty()) { 1040 for (const auto &MA : drop_end(Actions)) 1041 MA->emitActionOpcodes(Table, *this); 1042 } 1043 1044 assert((Table.isWithCoverage() ? !Table.isCombiner() : true) && 1045 "Combiner tables don't support coverage!"); 1046 if (Table.isWithCoverage()) 1047 Table << MatchTable::Opcode("GIR_Coverage") 1048 << MatchTable::IntValue(4, RuleID) << MatchTable::LineBreak; 1049 else if (!Table.isCombiner()) 1050 Table << MatchTable::Comment( 1051 ("GIR_Coverage, " + Twine(RuleID) + ",").str()) 1052 << MatchTable::LineBreak; 1053 1054 if (Actions.empty() || 1055 !Actions.back()->emitActionOpcodesAndDone(Table, *this)) { 1056 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak; 1057 } 1058 } 1059 1060 Table << MatchTable::Label(LabelID); 1061 ++NumPatternEmitted; 1062 } 1063 1064 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const { 1065 // Rules involving more match roots have higher priority. 1066 if (Matchers.size() > B.Matchers.size()) 1067 return true; 1068 if (Matchers.size() < B.Matchers.size()) 1069 return false; 1070 1071 for (auto Matcher : zip(Matchers, B.Matchers)) { 1072 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher))) 1073 return true; 1074 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher))) 1075 return false; 1076 } 1077 1078 return false; 1079 } 1080 1081 unsigned RuleMatcher::countRendererFns() const { 1082 return std::accumulate( 1083 Matchers.begin(), Matchers.end(), 0, 1084 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) { 1085 return A + Matcher->countRendererFns(); 1086 }); 1087 } 1088 1089 //===- PredicateMatcher ---------------------------------------------------===// 1090 1091 PredicateMatcher::~PredicateMatcher() {} 1092 1093 //===- OperandPredicateMatcher --------------------------------------------===// 1094 1095 OperandPredicateMatcher::~OperandPredicateMatcher() {} 1096 1097 bool OperandPredicateMatcher::isHigherPriorityThan( 1098 const OperandPredicateMatcher &B) const { 1099 // Generally speaking, an instruction is more important than an Int or a 1100 // LiteralInt because it can cover more nodes but there's an exception to 1101 // this. G_CONSTANT's are less important than either of those two because they 1102 // are more permissive. 1103 1104 const auto *AOM = dyn_cast<InstructionOperandMatcher>(this); 1105 const auto *BOM = dyn_cast<InstructionOperandMatcher>(&B); 1106 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction(); 1107 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction(); 1108 1109 // The relative priorities between a G_CONSTANT and any other instruction 1110 // don't actually matter but this code is needed to ensure a strict weak 1111 // ordering. This is particularly important on Windows where the rules will 1112 // be incorrectly sorted without it. 1113 if (AOM && BOM) 1114 return !AIsConstantInsn && BIsConstantInsn; 1115 1116 if (AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt)) 1117 return false; 1118 if (BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt)) 1119 return true; 1120 1121 return Kind < B.Kind; 1122 } 1123 1124 //===- SameOperandMatcher -------------------------------------------------===// 1125 1126 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1127 RuleMatcher &Rule) const { 1128 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName); 1129 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher()); 1130 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID()); 1131 const bool IgnoreCopies = Flags & GISF_IgnoreCopies; 1132 Table << MatchTable::Opcode(IgnoreCopies 1133 ? "GIM_CheckIsSameOperandIgnoreCopies" 1134 : "GIM_CheckIsSameOperand") 1135 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1136 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx) 1137 << MatchTable::Comment("OtherMI") 1138 << MatchTable::ULEB128Value(OtherInsnVarID) 1139 << MatchTable::Comment("OtherOpIdx") 1140 << MatchTable::ULEB128Value(OtherOM.getOpIdx()) 1141 << MatchTable::LineBreak; 1142 } 1143 1144 //===- LLTOperandMatcher --------------------------------------------------===// 1145 1146 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues; 1147 1148 MatchTableRecord LLTOperandMatcher::getValue() const { 1149 const auto VI = TypeIDValues.find(Ty); 1150 if (VI == TypeIDValues.end()) 1151 return MatchTable::NamedValue(1, getTy().getCxxEnumValue()); 1152 return MatchTable::NamedValue(1, getTy().getCxxEnumValue(), VI->second); 1153 } 1154 1155 bool LLTOperandMatcher::hasValue() const { 1156 if (TypeIDValues.size() != KnownTypes.size()) 1157 initTypeIDValuesMap(); 1158 return TypeIDValues.count(Ty); 1159 } 1160 1161 void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1162 RuleMatcher &Rule) const { 1163 if (InsnVarID == 0) { 1164 Table << MatchTable::Opcode("GIM_RootCheckType"); 1165 } else { 1166 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI") 1167 << MatchTable::ULEB128Value(InsnVarID); 1168 } 1169 Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1170 << MatchTable::Comment("Type") << getValue() << MatchTable::LineBreak; 1171 } 1172 1173 //===- PointerToAnyOperandMatcher -----------------------------------------===// 1174 1175 void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1176 RuleMatcher &Rule) const { 1177 Table << MatchTable::Opcode("GIM_CheckPointerToAny") 1178 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1179 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1180 << MatchTable::Comment("SizeInBits") 1181 << MatchTable::ULEB128Value(SizeInBits) << MatchTable::LineBreak; 1182 } 1183 1184 //===- RecordNamedOperandMatcher ------------------------------------------===// 1185 1186 void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1187 RuleMatcher &Rule) const { 1188 Table << MatchTable::Opcode("GIM_RecordNamedOperand") 1189 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1190 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1191 << MatchTable::Comment("StoreIdx") << MatchTable::ULEB128Value(StoreIdx) 1192 << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak; 1193 } 1194 1195 //===- RecordRegisterType ------------------------------------------===// 1196 1197 void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table, 1198 RuleMatcher &Rule) const { 1199 assert(Idx < 0 && "Temp types always have negative indexes!"); 1200 Table << MatchTable::Opcode("GIM_RecordRegType") << MatchTable::Comment("MI") 1201 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op") 1202 << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("TempTypeIdx") 1203 << MatchTable::IntValue(1, Idx) << MatchTable::LineBreak; 1204 } 1205 1206 //===- ComplexPatternOperandMatcher ---------------------------------------===// 1207 1208 void ComplexPatternOperandMatcher::emitPredicateOpcodes( 1209 MatchTable &Table, RuleMatcher &Rule) const { 1210 unsigned ID = getAllocatedTemporariesBaseID(); 1211 Table << MatchTable::Opcode("GIM_CheckComplexPattern") 1212 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1213 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1214 << MatchTable::Comment("Renderer") << MatchTable::IntValue(2, ID) 1215 << MatchTable::NamedValue(2, ("GICP_" + TheDef.getName()).str()) 1216 << MatchTable::LineBreak; 1217 } 1218 1219 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const { 1220 return Operand.getAllocatedTemporariesBaseID(); 1221 } 1222 1223 //===- RegisterBankOperandMatcher -----------------------------------------===// 1224 1225 bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const { 1226 return OperandPredicateMatcher::isIdentical(B) && 1227 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef(); 1228 } 1229 1230 void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1231 RuleMatcher &Rule) const { 1232 if (InsnVarID == 0) { 1233 Table << MatchTable::Opcode("GIM_RootCheckRegBankForClass"); 1234 } else { 1235 Table << MatchTable::Opcode("GIM_CheckRegBankForClass") 1236 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID); 1237 } 1238 1239 Table << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1240 << MatchTable::Comment("RC") 1241 << MatchTable::NamedValue(2, RC.getQualifiedIdName()) 1242 << MatchTable::LineBreak; 1243 } 1244 1245 //===- MBBOperandMatcher --------------------------------------------------===// 1246 1247 void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1248 RuleMatcher &Rule) const { 1249 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI") 1250 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op") 1251 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak; 1252 } 1253 1254 //===- ImmOperandMatcher --------------------------------------------------===// 1255 1256 void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1257 RuleMatcher &Rule) const { 1258 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI") 1259 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op") 1260 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak; 1261 } 1262 1263 //===- ConstantIntOperandMatcher ------------------------------------------===// 1264 1265 void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1266 RuleMatcher &Rule) const { 1267 const bool IsInt8 = isInt<8>(Value); 1268 Table << MatchTable::Opcode(IsInt8 ? "GIM_CheckConstantInt8" 1269 : "GIM_CheckConstantInt") 1270 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1271 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1272 << MatchTable::IntValue(IsInt8 ? 1 : 8, Value) << MatchTable::LineBreak; 1273 } 1274 1275 //===- LiteralIntOperandMatcher -------------------------------------------===// 1276 1277 void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1278 RuleMatcher &Rule) const { 1279 Table << MatchTable::Opcode("GIM_CheckLiteralInt") 1280 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1281 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1282 << MatchTable::IntValue(8, Value) << MatchTable::LineBreak; 1283 } 1284 1285 //===- CmpPredicateOperandMatcher -----------------------------------------===// 1286 1287 void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1288 RuleMatcher &Rule) const { 1289 Table << MatchTable::Opcode("GIM_CheckCmpPredicate") 1290 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1291 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1292 << MatchTable::Comment("Predicate") 1293 << MatchTable::NamedValue(2, "CmpInst", PredName) 1294 << MatchTable::LineBreak; 1295 } 1296 1297 //===- IntrinsicIDOperandMatcher ------------------------------------------===// 1298 1299 void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1300 RuleMatcher &Rule) const { 1301 Table << MatchTable::Opcode("GIM_CheckIntrinsicID") 1302 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1303 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 1304 << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str()) 1305 << MatchTable::LineBreak; 1306 } 1307 1308 //===- OperandImmPredicateMatcher -----------------------------------------===// 1309 1310 void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table, 1311 RuleMatcher &Rule) const { 1312 Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate") 1313 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1314 << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx) 1315 << MatchTable::Comment("Predicate") 1316 << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate)) 1317 << MatchTable::LineBreak; 1318 } 1319 1320 //===- OperandMatcher -----------------------------------------------------===// 1321 1322 std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const { 1323 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" + 1324 llvm::to_string(OpIdx) + ")"; 1325 } 1326 1327 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); } 1328 1329 TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) { 1330 assert(!IsVariadic && "Cannot use this on variadic operands!"); 1331 if (TTIdx >= 0) { 1332 // Temp type index not assigned yet, so assign one and add the necessary 1333 // predicate. 1334 TTIdx = Rule.getNextTempTypeIdx(); 1335 assert(TTIdx < 0); 1336 addPredicate<RecordRegisterType>(TTIdx); 1337 return TTIdx; 1338 } 1339 return TTIdx; 1340 } 1341 1342 void OperandMatcher::emitPredicateOpcodes(MatchTable &Table, 1343 RuleMatcher &Rule) { 1344 if (!Optimized) { 1345 std::string Comment; 1346 raw_string_ostream CommentOS(Comment); 1347 CommentOS << "MIs[" << getInsnVarID() << "] "; 1348 if (SymbolicName.empty()) 1349 CommentOS << "Operand " << OpIdx; 1350 else 1351 CommentOS << SymbolicName; 1352 Table << MatchTable::Comment(Comment) << MatchTable::LineBreak; 1353 } 1354 1355 emitPredicateListOpcodes(Table, Rule); 1356 } 1357 1358 bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) { 1359 // Operand matchers involving more predicates have higher priority. 1360 if (predicates_size() > B.predicates_size()) 1361 return true; 1362 if (predicates_size() < B.predicates_size()) 1363 return false; 1364 1365 // This assumes that predicates are added in a consistent order. 1366 for (auto &&Predicate : zip(predicates(), B.predicates())) { 1367 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) 1368 return true; 1369 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) 1370 return false; 1371 } 1372 1373 return false; 1374 } 1375 1376 unsigned OperandMatcher::countRendererFns() { 1377 return std::accumulate( 1378 predicates().begin(), predicates().end(), 0, 1379 [](unsigned A, 1380 const std::unique_ptr<OperandPredicateMatcher> &Predicate) { 1381 return A + Predicate->countRendererFns(); 1382 }); 1383 } 1384 1385 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy, 1386 bool OperandIsAPointer) { 1387 if (!VTy.isMachineValueType()) 1388 return failUnsupported("unsupported typeset"); 1389 1390 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) { 1391 addPredicate<PointerToAnyOperandMatcher>(0); 1392 return Error::success(); 1393 } 1394 1395 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy); 1396 if (!OpTyOrNone) 1397 return failUnsupported("unsupported type"); 1398 1399 if (OperandIsAPointer) 1400 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits()); 1401 else if (VTy.isPointer()) 1402 addPredicate<LLTOperandMatcher>( 1403 LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits())); 1404 else 1405 addPredicate<LLTOperandMatcher>(*OpTyOrNone); 1406 return Error::success(); 1407 } 1408 1409 //===- InstructionOpcodeMatcher -------------------------------------------===// 1410 1411 DenseMap<const CodeGenInstruction *, unsigned> 1412 InstructionOpcodeMatcher::OpcodeValues; 1413 1414 MatchTableRecord 1415 InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const { 1416 const auto VI = OpcodeValues.find(I); 1417 if (VI != OpcodeValues.end()) 1418 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(), 1419 VI->second); 1420 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName()); 1421 } 1422 1423 void InstructionOpcodeMatcher::initOpcodeValuesMap( 1424 const CodeGenTarget &Target) { 1425 OpcodeValues.clear(); 1426 1427 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue()) 1428 OpcodeValues[I] = Target.getInstrIntValue(I->TheDef); 1429 } 1430 1431 MatchTableRecord InstructionOpcodeMatcher::getValue() const { 1432 assert(Insts.size() == 1); 1433 1434 const CodeGenInstruction *I = Insts[0]; 1435 const auto VI = OpcodeValues.find(I); 1436 if (VI != OpcodeValues.end()) 1437 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(), 1438 VI->second); 1439 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName()); 1440 } 1441 1442 void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table, 1443 RuleMatcher &Rule) const { 1444 StringRef CheckType = 1445 Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither"; 1446 Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI") 1447 << MatchTable::ULEB128Value(InsnVarID); 1448 1449 for (const CodeGenInstruction *I : Insts) 1450 Table << getInstValue(I); 1451 Table << MatchTable::LineBreak; 1452 } 1453 1454 bool InstructionOpcodeMatcher::isHigherPriorityThan( 1455 const InstructionPredicateMatcher &B) const { 1456 if (InstructionPredicateMatcher::isHigherPriorityThan(B)) 1457 return true; 1458 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this)) 1459 return false; 1460 1461 // Prioritize opcodes for cosmetic reasons in the generated source. Although 1462 // this is cosmetic at the moment, we may want to drive a similar ordering 1463 // using instruction frequency information to improve compile time. 1464 if (const InstructionOpcodeMatcher *BO = 1465 dyn_cast<InstructionOpcodeMatcher>(&B)) 1466 return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName(); 1467 1468 return false; 1469 } 1470 1471 bool InstructionOpcodeMatcher::isConstantInstruction() const { 1472 return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT"; 1473 } 1474 1475 StringRef InstructionOpcodeMatcher::getOpcode() const { 1476 return Insts[0]->TheDef->getName(); 1477 } 1478 1479 bool InstructionOpcodeMatcher::isVariadicNumOperands() const { 1480 // If one is variadic, they all should be. 1481 return Insts[0]->Operands.isVariadic; 1482 } 1483 1484 StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const { 1485 // Types expected to be uniform for all alternatives. 1486 return Insts[0]->Operands[OpIdx].OperandType; 1487 } 1488 1489 //===- InstructionNumOperandsMatcher --------------------------------------===// 1490 1491 void InstructionNumOperandsMatcher::emitPredicateOpcodes( 1492 MatchTable &Table, RuleMatcher &Rule) const { 1493 StringRef Opc; 1494 switch (CK) { 1495 case CheckKind::Eq: 1496 Opc = "GIM_CheckNumOperands"; 1497 break; 1498 case CheckKind::GE: 1499 Opc = "GIM_CheckNumOperandsGE"; 1500 break; 1501 case CheckKind::LE: 1502 Opc = "GIM_CheckNumOperandsLE"; 1503 break; 1504 } 1505 Table << MatchTable::Opcode(Opc) << MatchTable::Comment("MI") 1506 << MatchTable::ULEB128Value(InsnVarID) 1507 << MatchTable::Comment("Expected") 1508 << MatchTable::ULEB128Value(NumOperands) << MatchTable::LineBreak; 1509 } 1510 1511 //===- InstructionImmPredicateMatcher -------------------------------------===// 1512 1513 bool InstructionImmPredicateMatcher::isIdentical( 1514 const PredicateMatcher &B) const { 1515 return InstructionPredicateMatcher::isIdentical(B) && 1516 Predicate.getOrigPatFragRecord() == 1517 cast<InstructionImmPredicateMatcher>(&B) 1518 ->Predicate.getOrigPatFragRecord(); 1519 } 1520 1521 void InstructionImmPredicateMatcher::emitPredicateOpcodes( 1522 MatchTable &Table, RuleMatcher &Rule) const { 1523 Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate)) 1524 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1525 << MatchTable::Comment("Predicate") 1526 << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate)) 1527 << MatchTable::LineBreak; 1528 } 1529 1530 //===- AtomicOrderingMMOPredicateMatcher ----------------------------------===// 1531 1532 bool AtomicOrderingMMOPredicateMatcher::isIdentical( 1533 const PredicateMatcher &B) const { 1534 if (!InstructionPredicateMatcher::isIdentical(B)) 1535 return false; 1536 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B); 1537 return Order == R.Order && Comparator == R.Comparator; 1538 } 1539 1540 void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes( 1541 MatchTable &Table, RuleMatcher &Rule) const { 1542 StringRef Opcode = "GIM_CheckAtomicOrdering"; 1543 1544 if (Comparator == AO_OrStronger) 1545 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan"; 1546 if (Comparator == AO_WeakerThan) 1547 Opcode = "GIM_CheckAtomicOrderingWeakerThan"; 1548 1549 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI") 1550 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Order") 1551 << MatchTable::NamedValue(1, 1552 ("(uint8_t)AtomicOrdering::" + Order).str()) 1553 << MatchTable::LineBreak; 1554 } 1555 1556 //===- MemorySizePredicateMatcher -----------------------------------------===// 1557 1558 void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table, 1559 RuleMatcher &Rule) const { 1560 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo") 1561 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1562 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx) 1563 << MatchTable::Comment("Size") << MatchTable::IntValue(4, Size) 1564 << MatchTable::LineBreak; 1565 } 1566 1567 //===- MemoryAddressSpacePredicateMatcher ---------------------------------===// 1568 1569 bool MemoryAddressSpacePredicateMatcher::isIdentical( 1570 const PredicateMatcher &B) const { 1571 if (!InstructionPredicateMatcher::isIdentical(B)) 1572 return false; 1573 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B); 1574 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces; 1575 } 1576 1577 void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes( 1578 MatchTable &Table, RuleMatcher &Rule) const { 1579 assert(AddrSpaces.size() < 256); 1580 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace") 1581 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1582 << MatchTable::Comment("MMO") 1583 << MatchTable::ULEB128Value(MMOIdx) 1584 // Encode number of address spaces to expect. 1585 << MatchTable::Comment("NumAddrSpace") 1586 << MatchTable::IntValue(1, AddrSpaces.size()); 1587 for (unsigned AS : AddrSpaces) 1588 Table << MatchTable::Comment("AddrSpace") << MatchTable::ULEB128Value(AS); 1589 1590 Table << MatchTable::LineBreak; 1591 } 1592 1593 //===- MemoryAlignmentPredicateMatcher ------------------------------------===// 1594 1595 bool MemoryAlignmentPredicateMatcher::isIdentical( 1596 const PredicateMatcher &B) const { 1597 if (!InstructionPredicateMatcher::isIdentical(B)) 1598 return false; 1599 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B); 1600 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign; 1601 } 1602 1603 void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes( 1604 MatchTable &Table, RuleMatcher &Rule) const { 1605 // TODO: we could support more, just need to emit the right opcode or switch 1606 // to log alignment. 1607 assert(MinAlign < 256); 1608 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment") 1609 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1610 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx) 1611 << MatchTable::Comment("MinAlign") << MatchTable::IntValue(1, MinAlign) 1612 << MatchTable::LineBreak; 1613 } 1614 1615 //===- MemoryVsLLTSizePredicateMatcher ------------------------------------===// 1616 1617 bool MemoryVsLLTSizePredicateMatcher::isIdentical( 1618 const PredicateMatcher &B) const { 1619 return InstructionPredicateMatcher::isIdentical(B) && 1620 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx && 1621 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation && 1622 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx; 1623 } 1624 1625 void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes( 1626 MatchTable &Table, RuleMatcher &Rule) const { 1627 Table << MatchTable::Opcode( 1628 Relation == EqualTo ? "GIM_CheckMemorySizeEqualToLLT" 1629 : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT" 1630 : "GIM_CheckMemorySizeLessThanLLT") 1631 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1632 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx) 1633 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx) 1634 << MatchTable::LineBreak; 1635 } 1636 1637 //===- VectorSplatImmPredicateMatcher -------------------------------------===// 1638 1639 void VectorSplatImmPredicateMatcher::emitPredicateOpcodes( 1640 MatchTable &Table, RuleMatcher &Rule) const { 1641 if (Kind == AllOnes) 1642 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes"); 1643 else 1644 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros"); 1645 1646 Table << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID); 1647 Table << MatchTable::LineBreak; 1648 } 1649 1650 //===- GenericInstructionPredicateMatcher ---------------------------------===// 1651 1652 GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher( 1653 unsigned InsnVarID, TreePredicateFn Predicate) 1654 : GenericInstructionPredicateMatcher(InsnVarID, 1655 getEnumNameForPredicate(Predicate)) {} 1656 1657 bool GenericInstructionPredicateMatcher::isIdentical( 1658 const PredicateMatcher &B) const { 1659 return InstructionPredicateMatcher::isIdentical(B) && 1660 EnumVal == 1661 static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal; 1662 } 1663 void GenericInstructionPredicateMatcher::emitPredicateOpcodes( 1664 MatchTable &Table, RuleMatcher &Rule) const { 1665 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate") 1666 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1667 << MatchTable::Comment("FnId") << MatchTable::NamedValue(2, EnumVal) 1668 << MatchTable::LineBreak; 1669 } 1670 1671 //===- MIFlagsInstructionPredicateMatcher ---------------------------------===// 1672 1673 bool MIFlagsInstructionPredicateMatcher::isIdentical( 1674 const PredicateMatcher &B) const { 1675 if (!InstructionPredicateMatcher::isIdentical(B)) 1676 return false; 1677 const auto &Other = 1678 static_cast<const MIFlagsInstructionPredicateMatcher &>(B); 1679 return Flags == Other.Flags && CheckNot == Other.CheckNot; 1680 } 1681 1682 void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes( 1683 MatchTable &Table, RuleMatcher &Rule) const { 1684 Table << MatchTable::Opcode(CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags") 1685 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID) 1686 << MatchTable::NamedValue(4, join(Flags, " | ")) 1687 << MatchTable::LineBreak; 1688 } 1689 1690 //===- InstructionMatcher -------------------------------------------------===// 1691 1692 OperandMatcher & 1693 InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName, 1694 unsigned AllocatedTemporariesBaseID, 1695 bool IsVariadic) { 1696 assert((Operands.empty() || !Operands.back()->isVariadic()) && 1697 "Cannot add more operands after a variadic operand"); 1698 Operands.emplace_back(new OperandMatcher( 1699 *this, OpIdx, SymbolicName, AllocatedTemporariesBaseID, IsVariadic)); 1700 if (!SymbolicName.empty()) 1701 Rule.defineOperand(SymbolicName, *Operands.back()); 1702 return *Operands.back(); 1703 } 1704 1705 OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) { 1706 auto I = llvm::find_if(Operands, 1707 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) { 1708 return X->getOpIdx() == OpIdx; 1709 }); 1710 if (I != Operands.end()) 1711 return **I; 1712 llvm_unreachable("Failed to lookup operand"); 1713 } 1714 1715 OperandMatcher &InstructionMatcher::addPhysRegInput(const Record *Reg, 1716 unsigned OpIdx, 1717 unsigned TempOpIdx) { 1718 assert(SymbolicName.empty()); 1719 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx); 1720 Operands.emplace_back(OM); 1721 Rule.definePhysRegOperand(Reg, *OM); 1722 return *OM; 1723 } 1724 1725 void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table, 1726 RuleMatcher &Rule) { 1727 if (canAddNumOperandsCheck()) { 1728 InstructionNumOperandsMatcher(InsnVarID, getNumOperandMatchers()) 1729 .emitPredicateOpcodes(Table, Rule); 1730 } 1731 1732 // First emit all instruction level predicates need to be verified before we 1733 // can verify operands. 1734 emitFilteredPredicateListOpcodes( 1735 [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table, 1736 Rule); 1737 1738 // Emit all operand constraints. 1739 for (const auto &Operand : Operands) 1740 Operand->emitPredicateOpcodes(Table, Rule); 1741 1742 // All of the tablegen defined predicates should now be matched. Now emit 1743 // any custom predicates that rely on all generated checks. 1744 emitFilteredPredicateListOpcodes( 1745 [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table, 1746 Rule); 1747 } 1748 1749 bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) { 1750 // Instruction matchers involving more operands have higher priority. 1751 if (Operands.size() > B.Operands.size()) 1752 return true; 1753 if (Operands.size() < B.Operands.size()) 1754 return false; 1755 1756 for (auto &&P : zip(predicates(), B.predicates())) { 1757 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get()); 1758 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get()); 1759 if (L->isHigherPriorityThan(*R)) 1760 return true; 1761 if (R->isHigherPriorityThan(*L)) 1762 return false; 1763 } 1764 1765 for (auto Operand : zip(Operands, B.Operands)) { 1766 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand))) 1767 return true; 1768 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand))) 1769 return false; 1770 } 1771 1772 return false; 1773 } 1774 1775 unsigned InstructionMatcher::countRendererFns() { 1776 return std::accumulate( 1777 predicates().begin(), predicates().end(), 0, 1778 [](unsigned A, 1779 const std::unique_ptr<PredicateMatcher> &Predicate) { 1780 return A + Predicate->countRendererFns(); 1781 }) + 1782 std::accumulate( 1783 Operands.begin(), Operands.end(), 0, 1784 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) { 1785 return A + Operand->countRendererFns(); 1786 }); 1787 } 1788 1789 void InstructionMatcher::optimize() { 1790 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash; 1791 const auto &OpcMatcher = getOpcodeMatcher(); 1792 1793 Stash.push_back(predicates_pop_front()); 1794 if (Stash.back().get() == &OpcMatcher) { 1795 // FIXME: Is this even needed still? Why the isVariadicNumOperands check? 1796 if (canAddNumOperandsCheck() && OpcMatcher.isVariadicNumOperands() && 1797 getNumOperandMatchers() != 0) { 1798 Stash.emplace_back(new InstructionNumOperandsMatcher( 1799 InsnVarID, getNumOperandMatchers())); 1800 } 1801 AllowNumOpsCheck = false; 1802 1803 for (auto &OM : Operands) 1804 for (auto &OP : OM->predicates()) 1805 if (isa<IntrinsicIDOperandMatcher>(OP)) { 1806 Stash.push_back(std::move(OP)); 1807 OM->eraseNullPredicates(); 1808 break; 1809 } 1810 } 1811 1812 if (InsnVarID > 0) { 1813 assert(!Operands.empty() && "Nested instruction is expected to def a vreg"); 1814 for (auto &OP : Operands[0]->predicates()) 1815 OP.reset(); 1816 Operands[0]->eraseNullPredicates(); 1817 } 1818 for (auto &OM : Operands) { 1819 for (auto &OP : OM->predicates()) 1820 if (isa<LLTOperandMatcher>(OP)) 1821 Stash.push_back(std::move(OP)); 1822 OM->eraseNullPredicates(); 1823 } 1824 while (!Stash.empty()) 1825 prependPredicate(Stash.pop_back_val()); 1826 } 1827 1828 //===- InstructionOperandMatcher ------------------------------------------===// 1829 1830 void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table, 1831 RuleMatcher &Rule) const { 1832 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID(); 1833 const bool IgnoreCopies = Flags & GISF_IgnoreCopies; 1834 Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies" 1835 : "GIM_RecordInsn") 1836 << MatchTable::Comment("DefineMI") 1837 << MatchTable::ULEB128Value(NewInsnVarID) << MatchTable::Comment("MI") 1838 << MatchTable::ULEB128Value(getInsnVarID()) 1839 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(getOpIdx()) 1840 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]") 1841 << MatchTable::LineBreak; 1842 } 1843 1844 bool InstructionOperandMatcher::isHigherPriorityThan( 1845 const OperandPredicateMatcher &B) const { 1846 if (OperandPredicateMatcher::isHigherPriorityThan(B)) 1847 return true; 1848 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this)) 1849 return false; 1850 1851 if (const InstructionOperandMatcher *BP = 1852 dyn_cast<InstructionOperandMatcher>(&B)) 1853 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher)) 1854 return true; 1855 return false; 1856 } 1857 1858 //===- OperandRenderer ----------------------------------------------------===// 1859 1860 OperandRenderer::~OperandRenderer() {} 1861 1862 //===- CopyRenderer -------------------------------------------------------===// 1863 1864 void CopyRenderer::emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule, 1865 unsigned NewInsnID, unsigned OldInsnID, 1866 unsigned OpIdx, StringRef Name, 1867 bool ForVariadic) { 1868 if (!ForVariadic && NewInsnID == 0 && OldInsnID == 0) { 1869 Table << MatchTable::Opcode("GIR_RootToRootCopy"); 1870 } else { 1871 Table << MatchTable::Opcode(ForVariadic ? "GIR_CopyRemaining" : "GIR_Copy") 1872 << MatchTable::Comment("NewInsnID") 1873 << MatchTable::ULEB128Value(NewInsnID) 1874 << MatchTable::Comment("OldInsnID") 1875 << MatchTable::ULEB128Value(OldInsnID); 1876 } 1877 1878 Table << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx) 1879 << MatchTable::Comment(Name) << MatchTable::LineBreak; 1880 } 1881 1882 void CopyRenderer::emitRenderOpcodes(MatchTable &Table, 1883 RuleMatcher &Rule) const { 1884 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); 1885 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); 1886 1887 emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnVarID, Operand.getOpIdx(), 1888 SymbolicName, Operand.isVariadic()); 1889 } 1890 1891 //===- CopyPhysRegRenderer ------------------------------------------------===// 1892 1893 void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table, 1894 RuleMatcher &Rule) const { 1895 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg); 1896 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); 1897 CopyRenderer::emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnVarID, 1898 Operand.getOpIdx(), PhysReg->getName()); 1899 } 1900 1901 //===- CopyOrAddZeroRegRenderer -------------------------------------------===// 1902 1903 void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table, 1904 RuleMatcher &Rule) const { 1905 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); 1906 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); 1907 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg") 1908 << MatchTable::Comment("NewInsnID") 1909 << MatchTable::ULEB128Value(NewInsnID) 1910 << MatchTable::Comment("OldInsnID") 1911 << MatchTable::ULEB128Value(OldInsnVarID) 1912 << MatchTable::Comment("OpIdx") 1913 << MatchTable::ULEB128Value(Operand.getOpIdx()) 1914 << MatchTable::NamedValue( 1915 2, 1916 (ZeroRegisterDef->getValue("Namespace") 1917 ? ZeroRegisterDef->getValueAsString("Namespace") 1918 : ""), 1919 ZeroRegisterDef->getName()) 1920 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 1921 } 1922 1923 //===- CopyConstantAsImmRenderer ------------------------------------------===// 1924 1925 void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table, 1926 RuleMatcher &Rule) const { 1927 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); 1928 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); 1929 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm" 1930 : "GIR_CopyConstantAsUImm") 1931 << MatchTable::Comment("NewInsnID") 1932 << MatchTable::ULEB128Value(NewInsnID) 1933 << MatchTable::Comment("OldInsnID") 1934 << MatchTable::ULEB128Value(OldInsnVarID) 1935 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 1936 } 1937 1938 //===- CopyFConstantAsFPImmRenderer ---------------------------------------===// 1939 1940 void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table, 1941 RuleMatcher &Rule) const { 1942 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); 1943 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); 1944 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm") 1945 << MatchTable::Comment("NewInsnID") 1946 << MatchTable::ULEB128Value(NewInsnID) 1947 << MatchTable::Comment("OldInsnID") 1948 << MatchTable::ULEB128Value(OldInsnVarID) 1949 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 1950 } 1951 1952 //===- CopySubRegRenderer -------------------------------------------------===// 1953 1954 void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table, 1955 RuleMatcher &Rule) const { 1956 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); 1957 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); 1958 Table << MatchTable::Opcode("GIR_CopySubReg") 1959 << MatchTable::Comment("NewInsnID") 1960 << MatchTable::ULEB128Value(NewInsnID) 1961 << MatchTable::Comment("OldInsnID") 1962 << MatchTable::ULEB128Value(OldInsnVarID) 1963 << MatchTable::Comment("OpIdx") 1964 << MatchTable::ULEB128Value(Operand.getOpIdx()) 1965 << MatchTable::Comment("SubRegIdx") 1966 << MatchTable::IntValue(2, SubReg->EnumValue) 1967 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 1968 } 1969 1970 //===- AddRegisterRenderer ------------------------------------------------===// 1971 1972 void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table, 1973 RuleMatcher &Rule) const { 1974 Table << MatchTable::Opcode("GIR_AddRegister") 1975 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID); 1976 if (RegisterDef->getName() != "zero_reg") { 1977 Table << MatchTable::NamedValue( 1978 2, 1979 (RegisterDef->getValue("Namespace") 1980 ? RegisterDef->getValueAsString("Namespace") 1981 : ""), 1982 RegisterDef->getName()); 1983 } else { 1984 Table << MatchTable::NamedValue(2, Target.getRegNamespace(), "NoRegister"); 1985 } 1986 Table << MatchTable::Comment("AddRegisterRegFlags"); 1987 1988 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are 1989 // really needed for a physical register reference. We can pack the 1990 // register and flags in a single field. 1991 if (IsDef) { 1992 Table << MatchTable::NamedValue( 1993 2, IsDead ? "RegState::Define | RegState::Dead" : "RegState::Define"); 1994 } else { 1995 assert(!IsDead && "A use cannot be dead"); 1996 Table << MatchTable::IntValue(2, 0); 1997 } 1998 Table << MatchTable::LineBreak; 1999 } 2000 2001 //===- TempRegRenderer ----------------------------------------------------===// 2002 2003 void TempRegRenderer::emitRenderOpcodes(MatchTable &Table, 2004 RuleMatcher &Rule) const { 2005 const bool NeedsFlags = (SubRegIdx || IsDef); 2006 if (SubRegIdx) { 2007 assert(!IsDef); 2008 Table << MatchTable::Opcode("GIR_AddTempSubRegister"); 2009 } else 2010 Table << MatchTable::Opcode(NeedsFlags ? "GIR_AddTempRegister" 2011 : "GIR_AddSimpleTempRegister"); 2012 2013 Table << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2014 << MatchTable::Comment("TempRegID") 2015 << MatchTable::ULEB128Value(TempRegID); 2016 2017 if (!NeedsFlags) { 2018 Table << MatchTable::LineBreak; 2019 return; 2020 } 2021 2022 Table << MatchTable::Comment("TempRegFlags"); 2023 if (IsDef) { 2024 SmallString<32> RegFlags; 2025 RegFlags += "RegState::Define"; 2026 if (IsDead) 2027 RegFlags += "|RegState::Dead"; 2028 Table << MatchTable::NamedValue(2, RegFlags); 2029 } else 2030 Table << MatchTable::IntValue(2, 0); 2031 2032 if (SubRegIdx) 2033 Table << MatchTable::NamedValue(2, SubRegIdx->getQualifiedName()); 2034 Table << MatchTable::LineBreak; 2035 } 2036 2037 //===- ImmRenderer --------------------------------------------------------===// 2038 2039 void ImmRenderer::emitAddImm(MatchTable &Table, RuleMatcher &RM, 2040 unsigned InsnID, int64_t Imm, StringRef ImmName) { 2041 const bool IsInt8 = isInt<8>(Imm); 2042 2043 Table << MatchTable::Opcode(IsInt8 ? "GIR_AddImm8" : "GIR_AddImm") 2044 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2045 << MatchTable::Comment(ImmName) 2046 << MatchTable::IntValue(IsInt8 ? 1 : 8, Imm) << MatchTable::LineBreak; 2047 } 2048 2049 void ImmRenderer::emitRenderOpcodes(MatchTable &Table, 2050 RuleMatcher &Rule) const { 2051 if (CImmLLT) { 2052 assert(Table.isCombiner() && 2053 "ConstantInt immediate are only for combiners!"); 2054 Table << MatchTable::Opcode("GIR_AddCImm") << MatchTable::Comment("InsnID") 2055 << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Type") 2056 << *CImmLLT << MatchTable::Comment("Imm") 2057 << MatchTable::IntValue(8, Imm) << MatchTable::LineBreak; 2058 } else 2059 emitAddImm(Table, Rule, InsnID, Imm); 2060 } 2061 2062 //===- SubRegIndexRenderer ------------------------------------------------===// 2063 2064 void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table, 2065 RuleMatcher &Rule) const { 2066 ImmRenderer::emitAddImm(Table, Rule, InsnID, SubRegIdx->EnumValue, 2067 "SubRegIndex"); 2068 } 2069 2070 //===- RenderComplexPatternOperand ----------------------------------------===// 2071 2072 void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table, 2073 RuleMatcher &Rule) const { 2074 Table << MatchTable::Opcode( 2075 SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer" 2076 : "GIR_ComplexSubOperandRenderer") 2077 : "GIR_ComplexRenderer") 2078 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2079 << MatchTable::Comment("RendererID") 2080 << MatchTable::IntValue(2, RendererID); 2081 if (SubOperand) 2082 Table << MatchTable::Comment("SubOperand") 2083 << MatchTable::ULEB128Value(*SubOperand); 2084 if (SubReg) 2085 Table << MatchTable::Comment("SubRegIdx") 2086 << MatchTable::IntValue(2, SubReg->EnumValue); 2087 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 2088 } 2089 2090 //===- IntrinsicIDRenderer ------------------------------------------------===// 2091 2092 void IntrinsicIDRenderer::emitRenderOpcodes(MatchTable &Table, 2093 RuleMatcher &Rule) const { 2094 Table << MatchTable::Opcode("GIR_AddIntrinsicID") << MatchTable::Comment("MI") 2095 << MatchTable::ULEB128Value(InsnID) 2096 << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName.str()) 2097 << MatchTable::LineBreak; 2098 } 2099 2100 //===- CustomRenderer -----------------------------------------------------===// 2101 2102 void CustomRenderer::emitRenderOpcodes(MatchTable &Table, 2103 RuleMatcher &Rule) const { 2104 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); 2105 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); 2106 Table << MatchTable::Opcode("GIR_CustomRenderer") 2107 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2108 << MatchTable::Comment("OldInsnID") 2109 << MatchTable::ULEB128Value(OldInsnVarID) 2110 << MatchTable::Comment("Renderer") 2111 << MatchTable::NamedValue( 2112 2, "GICR_" + Renderer.getValueAsString("RendererFn").str()) 2113 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 2114 } 2115 2116 //===- CustomOperandRenderer ----------------------------------------------===// 2117 2118 void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table, 2119 RuleMatcher &Rule) const { 2120 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName); 2121 Table << MatchTable::Opcode("GIR_CustomOperandRenderer") 2122 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2123 << MatchTable::Comment("OldInsnID") 2124 << MatchTable::ULEB128Value(OpdMatcher.getInsnVarID()) 2125 << MatchTable::Comment("OpIdx") 2126 << MatchTable::ULEB128Value(OpdMatcher.getOpIdx()) 2127 << MatchTable::Comment("OperandRenderer") 2128 << MatchTable::NamedValue( 2129 2, "GICR_" + Renderer.getValueAsString("RendererFn").str()) 2130 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; 2131 } 2132 2133 //===- BuildMIAction ------------------------------------------------------===// 2134 2135 bool BuildMIAction::canMutate(RuleMatcher &Rule, 2136 const InstructionMatcher *Insn) const { 2137 if (!Insn || Insn->hasVariadicMatcher()) 2138 return false; 2139 2140 if (OperandRenderers.size() != Insn->getNumOperandMatchers()) 2141 return false; 2142 2143 for (const auto &Renderer : enumerate(OperandRenderers)) { 2144 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) { 2145 const OperandMatcher &OM = 2146 Rule.getOperandMatcher(Copy->getSymbolicName()); 2147 if (Insn != &OM.getInstructionMatcher() || 2148 OM.getOpIdx() != Renderer.index()) 2149 return false; 2150 } else 2151 return false; 2152 } 2153 2154 return true; 2155 } 2156 2157 void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) { 2158 for (auto *MutateCandidate : Rule.mutatable_insns()) { 2159 if (canMutate(Rule, MutateCandidate)) { 2160 // Take the first one we're offered that we're able to mutate. 2161 Rule.reserveInsnMatcherForMutation(MutateCandidate); 2162 Matched = MutateCandidate; 2163 return; 2164 } 2165 } 2166 } 2167 2168 void BuildMIAction::emitActionOpcodes(MatchTable &Table, 2169 RuleMatcher &Rule) const { 2170 const auto AddMIFlags = [&]() { 2171 for (const InstructionMatcher *IM : CopiedFlags) { 2172 Table << MatchTable::Opcode("GIR_CopyMIFlags") 2173 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2174 << MatchTable::Comment("OldInsnID") 2175 << MatchTable::ULEB128Value(IM->getInsnVarID()) 2176 << MatchTable::LineBreak; 2177 } 2178 2179 if (!SetFlags.empty()) { 2180 Table << MatchTable::Opcode("GIR_SetMIFlags") 2181 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2182 << MatchTable::NamedValue(4, join(SetFlags, " | ")) 2183 << MatchTable::LineBreak; 2184 } 2185 2186 if (!UnsetFlags.empty()) { 2187 Table << MatchTable::Opcode("GIR_UnsetMIFlags") 2188 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2189 << MatchTable::NamedValue(4, join(UnsetFlags, " | ")) 2190 << MatchTable::LineBreak; 2191 } 2192 }; 2193 2194 if (Matched) { 2195 assert(canMutate(Rule, Matched) && 2196 "Arranged to mutate an insn that isn't mutatable"); 2197 2198 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched); 2199 Table << MatchTable::Opcode("GIR_MutateOpcode") 2200 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2201 << MatchTable::Comment("RecycleInsnID") 2202 << MatchTable::ULEB128Value(RecycleInsnID) 2203 << MatchTable::Comment("Opcode") 2204 << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName()) 2205 << MatchTable::LineBreak; 2206 2207 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) { 2208 for (auto *Def : I->ImplicitDefs) { 2209 auto Namespace = Def->getValue("Namespace") 2210 ? Def->getValueAsString("Namespace") 2211 : ""; 2212 const bool IsDead = DeadImplicitDefs.contains(Def); 2213 Table << MatchTable::Opcode("GIR_AddImplicitDef") 2214 << MatchTable::Comment("InsnID") 2215 << MatchTable::ULEB128Value(InsnID) 2216 << MatchTable::NamedValue(2, Namespace, Def->getName()) 2217 << (IsDead ? MatchTable::NamedValue(2, "RegState", "Dead") 2218 : MatchTable::IntValue(2, 0)) 2219 << MatchTable::LineBreak; 2220 } 2221 for (auto *Use : I->ImplicitUses) { 2222 auto Namespace = Use->getValue("Namespace") 2223 ? Use->getValueAsString("Namespace") 2224 : ""; 2225 Table << MatchTable::Opcode("GIR_AddImplicitUse") 2226 << MatchTable::Comment("InsnID") 2227 << MatchTable::ULEB128Value(InsnID) 2228 << MatchTable::NamedValue(2, Namespace, Use->getName()) 2229 << MatchTable::LineBreak; 2230 } 2231 } 2232 2233 AddMIFlags(); 2234 2235 // Mark the mutated instruction as erased. 2236 Rule.tryEraseInsnID(RecycleInsnID); 2237 return; 2238 } 2239 2240 // TODO: Simple permutation looks like it could be almost as common as 2241 // mutation due to commutative operations. 2242 2243 if (InsnID == 0) { 2244 Table << MatchTable::Opcode("GIR_BuildRootMI"); 2245 } else { 2246 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID") 2247 << MatchTable::ULEB128Value(InsnID); 2248 } 2249 2250 Table << MatchTable::Comment("Opcode") 2251 << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName()) 2252 << MatchTable::LineBreak; 2253 2254 for (const auto &Renderer : OperandRenderers) 2255 Renderer->emitRenderOpcodes(Table, Rule); 2256 2257 for (auto [OpIdx, Def] : enumerate(I->ImplicitDefs)) { 2258 auto Namespace = 2259 Def->getValue("Namespace") ? Def->getValueAsString("Namespace") : ""; 2260 if (DeadImplicitDefs.contains(Def)) { 2261 Table 2262 << MatchTable::Opcode("GIR_SetImplicitDefDead") 2263 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2264 << MatchTable::Comment( 2265 ("OpIdx for " + Namespace + "::" + Def->getName() + "").str()) 2266 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak; 2267 } 2268 } 2269 2270 if (I->mayLoad || I->mayStore) { 2271 // Emit the ID's for all the instructions that are matched by this rule. 2272 // TODO: Limit this to matched instructions that mayLoad/mayStore or have 2273 // some other means of having a memoperand. Also limit this to 2274 // emitted instructions that expect to have a memoperand too. For 2275 // example, (G_SEXT (G_LOAD x)) that results in separate load and 2276 // sign-extend instructions shouldn't put the memoperand on the 2277 // sign-extend since it has no effect there. 2278 2279 std::vector<unsigned> MergeInsnIDs; 2280 for (const auto &IDMatcherPair : Rule.defined_insn_vars()) 2281 MergeInsnIDs.push_back(IDMatcherPair.second); 2282 llvm::sort(MergeInsnIDs); 2283 2284 Table << MatchTable::Opcode("GIR_MergeMemOperands") 2285 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2286 << MatchTable::Comment("NumInsns") 2287 << MatchTable::IntValue(1, MergeInsnIDs.size()) 2288 << MatchTable::Comment("MergeInsnID's"); 2289 for (const auto &MergeInsnID : MergeInsnIDs) 2290 Table << MatchTable::ULEB128Value(MergeInsnID); 2291 Table << MatchTable::LineBreak; 2292 } 2293 2294 AddMIFlags(); 2295 } 2296 2297 //===- BuildConstantAction ------------------------------------------------===// 2298 2299 void BuildConstantAction::emitActionOpcodes(MatchTable &Table, 2300 RuleMatcher &Rule) const { 2301 Table << MatchTable::Opcode("GIR_BuildConstant") 2302 << MatchTable::Comment("TempRegID") 2303 << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("Val") 2304 << MatchTable::IntValue(8, Val) << MatchTable::LineBreak; 2305 } 2306 2307 //===- EraseInstAction ----------------------------------------------------===// 2308 2309 void EraseInstAction::emitActionOpcodes(MatchTable &Table, 2310 RuleMatcher &Rule) const { 2311 // Avoid erasing the same inst twice. 2312 if (!Rule.tryEraseInsnID(InsnID)) 2313 return; 2314 2315 Table << MatchTable::Opcode("GIR_EraseFromParent") 2316 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2317 << MatchTable::LineBreak; 2318 } 2319 2320 bool EraseInstAction::emitActionOpcodesAndDone(MatchTable &Table, 2321 RuleMatcher &Rule) const { 2322 if (InsnID != 0) { 2323 emitActionOpcodes(Table, Rule); 2324 return false; 2325 } 2326 2327 if (!Rule.tryEraseInsnID(0)) 2328 return false; 2329 2330 Table << MatchTable::Opcode("GIR_EraseRootFromParent_Done", -1) 2331 << MatchTable::LineBreak; 2332 return true; 2333 } 2334 2335 //===- ReplaceRegAction ---------------------------------------------------===// 2336 2337 void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table, 2338 RuleMatcher &Rule) const { 2339 if (TempRegID != (unsigned)-1) 2340 return; 2341 2342 Table << MatchTable::Opcode("GIM_CheckCanReplaceReg") 2343 << MatchTable::Comment("OldInsnID") 2344 << MatchTable::ULEB128Value(OldInsnID) 2345 << MatchTable::Comment("OldOpIdx") << MatchTable::ULEB128Value(OldOpIdx) 2346 << MatchTable::Comment("NewInsnId") 2347 << MatchTable::ULEB128Value(NewInsnId) 2348 << MatchTable::Comment("NewOpIdx") << MatchTable::ULEB128Value(NewOpIdx) 2349 << MatchTable::LineBreak; 2350 } 2351 2352 void ReplaceRegAction::emitActionOpcodes(MatchTable &Table, 2353 RuleMatcher &Rule) const { 2354 if (TempRegID != (unsigned)-1) { 2355 Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg") 2356 << MatchTable::Comment("OldInsnID") 2357 << MatchTable::ULEB128Value(OldInsnID) 2358 << MatchTable::Comment("OldOpIdx") 2359 << MatchTable::ULEB128Value(OldOpIdx) 2360 << MatchTable::Comment("TempRegID") 2361 << MatchTable::ULEB128Value(TempRegID) << MatchTable::LineBreak; 2362 } else { 2363 Table << MatchTable::Opcode("GIR_ReplaceReg") 2364 << MatchTable::Comment("OldInsnID") 2365 << MatchTable::ULEB128Value(OldInsnID) 2366 << MatchTable::Comment("OldOpIdx") 2367 << MatchTable::ULEB128Value(OldOpIdx) 2368 << MatchTable::Comment("NewInsnId") 2369 << MatchTable::ULEB128Value(NewInsnId) 2370 << MatchTable::Comment("NewOpIdx") 2371 << MatchTable::ULEB128Value(NewOpIdx) << MatchTable::LineBreak; 2372 } 2373 } 2374 2375 //===- ConstrainOperandToRegClassAction -----------------------------------===// 2376 2377 void ConstrainOperandToRegClassAction::emitActionOpcodes( 2378 MatchTable &Table, RuleMatcher &Rule) const { 2379 Table << MatchTable::Opcode("GIR_ConstrainOperandRC") 2380 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID) 2381 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx) 2382 << MatchTable::NamedValue(2, RC.getQualifiedIdName()) 2383 << MatchTable::LineBreak; 2384 } 2385 2386 //===- MakeTempRegisterAction ---------------------------------------------===// 2387 2388 void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table, 2389 RuleMatcher &Rule) const { 2390 Table << MatchTable::Opcode("GIR_MakeTempReg") 2391 << MatchTable::Comment("TempRegID") 2392 << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("TypeID") 2393 << Ty << MatchTable::LineBreak; 2394 } 2395 2396 } // namespace gi 2397 } // namespace llvm 2398