llvm/utils/TableGen/GlobalISelMatchTable.h

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