brintos / llvm-project-archived public Read only

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