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