1 //===- GlobalISelMatchTable.h ---------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file 10 /// This file contains the code related to the GlobalISel Match Table emitted by 11 /// GlobalISelEmitter.cpp. The generated match table is interpreted at runtime 12 /// by `GIMatchTableExecutorImpl.h` to match & apply ISel patterns. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H 17 #define LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H 18 19 #include "CodeGenDAGPatterns.h" 20 #include "llvm/ADT/ArrayRef.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/StringMap.h" 24 #include "llvm/ADT/StringRef.h" 25 #include "llvm/CodeGen/LowLevelType.h" 26 #include "llvm/Support/Error.h" 27 #include "llvm/Support/SaveAndRestore.h" 28 #include <deque> 29 #include <list> 30 #include <map> 31 #include <memory> 32 #include <optional> 33 #include <set> 34 #include <string> 35 #include <vector> 36 37 namespace llvm { 38 39 class raw_ostream; 40 class Record; 41 class SMLoc; 42 class CodeGenRegisterClass; 43 44 // Use a namespace to avoid conflicts because there's some fairly generic names 45 // in there (e.g. Matcher). 46 namespace gi { 47 class MatchTable; 48 class Matcher; 49 class OperandMatcher; 50 class MatchAction; 51 class PredicateMatcher; 52 class InstructionMatcher; 53 54 enum { 55 GISF_IgnoreCopies = 0x1, 56 }; 57 58 using GISelFlags = std::uint16_t; 59 60 //===- Helper functions ---------------------------------------------------===// 61 62 std::string getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset); 63 64 /// Takes a sequence of \p Rules and group them based on the predicates 65 /// they share. \p MatcherStorage is used as a memory container 66 /// for the group that are created as part of this process. 67 /// 68 /// What this optimization does looks like if GroupT = GroupMatcher: 69 /// Output without optimization: 70 /// \verbatim 71 /// # R1 72 /// # predicate A 73 /// # predicate B 74 /// ... 75 /// # R2 76 /// # predicate A // <-- effectively this is going to be checked twice. 77 /// // Once in R1 and once in R2. 78 /// # predicate C 79 /// \endverbatim 80 /// Output with optimization: 81 /// \verbatim 82 /// # Group1_2 83 /// # predicate A // <-- Check is now shared. 84 /// # R1 85 /// # predicate B 86 /// # R2 87 /// # predicate C 88 /// \endverbatim 89 template <class GroupT> 90 std::vector<Matcher *> 91 optimizeRules(ArrayRef<Matcher *> Rules, 92 std::vector<std::unique_ptr<Matcher>> &MatcherStorage); 93 94 /// A record to be stored in a MatchTable. 95 /// 96 /// This class represents any and all output that may be required to emit the 97 /// MatchTable. Instances are most often configured to represent an opcode or 98 /// value that will be emitted to the table with some formatting but it can also 99 /// represent commas, comments, and other formatting instructions. 100 struct MatchTableRecord { 101 enum RecordFlagsBits { 102 MTRF_None = 0x0, 103 /// Causes EmitStr to be formatted as comment when emitted. 104 MTRF_Comment = 0x1, 105 /// Causes the record value to be followed by a comma when emitted. 106 MTRF_CommaFollows = 0x2, 107 /// Causes the record value to be followed by a line break when emitted. 108 MTRF_LineBreakFollows = 0x4, 109 /// Indicates that the record defines a label and causes an additional 110 /// comment to be emitted containing the index of the label. 111 MTRF_Label = 0x8, 112 /// Causes the record to be emitted as the index of the label specified by 113 /// LabelID along with a comment indicating where that label is. 114 MTRF_JumpTarget = 0x10, 115 /// Causes the formatter to add a level of indentation before emitting the 116 /// record. 117 MTRF_Indent = 0x20, 118 /// Causes the formatter to remove a level of indentation after emitting the 119 /// record. 120 MTRF_Outdent = 0x40, 121 }; 122 123 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to 124 /// reference or define. 125 unsigned LabelID; 126 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a 127 /// value, a label name. 128 std::string EmitStr; 129 130 private: 131 /// The number of MatchTable elements described by this record. Comments are 0 132 /// while values are typically 1. Values >1 may occur when we need to emit 133 /// values that exceed the size of a MatchTable element. 134 unsigned NumElements; 135 136 public: 137 /// A bitfield of RecordFlagsBits flags. 138 unsigned Flags; 139 140 /// The actual run-time value, if known 141 int64_t RawValue; 142 143 MatchTableRecord(std::optional<unsigned> LabelID_, StringRef EmitStr, 144 unsigned NumElements, unsigned Flags, 145 int64_t RawValue = std::numeric_limits<int64_t>::min()) 146 : LabelID(LabelID_.value_or(~0u)), EmitStr(EmitStr), 147 NumElements(NumElements), Flags(Flags), RawValue(RawValue) { 148 assert((!LabelID_ || LabelID != ~0u) && 149 "This value is reserved for non-labels"); 150 } 151 MatchTableRecord(const MatchTableRecord &Other) = default; 152 MatchTableRecord(MatchTableRecord &&Other) = default; 153 154 /// Useful if a Match Table Record gets optimized out 155 void turnIntoComment() { 156 Flags |= MTRF_Comment; 157 Flags &= ~MTRF_CommaFollows; 158 NumElements = 0; 159 } 160 161 /// For Jump Table generation purposes 162 bool operator<(const MatchTableRecord &Other) const { 163 return RawValue < Other.RawValue; 164 } 165 int64_t getRawValue() const { return RawValue; } 166 167 void emit(raw_ostream &OS, bool LineBreakNextAfterThis, 168 const MatchTable &Table) const; 169 unsigned size() const { return NumElements; } 170 }; 171 172 /// Holds the contents of a generated MatchTable to enable formatting and the 173 /// necessary index tracking needed to support GIM_Try. 174 class MatchTable { 175 /// An unique identifier for the table. The generated table will be named 176 /// MatchTable${ID}. 177 unsigned ID; 178 /// The records that make up the table. Also includes comments describing the 179 /// values being emitted and line breaks to format it. 180 std::vector<MatchTableRecord> Contents; 181 /// The currently defined labels. 182 DenseMap<unsigned, unsigned> LabelMap; 183 /// Tracks the sum of MatchTableRecord::NumElements as the table is built. 184 unsigned CurrentSize = 0; 185 /// A unique identifier for a MatchTable label. 186 unsigned CurrentLabelID = 0; 187 /// Determines if the table should be instrumented for rule coverage tracking. 188 bool IsWithCoverage; 189 /// Whether this table is for the GISel combiner. 190 bool IsCombinerTable; 191 192 public: 193 static MatchTableRecord LineBreak; 194 static MatchTableRecord Comment(StringRef Comment); 195 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0); 196 static MatchTableRecord NamedValue(StringRef NamedValue); 197 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue); 198 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue); 199 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue, 200 int64_t RawValue); 201 static MatchTableRecord IntValue(int64_t IntValue); 202 static MatchTableRecord Label(unsigned LabelID); 203 static MatchTableRecord JumpTarget(unsigned LabelID); 204 205 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage, 206 bool IsCombiner = false); 207 208 MatchTable(bool WithCoverage, bool IsCombinerTable, unsigned ID = 0) 209 : ID(ID), IsWithCoverage(WithCoverage), IsCombinerTable(IsCombinerTable) { 210 } 211 212 bool isWithCoverage() const { return IsWithCoverage; } 213 bool isCombiner() const { return IsCombinerTable; } 214 215 void push_back(const MatchTableRecord &Value) { 216 if (Value.Flags & MatchTableRecord::MTRF_Label) 217 defineLabel(Value.LabelID); 218 Contents.push_back(Value); 219 CurrentSize += Value.size(); 220 } 221 222 unsigned allocateLabelID() { return CurrentLabelID++; } 223 224 void defineLabel(unsigned LabelID) { 225 LabelMap.insert(std::make_pair(LabelID, CurrentSize)); 226 } 227 228 unsigned getLabelIndex(unsigned LabelID) const { 229 const auto I = LabelMap.find(LabelID); 230 assert(I != LabelMap.end() && "Use of undeclared label"); 231 return I->second; 232 } 233 234 void emitUse(raw_ostream &OS) const; 235 void emitDeclaration(raw_ostream &OS) const; 236 }; 237 238 inline MatchTable &operator<<(MatchTable &Table, 239 const MatchTableRecord &Value) { 240 Table.push_back(Value); 241 return Table; 242 } 243 244 /// This class stands in for LLT wherever we want to tablegen-erate an 245 /// equivalent at compiler run-time. 246 class LLTCodeGen { 247 private: 248 LLT Ty; 249 250 public: 251 LLTCodeGen() = default; 252 LLTCodeGen(const LLT &Ty) : Ty(Ty) {} 253 254 std::string getCxxEnumValue() const; 255 256 void emitCxxEnumValue(raw_ostream &OS) const; 257 void emitCxxConstructorCall(raw_ostream &OS) const; 258 259 const LLT &get() const { return Ty; } 260 261 /// This ordering is used for std::unique() and llvm::sort(). There's no 262 /// particular logic behind the order but either A < B or B < A must be 263 /// true if A != B. 264 bool operator<(const LLTCodeGen &Other) const; 265 bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; } 266 }; 267 268 // Track all types that are used so we can emit the corresponding enum. 269 extern std::set<LLTCodeGen> KnownTypes; 270 271 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for 272 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...). 273 std::optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT); 274 275 //===- Matchers -----------------------------------------------------------===// 276 class Matcher { 277 public: 278 virtual ~Matcher(); 279 virtual void optimize(); 280 virtual void emit(MatchTable &Table) = 0; 281 282 virtual bool hasFirstCondition() const = 0; 283 virtual const PredicateMatcher &getFirstCondition() const = 0; 284 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0; 285 }; 286 287 class GroupMatcher final : public Matcher { 288 /// Conditions that form a common prefix of all the matchers contained. 289 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions; 290 291 /// All the nested matchers, sharing a common prefix. 292 std::vector<Matcher *> Matchers; 293 294 /// An owning collection for any auxiliary matchers created while optimizing 295 /// nested matchers contained. 296 std::vector<std::unique_ptr<Matcher>> MatcherStorage; 297 298 public: 299 /// Add a matcher to the collection of nested matchers if it meets the 300 /// requirements, and return true. If it doesn't, do nothing and return false. 301 /// 302 /// Expected to preserve its argument, so it could be moved out later on. 303 bool addMatcher(Matcher &Candidate); 304 305 /// Mark the matcher as fully-built and ensure any invariants expected by both 306 /// optimize() and emit(...) methods. Generally, both sequences of calls 307 /// are expected to lead to a sensible result: 308 /// 309 /// addMatcher(...)*; finalize(); optimize(); emit(...); and 310 /// addMatcher(...)*; finalize(); emit(...); 311 /// 312 /// or generally 313 /// 314 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }* 315 /// 316 /// Multiple calls to optimize() are expected to be handled gracefully, though 317 /// optimize() is not expected to be idempotent. Multiple calls to finalize() 318 /// aren't generally supported. emit(...) is expected to be non-mutating and 319 /// producing the exact same results upon repeated calls. 320 /// 321 /// addMatcher() calls after the finalize() call are not supported. 322 /// 323 /// finalize() and optimize() are both allowed to mutate the contained 324 /// matchers, so moving them out after finalize() is not supported. 325 void finalize(); 326 void optimize() override; 327 void emit(MatchTable &Table) override; 328 329 /// Could be used to move out the matchers added previously, unless finalize() 330 /// has been already called. If any of the matchers are moved out, the group 331 /// becomes safe to destroy, but not safe to re-use for anything else. 332 iterator_range<std::vector<Matcher *>::iterator> matchers() { 333 return make_range(Matchers.begin(), Matchers.end()); 334 } 335 size_t size() const { return Matchers.size(); } 336 bool empty() const { return Matchers.empty(); } 337 338 std::unique_ptr<PredicateMatcher> popFirstCondition() override { 339 assert(!Conditions.empty() && 340 "Trying to pop a condition from a condition-less group"); 341 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front()); 342 Conditions.erase(Conditions.begin()); 343 return P; 344 } 345 const PredicateMatcher &getFirstCondition() const override { 346 assert(!Conditions.empty() && 347 "Trying to get a condition from a condition-less group"); 348 return *Conditions.front(); 349 } 350 bool hasFirstCondition() const override { return !Conditions.empty(); } 351 352 private: 353 /// See if a candidate matcher could be added to this group solely by 354 /// analyzing its first condition. 355 bool candidateConditionMatches(const PredicateMatcher &Predicate) const; 356 }; 357 358 class SwitchMatcher : public Matcher { 359 /// All the nested matchers, representing distinct switch-cases. The first 360 /// conditions (as Matcher::getFirstCondition() reports) of all the nested 361 /// matchers must share the same type and path to a value they check, in other 362 /// words, be isIdenticalDownToValue, but have different values they check 363 /// against. 364 std::vector<Matcher *> Matchers; 365 366 /// The representative condition, with a type and a path (InsnVarID and OpIdx 367 /// in most cases) shared by all the matchers contained. 368 std::unique_ptr<PredicateMatcher> Condition = nullptr; 369 370 /// Temporary set used to check that the case values don't repeat within the 371 /// same switch. 372 std::set<MatchTableRecord> Values; 373 374 /// An owning collection for any auxiliary matchers created while optimizing 375 /// nested matchers contained. 376 std::vector<std::unique_ptr<Matcher>> MatcherStorage; 377 378 public: 379 bool addMatcher(Matcher &Candidate); 380 381 void finalize(); 382 void emit(MatchTable &Table) override; 383 384 iterator_range<std::vector<Matcher *>::iterator> matchers() { 385 return make_range(Matchers.begin(), Matchers.end()); 386 } 387 size_t size() const { return Matchers.size(); } 388 bool empty() const { return Matchers.empty(); } 389 390 std::unique_ptr<PredicateMatcher> popFirstCondition() override { 391 // SwitchMatcher doesn't have a common first condition for its cases, as all 392 // the cases only share a kind of a value (a type and a path to it) they 393 // match, but deliberately differ in the actual value they match. 394 llvm_unreachable("Trying to pop a condition from a condition-less group"); 395 } 396 397 const PredicateMatcher &getFirstCondition() const override { 398 llvm_unreachable("Trying to pop a condition from a condition-less group"); 399 } 400 401 bool hasFirstCondition() const override { return false; } 402 403 private: 404 /// See if the predicate type has a Switch-implementation for it. 405 static bool isSupportedPredicateType(const PredicateMatcher &Predicate); 406 407 bool candidateConditionMatches(const PredicateMatcher &Predicate) const; 408 409 /// emit()-helper 410 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P, 411 MatchTable &Table); 412 }; 413 414 /// Generates code to check that a match rule matches. 415 class RuleMatcher : public Matcher { 416 public: 417 using ActionList = std::list<std::unique_ptr<MatchAction>>; 418 using action_iterator = ActionList::iterator; 419 420 protected: 421 /// A list of matchers that all need to succeed for the current rule to match. 422 /// FIXME: This currently supports a single match position but could be 423 /// extended to support multiple positions to support div/rem fusion or 424 /// load-multiple instructions. 425 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>>; 426 MatchersTy Matchers; 427 428 /// A list of actions that need to be taken when all predicates in this rule 429 /// have succeeded. 430 ActionList Actions; 431 432 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>; 433 434 /// A map of instruction matchers to the local variables 435 DefinedInsnVariablesMap InsnVariableIDs; 436 437 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>; 438 439 // The set of instruction matchers that have not yet been claimed for mutation 440 // by a BuildMI. 441 MutatableInsnSet MutatableInsns; 442 443 /// A map of named operands defined by the matchers that may be referenced by 444 /// the renderers. 445 StringMap<OperandMatcher *> DefinedOperands; 446 447 /// A map of anonymous physical register operands defined by the matchers that 448 /// may be referenced by the renderers. 449 DenseMap<Record *, OperandMatcher *> PhysRegOperands; 450 451 /// ID for the next instruction variable defined with 452 /// implicitlyDefineInsnVar() 453 unsigned NextInsnVarID; 454 455 /// ID for the next output instruction allocated with allocateOutputInsnID() 456 unsigned NextOutputInsnID; 457 458 /// ID for the next temporary register ID allocated with allocateTempRegID() 459 unsigned NextTempRegID; 460 461 /// Current GISelFlags 462 GISelFlags Flags = 0; 463 464 std::vector<std::string> RequiredSimplePredicates; 465 std::vector<Record *> RequiredFeatures; 466 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers; 467 468 ArrayRef<SMLoc> SrcLoc; 469 470 typedef std::tuple<Record *, unsigned, unsigned> 471 DefinedComplexPatternSubOperand; 472 typedef StringMap<DefinedComplexPatternSubOperand> 473 DefinedComplexPatternSubOperandMap; 474 /// A map of Symbolic Names to ComplexPattern sub-operands. 475 DefinedComplexPatternSubOperandMap ComplexSubOperands; 476 /// A map used to for multiple referenced error check of ComplexSubOperand. 477 /// ComplexSubOperand can't be referenced multiple from different operands, 478 /// however multiple references from same operand are allowed since that is 479 /// how 'same operand checks' are generated. 480 StringMap<std::string> ComplexSubOperandsParentName; 481 482 uint64_t RuleID; 483 static uint64_t NextRuleID; 484 485 GISelFlags updateGISelFlag(GISelFlags CurFlags, const Record *R, 486 StringRef FlagName, GISelFlags FlagBit); 487 488 public: 489 RuleMatcher(ArrayRef<SMLoc> SrcLoc) 490 : NextInsnVarID(0), NextOutputInsnID(0), NextTempRegID(0), SrcLoc(SrcLoc), 491 RuleID(NextRuleID++) {} 492 RuleMatcher(RuleMatcher &&Other) = default; 493 RuleMatcher &operator=(RuleMatcher &&Other) = default; 494 495 uint64_t getRuleID() const { return RuleID; } 496 497 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName); 498 void addRequiredFeature(Record *Feature); 499 const std::vector<Record *> &getRequiredFeatures() const; 500 501 void addRequiredSimplePredicate(StringRef PredName); 502 const std::vector<std::string> &getRequiredSimplePredicates(); 503 504 // Emplaces an action of the specified Kind at the end of the action list. 505 // 506 // Returns a reference to the newly created action. 507 // 508 // Like std::vector::emplace_back(), may invalidate all iterators if the new 509 // size exceeds the capacity. Otherwise, only invalidates the past-the-end 510 // iterator. 511 template <class Kind, class... Args> Kind &addAction(Args &&...args) { 512 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...)); 513 return *static_cast<Kind *>(Actions.back().get()); 514 } 515 516 // Emplaces an action of the specified Kind before the given insertion point. 517 // 518 // Returns an iterator pointing at the newly created instruction. 519 // 520 // Like std::vector::insert(), may invalidate all iterators if the new size 521 // exceeds the capacity. Otherwise, only invalidates the iterators from the 522 // insertion point onwards. 523 template <class Kind, class... Args> 524 action_iterator insertAction(action_iterator InsertPt, Args &&...args) { 525 return Actions.emplace(InsertPt, 526 std::make_unique<Kind>(std::forward<Args>(args)...)); 527 } 528 529 // Update the active GISelFlags based on the GISelFlags Record R. 530 // A SaveAndRestore object is returned so the old GISelFlags are restored 531 // at the end of the scope. 532 SaveAndRestore<GISelFlags> setGISelFlags(const Record *R); 533 GISelFlags getGISelFlags() const { return Flags; } 534 535 /// Define an instruction without emitting any code to do so. 536 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher); 537 538 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const; 539 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const { 540 return InsnVariableIDs.begin(); 541 } 542 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const { 543 return InsnVariableIDs.end(); 544 } 545 iterator_range<typename DefinedInsnVariablesMap::const_iterator> 546 defined_insn_vars() const { 547 return make_range(defined_insn_vars_begin(), defined_insn_vars_end()); 548 } 549 550 MutatableInsnSet::const_iterator mutatable_insns_begin() const { 551 return MutatableInsns.begin(); 552 } 553 MutatableInsnSet::const_iterator mutatable_insns_end() const { 554 return MutatableInsns.end(); 555 } 556 iterator_range<typename MutatableInsnSet::const_iterator> 557 mutatable_insns() const { 558 return make_range(mutatable_insns_begin(), mutatable_insns_end()); 559 } 560 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) { 561 bool R = MutatableInsns.erase(InsnMatcher); 562 assert(R && "Reserving a mutatable insn that isn't available"); 563 (void)R; 564 } 565 566 action_iterator actions_begin() { return Actions.begin(); } 567 action_iterator actions_end() { return Actions.end(); } 568 iterator_range<action_iterator> actions() { 569 return make_range(actions_begin(), actions_end()); 570 } 571 572 void defineOperand(StringRef SymbolicName, OperandMatcher &OM); 573 574 void definePhysRegOperand(Record *Reg, OperandMatcher &OM); 575 576 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern, 577 unsigned RendererID, unsigned SubOperandID, 578 StringRef ParentSymbolicName); 579 580 std::optional<DefinedComplexPatternSubOperand> 581 getComplexSubOperand(StringRef SymbolicName) const { 582 const auto &I = ComplexSubOperands.find(SymbolicName); 583 if (I == ComplexSubOperands.end()) 584 return std::nullopt; 585 return I->second; 586 } 587 588 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const; 589 const OperandMatcher &getOperandMatcher(StringRef Name) const; 590 const OperandMatcher &getPhysRegOperandMatcher(Record *) const; 591 592 void optimize() override; 593 void emit(MatchTable &Table) override; 594 595 /// Compare the priority of this object and B. 596 /// 597 /// Returns true if this object is more important than B. 598 bool isHigherPriorityThan(const RuleMatcher &B) const; 599 600 /// Report the maximum number of temporary operands needed by the rule 601 /// matcher. 602 unsigned countRendererFns() const; 603 604 std::unique_ptr<PredicateMatcher> popFirstCondition() override; 605 const PredicateMatcher &getFirstCondition() const override; 606 LLTCodeGen getFirstConditionAsRootType(); 607 bool hasFirstCondition() const override; 608 unsigned getNumOperands() const; 609 StringRef getOpcode() const; 610 611 // FIXME: Remove this as soon as possible 612 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); } 613 614 unsigned allocateOutputInsnID() { return NextOutputInsnID++; } 615 unsigned allocateTempRegID() { return NextTempRegID++; } 616 617 iterator_range<MatchersTy::iterator> insnmatchers() { 618 return make_range(Matchers.begin(), Matchers.end()); 619 } 620 bool insnmatchers_empty() const { return Matchers.empty(); } 621 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); } 622 }; 623 624 template <class PredicateTy> class PredicateListMatcher { 625 private: 626 /// Template instantiations should specialize this to return a string to use 627 /// for the comment emitted when there are no predicates. 628 std::string getNoPredicateComment() const; 629 630 protected: 631 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>; 632 PredicatesTy Predicates; 633 634 /// Track if the list of predicates was manipulated by one of the optimization 635 /// methods. 636 bool Optimized = false; 637 638 public: 639 typename PredicatesTy::iterator predicates_begin() { 640 return Predicates.begin(); 641 } 642 typename PredicatesTy::iterator predicates_end() { return Predicates.end(); } 643 iterator_range<typename PredicatesTy::iterator> predicates() { 644 return make_range(predicates_begin(), predicates_end()); 645 } 646 typename PredicatesTy::size_type predicates_size() const { 647 return Predicates.size(); 648 } 649 bool predicates_empty() const { return Predicates.empty(); } 650 651 std::unique_ptr<PredicateTy> predicates_pop_front() { 652 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front()); 653 Predicates.pop_front(); 654 Optimized = true; 655 return Front; 656 } 657 658 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) { 659 Predicates.push_front(std::move(Predicate)); 660 } 661 662 void eraseNullPredicates() { 663 const auto NewEnd = 664 std::stable_partition(Predicates.begin(), Predicates.end(), 665 std::logical_not<std::unique_ptr<PredicateTy>>()); 666 if (NewEnd != Predicates.begin()) { 667 Predicates.erase(Predicates.begin(), NewEnd); 668 Optimized = true; 669 } 670 } 671 672 /// Emit MatchTable opcodes that tests whether all the predicates are met. 673 template <class... Args> 674 void emitPredicateListOpcodes(MatchTable &Table, Args &&...args) { 675 if (Predicates.empty() && !Optimized) { 676 Table << MatchTable::Comment(getNoPredicateComment()) 677 << MatchTable::LineBreak; 678 return; 679 } 680 681 for (const auto &Predicate : predicates()) 682 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...); 683 } 684 685 /// Provide a function to avoid emitting certain predicates. This is used to 686 /// defer some predicate checks until after others 687 using PredicateFilterFunc = std::function<bool(const PredicateTy &)>; 688 689 /// Emit MatchTable opcodes for predicates which satisfy \p 690 /// ShouldEmitPredicate. This should be called multiple times to ensure all 691 /// predicates are eventually added to the match table. 692 template <class... Args> 693 void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate, 694 MatchTable &Table, Args &&...args) { 695 if (Predicates.empty() && !Optimized) { 696 Table << MatchTable::Comment(getNoPredicateComment()) 697 << MatchTable::LineBreak; 698 return; 699 } 700 701 for (const auto &Predicate : predicates()) { 702 if (ShouldEmitPredicate(*Predicate)) 703 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...); 704 } 705 } 706 }; 707 708 class PredicateMatcher { 709 public: 710 /// This enum is used for RTTI and also defines the priority that is given to 711 /// the predicate when generating the matcher code. Kinds with higher priority 712 /// must be tested first. 713 /// 714 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter 715 /// but OPM_Int must have priority over OPM_RegBank since constant integers 716 /// are represented by a virtual register defined by a G_CONSTANT instruction. 717 /// 718 /// Note: The relative priority between IPM_ and OPM_ does not matter, they 719 /// are currently not compared between each other. 720 enum PredicateKind { 721 IPM_Opcode, 722 IPM_NumOperands, 723 IPM_ImmPredicate, 724 IPM_Imm, 725 IPM_AtomicOrderingMMO, 726 IPM_MemoryLLTSize, 727 IPM_MemoryVsLLTSize, 728 IPM_MemoryAddressSpace, 729 IPM_MemoryAlignment, 730 IPM_VectorSplatImm, 731 IPM_NoUse, 732 IPM_GenericPredicate, 733 OPM_SameOperand, 734 OPM_ComplexPattern, 735 OPM_IntrinsicID, 736 OPM_CmpPredicate, 737 OPM_Instruction, 738 OPM_Int, 739 OPM_LiteralInt, 740 OPM_LLT, 741 OPM_PointerToAny, 742 OPM_RegBank, 743 OPM_MBB, 744 OPM_RecordNamedOperand, 745 }; 746 747 protected: 748 PredicateKind Kind; 749 unsigned InsnVarID; 750 unsigned OpIdx; 751 752 public: 753 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0) 754 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {} 755 virtual ~PredicateMatcher(); 756 757 unsigned getInsnVarID() const { return InsnVarID; } 758 unsigned getOpIdx() const { return OpIdx; } 759 760 /// Emit MatchTable opcodes that check the predicate for the given operand. 761 virtual void emitPredicateOpcodes(MatchTable &Table, 762 RuleMatcher &Rule) const = 0; 763 764 PredicateKind getKind() const { return Kind; } 765 766 bool dependsOnOperands() const { 767 // Custom predicates really depend on the context pattern of the 768 // instruction, not just the individual instruction. This therefore 769 // implicitly depends on all other pattern constraints. 770 return Kind == IPM_GenericPredicate; 771 } 772 773 virtual bool isIdentical(const PredicateMatcher &B) const { 774 return B.getKind() == getKind() && InsnVarID == B.InsnVarID && 775 OpIdx == B.OpIdx; 776 } 777 778 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const { 779 return hasValue() && PredicateMatcher::isIdentical(B); 780 } 781 782 virtual MatchTableRecord getValue() const { 783 assert(hasValue() && "Can not get a value of a value-less predicate!"); 784 llvm_unreachable("Not implemented yet"); 785 } 786 virtual bool hasValue() const { return false; } 787 788 /// Report the maximum number of temporary operands needed by the predicate 789 /// matcher. 790 virtual unsigned countRendererFns() const { return 0; } 791 }; 792 793 /// Generates code to check a predicate of an operand. 794 /// 795 /// Typical predicates include: 796 /// * Operand is a particular register. 797 /// * Operand is assigned a particular register bank. 798 /// * Operand is an MBB. 799 class OperandPredicateMatcher : public PredicateMatcher { 800 public: 801 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID, 802 unsigned OpIdx) 803 : PredicateMatcher(Kind, InsnVarID, OpIdx) {} 804 virtual ~OperandPredicateMatcher(); 805 806 /// Compare the priority of this object and B. 807 /// 808 /// Returns true if this object is more important than B. 809 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const; 810 }; 811 812 template <> 813 inline std::string 814 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const { 815 return "No operand predicates"; 816 } 817 818 /// Generates code to check that a register operand is defined by the same exact 819 /// one as another. 820 class SameOperandMatcher : public OperandPredicateMatcher { 821 std::string MatchingName; 822 unsigned OrigOpIdx; 823 824 GISelFlags Flags; 825 826 public: 827 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName, 828 unsigned OrigOpIdx, GISelFlags Flags) 829 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx), 830 MatchingName(MatchingName), OrigOpIdx(OrigOpIdx), Flags(Flags) {} 831 832 static bool classof(const PredicateMatcher *P) { 833 return P->getKind() == OPM_SameOperand; 834 } 835 836 void emitPredicateOpcodes(MatchTable &Table, 837 RuleMatcher &Rule) const override; 838 839 bool isIdentical(const PredicateMatcher &B) const override { 840 return OperandPredicateMatcher::isIdentical(B) && 841 OrigOpIdx == cast<SameOperandMatcher>(&B)->OrigOpIdx && 842 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName; 843 } 844 }; 845 846 /// Generates code to check that an operand is a particular LLT. 847 class LLTOperandMatcher : public OperandPredicateMatcher { 848 protected: 849 LLTCodeGen Ty; 850 851 public: 852 static std::map<LLTCodeGen, unsigned> TypeIDValues; 853 854 static void initTypeIDValuesMap() { 855 TypeIDValues.clear(); 856 857 unsigned ID = 0; 858 for (const LLTCodeGen &LLTy : KnownTypes) 859 TypeIDValues[LLTy] = ID++; 860 } 861 862 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty) 863 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) { 864 KnownTypes.insert(Ty); 865 } 866 867 static bool classof(const PredicateMatcher *P) { 868 return P->getKind() == OPM_LLT; 869 } 870 871 bool isIdentical(const PredicateMatcher &B) const override { 872 return OperandPredicateMatcher::isIdentical(B) && 873 Ty == cast<LLTOperandMatcher>(&B)->Ty; 874 } 875 876 MatchTableRecord getValue() const override; 877 bool hasValue() const override; 878 879 LLTCodeGen getTy() const { return Ty; } 880 881 void emitPredicateOpcodes(MatchTable &Table, 882 RuleMatcher &Rule) const override; 883 }; 884 885 /// Generates code to check that an operand is a pointer to any address space. 886 /// 887 /// In SelectionDAG, the types did not describe pointers or address spaces. As a 888 /// result, iN is used to describe a pointer of N bits to any address space and 889 /// PatFrag predicates are typically used to constrain the address space. 890 /// There's no reliable means to derive the missing type information from the 891 /// pattern so imported rules must test the components of a pointer separately. 892 /// 893 /// If SizeInBits is zero, then the pointer size will be obtained from the 894 /// subtarget. 895 class PointerToAnyOperandMatcher : public OperandPredicateMatcher { 896 protected: 897 unsigned SizeInBits; 898 899 public: 900 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 901 unsigned SizeInBits) 902 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx), 903 SizeInBits(SizeInBits) {} 904 905 static bool classof(const PredicateMatcher *P) { 906 return P->getKind() == OPM_PointerToAny; 907 } 908 909 bool isIdentical(const PredicateMatcher &B) const override { 910 return OperandPredicateMatcher::isIdentical(B) && 911 SizeInBits == cast<PointerToAnyOperandMatcher>(&B)->SizeInBits; 912 } 913 914 void emitPredicateOpcodes(MatchTable &Table, 915 RuleMatcher &Rule) const override; 916 }; 917 918 /// Generates code to record named operand in RecordedOperands list at StoreIdx. 919 /// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as 920 /// an argument to predicate's c++ code once all operands have been matched. 921 class RecordNamedOperandMatcher : public OperandPredicateMatcher { 922 protected: 923 unsigned StoreIdx; 924 std::string Name; 925 926 public: 927 RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 928 unsigned StoreIdx, StringRef Name) 929 : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx), 930 StoreIdx(StoreIdx), Name(Name) {} 931 932 static bool classof(const PredicateMatcher *P) { 933 return P->getKind() == OPM_RecordNamedOperand; 934 } 935 936 bool isIdentical(const PredicateMatcher &B) const override { 937 return OperandPredicateMatcher::isIdentical(B) && 938 StoreIdx == cast<RecordNamedOperandMatcher>(&B)->StoreIdx && 939 Name == cast<RecordNamedOperandMatcher>(&B)->Name; 940 } 941 942 void emitPredicateOpcodes(MatchTable &Table, 943 RuleMatcher &Rule) const override; 944 }; 945 946 /// Generates code to check that an operand is a particular target constant. 947 class ComplexPatternOperandMatcher : public OperandPredicateMatcher { 948 protected: 949 const OperandMatcher &Operand; 950 const Record &TheDef; 951 952 unsigned getAllocatedTemporariesBaseID() const; 953 954 public: 955 bool isIdentical(const PredicateMatcher &B) const override { return false; } 956 957 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 958 const OperandMatcher &Operand, 959 const Record &TheDef) 960 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx), 961 Operand(Operand), TheDef(TheDef) {} 962 963 static bool classof(const PredicateMatcher *P) { 964 return P->getKind() == OPM_ComplexPattern; 965 } 966 967 void emitPredicateOpcodes(MatchTable &Table, 968 RuleMatcher &Rule) const override; 969 unsigned countRendererFns() const override { return 1; } 970 }; 971 972 /// Generates code to check that an operand is in a particular register bank. 973 class RegisterBankOperandMatcher : public OperandPredicateMatcher { 974 protected: 975 const CodeGenRegisterClass &RC; 976 977 public: 978 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 979 const CodeGenRegisterClass &RC) 980 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {} 981 982 bool isIdentical(const PredicateMatcher &B) const override; 983 984 static bool classof(const PredicateMatcher *P) { 985 return P->getKind() == OPM_RegBank; 986 } 987 988 void emitPredicateOpcodes(MatchTable &Table, 989 RuleMatcher &Rule) const override; 990 }; 991 992 /// Generates code to check that an operand is a basic block. 993 class MBBOperandMatcher : public OperandPredicateMatcher { 994 public: 995 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx) 996 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {} 997 998 static bool classof(const PredicateMatcher *P) { 999 return P->getKind() == OPM_MBB; 1000 } 1001 1002 void emitPredicateOpcodes(MatchTable &Table, 1003 RuleMatcher &Rule) const override; 1004 }; 1005 1006 class ImmOperandMatcher : public OperandPredicateMatcher { 1007 public: 1008 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx) 1009 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {} 1010 1011 static bool classof(const PredicateMatcher *P) { 1012 return P->getKind() == IPM_Imm; 1013 } 1014 1015 void emitPredicateOpcodes(MatchTable &Table, 1016 RuleMatcher &Rule) const override; 1017 }; 1018 1019 /// Generates code to check that an operand is a G_CONSTANT with a particular 1020 /// int. 1021 class ConstantIntOperandMatcher : public OperandPredicateMatcher { 1022 protected: 1023 int64_t Value; 1024 1025 public: 1026 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) 1027 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {} 1028 1029 bool isIdentical(const PredicateMatcher &B) const override { 1030 return OperandPredicateMatcher::isIdentical(B) && 1031 Value == cast<ConstantIntOperandMatcher>(&B)->Value; 1032 } 1033 1034 static bool classof(const PredicateMatcher *P) { 1035 return P->getKind() == OPM_Int; 1036 } 1037 1038 void emitPredicateOpcodes(MatchTable &Table, 1039 RuleMatcher &Rule) const override; 1040 }; 1041 1042 /// Generates code to check that an operand is a raw int (where MO.isImm() or 1043 /// MO.isCImm() is true). 1044 class LiteralIntOperandMatcher : public OperandPredicateMatcher { 1045 protected: 1046 int64_t Value; 1047 1048 public: 1049 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) 1050 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx), 1051 Value(Value) {} 1052 1053 bool isIdentical(const PredicateMatcher &B) const override { 1054 return OperandPredicateMatcher::isIdentical(B) && 1055 Value == cast<LiteralIntOperandMatcher>(&B)->Value; 1056 } 1057 1058 static bool classof(const PredicateMatcher *P) { 1059 return P->getKind() == OPM_LiteralInt; 1060 } 1061 1062 void emitPredicateOpcodes(MatchTable &Table, 1063 RuleMatcher &Rule) const override; 1064 }; 1065 1066 /// Generates code to check that an operand is an CmpInst predicate 1067 class CmpPredicateOperandMatcher : public OperandPredicateMatcher { 1068 protected: 1069 std::string PredName; 1070 1071 public: 1072 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx, std::string P) 1073 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), 1074 PredName(P) {} 1075 1076 bool isIdentical(const PredicateMatcher &B) const override { 1077 return OperandPredicateMatcher::isIdentical(B) && 1078 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName; 1079 } 1080 1081 static bool classof(const PredicateMatcher *P) { 1082 return P->getKind() == OPM_CmpPredicate; 1083 } 1084 1085 void emitPredicateOpcodes(MatchTable &Table, 1086 RuleMatcher &Rule) const override; 1087 }; 1088 1089 /// Generates code to check that an operand is an intrinsic ID. 1090 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher { 1091 protected: 1092 const CodeGenIntrinsic *II; 1093 1094 public: 1095 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 1096 const CodeGenIntrinsic *II) 1097 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {} 1098 1099 bool isIdentical(const PredicateMatcher &B) const override { 1100 return OperandPredicateMatcher::isIdentical(B) && 1101 II == cast<IntrinsicIDOperandMatcher>(&B)->II; 1102 } 1103 1104 static bool classof(const PredicateMatcher *P) { 1105 return P->getKind() == OPM_IntrinsicID; 1106 } 1107 1108 void emitPredicateOpcodes(MatchTable &Table, 1109 RuleMatcher &Rule) const override; 1110 }; 1111 1112 /// Generates code to check that this operand is an immediate whose value meets 1113 /// an immediate predicate. 1114 class OperandImmPredicateMatcher : public OperandPredicateMatcher { 1115 protected: 1116 TreePredicateFn Predicate; 1117 1118 public: 1119 OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx, 1120 const TreePredicateFn &Predicate) 1121 : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx), 1122 Predicate(Predicate) {} 1123 1124 bool isIdentical(const PredicateMatcher &B) const override { 1125 return OperandPredicateMatcher::isIdentical(B) && 1126 Predicate.getOrigPatFragRecord() == 1127 cast<OperandImmPredicateMatcher>(&B) 1128 ->Predicate.getOrigPatFragRecord(); 1129 } 1130 1131 static bool classof(const PredicateMatcher *P) { 1132 return P->getKind() == IPM_ImmPredicate; 1133 } 1134 1135 void emitPredicateOpcodes(MatchTable &Table, 1136 RuleMatcher &Rule) const override; 1137 }; 1138 1139 /// Generates code to check that a set of predicates match for a particular 1140 /// operand. 1141 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> { 1142 protected: 1143 InstructionMatcher &Insn; 1144 unsigned OpIdx; 1145 std::string SymbolicName; 1146 1147 /// The index of the first temporary variable allocated to this operand. The 1148 /// number of allocated temporaries can be found with 1149 /// countRendererFns(). 1150 unsigned AllocatedTemporariesBaseID; 1151 1152 public: 1153 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx, 1154 const std::string &SymbolicName, 1155 unsigned AllocatedTemporariesBaseID) 1156 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName), 1157 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {} 1158 1159 bool hasSymbolicName() const { return !SymbolicName.empty(); } 1160 StringRef getSymbolicName() const { return SymbolicName; } 1161 void setSymbolicName(StringRef Name) { 1162 assert(SymbolicName.empty() && "Operand already has a symbolic name"); 1163 SymbolicName = std::string(Name); 1164 } 1165 1166 /// Construct a new operand predicate and add it to the matcher. 1167 template <class Kind, class... Args> 1168 std::optional<Kind *> addPredicate(Args &&...args) { 1169 if (isSameAsAnotherOperand()) 1170 return std::nullopt; 1171 Predicates.emplace_back(std::make_unique<Kind>( 1172 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...)); 1173 return static_cast<Kind *>(Predicates.back().get()); 1174 } 1175 1176 unsigned getOpIdx() const { return OpIdx; } 1177 unsigned getInsnVarID() const; 1178 1179 std::string getOperandExpr(unsigned InsnVarID) const; 1180 1181 InstructionMatcher &getInstructionMatcher() const { return Insn; } 1182 1183 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy, 1184 bool OperandIsAPointer); 1185 1186 /// Emit MatchTable opcodes that test whether the instruction named in 1187 /// InsnVarID matches all the predicates and all the operands. 1188 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule); 1189 1190 /// Compare the priority of this object and B. 1191 /// 1192 /// Returns true if this object is more important than B. 1193 bool isHigherPriorityThan(OperandMatcher &B); 1194 1195 /// Report the maximum number of temporary operands needed by the operand 1196 /// matcher. 1197 unsigned countRendererFns(); 1198 1199 unsigned getAllocatedTemporariesBaseID() const { 1200 return AllocatedTemporariesBaseID; 1201 } 1202 1203 bool isSameAsAnotherOperand() { 1204 for (const auto &Predicate : predicates()) 1205 if (isa<SameOperandMatcher>(Predicate)) 1206 return true; 1207 return false; 1208 } 1209 }; 1210 1211 /// Generates code to check a predicate on an instruction. 1212 /// 1213 /// Typical predicates include: 1214 /// * The opcode of the instruction is a particular value. 1215 /// * The nsw/nuw flag is/isn't set. 1216 class InstructionPredicateMatcher : public PredicateMatcher { 1217 public: 1218 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID) 1219 : PredicateMatcher(Kind, InsnVarID) {} 1220 virtual ~InstructionPredicateMatcher() {} 1221 1222 /// Compare the priority of this object and B. 1223 /// 1224 /// Returns true if this object is more important than B. 1225 virtual bool 1226 isHigherPriorityThan(const InstructionPredicateMatcher &B) const { 1227 return Kind < B.Kind; 1228 }; 1229 }; 1230 1231 template <> 1232 inline std::string 1233 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const { 1234 return "No instruction predicates"; 1235 } 1236 1237 /// Generates code to check the opcode of an instruction. 1238 class InstructionOpcodeMatcher : public InstructionPredicateMatcher { 1239 protected: 1240 // Allow matching one to several, similar opcodes that share properties. This 1241 // is to handle patterns where one SelectionDAG operation maps to multiple 1242 // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first 1243 // is treated as the canonical opcode. 1244 SmallVector<const CodeGenInstruction *, 2> Insts; 1245 1246 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues; 1247 1248 MatchTableRecord getInstValue(const CodeGenInstruction *I) const; 1249 1250 public: 1251 static void initOpcodeValuesMap(const CodeGenTarget &Target); 1252 1253 InstructionOpcodeMatcher(unsigned InsnVarID, 1254 ArrayRef<const CodeGenInstruction *> I) 1255 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), 1256 Insts(I.begin(), I.end()) { 1257 assert((Insts.size() == 1 || Insts.size() == 2) && 1258 "unexpected number of opcode alternatives"); 1259 } 1260 1261 static bool classof(const PredicateMatcher *P) { 1262 return P->getKind() == IPM_Opcode; 1263 } 1264 1265 bool isIdentical(const PredicateMatcher &B) const override { 1266 return InstructionPredicateMatcher::isIdentical(B) && 1267 Insts == cast<InstructionOpcodeMatcher>(&B)->Insts; 1268 } 1269 1270 bool hasValue() const override { 1271 return Insts.size() == 1 && OpcodeValues.count(Insts[0]); 1272 } 1273 1274 // TODO: This is used for the SwitchMatcher optimization. We should be able to 1275 // return a list of the opcodes to match. 1276 MatchTableRecord getValue() const override; 1277 1278 void emitPredicateOpcodes(MatchTable &Table, 1279 RuleMatcher &Rule) const override; 1280 1281 /// Compare the priority of this object and B. 1282 /// 1283 /// Returns true if this object is more important than B. 1284 bool 1285 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override; 1286 1287 bool isConstantInstruction() const; 1288 1289 // The first opcode is the canonical opcode, and later are alternatives. 1290 StringRef getOpcode() const; 1291 ArrayRef<const CodeGenInstruction *> getAlternativeOpcodes() { return Insts; } 1292 bool isVariadicNumOperands() const; 1293 StringRef getOperandType(unsigned OpIdx) const; 1294 }; 1295 1296 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher { 1297 unsigned NumOperands = 0; 1298 1299 public: 1300 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands) 1301 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID), 1302 NumOperands(NumOperands) {} 1303 1304 static bool classof(const PredicateMatcher *P) { 1305 return P->getKind() == IPM_NumOperands; 1306 } 1307 1308 bool isIdentical(const PredicateMatcher &B) const override { 1309 return InstructionPredicateMatcher::isIdentical(B) && 1310 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands; 1311 } 1312 1313 void emitPredicateOpcodes(MatchTable &Table, 1314 RuleMatcher &Rule) const override; 1315 }; 1316 1317 /// Generates code to check that this instruction is a constant whose value 1318 /// meets an immediate predicate. 1319 /// 1320 /// Immediates are slightly odd since they are typically used like an operand 1321 /// but are represented as an operator internally. We typically write simm8:$src 1322 /// in a tablegen pattern, but this is just syntactic sugar for 1323 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes 1324 /// that will be matched and the predicate (which is attached to the imm 1325 /// operator) that will be tested. In SelectionDAG this describes a 1326 /// ConstantSDNode whose internal value will be tested using the simm8 1327 /// predicate. 1328 /// 1329 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In 1330 /// this representation, the immediate could be tested with an 1331 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a 1332 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but 1333 /// there are two implementation issues with producing that matcher 1334 /// configuration from the SelectionDAG pattern: 1335 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that 1336 /// were we to sink the immediate predicate to the operand we would have to 1337 /// have two partial implementations of PatFrag support, one for immediates 1338 /// and one for non-immediates. 1339 /// * At the point we handle the predicate, the OperandMatcher hasn't been 1340 /// created yet. If we were to sink the predicate to the OperandMatcher we 1341 /// would also have to complicate (or duplicate) the code that descends and 1342 /// creates matchers for the subtree. 1343 /// Overall, it's simpler to handle it in the place it was found. 1344 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher { 1345 protected: 1346 TreePredicateFn Predicate; 1347 1348 public: 1349 InstructionImmPredicateMatcher(unsigned InsnVarID, 1350 const TreePredicateFn &Predicate) 1351 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID), 1352 Predicate(Predicate) {} 1353 1354 bool isIdentical(const PredicateMatcher &B) const override; 1355 1356 static bool classof(const PredicateMatcher *P) { 1357 return P->getKind() == IPM_ImmPredicate; 1358 } 1359 1360 void emitPredicateOpcodes(MatchTable &Table, 1361 RuleMatcher &Rule) const override; 1362 }; 1363 1364 /// Generates code to check that a memory instruction has a atomic ordering 1365 /// MachineMemoryOperand. 1366 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher { 1367 public: 1368 enum AOComparator { 1369 AO_Exactly, 1370 AO_OrStronger, 1371 AO_WeakerThan, 1372 }; 1373 1374 protected: 1375 StringRef Order; 1376 AOComparator Comparator; 1377 1378 public: 1379 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order, 1380 AOComparator Comparator = AO_Exactly) 1381 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID), 1382 Order(Order), Comparator(Comparator) {} 1383 1384 static bool classof(const PredicateMatcher *P) { 1385 return P->getKind() == IPM_AtomicOrderingMMO; 1386 } 1387 1388 bool isIdentical(const PredicateMatcher &B) const override; 1389 1390 void emitPredicateOpcodes(MatchTable &Table, 1391 RuleMatcher &Rule) const override; 1392 }; 1393 1394 /// Generates code to check that the size of an MMO is exactly N bytes. 1395 class MemorySizePredicateMatcher : public InstructionPredicateMatcher { 1396 protected: 1397 unsigned MMOIdx; 1398 uint64_t Size; 1399 1400 public: 1401 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size) 1402 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID), 1403 MMOIdx(MMOIdx), Size(Size) {} 1404 1405 static bool classof(const PredicateMatcher *P) { 1406 return P->getKind() == IPM_MemoryLLTSize; 1407 } 1408 bool isIdentical(const PredicateMatcher &B) const override { 1409 return InstructionPredicateMatcher::isIdentical(B) && 1410 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx && 1411 Size == cast<MemorySizePredicateMatcher>(&B)->Size; 1412 } 1413 1414 void emitPredicateOpcodes(MatchTable &Table, 1415 RuleMatcher &Rule) const override; 1416 }; 1417 1418 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher { 1419 protected: 1420 unsigned MMOIdx; 1421 SmallVector<unsigned, 4> AddrSpaces; 1422 1423 public: 1424 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, 1425 ArrayRef<unsigned> AddrSpaces) 1426 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID), 1427 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {} 1428 1429 static bool classof(const PredicateMatcher *P) { 1430 return P->getKind() == IPM_MemoryAddressSpace; 1431 } 1432 1433 bool isIdentical(const PredicateMatcher &B) const override; 1434 1435 void emitPredicateOpcodes(MatchTable &Table, 1436 RuleMatcher &Rule) const override; 1437 }; 1438 1439 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher { 1440 protected: 1441 unsigned MMOIdx; 1442 int MinAlign; 1443 1444 public: 1445 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, 1446 int MinAlign) 1447 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID), 1448 MMOIdx(MMOIdx), MinAlign(MinAlign) { 1449 assert(MinAlign > 0); 1450 } 1451 1452 static bool classof(const PredicateMatcher *P) { 1453 return P->getKind() == IPM_MemoryAlignment; 1454 } 1455 1456 bool isIdentical(const PredicateMatcher &B) const override; 1457 1458 void emitPredicateOpcodes(MatchTable &Table, 1459 RuleMatcher &Rule) const override; 1460 }; 1461 1462 /// Generates code to check that the size of an MMO is less-than, equal-to, or 1463 /// greater than a given LLT. 1464 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher { 1465 public: 1466 enum RelationKind { 1467 GreaterThan, 1468 EqualTo, 1469 LessThan, 1470 }; 1471 1472 protected: 1473 unsigned MMOIdx; 1474 RelationKind Relation; 1475 unsigned OpIdx; 1476 1477 public: 1478 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, 1479 enum RelationKind Relation, unsigned OpIdx) 1480 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID), 1481 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {} 1482 1483 static bool classof(const PredicateMatcher *P) { 1484 return P->getKind() == IPM_MemoryVsLLTSize; 1485 } 1486 bool isIdentical(const PredicateMatcher &B) const override; 1487 1488 void emitPredicateOpcodes(MatchTable &Table, 1489 RuleMatcher &Rule) const override; 1490 }; 1491 1492 // Matcher for immAllOnesV/immAllZerosV 1493 class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher { 1494 public: 1495 enum SplatKind { AllZeros, AllOnes }; 1496 1497 private: 1498 SplatKind Kind; 1499 1500 public: 1501 VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K) 1502 : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {} 1503 1504 static bool classof(const PredicateMatcher *P) { 1505 return P->getKind() == IPM_VectorSplatImm; 1506 } 1507 1508 bool isIdentical(const PredicateMatcher &B) const override { 1509 return InstructionPredicateMatcher::isIdentical(B) && 1510 Kind == static_cast<const VectorSplatImmPredicateMatcher &>(B).Kind; 1511 } 1512 1513 void emitPredicateOpcodes(MatchTable &Table, 1514 RuleMatcher &Rule) const override; 1515 }; 1516 1517 /// Generates code to check an arbitrary C++ instruction predicate. 1518 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher { 1519 protected: 1520 std::string EnumVal; 1521 1522 public: 1523 GenericInstructionPredicateMatcher(unsigned InsnVarID, 1524 TreePredicateFn Predicate); 1525 1526 GenericInstructionPredicateMatcher(unsigned InsnVarID, 1527 const std::string &EnumVal) 1528 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID), 1529 EnumVal(EnumVal) {} 1530 1531 static bool classof(const InstructionPredicateMatcher *P) { 1532 return P->getKind() == IPM_GenericPredicate; 1533 } 1534 bool isIdentical(const PredicateMatcher &B) const override; 1535 void emitPredicateOpcodes(MatchTable &Table, 1536 RuleMatcher &Rule) const override; 1537 }; 1538 1539 /// Generates code to check for the absence of use of the result. 1540 // TODO? Generalize this to support checking for one use. 1541 class NoUsePredicateMatcher : public InstructionPredicateMatcher { 1542 public: 1543 NoUsePredicateMatcher(unsigned InsnVarID) 1544 : InstructionPredicateMatcher(IPM_NoUse, InsnVarID) {} 1545 1546 static bool classof(const PredicateMatcher *P) { 1547 return P->getKind() == IPM_NoUse; 1548 } 1549 1550 bool isIdentical(const PredicateMatcher &B) const override { 1551 return InstructionPredicateMatcher::isIdentical(B); 1552 } 1553 1554 void emitPredicateOpcodes(MatchTable &Table, 1555 RuleMatcher &Rule) const override { 1556 Table << MatchTable::Opcode("GIM_CheckHasNoUse") 1557 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) 1558 << MatchTable::LineBreak; 1559 } 1560 }; 1561 1562 /// Generates code to check that a set of predicates and operands match for a 1563 /// particular instruction. 1564 /// 1565 /// Typical predicates include: 1566 /// * Has a specific opcode. 1567 /// * Has an nsw/nuw flag or doesn't. 1568 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> { 1569 protected: 1570 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec; 1571 1572 RuleMatcher &Rule; 1573 1574 /// The operands to match. All rendered operands must be present even if the 1575 /// condition is always true. 1576 OperandVec Operands; 1577 bool NumOperandsCheck = true; 1578 1579 std::string SymbolicName; 1580 unsigned InsnVarID; 1581 1582 /// PhysRegInputs - List list has an entry for each explicitly specified 1583 /// physreg input to the pattern. The first elt is the Register node, the 1584 /// second is the recorded slot number the input pattern match saved it in. 1585 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs; 1586 1587 public: 1588 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName, 1589 bool NumOpsCheck = true) 1590 : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) { 1591 // We create a new instruction matcher. 1592 // Get a new ID for that instruction. 1593 InsnVarID = Rule.implicitlyDefineInsnVar(*this); 1594 } 1595 1596 /// Construct a new instruction predicate and add it to the matcher. 1597 template <class Kind, class... Args> 1598 std::optional<Kind *> addPredicate(Args &&...args) { 1599 Predicates.emplace_back( 1600 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...)); 1601 return static_cast<Kind *>(Predicates.back().get()); 1602 } 1603 1604 RuleMatcher &getRuleMatcher() const { return Rule; } 1605 1606 unsigned getInsnVarID() const { return InsnVarID; } 1607 1608 /// Add an operand to the matcher. 1609 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName, 1610 unsigned AllocatedTemporariesBaseID); 1611 OperandMatcher &getOperand(unsigned OpIdx); 1612 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx, 1613 unsigned TempOpIdx); 1614 1615 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const { 1616 return PhysRegInputs; 1617 } 1618 1619 StringRef getSymbolicName() const { return SymbolicName; } 1620 unsigned getNumOperands() const { return Operands.size(); } 1621 OperandVec::iterator operands_begin() { return Operands.begin(); } 1622 OperandVec::iterator operands_end() { return Operands.end(); } 1623 iterator_range<OperandVec::iterator> operands() { 1624 return make_range(operands_begin(), operands_end()); 1625 } 1626 OperandVec::const_iterator operands_begin() const { return Operands.begin(); } 1627 OperandVec::const_iterator operands_end() const { return Operands.end(); } 1628 iterator_range<OperandVec::const_iterator> operands() const { 1629 return make_range(operands_begin(), operands_end()); 1630 } 1631 bool operands_empty() const { return Operands.empty(); } 1632 1633 void pop_front() { Operands.erase(Operands.begin()); } 1634 1635 void optimize(); 1636 1637 /// Emit MatchTable opcodes that test whether the instruction named in 1638 /// InsnVarName matches all the predicates and all the operands. 1639 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule); 1640 1641 /// Compare the priority of this object and B. 1642 /// 1643 /// Returns true if this object is more important than B. 1644 bool isHigherPriorityThan(InstructionMatcher &B); 1645 1646 /// Report the maximum number of temporary operands needed by the instruction 1647 /// matcher. 1648 unsigned countRendererFns(); 1649 1650 InstructionOpcodeMatcher &getOpcodeMatcher() { 1651 for (auto &P : predicates()) 1652 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get())) 1653 return *OpMatcher; 1654 llvm_unreachable("Didn't find an opcode matcher"); 1655 } 1656 1657 bool isConstantInstruction() { 1658 return getOpcodeMatcher().isConstantInstruction(); 1659 } 1660 1661 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); } 1662 }; 1663 1664 /// Generates code to check that the operand is a register defined by an 1665 /// instruction that matches the given instruction matcher. 1666 /// 1667 /// For example, the pattern: 1668 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3)) 1669 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match 1670 /// the: 1671 /// (G_ADD $src1, $src2) 1672 /// subpattern. 1673 class InstructionOperandMatcher : public OperandPredicateMatcher { 1674 protected: 1675 std::unique_ptr<InstructionMatcher> InsnMatcher; 1676 1677 GISelFlags Flags; 1678 1679 public: 1680 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx, 1681 RuleMatcher &Rule, StringRef SymbolicName, 1682 bool NumOpsCheck = true) 1683 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx), 1684 InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)), 1685 Flags(Rule.getGISelFlags()) {} 1686 1687 static bool classof(const PredicateMatcher *P) { 1688 return P->getKind() == OPM_Instruction; 1689 } 1690 1691 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; } 1692 1693 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const; 1694 void emitPredicateOpcodes(MatchTable &Table, 1695 RuleMatcher &Rule) const override { 1696 emitCaptureOpcodes(Table, Rule); 1697 InsnMatcher->emitPredicateOpcodes(Table, Rule); 1698 } 1699 1700 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override; 1701 1702 /// Report the maximum number of temporary operands needed by the predicate 1703 /// matcher. 1704 unsigned countRendererFns() const override { 1705 return InsnMatcher->countRendererFns(); 1706 } 1707 }; 1708 1709 //===- Actions ------------------------------------------------------------===// 1710 class OperandRenderer { 1711 public: 1712 enum RendererKind { 1713 OR_Copy, 1714 OR_CopyOrAddZeroReg, 1715 OR_CopySubReg, 1716 OR_CopyPhysReg, 1717 OR_CopyConstantAsImm, 1718 OR_CopyFConstantAsFPImm, 1719 OR_Imm, 1720 OR_SubRegIndex, 1721 OR_Register, 1722 OR_TempRegister, 1723 OR_ComplexPattern, 1724 OR_Custom, 1725 OR_CustomOperand 1726 }; 1727 1728 protected: 1729 RendererKind Kind; 1730 1731 public: 1732 OperandRenderer(RendererKind Kind) : Kind(Kind) {} 1733 virtual ~OperandRenderer(); 1734 1735 RendererKind getKind() const { return Kind; } 1736 1737 virtual void emitRenderOpcodes(MatchTable &Table, 1738 RuleMatcher &Rule) const = 0; 1739 }; 1740 1741 /// A CopyRenderer emits code to copy a single operand from an existing 1742 /// instruction to the one being built. 1743 class CopyRenderer : public OperandRenderer { 1744 protected: 1745 unsigned NewInsnID; 1746 /// The name of the operand. 1747 const StringRef SymbolicName; 1748 1749 public: 1750 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName) 1751 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), 1752 SymbolicName(SymbolicName) { 1753 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); 1754 } 1755 1756 static bool classof(const OperandRenderer *R) { 1757 return R->getKind() == OR_Copy; 1758 } 1759 1760 StringRef getSymbolicName() const { return SymbolicName; } 1761 1762 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1763 }; 1764 1765 /// A CopyRenderer emits code to copy a virtual register to a specific physical 1766 /// register. 1767 class CopyPhysRegRenderer : public OperandRenderer { 1768 protected: 1769 unsigned NewInsnID; 1770 Record *PhysReg; 1771 1772 public: 1773 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg) 1774 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID), PhysReg(Reg) { 1775 assert(PhysReg); 1776 } 1777 1778 static bool classof(const OperandRenderer *R) { 1779 return R->getKind() == OR_CopyPhysReg; 1780 } 1781 1782 Record *getPhysReg() const { return PhysReg; } 1783 1784 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1785 }; 1786 1787 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an 1788 /// existing instruction to the one being built. If the operand turns out to be 1789 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register. 1790 class CopyOrAddZeroRegRenderer : public OperandRenderer { 1791 protected: 1792 unsigned NewInsnID; 1793 /// The name of the operand. 1794 const StringRef SymbolicName; 1795 const Record *ZeroRegisterDef; 1796 1797 public: 1798 CopyOrAddZeroRegRenderer(unsigned NewInsnID, StringRef SymbolicName, 1799 Record *ZeroRegisterDef) 1800 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID), 1801 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) { 1802 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); 1803 } 1804 1805 static bool classof(const OperandRenderer *R) { 1806 return R->getKind() == OR_CopyOrAddZeroReg; 1807 } 1808 1809 StringRef getSymbolicName() const { return SymbolicName; } 1810 1811 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1812 }; 1813 1814 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to 1815 /// an extended immediate operand. 1816 class CopyConstantAsImmRenderer : public OperandRenderer { 1817 protected: 1818 unsigned NewInsnID; 1819 /// The name of the operand. 1820 const std::string SymbolicName; 1821 bool Signed; 1822 1823 public: 1824 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName) 1825 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID), 1826 SymbolicName(SymbolicName), Signed(true) {} 1827 1828 static bool classof(const OperandRenderer *R) { 1829 return R->getKind() == OR_CopyConstantAsImm; 1830 } 1831 1832 StringRef getSymbolicName() const { return SymbolicName; } 1833 1834 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1835 }; 1836 1837 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT 1838 /// instruction to an extended immediate operand. 1839 class CopyFConstantAsFPImmRenderer : public OperandRenderer { 1840 protected: 1841 unsigned NewInsnID; 1842 /// The name of the operand. 1843 const std::string SymbolicName; 1844 1845 public: 1846 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName) 1847 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID), 1848 SymbolicName(SymbolicName) {} 1849 1850 static bool classof(const OperandRenderer *R) { 1851 return R->getKind() == OR_CopyFConstantAsFPImm; 1852 } 1853 1854 StringRef getSymbolicName() const { return SymbolicName; } 1855 1856 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1857 }; 1858 1859 /// A CopySubRegRenderer emits code to copy a single register operand from an 1860 /// existing instruction to the one being built and indicate that only a 1861 /// subregister should be copied. 1862 class CopySubRegRenderer : public OperandRenderer { 1863 protected: 1864 unsigned NewInsnID; 1865 /// The name of the operand. 1866 const StringRef SymbolicName; 1867 /// The subregister to extract. 1868 const CodeGenSubRegIndex *SubReg; 1869 1870 public: 1871 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName, 1872 const CodeGenSubRegIndex *SubReg) 1873 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), 1874 SymbolicName(SymbolicName), SubReg(SubReg) {} 1875 1876 static bool classof(const OperandRenderer *R) { 1877 return R->getKind() == OR_CopySubReg; 1878 } 1879 1880 StringRef getSymbolicName() const { return SymbolicName; } 1881 1882 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1883 }; 1884 1885 /// Adds a specific physical register to the instruction being built. 1886 /// This is typically useful for WZR/XZR on AArch64. 1887 class AddRegisterRenderer : public OperandRenderer { 1888 protected: 1889 unsigned InsnID; 1890 const Record *RegisterDef; 1891 bool IsDef; 1892 const CodeGenTarget &Target; 1893 1894 public: 1895 AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target, 1896 const Record *RegisterDef, bool IsDef = false) 1897 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef), 1898 IsDef(IsDef), Target(Target) {} 1899 1900 static bool classof(const OperandRenderer *R) { 1901 return R->getKind() == OR_Register; 1902 } 1903 1904 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1905 }; 1906 1907 /// Adds a specific temporary virtual register to the instruction being built. 1908 /// This is used to chain instructions together when emitting multiple 1909 /// instructions. 1910 class TempRegRenderer : public OperandRenderer { 1911 protected: 1912 unsigned InsnID; 1913 unsigned TempRegID; 1914 const CodeGenSubRegIndex *SubRegIdx; 1915 bool IsDef; 1916 bool IsDead; 1917 1918 public: 1919 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false, 1920 const CodeGenSubRegIndex *SubReg = nullptr, 1921 bool IsDead = false) 1922 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID), 1923 SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {} 1924 1925 static bool classof(const OperandRenderer *R) { 1926 return R->getKind() == OR_TempRegister; 1927 } 1928 1929 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1930 }; 1931 1932 /// Adds a specific immediate to the instruction being built. 1933 class ImmRenderer : public OperandRenderer { 1934 protected: 1935 unsigned InsnID; 1936 int64_t Imm; 1937 1938 public: 1939 ImmRenderer(unsigned InsnID, int64_t Imm) 1940 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {} 1941 1942 static bool classof(const OperandRenderer *R) { 1943 return R->getKind() == OR_Imm; 1944 } 1945 1946 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { 1947 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID") 1948 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm") 1949 << MatchTable::IntValue(Imm) << MatchTable::LineBreak; 1950 } 1951 }; 1952 1953 /// Adds an enum value for a subreg index to the instruction being built. 1954 class SubRegIndexRenderer : public OperandRenderer { 1955 protected: 1956 unsigned InsnID; 1957 const CodeGenSubRegIndex *SubRegIdx; 1958 1959 public: 1960 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI) 1961 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {} 1962 1963 static bool classof(const OperandRenderer *R) { 1964 return R->getKind() == OR_SubRegIndex; 1965 } 1966 1967 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 1968 }; 1969 1970 /// Adds operands by calling a renderer function supplied by the ComplexPattern 1971 /// matcher function. 1972 class RenderComplexPatternOperand : public OperandRenderer { 1973 private: 1974 unsigned InsnID; 1975 const Record &TheDef; 1976 /// The name of the operand. 1977 const StringRef SymbolicName; 1978 /// The renderer number. This must be unique within a rule since it's used to 1979 /// identify a temporary variable to hold the renderer function. 1980 unsigned RendererID; 1981 /// When provided, this is the suboperand of the ComplexPattern operand to 1982 /// render. Otherwise all the suboperands will be rendered. 1983 std::optional<unsigned> SubOperand; 1984 /// The subregister to extract. Render the whole register if not specified. 1985 const CodeGenSubRegIndex *SubReg; 1986 1987 unsigned getNumOperands() const { 1988 return TheDef.getValueAsDag("Operands")->getNumArgs(); 1989 } 1990 1991 public: 1992 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef, 1993 StringRef SymbolicName, unsigned RendererID, 1994 std::optional<unsigned> SubOperand = std::nullopt, 1995 const CodeGenSubRegIndex *SubReg = nullptr) 1996 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef), 1997 SymbolicName(SymbolicName), RendererID(RendererID), 1998 SubOperand(SubOperand), SubReg(SubReg) {} 1999 2000 static bool classof(const OperandRenderer *R) { 2001 return R->getKind() == OR_ComplexPattern; 2002 } 2003 2004 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2005 }; 2006 2007 class CustomRenderer : public OperandRenderer { 2008 protected: 2009 unsigned InsnID; 2010 const Record &Renderer; 2011 /// The name of the operand. 2012 const std::string SymbolicName; 2013 2014 public: 2015 CustomRenderer(unsigned InsnID, const Record &Renderer, 2016 StringRef SymbolicName) 2017 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer), 2018 SymbolicName(SymbolicName) {} 2019 2020 static bool classof(const OperandRenderer *R) { 2021 return R->getKind() == OR_Custom; 2022 } 2023 2024 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2025 }; 2026 2027 class CustomOperandRenderer : public OperandRenderer { 2028 protected: 2029 unsigned InsnID; 2030 const Record &Renderer; 2031 /// The name of the operand. 2032 const std::string SymbolicName; 2033 2034 public: 2035 CustomOperandRenderer(unsigned InsnID, const Record &Renderer, 2036 StringRef SymbolicName) 2037 : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer), 2038 SymbolicName(SymbolicName) {} 2039 2040 static bool classof(const OperandRenderer *R) { 2041 return R->getKind() == OR_CustomOperand; 2042 } 2043 2044 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2045 }; 2046 2047 /// An action taken when all Matcher predicates succeeded for a parent rule. 2048 /// 2049 /// Typical actions include: 2050 /// * Changing the opcode of an instruction. 2051 /// * Adding an operand to an instruction. 2052 class MatchAction { 2053 public: 2054 virtual ~MatchAction() {} 2055 2056 /// Emit the MatchTable opcodes to implement the action. 2057 virtual void emitActionOpcodes(MatchTable &Table, 2058 RuleMatcher &Rule) const = 0; 2059 }; 2060 2061 /// Generates a comment describing the matched rule being acted upon. 2062 class DebugCommentAction : public MatchAction { 2063 private: 2064 std::string S; 2065 2066 public: 2067 DebugCommentAction(StringRef S) : S(std::string(S)) {} 2068 2069 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { 2070 Table << MatchTable::Comment(S) << MatchTable::LineBreak; 2071 } 2072 }; 2073 2074 class CustomCXXAction : public MatchAction { 2075 std::string FnEnumName; 2076 2077 public: 2078 CustomCXXAction(StringRef FnEnumName) : FnEnumName(FnEnumName.str()) {} 2079 2080 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2081 }; 2082 2083 /// Generates code to build an instruction or mutate an existing instruction 2084 /// into the desired instruction when this is possible. 2085 class BuildMIAction : public MatchAction { 2086 private: 2087 unsigned InsnID; 2088 const CodeGenInstruction *I; 2089 InstructionMatcher *Matched; 2090 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers; 2091 2092 /// True if the instruction can be built solely by mutating the opcode. 2093 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const; 2094 2095 public: 2096 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I) 2097 : InsnID(InsnID), I(I), Matched(nullptr) {} 2098 2099 unsigned getInsnID() const { return InsnID; } 2100 const CodeGenInstruction *getCGI() const { return I; } 2101 2102 void chooseInsnToMutate(RuleMatcher &Rule); 2103 2104 template <class Kind, class... Args> Kind &addRenderer(Args &&...args) { 2105 OperandRenderers.emplace_back( 2106 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...)); 2107 return *static_cast<Kind *>(OperandRenderers.back().get()); 2108 } 2109 2110 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2111 }; 2112 2113 /// Generates code to constrain the operands of an output instruction to the 2114 /// register classes specified by the definition of that instruction. 2115 class ConstrainOperandsToDefinitionAction : public MatchAction { 2116 unsigned InsnID; 2117 2118 public: 2119 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {} 2120 2121 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { 2122 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands") 2123 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) 2124 << MatchTable::LineBreak; 2125 } 2126 }; 2127 2128 /// Generates code to constrain the specified operand of an output instruction 2129 /// to the specified register class. 2130 class ConstrainOperandToRegClassAction : public MatchAction { 2131 unsigned InsnID; 2132 unsigned OpIdx; 2133 const CodeGenRegisterClass &RC; 2134 2135 public: 2136 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx, 2137 const CodeGenRegisterClass &RC) 2138 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {} 2139 2140 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2141 }; 2142 2143 /// Generates code to create a temporary register which can be used to chain 2144 /// instructions together. 2145 class MakeTempRegisterAction : public MatchAction { 2146 private: 2147 LLTCodeGen Ty; 2148 unsigned TempRegID; 2149 2150 public: 2151 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID) 2152 : Ty(Ty), TempRegID(TempRegID) { 2153 KnownTypes.insert(Ty); 2154 } 2155 2156 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; 2157 }; 2158 2159 } // namespace gi 2160 } // namespace llvm 2161 2162 #endif 2163