diff --git a/llvm/utils/TableGen/CMakeLists.txt b/llvm/utils/TableGen/CMakeLists.txt --- a/llvm/utils/TableGen/CMakeLists.txt +++ b/llvm/utils/TableGen/CMakeLists.txt @@ -61,6 +61,7 @@ FastISelEmitter.cpp GICombinerEmitter.cpp GlobalISelEmitter.cpp + GlobalISelMatchTable.cpp InfoByHwMode.cpp InstrInfoEmitter.cpp InstrDocsEmitter.cpp diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp --- a/llvm/utils/TableGen/GlobalISelEmitter.cpp +++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp @@ -34,6 +34,7 @@ #include "CodeGenIntrinsics.h" #include "CodeGenRegisters.h" #include "CodeGenTarget.h" +#include "GlobalISelMatchTable.h" #include "InfoByHwMode.h" #include "SubtargetFeatureInfo.h" #include "llvm/ADT/Statistic.h" @@ -49,15 +50,19 @@ #include "llvm/TableGen/TableGenBackend.h" #include #include + using namespace llvm; +using namespace llvm::gi; + +using action_iterator = RuleMatcher::action_iterator; #define DEBUG_TYPE "gisel-emitter" STATISTIC(NumPatternTotal, "Total number of patterns"); STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG"); STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped"); -STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information"); -STATISTIC(NumPatternEmitted, "Number of patterns emitted"); +STATISTIC(NumPatternsTested, + "Number of patterns executed according to coverage information"); cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel"); @@ -83,140 +88,6 @@ cl::init(true), cl::cat(GlobalISelEmitterCat)); namespace { -//===- Helper functions ---------------------------------------------------===// - -/// Get the name of the enum value used to number the predicate function. -std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) { - if (Predicate.hasGISelPredicateCode()) - return "GIPFP_MI_" + Predicate.getFnName(); - return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" + - Predicate.getFnName(); -} - -/// Get the opcode used to check this predicate. -std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) { - return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate"; -} - -/// This class stands in for LLT wherever we want to tablegen-erate an -/// equivalent at compiler run-time. -class LLTCodeGen { -private: - LLT Ty; - -public: - LLTCodeGen() = default; - LLTCodeGen(const LLT &Ty) : Ty(Ty) {} - - std::string getCxxEnumValue() const { - std::string Str; - raw_string_ostream OS(Str); - - emitCxxEnumValue(OS); - return Str; - } - - void emitCxxEnumValue(raw_ostream &OS) const { - if (Ty.isScalar()) { - OS << "GILLT_s" << Ty.getSizeInBits(); - return; - } - if (Ty.isVector()) { - OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v") - << Ty.getElementCount().getKnownMinValue() << "s" - << Ty.getScalarSizeInBits(); - return; - } - if (Ty.isPointer()) { - OS << "GILLT_p" << Ty.getAddressSpace(); - if (Ty.getSizeInBits() > 0) - OS << "s" << Ty.getSizeInBits(); - return; - } - llvm_unreachable("Unhandled LLT"); - } - - void emitCxxConstructorCall(raw_ostream &OS) const { - if (Ty.isScalar()) { - OS << "LLT::scalar(" << Ty.getSizeInBits() << ")"; - return; - } - if (Ty.isVector()) { - OS << "LLT::vector(" - << (Ty.isScalable() ? "ElementCount::getScalable(" - : "ElementCount::getFixed(") - << Ty.getElementCount().getKnownMinValue() << "), " - << Ty.getScalarSizeInBits() << ")"; - return; - } - if (Ty.isPointer() && Ty.getSizeInBits() > 0) { - OS << "LLT::pointer(" << Ty.getAddressSpace() << ", " - << Ty.getSizeInBits() << ")"; - return; - } - llvm_unreachable("Unhandled LLT"); - } - - const LLT &get() const { return Ty; } - - /// This ordering is used for std::unique() and llvm::sort(). There's no - /// particular logic behind the order but either A < B or B < A must be - /// true if A != B. - bool operator<(const LLTCodeGen &Other) const { - if (Ty.isValid() != Other.Ty.isValid()) - return Ty.isValid() < Other.Ty.isValid(); - if (!Ty.isValid()) - return false; - - if (Ty.isVector() != Other.Ty.isVector()) - return Ty.isVector() < Other.Ty.isVector(); - if (Ty.isScalar() != Other.Ty.isScalar()) - return Ty.isScalar() < Other.Ty.isScalar(); - if (Ty.isPointer() != Other.Ty.isPointer()) - return Ty.isPointer() < Other.Ty.isPointer(); - - if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace()) - return Ty.getAddressSpace() < Other.Ty.getAddressSpace(); - - if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount()) - return std::make_tuple(Ty.isScalable(), - Ty.getElementCount().getKnownMinValue()) < - std::make_tuple(Other.Ty.isScalable(), - Other.Ty.getElementCount().getKnownMinValue()); - - assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) && - "Unexpected mismatch of scalable property"); - return Ty.isVector() - ? std::make_tuple(Ty.isScalable(), - Ty.getSizeInBits().getKnownMinValue()) < - std::make_tuple( - Other.Ty.isScalable(), - Other.Ty.getSizeInBits().getKnownMinValue()) - : Ty.getSizeInBits().getFixedValue() < - Other.Ty.getSizeInBits().getFixedValue(); - } - - bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; } -}; - -// Track all types that are used so we can emit the corresponding enum. -std::set KnownTypes; - -class InstructionMatcher; -/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for -/// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...). -static std::optional MVTToLLT(MVT::SimpleValueType SVT) { - MVT VT(SVT); - - if (VT.isVector() && !VT.getVectorElementCount().isScalar()) - return LLTCodeGen( - LLT::vector(VT.getVectorElementCount(), VT.getScalarSizeInBits())); - - if (VT.isInteger() || VT.isFloatingPoint()) - return LLTCodeGen(LLT::scalar(VT.getSizeInBits())); - - return std::nullopt; -} static std::string explainPredicates(const TreePatternNode *N) { std::string Explanation; @@ -242,3368 +113,172 @@ if (P.isSignExtLoad()) Explanation += " sextload"; if (P.isZeroExtLoad()) - Explanation += " zextload"; - - if (P.isNonTruncStore()) - Explanation += " non-truncstore"; - if (P.isTruncStore()) - Explanation += " truncstore"; - - if (Record *VT = P.getMemoryVT()) - Explanation += (" MemVT=" + VT->getName()).str(); - if (Record *VT = P.getScalarMemoryVT()) - Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str(); - - if (ListInit *AddrSpaces = P.getAddressSpaces()) { - raw_string_ostream OS(Explanation); - OS << " AddressSpaces=["; - - StringRef AddrSpaceSeparator; - for (Init *Val : AddrSpaces->getValues()) { - IntInit *IntVal = dyn_cast(Val); - if (!IntVal) - continue; - - OS << AddrSpaceSeparator << IntVal->getValue(); - AddrSpaceSeparator = ", "; - } - - OS << ']'; - } - - int64_t MinAlign = P.getMinAlignment(); - if (MinAlign > 0) - Explanation += " MinAlign=" + utostr(MinAlign); - - if (P.isAtomicOrderingMonotonic()) - Explanation += " monotonic"; - if (P.isAtomicOrderingAcquire()) - Explanation += " acquire"; - if (P.isAtomicOrderingRelease()) - Explanation += " release"; - if (P.isAtomicOrderingAcquireRelease()) - Explanation += " acq_rel"; - if (P.isAtomicOrderingSequentiallyConsistent()) - Explanation += " seq_cst"; - if (P.isAtomicOrderingAcquireOrStronger()) - Explanation += " >=acquire"; - if (P.isAtomicOrderingWeakerThanAcquire()) - Explanation += " isSubClassOf("SDNode")) - return (" (" + Operator->getValueAsString("Opcode") + ")").str(); - - if (Operator->isSubClassOf("Intrinsic")) - return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str(); - - if (Operator->isSubClassOf("ComplexPattern")) - return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() + - ")") - .str(); - - if (Operator->isSubClassOf("SDNodeXForm")) - return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() + - ")") - .str(); - - return (" (Operator " + Operator->getName() + " not understood)").str(); -} - -/// Helper function to let the emitter report skip reason error messages. -static Error failedImport(const Twine &Reason) { - return make_error(Reason, inconvertibleErrorCode()); -} - -static Error isTrivialOperatorNode(const TreePatternNode *N) { - std::string Explanation; - std::string Separator; - - bool HasUnsupportedPredicate = false; - for (const TreePredicateCall &Call : N->getPredicateCalls()) { - const TreePredicateFn &Predicate = Call.Fn; - - if (Predicate.isAlwaysTrue()) - continue; - - if (Predicate.isImmediatePattern()) - continue; - - if (Predicate.hasNoUse()) - continue; - - if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() || - Predicate.isSignExtLoad() || Predicate.isZeroExtLoad()) - continue; - - if (Predicate.isNonTruncStore() || Predicate.isTruncStore()) - continue; - - if (Predicate.isLoad() && Predicate.getMemoryVT()) - continue; - - if (Predicate.isLoad() || Predicate.isStore()) { - if (Predicate.isUnindexed()) - continue; - } - - if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) { - const ListInit *AddrSpaces = Predicate.getAddressSpaces(); - if (AddrSpaces && !AddrSpaces->empty()) - continue; - - if (Predicate.getMinAlignment() > 0) - continue; - } - - if (Predicate.isAtomic() && Predicate.getMemoryVT()) - continue; - - if (Predicate.isAtomic() && - (Predicate.isAtomicOrderingMonotonic() || - Predicate.isAtomicOrderingAcquire() || - Predicate.isAtomicOrderingRelease() || - Predicate.isAtomicOrderingAcquireRelease() || - Predicate.isAtomicOrderingSequentiallyConsistent() || - Predicate.isAtomicOrderingAcquireOrStronger() || - Predicate.isAtomicOrderingWeakerThanAcquire() || - Predicate.isAtomicOrderingReleaseOrStronger() || - Predicate.isAtomicOrderingWeakerThanRelease())) - continue; - - if (Predicate.hasGISelPredicateCode()) - continue; - - HasUnsupportedPredicate = true; - Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")"; - Separator = ", "; - Explanation += (Separator + "first-failing:" + - Predicate.getOrigPatFragRecord()->getRecord()->getName()) - .str(); - break; - } - - if (!HasUnsupportedPredicate) - return Error::success(); - - return failedImport(Explanation); -} - -static Record *getInitValueAsRegClass(Init *V) { - if (DefInit *VDefInit = dyn_cast(V)) { - if (VDefInit->getDef()->isSubClassOf("RegisterOperand")) - return VDefInit->getDef()->getValueAsDef("RegClass"); - if (VDefInit->getDef()->isSubClassOf("RegisterClass")) - return VDefInit->getDef(); - } - return nullptr; -} - -std::string -getNameForFeatureBitset(const std::vector &FeatureBitset) { - std::string Name = "GIFBS"; - for (const auto &Feature : FeatureBitset) - Name += ("_" + Feature->getName()).str(); - return Name; -} - -static std::string getScopedName(unsigned Scope, const std::string &Name) { - return ("pred:" + Twine(Scope) + ":" + Name).str(); -} - -//===- MatchTable Helpers -------------------------------------------------===// - -class MatchTable; - -/// A record to be stored in a MatchTable. -/// -/// This class represents any and all output that may be required to emit the -/// MatchTable. Instances are most often configured to represent an opcode or -/// value that will be emitted to the table with some formatting but it can also -/// represent commas, comments, and other formatting instructions. -struct MatchTableRecord { - enum RecordFlagsBits { - MTRF_None = 0x0, - /// Causes EmitStr to be formatted as comment when emitted. - MTRF_Comment = 0x1, - /// Causes the record value to be followed by a comma when emitted. - MTRF_CommaFollows = 0x2, - /// Causes the record value to be followed by a line break when emitted. - MTRF_LineBreakFollows = 0x4, - /// Indicates that the record defines a label and causes an additional - /// comment to be emitted containing the index of the label. - MTRF_Label = 0x8, - /// Causes the record to be emitted as the index of the label specified by - /// LabelID along with a comment indicating where that label is. - MTRF_JumpTarget = 0x10, - /// Causes the formatter to add a level of indentation before emitting the - /// record. - MTRF_Indent = 0x20, - /// Causes the formatter to remove a level of indentation after emitting the - /// record. - MTRF_Outdent = 0x40, - }; - - /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to - /// reference or define. - unsigned LabelID; - /// The string to emit. Depending on the MTRF_* flags it may be a comment, a - /// value, a label name. - std::string EmitStr; - -private: - /// The number of MatchTable elements described by this record. Comments are 0 - /// while values are typically 1. Values >1 may occur when we need to emit - /// values that exceed the size of a MatchTable element. - unsigned NumElements; - -public: - /// A bitfield of RecordFlagsBits flags. - unsigned Flags; - - /// The actual run-time value, if known - int64_t RawValue; - - MatchTableRecord(std::optional LabelID_, StringRef EmitStr, - unsigned NumElements, unsigned Flags, - int64_t RawValue = std::numeric_limits::min()) - : LabelID(LabelID_.value_or(~0u)), EmitStr(EmitStr), - NumElements(NumElements), Flags(Flags), RawValue(RawValue) { - assert((!LabelID_ || LabelID != ~0u) && - "This value is reserved for non-labels"); - } - MatchTableRecord(const MatchTableRecord &Other) = default; - MatchTableRecord(MatchTableRecord &&Other) = default; - - /// Useful if a Match Table Record gets optimized out - void turnIntoComment() { - Flags |= MTRF_Comment; - Flags &= ~MTRF_CommaFollows; - NumElements = 0; - } - - /// For Jump Table generation purposes - bool operator<(const MatchTableRecord &Other) const { - return RawValue < Other.RawValue; - } - int64_t getRawValue() const { return RawValue; } - - void emit(raw_ostream &OS, bool LineBreakNextAfterThis, - const MatchTable &Table) const; - unsigned size() const { return NumElements; } -}; - -class Matcher; - -/// Holds the contents of a generated MatchTable to enable formatting and the -/// necessary index tracking needed to support GIM_Try. -class MatchTable { - /// An unique identifier for the table. The generated table will be named - /// MatchTable${ID}. - unsigned ID; - /// The records that make up the table. Also includes comments describing the - /// values being emitted and line breaks to format it. - std::vector Contents; - /// The currently defined labels. - DenseMap LabelMap; - /// Tracks the sum of MatchTableRecord::NumElements as the table is built. - unsigned CurrentSize = 0; - /// A unique identifier for a MatchTable label. - unsigned CurrentLabelID = 0; - /// Determines if the table should be instrumented for rule coverage tracking. - bool IsWithCoverage; - -public: - static MatchTableRecord LineBreak; - static MatchTableRecord Comment(StringRef Comment) { - return MatchTableRecord(std::nullopt, Comment, 0, - MatchTableRecord::MTRF_Comment); - } - static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) { - unsigned ExtraFlags = 0; - if (IndentAdjust > 0) - ExtraFlags |= MatchTableRecord::MTRF_Indent; - if (IndentAdjust < 0) - ExtraFlags |= MatchTableRecord::MTRF_Outdent; - - return MatchTableRecord(std::nullopt, Opcode, 1, - MatchTableRecord::MTRF_CommaFollows | ExtraFlags); - } - static MatchTableRecord NamedValue(StringRef NamedValue) { - return MatchTableRecord(std::nullopt, NamedValue, 1, - MatchTableRecord::MTRF_CommaFollows); - } - static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) { - return MatchTableRecord(std::nullopt, NamedValue, 1, - MatchTableRecord::MTRF_CommaFollows, RawValue); - } - static MatchTableRecord NamedValue(StringRef Namespace, - StringRef NamedValue) { - return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(), - 1, MatchTableRecord::MTRF_CommaFollows); - } - static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue, - int64_t RawValue) { - return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(), - 1, MatchTableRecord::MTRF_CommaFollows, RawValue); - } - static MatchTableRecord IntValue(int64_t IntValue) { - return MatchTableRecord(std::nullopt, llvm::to_string(IntValue), 1, - MatchTableRecord::MTRF_CommaFollows); - } - static MatchTableRecord Label(unsigned LabelID) { - return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0, - MatchTableRecord::MTRF_Label | - MatchTableRecord::MTRF_Comment | - MatchTableRecord::MTRF_LineBreakFollows); - } - static MatchTableRecord JumpTarget(unsigned LabelID) { - return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1, - MatchTableRecord::MTRF_JumpTarget | - MatchTableRecord::MTRF_Comment | - MatchTableRecord::MTRF_CommaFollows); - } - - static MatchTable buildTable(ArrayRef Rules, bool WithCoverage); - - MatchTable(bool WithCoverage, unsigned ID = 0) - : ID(ID), IsWithCoverage(WithCoverage) {} - - bool isWithCoverage() const { return IsWithCoverage; } - - void push_back(const MatchTableRecord &Value) { - if (Value.Flags & MatchTableRecord::MTRF_Label) - defineLabel(Value.LabelID); - Contents.push_back(Value); - CurrentSize += Value.size(); - } - - unsigned allocateLabelID() { return CurrentLabelID++; } - - void defineLabel(unsigned LabelID) { - LabelMap.insert(std::make_pair(LabelID, CurrentSize)); - } - - unsigned getLabelIndex(unsigned LabelID) const { - const auto I = LabelMap.find(LabelID); - assert(I != LabelMap.end() && "Use of undeclared label"); - return I->second; - } - - void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; } - - void emitDeclaration(raw_ostream &OS) const { - unsigned Indentation = 4; - OS << " constexpr static int64_t MatchTable" << ID << "[] = {"; - LineBreak.emit(OS, true, *this); - OS << std::string(Indentation, ' '); - - for (auto I = Contents.begin(), E = Contents.end(); I != E; - ++I) { - bool LineBreakIsNext = false; - const auto &NextI = std::next(I); - - if (NextI != E) { - if (NextI->EmitStr == "" && - NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows) - LineBreakIsNext = true; - } - - if (I->Flags & MatchTableRecord::MTRF_Indent) - Indentation += 2; - - I->emit(OS, LineBreakIsNext, *this); - if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows) - OS << std::string(Indentation, ' '); - - if (I->Flags & MatchTableRecord::MTRF_Outdent) - Indentation -= 2; - } - OS << "};\n"; - } -}; - -MatchTableRecord MatchTable::LineBreak = { - std::nullopt, "" /* Emit String */, 0 /* Elements */, - MatchTableRecord::MTRF_LineBreakFollows}; - -void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis, - const MatchTable &Table) const { - bool UseLineComment = - LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows); - if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows)) - UseLineComment = false; - - if (Flags & MTRF_Comment) - OS << (UseLineComment ? "// " : "/*"); - - OS << EmitStr; - if (Flags & MTRF_Label) - OS << ": @" << Table.getLabelIndex(LabelID); - - if ((Flags & MTRF_Comment) && !UseLineComment) - OS << "*/"; - - if (Flags & MTRF_JumpTarget) { - if (Flags & MTRF_Comment) - OS << " "; - OS << Table.getLabelIndex(LabelID); - } - - if (Flags & MTRF_CommaFollows) { - OS << ","; - if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows)) - OS << " "; - } - - if (Flags & MTRF_LineBreakFollows) - OS << "\n"; -} - -MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) { - Table.push_back(Value); - return Table; -} - -//===- Matchers -----------------------------------------------------------===// - -class OperandMatcher; -class MatchAction; -class PredicateMatcher; - -enum { - GISF_IgnoreCopies = 0x1, -}; - -using GISelFlags = std::uint16_t; - -class Matcher { -public: - virtual ~Matcher() = default; - virtual void optimize() {} - virtual void emit(MatchTable &Table) = 0; - - virtual bool hasFirstCondition() const = 0; - virtual const PredicateMatcher &getFirstCondition() const = 0; - virtual std::unique_ptr popFirstCondition() = 0; -}; - -MatchTable MatchTable::buildTable(ArrayRef Rules, - bool WithCoverage) { - MatchTable Table(WithCoverage); - for (Matcher *Rule : Rules) - Rule->emit(Table); - - return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; -} - -class GroupMatcher final : public Matcher { - /// Conditions that form a common prefix of all the matchers contained. - SmallVector, 1> Conditions; - - /// All the nested matchers, sharing a common prefix. - std::vector Matchers; - - /// An owning collection for any auxiliary matchers created while optimizing - /// nested matchers contained. - std::vector> MatcherStorage; - -public: - /// Add a matcher to the collection of nested matchers if it meets the - /// requirements, and return true. If it doesn't, do nothing and return false. - /// - /// Expected to preserve its argument, so it could be moved out later on. - bool addMatcher(Matcher &Candidate); - - /// Mark the matcher as fully-built and ensure any invariants expected by both - /// optimize() and emit(...) methods. Generally, both sequences of calls - /// are expected to lead to a sensible result: - /// - /// addMatcher(...)*; finalize(); optimize(); emit(...); and - /// addMatcher(...)*; finalize(); emit(...); - /// - /// or generally - /// - /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }* - /// - /// Multiple calls to optimize() are expected to be handled gracefully, though - /// optimize() is not expected to be idempotent. Multiple calls to finalize() - /// aren't generally supported. emit(...) is expected to be non-mutating and - /// producing the exact same results upon repeated calls. - /// - /// addMatcher() calls after the finalize() call are not supported. - /// - /// finalize() and optimize() are both allowed to mutate the contained - /// matchers, so moving them out after finalize() is not supported. - void finalize(); - void optimize() override; - void emit(MatchTable &Table) override; - - /// Could be used to move out the matchers added previously, unless finalize() - /// has been already called. If any of the matchers are moved out, the group - /// becomes safe to destroy, but not safe to re-use for anything else. - iterator_range::iterator> matchers() { - return make_range(Matchers.begin(), Matchers.end()); - } - size_t size() const { return Matchers.size(); } - bool empty() const { return Matchers.empty(); } - - std::unique_ptr popFirstCondition() override { - assert(!Conditions.empty() && - "Trying to pop a condition from a condition-less group"); - std::unique_ptr P = std::move(Conditions.front()); - Conditions.erase(Conditions.begin()); - return P; - } - const PredicateMatcher &getFirstCondition() const override { - assert(!Conditions.empty() && - "Trying to get a condition from a condition-less group"); - return *Conditions.front(); - } - bool hasFirstCondition() const override { return !Conditions.empty(); } - -private: - /// See if a candidate matcher could be added to this group solely by - /// analyzing its first condition. - bool candidateConditionMatches(const PredicateMatcher &Predicate) const; -}; - -class SwitchMatcher : public Matcher { - /// All the nested matchers, representing distinct switch-cases. The first - /// conditions (as Matcher::getFirstCondition() reports) of all the nested - /// matchers must share the same type and path to a value they check, in other - /// words, be isIdenticalDownToValue, but have different values they check - /// against. - std::vector Matchers; - - /// The representative condition, with a type and a path (InsnVarID and OpIdx - /// in most cases) shared by all the matchers contained. - std::unique_ptr Condition = nullptr; - - /// Temporary set used to check that the case values don't repeat within the - /// same switch. - std::set Values; - - /// An owning collection for any auxiliary matchers created while optimizing - /// nested matchers contained. - std::vector> MatcherStorage; - -public: - bool addMatcher(Matcher &Candidate); - - void finalize(); - void emit(MatchTable &Table) override; - - iterator_range::iterator> matchers() { - return make_range(Matchers.begin(), Matchers.end()); - } - size_t size() const { return Matchers.size(); } - bool empty() const { return Matchers.empty(); } - - std::unique_ptr popFirstCondition() override { - // SwitchMatcher doesn't have a common first condition for its cases, as all - // the cases only share a kind of a value (a type and a path to it) they - // match, but deliberately differ in the actual value they match. - llvm_unreachable("Trying to pop a condition from a condition-less group"); - } - const PredicateMatcher &getFirstCondition() const override { - llvm_unreachable("Trying to pop a condition from a condition-less group"); - } - bool hasFirstCondition() const override { return false; } - -private: - /// See if the predicate type has a Switch-implementation for it. - static bool isSupportedPredicateType(const PredicateMatcher &Predicate); - - bool candidateConditionMatches(const PredicateMatcher &Predicate) const; - - /// emit()-helper - static void emitPredicateSpecificOpcodes(const PredicateMatcher &P, - MatchTable &Table); -}; - -/// Generates code to check that a match rule matches. -class RuleMatcher : public Matcher { -public: - using ActionList = std::list>; - using action_iterator = ActionList::iterator; - -protected: - /// A list of matchers that all need to succeed for the current rule to match. - /// FIXME: This currently supports a single match position but could be - /// extended to support multiple positions to support div/rem fusion or - /// load-multiple instructions. - using MatchersTy = std::vector> ; - MatchersTy Matchers; - - /// A list of actions that need to be taken when all predicates in this rule - /// have succeeded. - ActionList Actions; - - using DefinedInsnVariablesMap = std::map; - - /// A map of instruction matchers to the local variables - DefinedInsnVariablesMap InsnVariableIDs; - - using MutatableInsnSet = SmallPtrSet; - - // The set of instruction matchers that have not yet been claimed for mutation - // by a BuildMI. - MutatableInsnSet MutatableInsns; - - /// A map of named operands defined by the matchers that may be referenced by - /// the renderers. - StringMap DefinedOperands; - - /// A map of anonymous physical register operands defined by the matchers that - /// may be referenced by the renderers. - DenseMap PhysRegOperands; - - /// ID for the next instruction variable defined with implicitlyDefineInsnVar() - unsigned NextInsnVarID; - - /// ID for the next output instruction allocated with allocateOutputInsnID() - unsigned NextOutputInsnID; - - /// ID for the next temporary register ID allocated with allocateTempRegID() - unsigned NextTempRegID; - - /// Current GISelFlags - GISelFlags Flags = 0; - - std::vector RequiredFeatures; - std::vector> EpilogueMatchers; - - ArrayRef SrcLoc; - - typedef std::tuple - DefinedComplexPatternSubOperand; - typedef StringMap - DefinedComplexPatternSubOperandMap; - /// A map of Symbolic Names to ComplexPattern sub-operands. - DefinedComplexPatternSubOperandMap ComplexSubOperands; - /// A map used to for multiple referenced error check of ComplexSubOperand. - /// ComplexSubOperand can't be referenced multiple from different operands, - /// however multiple references from same operand are allowed since that is - /// how 'same operand checks' are generated. - StringMap ComplexSubOperandsParentName; - - uint64_t RuleID; - static uint64_t NextRuleID; - - GISelFlags updateGISelFlag(GISelFlags CurFlags, const Record *R, - StringRef FlagName, GISelFlags FlagBit) { - // If the value of a flag is unset, ignore it. - // If it's set, it always takes precedence over the existing value so - // clear/set the corresponding bit. - bool Unset = false; - bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset); - if (!Unset) - return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit); - return CurFlags; - } - -public: - RuleMatcher(ArrayRef SrcLoc) - : NextInsnVarID(0), NextOutputInsnID(0), NextTempRegID(0), SrcLoc(SrcLoc), - RuleID(NextRuleID++) {} - RuleMatcher(RuleMatcher &&Other) = default; - RuleMatcher &operator=(RuleMatcher &&Other) = default; - - uint64_t getRuleID() const { return RuleID; } - - InstructionMatcher &addInstructionMatcher(StringRef SymbolicName); - void addRequiredFeature(Record *Feature); - const std::vector &getRequiredFeatures() const; - - template Kind &addAction(Args &&... args); - template - action_iterator insertAction(action_iterator InsertPt, Args &&... args); - - // Update the active GISelFlags based on the GISelFlags Record R. - // A SaveAndRestore object is returned so the old GISelFlags are restored - // at the end of the scope. - SaveAndRestore setGISelFlags(const Record *R) { - if (!R || !R->isSubClassOf("GISelFlags")) - return {Flags, Flags}; - - assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) && - "GISelFlags is only expected on Pattern/PatFrags!"); - - GISelFlags NewFlags = - updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies); - return {Flags, NewFlags}; - } - - GISelFlags getGISelFlags() const { return Flags; } - - /// Define an instruction without emitting any code to do so. - unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher); - - unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const; - DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const { - return InsnVariableIDs.begin(); - } - DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const { - return InsnVariableIDs.end(); - } - iterator_range - defined_insn_vars() const { - return make_range(defined_insn_vars_begin(), defined_insn_vars_end()); - } - - MutatableInsnSet::const_iterator mutatable_insns_begin() const { - return MutatableInsns.begin(); - } - MutatableInsnSet::const_iterator mutatable_insns_end() const { - return MutatableInsns.end(); - } - iterator_range - mutatable_insns() const { - return make_range(mutatable_insns_begin(), mutatable_insns_end()); - } - void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) { - bool R = MutatableInsns.erase(InsnMatcher); - assert(R && "Reserving a mutatable insn that isn't available"); - (void)R; - } - - action_iterator actions_begin() { return Actions.begin(); } - action_iterator actions_end() { return Actions.end(); } - iterator_range actions() { - return make_range(actions_begin(), actions_end()); - } - - void defineOperand(StringRef SymbolicName, OperandMatcher &OM); - - void definePhysRegOperand(Record *Reg, OperandMatcher &OM); - - Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern, - unsigned RendererID, unsigned SubOperandID, - StringRef ParentSymbolicName) { - std::string ParentName(ParentSymbolicName); - if (ComplexSubOperands.count(SymbolicName)) { - const std::string &RecordedParentName = - ComplexSubOperandsParentName[SymbolicName]; - if (RecordedParentName != ParentName) - return failedImport("Error: Complex suboperand " + SymbolicName + - " referenced by different operands: " + - RecordedParentName + " and " + ParentName + "."); - // Complex suboperand referenced more than once from same the operand is - // used to generate 'same operand check'. Emitting of - // GIR_ComplexSubOperandRenderer for them is already handled. - return Error::success(); - } - - ComplexSubOperands[SymbolicName] = - std::make_tuple(ComplexPattern, RendererID, SubOperandID); - ComplexSubOperandsParentName[SymbolicName] = ParentName; - - return Error::success(); - } - - std::optional - getComplexSubOperand(StringRef SymbolicName) const { - const auto &I = ComplexSubOperands.find(SymbolicName); - if (I == ComplexSubOperands.end()) - return std::nullopt; - return I->second; - } - - InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const; - const OperandMatcher &getOperandMatcher(StringRef Name) const; - const OperandMatcher &getPhysRegOperandMatcher(Record *) const; - - void optimize() override; - void emit(MatchTable &Table) override; - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - bool isHigherPriorityThan(const RuleMatcher &B) const; - - /// Report the maximum number of temporary operands needed by the rule - /// matcher. - unsigned countRendererFns() const; - - std::unique_ptr popFirstCondition() override; - const PredicateMatcher &getFirstCondition() const override; - LLTCodeGen getFirstConditionAsRootType(); - bool hasFirstCondition() const override; - unsigned getNumOperands() const; - StringRef getOpcode() const; - - // FIXME: Remove this as soon as possible - InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); } - - unsigned allocateOutputInsnID() { return NextOutputInsnID++; } - unsigned allocateTempRegID() { return NextTempRegID++; } - - iterator_range insnmatchers() { - return make_range(Matchers.begin(), Matchers.end()); - } - bool insnmatchers_empty() const { return Matchers.empty(); } - void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); } -}; - -uint64_t RuleMatcher::NextRuleID = 0; - -using action_iterator = RuleMatcher::action_iterator; - -template class PredicateListMatcher { -private: - /// Template instantiations should specialize this to return a string to use - /// for the comment emitted when there are no predicates. - std::string getNoPredicateComment() const; - -protected: - using PredicatesTy = std::deque>; - PredicatesTy Predicates; - - /// Track if the list of predicates was manipulated by one of the optimization - /// methods. - bool Optimized = false; - -public: - typename PredicatesTy::iterator predicates_begin() { - return Predicates.begin(); - } - typename PredicatesTy::iterator predicates_end() { - return Predicates.end(); - } - iterator_range predicates() { - return make_range(predicates_begin(), predicates_end()); - } - typename PredicatesTy::size_type predicates_size() const { - return Predicates.size(); - } - bool predicates_empty() const { return Predicates.empty(); } - - std::unique_ptr predicates_pop_front() { - std::unique_ptr Front = std::move(Predicates.front()); - Predicates.pop_front(); - Optimized = true; - return Front; - } - - void prependPredicate(std::unique_ptr &&Predicate) { - Predicates.push_front(std::move(Predicate)); - } - - void eraseNullPredicates() { - const auto NewEnd = - std::stable_partition(Predicates.begin(), Predicates.end(), - std::logical_not>()); - if (NewEnd != Predicates.begin()) { - Predicates.erase(Predicates.begin(), NewEnd); - Optimized = true; - } - } - - /// Emit MatchTable opcodes that tests whether all the predicates are met. - template - void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) { - if (Predicates.empty() && !Optimized) { - Table << MatchTable::Comment(getNoPredicateComment()) - << MatchTable::LineBreak; - return; - } - - for (const auto &Predicate : predicates()) - Predicate->emitPredicateOpcodes(Table, std::forward(args)...); - } - - /// Provide a function to avoid emitting certain predicates. This is used to - /// defer some predicate checks until after others - using PredicateFilterFunc = std::function; - - /// Emit MatchTable opcodes for predicates which satisfy \p - /// ShouldEmitPredicate. This should be called multiple times to ensure all - /// predicates are eventually added to the match table. - template - void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate, - MatchTable &Table, Args &&... args) { - if (Predicates.empty() && !Optimized) { - Table << MatchTable::Comment(getNoPredicateComment()) - << MatchTable::LineBreak; - return; - } - - for (const auto &Predicate : predicates()) { - if (ShouldEmitPredicate(*Predicate)) - Predicate->emitPredicateOpcodes(Table, std::forward(args)...); - } - } -}; - -class PredicateMatcher { -public: - /// This enum is used for RTTI and also defines the priority that is given to - /// the predicate when generating the matcher code. Kinds with higher priority - /// must be tested first. - /// - /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter - /// but OPM_Int must have priority over OPM_RegBank since constant integers - /// are represented by a virtual register defined by a G_CONSTANT instruction. - /// - /// Note: The relative priority between IPM_ and OPM_ does not matter, they - /// are currently not compared between each other. - enum PredicateKind { - IPM_Opcode, - IPM_NumOperands, - IPM_ImmPredicate, - IPM_Imm, - IPM_AtomicOrderingMMO, - IPM_MemoryLLTSize, - IPM_MemoryVsLLTSize, - IPM_MemoryAddressSpace, - IPM_MemoryAlignment, - IPM_VectorSplatImm, - IPM_NoUse, - IPM_GenericPredicate, - OPM_SameOperand, - OPM_ComplexPattern, - OPM_IntrinsicID, - OPM_CmpPredicate, - OPM_Instruction, - OPM_Int, - OPM_LiteralInt, - OPM_LLT, - OPM_PointerToAny, - OPM_RegBank, - OPM_MBB, - OPM_RecordNamedOperand, - }; - -protected: - PredicateKind Kind; - unsigned InsnVarID; - unsigned OpIdx; - -public: - PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0) - : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {} - - unsigned getInsnVarID() const { return InsnVarID; } - unsigned getOpIdx() const { return OpIdx; } - - virtual ~PredicateMatcher() = default; - /// Emit MatchTable opcodes that check the predicate for the given operand. - virtual void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const = 0; - - PredicateKind getKind() const { return Kind; } - - bool dependsOnOperands() const { - // Custom predicates really depend on the context pattern of the - // instruction, not just the individual instruction. This therefore - // implicitly depends on all other pattern constraints. - return Kind == IPM_GenericPredicate; - } - - virtual bool isIdentical(const PredicateMatcher &B) const { - return B.getKind() == getKind() && InsnVarID == B.InsnVarID && - OpIdx == B.OpIdx; - } - - virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const { - return hasValue() && PredicateMatcher::isIdentical(B); - } - - virtual MatchTableRecord getValue() const { - assert(hasValue() && "Can not get a value of a value-less predicate!"); - llvm_unreachable("Not implemented yet"); - } - virtual bool hasValue() const { return false; } - - /// Report the maximum number of temporary operands needed by the predicate - /// matcher. - virtual unsigned countRendererFns() const { return 0; } -}; - -/// Generates code to check a predicate of an operand. -/// -/// Typical predicates include: -/// * Operand is a particular register. -/// * Operand is assigned a particular register bank. -/// * Operand is an MBB. -class OperandPredicateMatcher : public PredicateMatcher { -public: - OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID, - unsigned OpIdx) - : PredicateMatcher(Kind, InsnVarID, OpIdx) {} - virtual ~OperandPredicateMatcher() {} - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const; -}; - -template <> -std::string -PredicateListMatcher::getNoPredicateComment() const { - return "No operand predicates"; -} - -/// Generates code to check that a register operand is defined by the same exact -/// one as another. -class SameOperandMatcher : public OperandPredicateMatcher { - std::string MatchingName; - unsigned OrigOpIdx; - - GISelFlags Flags; - -public: - SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName, - unsigned OrigOpIdx, GISelFlags Flags) - : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx), - MatchingName(MatchingName), OrigOpIdx(OrigOpIdx), Flags(Flags) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_SameOperand; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override; - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - OrigOpIdx == cast(&B)->OrigOpIdx && - MatchingName == cast(&B)->MatchingName; - } -}; - -/// Generates code to check that an operand is a particular LLT. -class LLTOperandMatcher : public OperandPredicateMatcher { -protected: - LLTCodeGen Ty; - -public: - static std::map TypeIDValues; - - static void initTypeIDValuesMap() { - TypeIDValues.clear(); - - unsigned ID = 0; - for (const LLTCodeGen &LLTy : KnownTypes) - TypeIDValues[LLTy] = ID++; - } - - LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty) - : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) { - KnownTypes.insert(Ty); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_LLT; - } - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - Ty == cast(&B)->Ty; - } - MatchTableRecord getValue() const override { - const auto VI = TypeIDValues.find(Ty); - if (VI == TypeIDValues.end()) - return MatchTable::NamedValue(getTy().getCxxEnumValue()); - return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second); - } - bool hasValue() const override { - if (TypeIDValues.size() != KnownTypes.size()) - initTypeIDValuesMap(); - return TypeIDValues.count(Ty); - } - - LLTCodeGen getTy() const { return Ty; } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") - << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type") - << getValue() << MatchTable::LineBreak; - } -}; - -std::map LLTOperandMatcher::TypeIDValues; - -/// Generates code to check that an operand is a pointer to any address space. -/// -/// In SelectionDAG, the types did not describe pointers or address spaces. As a -/// result, iN is used to describe a pointer of N bits to any address space and -/// PatFrag predicates are typically used to constrain the address space. There's -/// no reliable means to derive the missing type information from the pattern so -/// imported rules must test the components of a pointer separately. -/// -/// If SizeInBits is zero, then the pointer size will be obtained from the -/// subtarget. -class PointerToAnyOperandMatcher : public OperandPredicateMatcher { -protected: - unsigned SizeInBits; - -public: - PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - unsigned SizeInBits) - : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx), - SizeInBits(SizeInBits) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_PointerToAny; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - SizeInBits == cast(&B)->SizeInBits; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckPointerToAny") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("SizeInBits") - << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak; - } -}; - -/// Generates code to record named operand in RecordedOperands list at StoreIdx. -/// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as -/// an argument to predicate's c++ code once all operands have been matched. -class RecordNamedOperandMatcher : public OperandPredicateMatcher { -protected: - unsigned StoreIdx; - std::string Name; - -public: - RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - unsigned StoreIdx, StringRef Name) - : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx), - StoreIdx(StoreIdx), Name(Name) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_RecordNamedOperand; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - StoreIdx == cast(&B)->StoreIdx && - Name == cast(&B)->Name; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_RecordNamedOperand") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("StoreIdx") << MatchTable::IntValue(StoreIdx) - << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is a particular target constant. -class ComplexPatternOperandMatcher : public OperandPredicateMatcher { -protected: - const OperandMatcher &Operand; - const Record &TheDef; - - unsigned getAllocatedTemporariesBaseID() const; - -public: - bool isIdentical(const PredicateMatcher &B) const override { return false; } - - ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - const OperandMatcher &Operand, - const Record &TheDef) - : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx), - Operand(Operand), TheDef(TheDef) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_ComplexPattern; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - unsigned ID = getAllocatedTemporariesBaseID(); - Table << MatchTable::Opcode("GIM_CheckComplexPattern") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID) - << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str()) - << MatchTable::LineBreak; - } - - unsigned countRendererFns() const override { - return 1; - } -}; - -/// Generates code to check that an operand is in a particular register bank. -class RegisterBankOperandMatcher : public OperandPredicateMatcher { -protected: - const CodeGenRegisterClass &RC; - -public: - RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - const CodeGenRegisterClass &RC) - : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - RC.getDef() == cast(&B)->RC.getDef(); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_RegBank; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckRegBankForClass") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("RC") - << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID") - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is a basic block. -class MBBOperandMatcher : public OperandPredicateMatcher { -public: - MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx) - : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_MBB; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") - << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak; - } -}; - -class ImmOperandMatcher : public OperandPredicateMatcher { -public: - ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx) - : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_Imm; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") - << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is a G_CONSTANT with a particular -/// int. -class ConstantIntOperandMatcher : public OperandPredicateMatcher { -protected: - int64_t Value; - -public: - ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) - : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - Value == cast(&B)->Value; - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_Int; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckConstantInt") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::IntValue(Value) << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is a raw int (where MO.isImm() or -/// MO.isCImm() is true). -class LiteralIntOperandMatcher : public OperandPredicateMatcher { -protected: - int64_t Value; - -public: - LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) - : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx), - Value(Value) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - Value == cast(&B)->Value; - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_LiteralInt; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckLiteralInt") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::IntValue(Value) << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is an CmpInst predicate -class CmpPredicateOperandMatcher : public OperandPredicateMatcher { -protected: - std::string PredName; - -public: - CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - std::string P) - : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - PredName == cast(&B)->PredName; - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_CmpPredicate; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckCmpPredicate") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("Predicate") - << MatchTable::NamedValue("CmpInst", PredName) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that an operand is an intrinsic ID. -class IntrinsicIDOperandMatcher : public OperandPredicateMatcher { -protected: - const CodeGenIntrinsic *II; - -public: - IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - const CodeGenIntrinsic *II) - : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - II == cast(&B)->II; - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_IntrinsicID; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckIntrinsicID") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::NamedValue("Intrinsic::" + II->EnumName) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that this operand is an immediate whose value meets -/// an immediate predicate. -class OperandImmPredicateMatcher : public OperandPredicateMatcher { -protected: - TreePredicateFn Predicate; - -public: - OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx, - const TreePredicateFn &Predicate) - : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx), - Predicate(Predicate) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return OperandPredicateMatcher::isIdentical(B) && - Predicate.getOrigPatFragRecord() == - cast(&B) - ->Predicate.getOrigPatFragRecord(); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_ImmPredicate; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("MO") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("Predicate") - << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that a set of predicates match for a particular -/// operand. -class OperandMatcher : public PredicateListMatcher { -protected: - InstructionMatcher &Insn; - unsigned OpIdx; - std::string SymbolicName; - - /// The index of the first temporary variable allocated to this operand. The - /// number of allocated temporaries can be found with - /// countRendererFns(). - unsigned AllocatedTemporariesBaseID; - -public: - OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx, - const std::string &SymbolicName, - unsigned AllocatedTemporariesBaseID) - : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName), - AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {} - - bool hasSymbolicName() const { return !SymbolicName.empty(); } - StringRef getSymbolicName() const { return SymbolicName; } - void setSymbolicName(StringRef Name) { - assert(SymbolicName.empty() && "Operand already has a symbolic name"); - SymbolicName = std::string(Name); - } - - /// Construct a new operand predicate and add it to the matcher. - template - std::optional addPredicate(Args &&...args) { - if (isSameAsAnotherOperand()) - return std::nullopt; - Predicates.emplace_back(std::make_unique( - getInsnVarID(), getOpIdx(), std::forward(args)...)); - return static_cast(Predicates.back().get()); - } - - unsigned getOpIdx() const { return OpIdx; } - unsigned getInsnVarID() const; - - std::string getOperandExpr(unsigned InsnVarID) const { - return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" + - llvm::to_string(OpIdx) + ")"; - } - - InstructionMatcher &getInstructionMatcher() const { return Insn; } - - Error addTypeCheckPredicate(const TypeSetByHwMode &VTy, - bool OperandIsAPointer); - - /// Emit MatchTable opcodes that test whether the instruction named in - /// InsnVarID matches all the predicates and all the operands. - void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) { - if (!Optimized) { - std::string Comment; - raw_string_ostream CommentOS(Comment); - CommentOS << "MIs[" << getInsnVarID() << "] "; - if (SymbolicName.empty()) - CommentOS << "Operand " << OpIdx; - else - CommentOS << SymbolicName; - Table << MatchTable::Comment(Comment) << MatchTable::LineBreak; - } - - emitPredicateListOpcodes(Table, Rule); - } - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - bool isHigherPriorityThan(OperandMatcher &B) { - // Operand matchers involving more predicates have higher priority. - if (predicates_size() > B.predicates_size()) - return true; - if (predicates_size() < B.predicates_size()) - return false; - - // This assumes that predicates are added in a consistent order. - for (auto &&Predicate : zip(predicates(), B.predicates())) { - if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) - return true; - if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) - return false; - } - - return false; - }; - - /// Report the maximum number of temporary operands needed by the operand - /// matcher. - unsigned countRendererFns() { - return std::accumulate( - predicates().begin(), predicates().end(), 0, - [](unsigned A, - const std::unique_ptr &Predicate) { - return A + Predicate->countRendererFns(); - }); - } - - unsigned getAllocatedTemporariesBaseID() const { - return AllocatedTemporariesBaseID; - } - - bool isSameAsAnotherOperand() { - for (const auto &Predicate : predicates()) - if (isa(Predicate)) - return true; - return false; - } -}; - -Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy, - bool OperandIsAPointer) { - if (!VTy.isMachineValueType()) - return failedImport("unsupported typeset"); - - if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) { - addPredicate(0); - return Error::success(); - } - - auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy); - if (!OpTyOrNone) - return failedImport("unsupported type"); - - if (OperandIsAPointer) - addPredicate(OpTyOrNone->get().getSizeInBits()); - else if (VTy.isPointer()) - addPredicate(LLT::pointer(VTy.getPtrAddrSpace(), - OpTyOrNone->get().getSizeInBits())); - else - addPredicate(*OpTyOrNone); - return Error::success(); -} - -unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const { - return Operand.getAllocatedTemporariesBaseID(); -} - -/// Generates code to check a predicate on an instruction. -/// -/// Typical predicates include: -/// * The opcode of the instruction is a particular value. -/// * The nsw/nuw flag is/isn't set. -class InstructionPredicateMatcher : public PredicateMatcher { -public: - InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID) - : PredicateMatcher(Kind, InsnVarID) {} - virtual ~InstructionPredicateMatcher() {} - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - virtual bool - isHigherPriorityThan(const InstructionPredicateMatcher &B) const { - return Kind < B.Kind; - }; -}; - -template <> -std::string -PredicateListMatcher::getNoPredicateComment() const { - return "No instruction predicates"; -} - -/// Generates code to check the opcode of an instruction. -class InstructionOpcodeMatcher : public InstructionPredicateMatcher { -protected: - // Allow matching one to several, similar opcodes that share properties. This - // is to handle patterns where one SelectionDAG operation maps to multiple - // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first - // is treated as the canonical opcode. - SmallVector Insts; - - static DenseMap OpcodeValues; - - - MatchTableRecord getInstValue(const CodeGenInstruction *I) const { - const auto VI = OpcodeValues.find(I); - if (VI != OpcodeValues.end()) - return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(), - VI->second); - return MatchTable::NamedValue(I->Namespace, I->TheDef->getName()); - } - -public: - static void initOpcodeValuesMap(const CodeGenTarget &Target) { - OpcodeValues.clear(); - - unsigned OpcodeValue = 0; - for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue()) - OpcodeValues[I] = OpcodeValue++; - } - - InstructionOpcodeMatcher(unsigned InsnVarID, - ArrayRef I) - : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), - Insts(I.begin(), I.end()) { - assert((Insts.size() == 1 || Insts.size() == 2) && - "unexpected number of opcode alternatives"); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_Opcode; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - Insts == cast(&B)->Insts; - } - - bool hasValue() const override { - return Insts.size() == 1 && OpcodeValues.count(Insts[0]); - } - - // TODO: This is used for the SwitchMatcher optimization. We should be able to - // return a list of the opcodes to match. - MatchTableRecord getValue() const override { - assert(Insts.size() == 1); - - const CodeGenInstruction *I = Insts[0]; - const auto VI = OpcodeValues.find(I); - if (VI != OpcodeValues.end()) - return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(), - VI->second); - return MatchTable::NamedValue(I->Namespace, I->TheDef->getName()); - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - StringRef CheckType = Insts.size() == 1 ? - "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither"; - Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID); - - for (const CodeGenInstruction *I : Insts) - Table << getInstValue(I); - Table << MatchTable::LineBreak; - } - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - bool - isHigherPriorityThan(const InstructionPredicateMatcher &B) const override { - if (InstructionPredicateMatcher::isHigherPriorityThan(B)) - return true; - if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this)) - return false; - - // Prioritize opcodes for cosmetic reasons in the generated source. Although - // this is cosmetic at the moment, we may want to drive a similar ordering - // using instruction frequency information to improve compile time. - if (const InstructionOpcodeMatcher *BO = - dyn_cast(&B)) - return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName(); - - return false; - }; - - bool isConstantInstruction() const { - return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT"; - } - - // The first opcode is the canonical opcode, and later are alternatives. - StringRef getOpcode() const { - return Insts[0]->TheDef->getName(); - } - - ArrayRef getAlternativeOpcodes() { - return Insts; - } - - bool isVariadicNumOperands() const { - // If one is variadic, they all should be. - return Insts[0]->Operands.isVariadic; - } - - StringRef getOperandType(unsigned OpIdx) const { - // Types expected to be uniform for all alternatives. - return Insts[0]->Operands[OpIdx].OperandType; - } -}; - -DenseMap - InstructionOpcodeMatcher::OpcodeValues; - -class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher { - unsigned NumOperands = 0; - -public: - InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands) - : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID), - NumOperands(NumOperands) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_NumOperands; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - NumOperands == cast(&B)->NumOperands; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckNumOperands") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Expected") - << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak; - } -}; - -/// Generates code to check that this instruction is a constant whose value -/// meets an immediate predicate. -/// -/// Immediates are slightly odd since they are typically used like an operand -/// but are represented as an operator internally. We typically write simm8:$src -/// in a tablegen pattern, but this is just syntactic sugar for -/// (imm:i32)<>:$imm which more directly describes the nodes -/// that will be matched and the predicate (which is attached to the imm -/// operator) that will be tested. In SelectionDAG this describes a -/// ConstantSDNode whose internal value will be tested using the simm8 predicate. -/// -/// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In -/// this representation, the immediate could be tested with an -/// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a -/// OperandPredicateMatcher-subclass to check the Value meets the predicate but -/// there are two implementation issues with producing that matcher -/// configuration from the SelectionDAG pattern: -/// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that -/// were we to sink the immediate predicate to the operand we would have to -/// have two partial implementations of PatFrag support, one for immediates -/// and one for non-immediates. -/// * At the point we handle the predicate, the OperandMatcher hasn't been -/// created yet. If we were to sink the predicate to the OperandMatcher we -/// would also have to complicate (or duplicate) the code that descends and -/// creates matchers for the subtree. -/// Overall, it's simpler to handle it in the place it was found. -class InstructionImmPredicateMatcher : public InstructionPredicateMatcher { -protected: - TreePredicateFn Predicate; - -public: - InstructionImmPredicateMatcher(unsigned InsnVarID, - const TreePredicateFn &Predicate) - : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID), - Predicate(Predicate) {} - - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - Predicate.getOrigPatFragRecord() == - cast(&B) - ->Predicate.getOrigPatFragRecord(); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_ImmPredicate; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate)) - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Predicate") - << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that a memory instruction has a atomic ordering -/// MachineMemoryOperand. -class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher { -public: - enum AOComparator { - AO_Exactly, - AO_OrStronger, - AO_WeakerThan, - }; - -protected: - StringRef Order; - AOComparator Comparator; - -public: - AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order, - AOComparator Comparator = AO_Exactly) - : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID), - Order(Order), Comparator(Comparator) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_AtomicOrderingMMO; - } - - bool isIdentical(const PredicateMatcher &B) const override { - if (!InstructionPredicateMatcher::isIdentical(B)) - return false; - const auto &R = *cast(&B); - return Order == R.Order && Comparator == R.Comparator; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - StringRef Opcode = "GIM_CheckAtomicOrdering"; - - if (Comparator == AO_OrStronger) - Opcode = "GIM_CheckAtomicOrderingOrStrongerThan"; - if (Comparator == AO_WeakerThan) - Opcode = "GIM_CheckAtomicOrderingWeakerThan"; - - Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order") - << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str()) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that the size of an MMO is exactly N bytes. -class MemorySizePredicateMatcher : public InstructionPredicateMatcher { -protected: - unsigned MMOIdx; - uint64_t Size; - -public: - MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size) - : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID), - MMOIdx(MMOIdx), Size(Size) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_MemoryLLTSize; - } - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - MMOIdx == cast(&B)->MMOIdx && - Size == cast(&B)->Size; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) - << MatchTable::Comment("Size") << MatchTable::IntValue(Size) - << MatchTable::LineBreak; - } -}; - -class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher { -protected: - unsigned MMOIdx; - SmallVector AddrSpaces; - -public: - MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, - ArrayRef AddrSpaces) - : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID), - MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_MemoryAddressSpace; - } - bool isIdentical(const PredicateMatcher &B) const override { - if (!InstructionPredicateMatcher::isIdentical(B)) - return false; - auto *Other = cast(&B); - return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) - // Encode number of address spaces to expect. - << MatchTable::Comment("NumAddrSpace") - << MatchTable::IntValue(AddrSpaces.size()); - for (unsigned AS : AddrSpaces) - Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS); - - Table << MatchTable::LineBreak; - } -}; - -class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher { -protected: - unsigned MMOIdx; - int MinAlign; - -public: - MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, - int MinAlign) - : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID), - MMOIdx(MMOIdx), MinAlign(MinAlign) { - assert(MinAlign > 0); - } - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_MemoryAlignment; - } - - bool isIdentical(const PredicateMatcher &B) const override { - if (!InstructionPredicateMatcher::isIdentical(B)) - return false; - auto *Other = cast(&B); - return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckMemoryAlignment") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) - << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that the size of an MMO is less-than, equal-to, or -/// greater than a given LLT. -class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher { -public: - enum RelationKind { - GreaterThan, - EqualTo, - LessThan, - }; - -protected: - unsigned MMOIdx; - RelationKind Relation; - unsigned OpIdx; - -public: - MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, - enum RelationKind Relation, - unsigned OpIdx) - : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID), - MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_MemoryVsLLTSize; - } - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - MMOIdx == cast(&B)->MMOIdx && - Relation == cast(&B)->Relation && - OpIdx == cast(&B)->OpIdx; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode(Relation == EqualTo - ? "GIM_CheckMemorySizeEqualToLLT" - : Relation == GreaterThan - ? "GIM_CheckMemorySizeGreaterThanLLT" - : "GIM_CheckMemorySizeLessThanLLT") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) - << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) - << MatchTable::LineBreak; - } -}; - -// Matcher for immAllOnesV/immAllZerosV -class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher { -public: - enum SplatKind { - AllZeros, - AllOnes - }; - -private: - SplatKind Kind; - -public: - VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K) - : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_VectorSplatImm; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - Kind == static_cast(B).Kind; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - if (Kind == AllOnes) - Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes"); - else - Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros"); - - Table << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID); - Table << MatchTable::LineBreak; - } -}; - -/// Generates code to check an arbitrary C++ instruction predicate. -class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher { -protected: - TreePredicateFn Predicate; - -public: - GenericInstructionPredicateMatcher(unsigned InsnVarID, - TreePredicateFn Predicate) - : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID), - Predicate(Predicate) {} - - static bool classof(const InstructionPredicateMatcher *P) { - return P->getKind() == IPM_GenericPredicate; - } - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B) && - Predicate == - static_cast(B) - .Predicate; - } - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("FnId") - << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check for the absence of use of the result. -// TODO? Generalize this to support checking for one use. -class NoUsePredicateMatcher : public InstructionPredicateMatcher { -public: - NoUsePredicateMatcher(unsigned InsnVarID) - : InstructionPredicateMatcher(IPM_NoUse, InsnVarID) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == IPM_NoUse; - } - - bool isIdentical(const PredicateMatcher &B) const override { - return InstructionPredicateMatcher::isIdentical(B); - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIM_CheckHasNoUse") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::LineBreak; - } -}; - -/// Generates code to check that a set of predicates and operands match for a -/// particular instruction. -/// -/// Typical predicates include: -/// * Has a specific opcode. -/// * Has an nsw/nuw flag or doesn't. -class InstructionMatcher final : public PredicateListMatcher { -protected: - typedef std::vector> OperandVec; - - RuleMatcher &Rule; - - /// The operands to match. All rendered operands must be present even if the - /// condition is always true. - OperandVec Operands; - bool NumOperandsCheck = true; - - std::string SymbolicName; - unsigned InsnVarID; - - /// PhysRegInputs - List list has an entry for each explicitly specified - /// physreg input to the pattern. The first elt is the Register node, the - /// second is the recorded slot number the input pattern match saved it in. - SmallVector, 2> PhysRegInputs; - -public: - InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName, - bool NumOpsCheck = true) - : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) { - // We create a new instruction matcher. - // Get a new ID for that instruction. - InsnVarID = Rule.implicitlyDefineInsnVar(*this); - } - - /// Construct a new instruction predicate and add it to the matcher. - template - std::optional addPredicate(Args &&...args) { - Predicates.emplace_back( - std::make_unique(getInsnVarID(), std::forward(args)...)); - return static_cast(Predicates.back().get()); - } - - RuleMatcher &getRuleMatcher() const { return Rule; } - - unsigned getInsnVarID() const { return InsnVarID; } - - /// Add an operand to the matcher. - OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName, - unsigned AllocatedTemporariesBaseID) { - Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName, - AllocatedTemporariesBaseID)); - if (!SymbolicName.empty()) - Rule.defineOperand(SymbolicName, *Operands.back()); - - return *Operands.back(); - } - - OperandMatcher &getOperand(unsigned OpIdx) { - auto I = llvm::find_if(Operands, - [&OpIdx](const std::unique_ptr &X) { - return X->getOpIdx() == OpIdx; - }); - if (I != Operands.end()) - return **I; - llvm_unreachable("Failed to lookup operand"); - } - - OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx, - unsigned TempOpIdx) { - assert(SymbolicName.empty()); - OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx); - Operands.emplace_back(OM); - Rule.definePhysRegOperand(Reg, *OM); - PhysRegInputs.emplace_back(Reg, OpIdx); - return *OM; - } - - ArrayRef> getPhysRegInputs() const { - return PhysRegInputs; - } - - StringRef getSymbolicName() const { return SymbolicName; } - unsigned getNumOperands() const { return Operands.size(); } - OperandVec::iterator operands_begin() { return Operands.begin(); } - OperandVec::iterator operands_end() { return Operands.end(); } - iterator_range operands() { - return make_range(operands_begin(), operands_end()); - } - OperandVec::const_iterator operands_begin() const { return Operands.begin(); } - OperandVec::const_iterator operands_end() const { return Operands.end(); } - iterator_range operands() const { - return make_range(operands_begin(), operands_end()); - } - bool operands_empty() const { return Operands.empty(); } - - void pop_front() { Operands.erase(Operands.begin()); } - - void optimize(); - - /// Emit MatchTable opcodes that test whether the instruction named in - /// InsnVarName matches all the predicates and all the operands. - void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) { - if (NumOperandsCheck) - InstructionNumOperandsMatcher(InsnVarID, getNumOperands()) - .emitPredicateOpcodes(Table, Rule); - - // First emit all instruction level predicates need to be verified before we - // can verify operands. - emitFilteredPredicateListOpcodes( - [](const PredicateMatcher &P) { - return !P.dependsOnOperands(); - }, Table, Rule); - - // Emit all operand constraints. - for (const auto &Operand : Operands) - Operand->emitPredicateOpcodes(Table, Rule); - - // All of the tablegen defined predicates should now be matched. Now emit - // any custom predicates that rely on all generated checks. - emitFilteredPredicateListOpcodes( - [](const PredicateMatcher &P) { - return P.dependsOnOperands(); - }, Table, Rule); - } - - /// Compare the priority of this object and B. - /// - /// Returns true if this object is more important than B. - bool isHigherPriorityThan(InstructionMatcher &B) { - // Instruction matchers involving more operands have higher priority. - if (Operands.size() > B.Operands.size()) - return true; - if (Operands.size() < B.Operands.size()) - return false; - - for (auto &&P : zip(predicates(), B.predicates())) { - auto L = static_cast(std::get<0>(P).get()); - auto R = static_cast(std::get<1>(P).get()); - if (L->isHigherPriorityThan(*R)) - return true; - if (R->isHigherPriorityThan(*L)) - return false; - } - - for (auto Operand : zip(Operands, B.Operands)) { - if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand))) - return true; - if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand))) - return false; - } - - return false; - }; - - /// Report the maximum number of temporary operands needed by the instruction - /// matcher. - unsigned countRendererFns() { - return std::accumulate( - predicates().begin(), predicates().end(), 0, - [](unsigned A, - const std::unique_ptr &Predicate) { - return A + Predicate->countRendererFns(); - }) + - std::accumulate( - Operands.begin(), Operands.end(), 0, - [](unsigned A, const std::unique_ptr &Operand) { - return A + Operand->countRendererFns(); - }); - } - - InstructionOpcodeMatcher &getOpcodeMatcher() { - for (auto &P : predicates()) - if (auto *OpMatcher = dyn_cast(P.get())) - return *OpMatcher; - llvm_unreachable("Didn't find an opcode matcher"); - } - - bool isConstantInstruction() { - return getOpcodeMatcher().isConstantInstruction(); - } - - StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); } -}; - -StringRef RuleMatcher::getOpcode() const { - return Matchers.front()->getOpcode(); -} - -unsigned RuleMatcher::getNumOperands() const { - return Matchers.front()->getNumOperands(); -} - -LLTCodeGen RuleMatcher::getFirstConditionAsRootType() { - InstructionMatcher &InsnMatcher = *Matchers.front(); - if (!InsnMatcher.predicates_empty()) - if (const auto *TM = - dyn_cast(&**InsnMatcher.predicates_begin())) - if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0) - return TM->getTy(); - return {}; -} - -/// Generates code to check that the operand is a register defined by an -/// instruction that matches the given instruction matcher. -/// -/// For example, the pattern: -/// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3)) -/// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match -/// the: -/// (G_ADD $src1, $src2) -/// subpattern. -class InstructionOperandMatcher : public OperandPredicateMatcher { -protected: - std::unique_ptr InsnMatcher; - - GISelFlags Flags; - -public: - InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx, - RuleMatcher &Rule, StringRef SymbolicName, - bool NumOpsCheck = true) - : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx), - InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)), - Flags(Rule.getGISelFlags()) {} - - static bool classof(const PredicateMatcher *P) { - return P->getKind() == OPM_Instruction; - } - - InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; } - - void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const { - const unsigned NewInsnVarID = InsnMatcher->getInsnVarID(); - const bool IgnoreCopies = Flags & GISF_IgnoreCopies; - Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies" - : "GIM_RecordInsn") - << MatchTable::Comment("DefineMI") - << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI") - << MatchTable::IntValue(getInsnVarID()) - << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx()) - << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]") - << MatchTable::LineBreak; - } - - void emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const override { - emitCaptureOpcodes(Table, Rule); - InsnMatcher->emitPredicateOpcodes(Table, Rule); - } - - bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override { - if (OperandPredicateMatcher::isHigherPriorityThan(B)) - return true; - if (B.OperandPredicateMatcher::isHigherPriorityThan(*this)) - return false; - - if (const InstructionOperandMatcher *BP = - dyn_cast(&B)) - if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher)) - return true; - return false; - } - - /// Report the maximum number of temporary operands needed by the predicate - /// matcher. - unsigned countRendererFns() const override { - return InsnMatcher->countRendererFns(); - } -}; - -void InstructionMatcher::optimize() { - SmallVector, 8> Stash; - const auto &OpcMatcher = getOpcodeMatcher(); - - Stash.push_back(predicates_pop_front()); - if (Stash.back().get() == &OpcMatcher) { - if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands()) - Stash.emplace_back( - new InstructionNumOperandsMatcher(InsnVarID, getNumOperands())); - NumOperandsCheck = false; - - for (auto &OM : Operands) - for (auto &OP : OM->predicates()) - if (isa(OP)) { - Stash.push_back(std::move(OP)); - OM->eraseNullPredicates(); - break; - } - } - - if (InsnVarID > 0) { - assert(!Operands.empty() && "Nested instruction is expected to def a vreg"); - for (auto &OP : Operands[0]->predicates()) - OP.reset(); - Operands[0]->eraseNullPredicates(); - } - for (auto &OM : Operands) { - for (auto &OP : OM->predicates()) - if (isa(OP)) - Stash.push_back(std::move(OP)); - OM->eraseNullPredicates(); - } - while (!Stash.empty()) - prependPredicate(Stash.pop_back_val()); -} - -//===- Actions ------------------------------------------------------------===// -class OperandRenderer { -public: - enum RendererKind { - OR_Copy, - OR_CopyOrAddZeroReg, - OR_CopySubReg, - OR_CopyPhysReg, - OR_CopyConstantAsImm, - OR_CopyFConstantAsFPImm, - OR_Imm, - OR_SubRegIndex, - OR_Register, - OR_TempRegister, - OR_ComplexPattern, - OR_Custom, - OR_CustomOperand - }; - -protected: - RendererKind Kind; - -public: - OperandRenderer(RendererKind Kind) : Kind(Kind) {} - virtual ~OperandRenderer() {} - - RendererKind getKind() const { return Kind; } - - virtual void emitRenderOpcodes(MatchTable &Table, - RuleMatcher &Rule) const = 0; -}; - -/// A CopyRenderer emits code to copy a single operand from an existing -/// instruction to the one being built. -class CopyRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - /// The name of the operand. - const StringRef SymbolicName; - -public: - CopyRenderer(unsigned NewInsnID, StringRef SymbolicName) - : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), - SymbolicName(SymbolicName) { - assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); - } - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_Copy; - } - - StringRef getSymbolicName() const { return SymbolicName; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); - Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID") - << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOpIdx()) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// A CopyRenderer emits code to copy a virtual register to a specific physical -/// register. -class CopyPhysRegRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - Record *PhysReg; - -public: - CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg) - : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID), - PhysReg(Reg) { - assert(PhysReg); - } - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CopyPhysReg; - } - - Record *getPhysReg() const { return PhysReg; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg); - unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); - Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID") - << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOpIdx()) - << MatchTable::Comment(PhysReg->getName()) - << MatchTable::LineBreak; - } -}; - -/// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an -/// existing instruction to the one being built. If the operand turns out to be -/// a 'G_CONSTANT 0' then it replaces the operand with a zero register. -class CopyOrAddZeroRegRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - /// The name of the operand. - const StringRef SymbolicName; - const Record *ZeroRegisterDef; - -public: - CopyOrAddZeroRegRenderer(unsigned NewInsnID, - StringRef SymbolicName, Record *ZeroRegisterDef) - : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID), - SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) { - assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); - } - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CopyOrAddZeroReg; - } - - StringRef getSymbolicName() const { return SymbolicName; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); - Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg") - << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOpIdx()) - << MatchTable::NamedValue( - (ZeroRegisterDef->getValue("Namespace") - ? ZeroRegisterDef->getValueAsString("Namespace") - : ""), - ZeroRegisterDef->getName()) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to -/// an extended immediate operand. -class CopyConstantAsImmRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - /// The name of the operand. - const std::string SymbolicName; - bool Signed; - -public: - CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName) - : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID), - SymbolicName(SymbolicName), Signed(true) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CopyConstantAsImm; - } - - StringRef getSymbolicName() const { return SymbolicName; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); - Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm" - : "GIR_CopyConstantAsUImm") - << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT -/// instruction to an extended immediate operand. -class CopyFConstantAsFPImmRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - /// The name of the operand. - const std::string SymbolicName; - -public: - CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName) - : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID), - SymbolicName(SymbolicName) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CopyFConstantAsFPImm; - } - - StringRef getSymbolicName() const { return SymbolicName; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); - Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm") - << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// A CopySubRegRenderer emits code to copy a single register operand from an -/// existing instruction to the one being built and indicate that only a -/// subregister should be copied. -class CopySubRegRenderer : public OperandRenderer { -protected: - unsigned NewInsnID; - /// The name of the operand. - const StringRef SymbolicName; - /// The subregister to extract. - const CodeGenSubRegIndex *SubReg; - -public: - CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName, - const CodeGenSubRegIndex *SubReg) - : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), - SymbolicName(SymbolicName), SubReg(SubReg) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CopySubReg; - } - - StringRef getSymbolicName() const { return SymbolicName; } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); - Table << MatchTable::Opcode("GIR_CopySubReg") - << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOpIdx()) - << MatchTable::Comment("SubRegIdx") - << MatchTable::IntValue(SubReg->EnumValue) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// Adds a specific physical register to the instruction being built. -/// This is typically useful for WZR/XZR on AArch64. -class AddRegisterRenderer : public OperandRenderer { -protected: - unsigned InsnID; - const Record *RegisterDef; - bool IsDef; - const CodeGenTarget &Target; - -public: - AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target, - const Record *RegisterDef, bool IsDef = false) - : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef), - IsDef(IsDef), Target(Target) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_Register; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_AddRegister") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID); - if (RegisterDef->getName() != "zero_reg") { - Table << MatchTable::NamedValue( - (RegisterDef->getValue("Namespace") - ? RegisterDef->getValueAsString("Namespace") - : ""), - RegisterDef->getName()); - } else { - Table << MatchTable::NamedValue(Target.getRegNamespace(), "NoRegister"); - } - Table << MatchTable::Comment("AddRegisterRegFlags"); - - // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are - // really needed for a physical register reference. We can pack the - // register and flags in a single field. - if (IsDef) - Table << MatchTable::NamedValue("RegState::Define"); - else - Table << MatchTable::IntValue(0); - Table << MatchTable::LineBreak; - } -}; - -/// Adds a specific temporary virtual register to the instruction being built. -/// This is used to chain instructions together when emitting multiple -/// instructions. -class TempRegRenderer : public OperandRenderer { -protected: - unsigned InsnID; - unsigned TempRegID; - const CodeGenSubRegIndex *SubRegIdx; - bool IsDef; - bool IsDead; - -public: - TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false, - const CodeGenSubRegIndex *SubReg = nullptr, - bool IsDead = false) - : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID), - SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_TempRegister; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - if (SubRegIdx) { - assert(!IsDef); - Table << MatchTable::Opcode("GIR_AddTempSubRegister"); - } else - Table << MatchTable::Opcode("GIR_AddTempRegister"); - - Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID) - << MatchTable::Comment("TempRegFlags"); - - if (IsDef) { - SmallString<32> RegFlags; - RegFlags += "RegState::Define"; - if (IsDead) - RegFlags += "|RegState::Dead"; - Table << MatchTable::NamedValue(RegFlags); - } else - Table << MatchTable::IntValue(0); - - if (SubRegIdx) - Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName()); - Table << MatchTable::LineBreak; - } -}; - -/// Adds a specific immediate to the instruction being built. -class ImmRenderer : public OperandRenderer { -protected: - unsigned InsnID; - int64_t Imm; - -public: - ImmRenderer(unsigned InsnID, int64_t Imm) - : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_Imm; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID") - << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm") - << MatchTable::IntValue(Imm) << MatchTable::LineBreak; - } -}; - -/// Adds an enum value for a subreg index to the instruction being built. -class SubRegIndexRenderer : public OperandRenderer { -protected: - unsigned InsnID; - const CodeGenSubRegIndex *SubRegIdx; - -public: - SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI) - : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_SubRegIndex; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID") - << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex") - << MatchTable::IntValue(SubRegIdx->EnumValue) - << MatchTable::LineBreak; - } -}; - -/// Adds operands by calling a renderer function supplied by the ComplexPattern -/// matcher function. -class RenderComplexPatternOperand : public OperandRenderer { -private: - unsigned InsnID; - const Record &TheDef; - /// The name of the operand. - const StringRef SymbolicName; - /// The renderer number. This must be unique within a rule since it's used to - /// identify a temporary variable to hold the renderer function. - unsigned RendererID; - /// When provided, this is the suboperand of the ComplexPattern operand to - /// render. Otherwise all the suboperands will be rendered. - std::optional SubOperand; - /// The subregister to extract. Render the whole register if not specified. - const CodeGenSubRegIndex *SubReg; - - unsigned getNumOperands() const { - return TheDef.getValueAsDag("Operands")->getNumArgs(); - } - -public: - RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef, - StringRef SymbolicName, unsigned RendererID, - std::optional SubOperand = std::nullopt, - const CodeGenSubRegIndex *SubReg = nullptr) - : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef), - SymbolicName(SymbolicName), RendererID(RendererID), - SubOperand(SubOperand), SubReg(SubReg) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_ComplexPattern; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode( - SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer" - : "GIR_ComplexSubOperandRenderer") - : "GIR_ComplexRenderer") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("RendererID") - << MatchTable::IntValue(RendererID); - if (SubOperand) - Table << MatchTable::Comment("SubOperand") - << MatchTable::IntValue(*SubOperand); - if (SubReg) - Table << MatchTable::Comment("SubRegIdx") - << MatchTable::IntValue(SubReg->EnumValue); - Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -class CustomRenderer : public OperandRenderer { -protected: - unsigned InsnID; - const Record &Renderer; - /// The name of the operand. - const std::string SymbolicName; - -public: - CustomRenderer(unsigned InsnID, const Record &Renderer, - StringRef SymbolicName) - : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer), - SymbolicName(SymbolicName) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_Custom; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); - unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); - Table << MatchTable::Opcode("GIR_CustomRenderer") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OldInsnVarID) - << MatchTable::Comment("Renderer") - << MatchTable::NamedValue( - "GICR_" + Renderer.getValueAsString("RendererFn").str()) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -class CustomOperandRenderer : public OperandRenderer { -protected: - unsigned InsnID; - const Record &Renderer; - /// The name of the operand. - const std::string SymbolicName; - -public: - CustomOperandRenderer(unsigned InsnID, const Record &Renderer, - StringRef SymbolicName) - : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer), - SymbolicName(SymbolicName) {} - - static bool classof(const OperandRenderer *R) { - return R->getKind() == OR_CustomOperand; - } - - void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName); - Table << MatchTable::Opcode("GIR_CustomOperandRenderer") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("OldInsnID") - << MatchTable::IntValue(OpdMatcher.getInsnVarID()) - << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(OpdMatcher.getOpIdx()) - << MatchTable::Comment("OperandRenderer") - << MatchTable::NamedValue( - "GICR_" + Renderer.getValueAsString("RendererFn").str()) - << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; - } -}; - -/// An action taken when all Matcher predicates succeeded for a parent rule. -/// -/// Typical actions include: -/// * Changing the opcode of an instruction. -/// * Adding an operand to an instruction. -class MatchAction { -public: - virtual ~MatchAction() {} - - /// Emit the MatchTable opcodes to implement the action. - virtual void emitActionOpcodes(MatchTable &Table, - RuleMatcher &Rule) const = 0; -}; - -/// Generates a comment describing the matched rule being acted upon. -class DebugCommentAction : public MatchAction { -private: - std::string S; - -public: - DebugCommentAction(StringRef S) : S(std::string(S)) {} - - void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Comment(S) << MatchTable::LineBreak; - } -}; - -/// Generates code to build an instruction or mutate an existing instruction -/// into the desired instruction when this is possible. -class BuildMIAction : public MatchAction { -private: - unsigned InsnID; - const CodeGenInstruction *I; - InstructionMatcher *Matched; - std::vector> OperandRenderers; - - /// True if the instruction can be built solely by mutating the opcode. - bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const { - if (!Insn) - return false; - - if (OperandRenderers.size() != Insn->getNumOperands()) - return false; - - for (const auto &Renderer : enumerate(OperandRenderers)) { - if (const auto *Copy = dyn_cast(&*Renderer.value())) { - const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName()); - if (Insn != &OM.getInstructionMatcher() || - OM.getOpIdx() != Renderer.index()) - return false; - } else - return false; - } - - return true; - } - -public: - BuildMIAction(unsigned InsnID, const CodeGenInstruction *I) - : InsnID(InsnID), I(I), Matched(nullptr) {} - - unsigned getInsnID() const { return InsnID; } - const CodeGenInstruction *getCGI() const { return I; } - - void chooseInsnToMutate(RuleMatcher &Rule) { - for (auto *MutateCandidate : Rule.mutatable_insns()) { - if (canMutate(Rule, MutateCandidate)) { - // Take the first one we're offered that we're able to mutate. - Rule.reserveInsnMatcherForMutation(MutateCandidate); - Matched = MutateCandidate; - return; - } - } - } - - template - Kind &addRenderer(Args&&... args) { - OperandRenderers.emplace_back( - std::make_unique(InsnID, std::forward(args)...)); - return *static_cast(OperandRenderers.back().get()); - } - - void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - if (Matched) { - assert(canMutate(Rule, Matched) && - "Arranged to mutate an insn that isn't mutatable"); - - unsigned RecycleInsnID = Rule.getInsnVarID(*Matched); - Table << MatchTable::Opcode("GIR_MutateOpcode") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("RecycleInsnID") - << MatchTable::IntValue(RecycleInsnID) - << MatchTable::Comment("Opcode") - << MatchTable::NamedValue(I->Namespace, I->TheDef->getName()) - << MatchTable::LineBreak; - - if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) { - for (auto *Def : I->ImplicitDefs) { - auto Namespace = Def->getValue("Namespace") - ? Def->getValueAsString("Namespace") - : ""; - Table << MatchTable::Opcode("GIR_AddImplicitDef") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::NamedValue(Namespace, Def->getName()) - << MatchTable::LineBreak; - } - for (auto *Use : I->ImplicitUses) { - auto Namespace = Use->getValue("Namespace") - ? Use->getValueAsString("Namespace") - : ""; - Table << MatchTable::Opcode("GIR_AddImplicitUse") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::NamedValue(Namespace, Use->getName()) - << MatchTable::LineBreak; - } - } - return; - } - - // TODO: Simple permutation looks like it could be almost as common as - // mutation due to commutative operations. - - Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID") - << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode") - << MatchTable::NamedValue(I->Namespace, I->TheDef->getName()) - << MatchTable::LineBreak; - for (const auto &Renderer : OperandRenderers) - Renderer->emitRenderOpcodes(Table, Rule); - - if (I->mayLoad || I->mayStore) { - Table << MatchTable::Opcode("GIR_MergeMemOperands") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("MergeInsnID's"); - // Emit the ID's for all the instructions that are matched by this rule. - // TODO: Limit this to matched instructions that mayLoad/mayStore or have - // some other means of having a memoperand. Also limit this to - // emitted instructions that expect to have a memoperand too. For - // example, (G_SEXT (G_LOAD x)) that results in separate load and - // sign-extend instructions shouldn't put the memoperand on the - // sign-extend since it has no effect there. - std::vector MergeInsnIDs; - for (const auto &IDMatcherPair : Rule.defined_insn_vars()) - MergeInsnIDs.push_back(IDMatcherPair.second); - llvm::sort(MergeInsnIDs); - for (const auto &MergeInsnID : MergeInsnIDs) - Table << MatchTable::IntValue(MergeInsnID); - Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList") - << MatchTable::LineBreak; - } - - // FIXME: This is a hack but it's sufficient for ISel. We'll need to do - // better for combines. Particularly when there are multiple match - // roots. - if (InsnID == 0) - Table << MatchTable::Opcode("GIR_EraseFromParent") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::LineBreak; - } -}; + Explanation += " zextload"; -/// Generates code to constrain the operands of an output instruction to the -/// register classes specified by the definition of that instruction. -class ConstrainOperandsToDefinitionAction : public MatchAction { - unsigned InsnID; + if (P.isNonTruncStore()) + Explanation += " non-truncstore"; + if (P.isTruncStore()) + Explanation += " truncstore"; -public: - ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {} + if (Record *VT = P.getMemoryVT()) + Explanation += (" MemVT=" + VT->getName()).str(); + if (Record *VT = P.getScalarMemoryVT()) + Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str(); - void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::LineBreak; - } -}; + if (ListInit *AddrSpaces = P.getAddressSpaces()) { + raw_string_ostream OS(Explanation); + OS << " AddressSpaces=["; -/// Generates code to constrain the specified operand of an output instruction -/// to the specified register class. -class ConstrainOperandToRegClassAction : public MatchAction { - unsigned InsnID; - unsigned OpIdx; - const CodeGenRegisterClass &RC; + StringRef AddrSpaceSeparator; + for (Init *Val : AddrSpaces->getValues()) { + IntInit *IntVal = dyn_cast(Val); + if (!IntVal) + continue; -public: - ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx, - const CodeGenRegisterClass &RC) - : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {} - - void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_ConstrainOperandRC") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) - << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID") - << MatchTable::LineBreak; - } -}; + OS << AddrSpaceSeparator << IntVal->getValue(); + AddrSpaceSeparator = ", "; + } -/// Generates code to create a temporary register which can be used to chain -/// instructions together. -class MakeTempRegisterAction : public MatchAction { -private: - LLTCodeGen Ty; - unsigned TempRegID; + OS << ']'; + } -public: - MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID) - : Ty(Ty), TempRegID(TempRegID) { - KnownTypes.insert(Ty); - } + int64_t MinAlign = P.getMinAlignment(); + if (MinAlign > 0) + Explanation += " MinAlign=" + utostr(MinAlign); - void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - Table << MatchTable::Opcode("GIR_MakeTempReg") - << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID) - << MatchTable::Comment("TypeID") - << MatchTable::NamedValue(Ty.getCxxEnumValue()) - << MatchTable::LineBreak; + if (P.isAtomicOrderingMonotonic()) + Explanation += " monotonic"; + if (P.isAtomicOrderingAcquire()) + Explanation += " acquire"; + if (P.isAtomicOrderingRelease()) + Explanation += " release"; + if (P.isAtomicOrderingAcquireRelease()) + Explanation += " acq_rel"; + if (P.isAtomicOrderingSequentiallyConsistent()) + Explanation += " seq_cst"; + if (P.isAtomicOrderingAcquireOrStronger()) + Explanation += " >=acquire"; + if (P.isAtomicOrderingWeakerThanAcquire()) + Explanation += " &RuleMatcher::getRequiredFeatures() const { - return RequiredFeatures; -} - -// Emplaces an action of the specified Kind at the end of the action list. -// -// Returns a reference to the newly created action. -// -// Like std::vector::emplace_back(), may invalidate all iterators if the new -// size exceeds the capacity. Otherwise, only invalidates the past-the-end -// iterator. -template -Kind &RuleMatcher::addAction(Args &&... args) { - Actions.emplace_back(std::make_unique(std::forward(args)...)); - return *static_cast(Actions.back().get()); -} - -// Emplaces an action of the specified Kind before the given insertion point. -// -// Returns an iterator pointing at the newly created instruction. -// -// Like std::vector::insert(), may invalidate all iterators if the new size -// exceeds the capacity. Otherwise, only invalidates the iterators from the -// insertion point onwards. -template -action_iterator RuleMatcher::insertAction(action_iterator InsertPt, - Args &&... args) { - return Actions.emplace(InsertPt, - std::make_unique(std::forward(args)...)); + return Explanation; } -unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) { - unsigned NewInsnVarID = NextInsnVarID++; - InsnVariableIDs[&Matcher] = NewInsnVarID; - return NewInsnVarID; -} +std::string explainOperator(Record *Operator) { + if (Operator->isSubClassOf("SDNode")) + return (" (" + Operator->getValueAsString("Opcode") + ")").str(); -unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const { - const auto &I = InsnVariableIDs.find(&InsnMatcher); - if (I != InsnVariableIDs.end()) - return I->second; - llvm_unreachable("Matched Insn was not captured in a local variable"); -} + if (Operator->isSubClassOf("Intrinsic")) + return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str(); -void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) { - if (!DefinedOperands.contains(SymbolicName)) { - DefinedOperands[SymbolicName] = &OM; - return; - } + if (Operator->isSubClassOf("ComplexPattern")) + return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() + + ")") + .str(); - // If the operand is already defined, then we must ensure both references in - // the matcher have the exact same node. - RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher(); - OM.addPredicate( - OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(), - RM.getGISelFlags()); -} + if (Operator->isSubClassOf("SDNodeXForm")) + return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() + + ")") + .str(); -void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) { - if (!PhysRegOperands.contains(Reg)) { - PhysRegOperands[Reg] = &OM; - return; - } + return (" (Operator " + Operator->getName() + " not understood)").str(); } -InstructionMatcher & -RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const { - for (const auto &I : InsnVariableIDs) - if (I.first->getSymbolicName() == SymbolicName) - return *I.first; - llvm_unreachable( - ("Failed to lookup instruction " + SymbolicName).str().c_str()); +/// Helper function to let the emitter report skip reason error messages. +static Error failedImport(const Twine &Reason) { + return make_error(Reason, inconvertibleErrorCode()); } -const OperandMatcher & -RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const { - const auto &I = PhysRegOperands.find(Reg); +static Error isTrivialOperatorNode(const TreePatternNode *N) { + std::string Explanation; + std::string Separator; - if (I == PhysRegOperands.end()) { - PrintFatalError(SrcLoc, "Register " + Reg->getName() + - " was not declared in matcher"); - } + bool HasUnsupportedPredicate = false; + for (const TreePredicateCall &Call : N->getPredicateCalls()) { + const TreePredicateFn &Predicate = Call.Fn; - return *I->second; -} + if (Predicate.isAlwaysTrue()) + continue; -const OperandMatcher & -RuleMatcher::getOperandMatcher(StringRef Name) const { - const auto &I = DefinedOperands.find(Name); + if (Predicate.isImmediatePattern()) + continue; - if (I == DefinedOperands.end()) - PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher"); + if (Predicate.hasNoUse()) + continue; - return *I->second; -} + if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() || + Predicate.isSignExtLoad() || Predicate.isZeroExtLoad()) + continue; -void RuleMatcher::emit(MatchTable &Table) { - if (Matchers.empty()) - llvm_unreachable("Unexpected empty matcher!"); - - // The representation supports rules that require multiple roots such as: - // %ptr(p0) = ... - // %elt0(s32) = G_LOAD %ptr - // %1(p0) = G_ADD %ptr, 4 - // %elt1(s32) = G_LOAD p0 %1 - // which could be usefully folded into: - // %ptr(p0) = ... - // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr - // on some targets but we don't need to make use of that yet. - assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); - - unsigned LabelID = Table.allocateLabelID(); - Table << MatchTable::Opcode("GIM_Try", +1) - << MatchTable::Comment("On fail goto") - << MatchTable::JumpTarget(LabelID) - << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str()) - << MatchTable::LineBreak; - - if (!RequiredFeatures.empty()) { - Table << MatchTable::Opcode("GIM_CheckFeatures") - << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures)) - << MatchTable::LineBreak; - } + if (Predicate.isNonTruncStore() || Predicate.isTruncStore()) + continue; - Matchers.front()->emitPredicateOpcodes(Table, *this); + if (Predicate.isLoad() && Predicate.getMemoryVT()) + continue; - // We must also check if it's safe to fold the matched instructions. - if (InsnVariableIDs.size() >= 2) { - // Invert the map to create stable ordering (by var names) - SmallVector InsnIDs; - for (const auto &Pair : InsnVariableIDs) { - // Skip the root node since it isn't moving anywhere. Everything else is - // sinking to meet it. - if (Pair.first == Matchers.front().get()) + if (Predicate.isLoad() || Predicate.isStore()) { + if (Predicate.isUnindexed()) continue; - - InsnIDs.push_back(Pair.second); } - llvm::sort(InsnIDs); - for (const auto &InsnID : InsnIDs) { - // Reject the difficult cases until we have a more accurate check. - Table << MatchTable::Opcode("GIM_CheckIsSafeToFold") - << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) - << MatchTable::LineBreak; + if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) { + const ListInit *AddrSpaces = Predicate.getAddressSpaces(); + if (AddrSpaces && !AddrSpaces->empty()) + continue; - // FIXME: Emit checks to determine it's _actually_ safe to fold and/or - // account for unsafe cases. - // - // Example: - // MI1--> %0 = ... - // %1 = ... %0 - // MI0--> %2 = ... %0 - // It's not safe to erase MI1. We currently handle this by not - // erasing %0 (even when it's dead). - // - // Example: - // MI1--> %0 = load volatile @a - // %1 = load volatile @a - // MI0--> %2 = ... %0 - // It's not safe to sink %0's def past %1. We currently handle - // this by rejecting all loads. - // - // Example: - // MI1--> %0 = load @a - // %1 = store @a - // MI0--> %2 = ... %0 - // It's not safe to sink %0's def past %1. We currently handle - // this by rejecting all loads. - // - // Example: - // G_CONDBR %cond, @BB1 - // BB0: - // MI1--> %0 = load @a - // G_BR @BB1 - // BB1: - // MI0--> %2 = ... %0 - // It's not always safe to sink %0 across control flow. In this - // case it may introduce a memory fault. We currentl handle this - // by rejecting all loads. + if (Predicate.getMinAlignment() > 0) + continue; } - } - - for (const auto &PM : EpilogueMatchers) - PM->emitPredicateOpcodes(Table, *this); - - for (const auto &MA : Actions) - MA->emitActionOpcodes(Table, *this); - if (Table.isWithCoverage()) - Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID) - << MatchTable::LineBreak; - else - Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str()) - << MatchTable::LineBreak; + if (Predicate.isAtomic() && Predicate.getMemoryVT()) + continue; - Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak - << MatchTable::Label(LabelID); - ++NumPatternEmitted; -} + if (Predicate.isAtomic() && + (Predicate.isAtomicOrderingMonotonic() || + Predicate.isAtomicOrderingAcquire() || + Predicate.isAtomicOrderingRelease() || + Predicate.isAtomicOrderingAcquireRelease() || + Predicate.isAtomicOrderingSequentiallyConsistent() || + Predicate.isAtomicOrderingAcquireOrStronger() || + Predicate.isAtomicOrderingWeakerThanAcquire() || + Predicate.isAtomicOrderingReleaseOrStronger() || + Predicate.isAtomicOrderingWeakerThanRelease())) + continue; -bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const { - // Rules involving more match roots have higher priority. - if (Matchers.size() > B.Matchers.size()) - return true; - if (Matchers.size() < B.Matchers.size()) - return false; + if (Predicate.hasGISelPredicateCode()) + continue; - for (auto Matcher : zip(Matchers, B.Matchers)) { - if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher))) - return true; - if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher))) - return false; + HasUnsupportedPredicate = true; + Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")"; + Separator = ", "; + Explanation += (Separator + "first-failing:" + + Predicate.getOrigPatFragRecord()->getRecord()->getName()) + .str(); + break; } - return false; -} + if (!HasUnsupportedPredicate) + return Error::success(); -unsigned RuleMatcher::countRendererFns() const { - return std::accumulate( - Matchers.begin(), Matchers.end(), 0, - [](unsigned A, const std::unique_ptr &Matcher) { - return A + Matcher->countRendererFns(); - }); + return failedImport(Explanation); } -bool OperandPredicateMatcher::isHigherPriorityThan( - const OperandPredicateMatcher &B) const { - // Generally speaking, an instruction is more important than an Int or a - // LiteralInt because it can cover more nodes but theres an exception to - // this. G_CONSTANT's are less important than either of those two because they - // are more permissive. - - const InstructionOperandMatcher *AOM = - dyn_cast(this); - const InstructionOperandMatcher *BOM = - dyn_cast(&B); - bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction(); - bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction(); - - if (AOM && BOM) { - // The relative priorities between a G_CONSTANT and any other instruction - // don't actually matter but this code is needed to ensure a strict weak - // ordering. This is particularly important on Windows where the rules will - // be incorrectly sorted without it. - if (AIsConstantInsn != BIsConstantInsn) - return AIsConstantInsn < BIsConstantInsn; - return false; +static Record *getInitValueAsRegClass(Init *V) { + if (DefInit *VDefInit = dyn_cast(V)) { + if (VDefInit->getDef()->isSubClassOf("RegisterOperand")) + return VDefInit->getDef()->getValueAsDef("RegClass"); + if (VDefInit->getDef()->isSubClassOf("RegisterClass")) + return VDefInit->getDef(); } - - if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt)) - return false; - if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt)) - return true; - - return Kind < B.Kind; + return nullptr; } -void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table, - RuleMatcher &Rule) const { - const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName); - unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher()); - assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID()); - const bool IgnoreCopies = Flags & GISF_IgnoreCopies; - Table << MatchTable::Opcode(IgnoreCopies - ? "GIM_CheckIsSameOperandIgnoreCopies" - : "GIM_CheckIsSameOperand") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("OtherMI") - << MatchTable::IntValue(OtherInsnVarID) - << MatchTable::Comment("OtherOpIdx") - << MatchTable::IntValue(OtherOM.getOpIdx()) << MatchTable::LineBreak; +static std::string getScopedName(unsigned Scope, const std::string &Name) { + return ("pred:" + Twine(Scope) + ":" + Name).str(); } //===- GlobalISelEmitter class --------------------------------------------===// @@ -3772,37 +447,6 @@ addBuiltinPredicates(const Record *SrcGIEquivOrNull, const TreePredicateFn &Predicate, InstructionMatcher &InsnMatcher, bool &HasAddedMatcher); - -public: - /// Takes a sequence of \p Rules and group them based on the predicates - /// they share. \p MatcherStorage is used as a memory container - /// for the group that are created as part of this process. - /// - /// What this optimization does looks like if GroupT = GroupMatcher: - /// Output without optimization: - /// \verbatim - /// # R1 - /// # predicate A - /// # predicate B - /// ... - /// # R2 - /// # predicate A // <-- effectively this is going to be checked twice. - /// // Once in R1 and once in R2. - /// # predicate C - /// \endverbatim - /// Output with optimization: - /// \verbatim - /// # Group1_2 - /// # predicate A // <-- Check is now shared. - /// # R1 - /// # predicate B - /// # R2 - /// # predicate C - /// \endverbatim - template - static std::vector optimizeRules( - ArrayRef Rules, - std::vector> &MatcherStorage); }; void GlobalISelEmitter::gatherOpcodeValues() { @@ -5637,56 +2281,6 @@ [](const Record *R) { return true; }); } -template -std::vector GlobalISelEmitter::optimizeRules( - ArrayRef Rules, - std::vector> &MatcherStorage) { - - std::vector OptRules; - std::unique_ptr CurrentGroup = std::make_unique(); - assert(CurrentGroup->empty() && "Newly created group isn't empty!"); - unsigned NumGroups = 0; - - auto ProcessCurrentGroup = [&]() { - if (CurrentGroup->empty()) - // An empty group is good to be reused: - return; - - // If the group isn't large enough to provide any benefit, move all the - // added rules out of it and make sure to re-create the group to properly - // re-initialize it: - if (CurrentGroup->size() < 2) - append_range(OptRules, CurrentGroup->matchers()); - else { - CurrentGroup->finalize(); - OptRules.push_back(CurrentGroup.get()); - MatcherStorage.emplace_back(std::move(CurrentGroup)); - ++NumGroups; - } - CurrentGroup = std::make_unique(); - }; - for (Matcher *Rule : Rules) { - // Greedily add as many matchers as possible to the current group: - if (CurrentGroup->addMatcher(*Rule)) - continue; - - ProcessCurrentGroup(); - assert(CurrentGroup->empty() && "A group wasn't properly re-initialized"); - - // Try to add the pending matcher to a newly created empty group: - if (!CurrentGroup->addMatcher(*Rule)) - // If we couldn't add the matcher to an empty group, that group type - // doesn't support that kind of matchers at all, so just skip it: - OptRules.push_back(Rule); - } - ProcessCurrentGroup(); - - LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n"); - (void) NumGroups; - assert(CurrentGroup->empty() && "The last group wasn't properly processed"); - return OptRules; -} - MatchTable GlobalISelEmitter::buildMatchTable(MutableArrayRef Rules, bool Optimize, bool WithCoverage) { @@ -5729,34 +2323,6 @@ return MatchTable::buildTable(OptRules, WithCoverage); } -void GroupMatcher::optimize() { - // Make sure we only sort by a specific predicate within a range of rules that - // all have that predicate checked against a specific value (not a wildcard): - auto F = Matchers.begin(); - auto T = F; - auto E = Matchers.end(); - while (T != E) { - while (T != E) { - auto *R = static_cast(*T); - if (!R->getFirstConditionAsRootType().get().isValid()) - break; - ++T; - } - std::stable_sort(F, T, [](Matcher *A, Matcher *B) { - auto *L = static_cast(A); - auto *R = static_cast(B); - return L->getFirstConditionAsRootType() < - R->getFirstConditionAsRootType(); - }); - if (T != E) - F = ++T; - } - GlobalISelEmitter::optimizeRules(Matchers, MatcherStorage) - .swap(Matchers); - GlobalISelEmitter::optimizeRules(Matchers, MatcherStorage) - .swap(Matchers); -} - void GlobalISelEmitter::run(raw_ostream &OS) { if (!UseCoverageFile.empty()) { RuleCoverage = CodeGenCoverage(); @@ -6101,288 +2667,6 @@ Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size())); } -void RuleMatcher::optimize() { - for (auto &Item : InsnVariableIDs) { - InstructionMatcher &InsnMatcher = *Item.first; - for (auto &OM : InsnMatcher.operands()) { - // Complex Patterns are usually expensive and they relatively rarely fail - // on their own: more often we end up throwing away all the work done by a - // matching part of a complex pattern because some other part of the - // enclosing pattern didn't match. All of this makes it beneficial to - // delay complex patterns until the very end of the rule matching, - // especially for targets having lots of complex patterns. - for (auto &OP : OM->predicates()) - if (isa(OP)) - EpilogueMatchers.emplace_back(std::move(OP)); - OM->eraseNullPredicates(); - } - InsnMatcher.optimize(); - } - llvm::sort(EpilogueMatchers, [](const std::unique_ptr &L, - const std::unique_ptr &R) { - return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) < - std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx()); - }); -} - -bool RuleMatcher::hasFirstCondition() const { - if (insnmatchers_empty()) - return false; - InstructionMatcher &Matcher = insnmatchers_front(); - if (!Matcher.predicates_empty()) - return true; - for (auto &OM : Matcher.operands()) - for (auto &OP : OM->predicates()) - if (!isa(OP)) - return true; - return false; -} - -const PredicateMatcher &RuleMatcher::getFirstCondition() const { - assert(!insnmatchers_empty() && - "Trying to get a condition from an empty RuleMatcher"); - - InstructionMatcher &Matcher = insnmatchers_front(); - if (!Matcher.predicates_empty()) - return **Matcher.predicates_begin(); - // If there is no more predicate on the instruction itself, look at its - // operands. - for (auto &OM : Matcher.operands()) - for (auto &OP : OM->predicates()) - if (!isa(OP)) - return *OP; - - llvm_unreachable("Trying to get a condition from an InstructionMatcher with " - "no conditions"); -} - -std::unique_ptr RuleMatcher::popFirstCondition() { - assert(!insnmatchers_empty() && - "Trying to pop a condition from an empty RuleMatcher"); - - InstructionMatcher &Matcher = insnmatchers_front(); - if (!Matcher.predicates_empty()) - return Matcher.predicates_pop_front(); - // If there is no more predicate on the instruction itself, look at its - // operands. - for (auto &OM : Matcher.operands()) - for (auto &OP : OM->predicates()) - if (!isa(OP)) { - std::unique_ptr Result = std::move(OP); - OM->eraseNullPredicates(); - return Result; - } - - llvm_unreachable("Trying to pop a condition from an InstructionMatcher with " - "no conditions"); -} - -bool GroupMatcher::candidateConditionMatches( - const PredicateMatcher &Predicate) const { - - if (empty()) { - // Sharing predicates for nested instructions is not supported yet as we - // currently don't hoist the GIM_RecordInsn's properly, therefore we can - // only work on the original root instruction (InsnVarID == 0): - if (Predicate.getInsnVarID() != 0) - return false; - // ... otherwise an empty group can handle any predicate with no specific - // requirements: - return true; - } - - const Matcher &Representative = **Matchers.begin(); - const auto &RepresentativeCondition = Representative.getFirstCondition(); - // ... if not empty, the group can only accomodate matchers with the exact - // same first condition: - return Predicate.isIdentical(RepresentativeCondition); -} - -bool GroupMatcher::addMatcher(Matcher &Candidate) { - if (!Candidate.hasFirstCondition()) - return false; - - const PredicateMatcher &Predicate = Candidate.getFirstCondition(); - if (!candidateConditionMatches(Predicate)) - return false; - - Matchers.push_back(&Candidate); - return true; -} - -void GroupMatcher::finalize() { - assert(Conditions.empty() && "Already finalized?"); - if (empty()) - return; - - Matcher &FirstRule = **Matchers.begin(); - for (;;) { - // All the checks are expected to succeed during the first iteration: - for (const auto &Rule : Matchers) - if (!Rule->hasFirstCondition()) - return; - const auto &FirstCondition = FirstRule.getFirstCondition(); - for (unsigned I = 1, E = Matchers.size(); I < E; ++I) - if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition)) - return; - - Conditions.push_back(FirstRule.popFirstCondition()); - for (unsigned I = 1, E = Matchers.size(); I < E; ++I) - Matchers[I]->popFirstCondition(); - } -} - -void GroupMatcher::emit(MatchTable &Table) { - unsigned LabelID = ~0U; - if (!Conditions.empty()) { - LabelID = Table.allocateLabelID(); - Table << MatchTable::Opcode("GIM_Try", +1) - << MatchTable::Comment("On fail goto") - << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak; - } - for (auto &Condition : Conditions) - Condition->emitPredicateOpcodes( - Table, *static_cast(*Matchers.begin())); - - for (const auto &M : Matchers) - M->emit(Table); - - // Exit the group - if (!Conditions.empty()) - Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak - << MatchTable::Label(LabelID); -} - -bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) { - return isa(P) || isa(P); -} - -bool SwitchMatcher::candidateConditionMatches( - const PredicateMatcher &Predicate) const { - - if (empty()) { - // Sharing predicates for nested instructions is not supported yet as we - // currently don't hoist the GIM_RecordInsn's properly, therefore we can - // only work on the original root instruction (InsnVarID == 0): - if (Predicate.getInsnVarID() != 0) - return false; - // ... while an attempt to add even a root matcher to an empty SwitchMatcher - // could fail as not all the types of conditions are supported: - if (!isSupportedPredicateType(Predicate)) - return false; - // ... or the condition might not have a proper implementation of - // getValue() / isIdenticalDownToValue() yet: - if (!Predicate.hasValue()) - return false; - // ... otherwise an empty Switch can accomodate the condition with no - // further requirements: - return true; - } - - const Matcher &CaseRepresentative = **Matchers.begin(); - const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition(); - // Switch-cases must share the same kind of condition and path to the value it - // checks: - if (!Predicate.isIdenticalDownToValue(RepresentativeCondition)) - return false; - - const auto Value = Predicate.getValue(); - // ... but be unique with respect to the actual value they check: - return Values.count(Value) == 0; -} - -bool SwitchMatcher::addMatcher(Matcher &Candidate) { - if (!Candidate.hasFirstCondition()) - return false; - - const PredicateMatcher &Predicate = Candidate.getFirstCondition(); - if (!candidateConditionMatches(Predicate)) - return false; - const auto Value = Predicate.getValue(); - Values.insert(Value); - - Matchers.push_back(&Candidate); - return true; -} - -void SwitchMatcher::finalize() { - assert(Condition == nullptr && "Already finalized"); - assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); - if (empty()) - return; - - llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) { - return L->getFirstCondition().getValue() < - R->getFirstCondition().getValue(); - }); - Condition = Matchers[0]->popFirstCondition(); - for (unsigned I = 1, E = Values.size(); I < E; ++I) - Matchers[I]->popFirstCondition(); -} - -void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P, - MatchTable &Table) { - assert(isSupportedPredicateType(P) && "Predicate type is not supported"); - - if (const auto *Condition = dyn_cast(&P)) { - Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI") - << MatchTable::IntValue(Condition->getInsnVarID()); - return; - } - if (const auto *Condition = dyn_cast(&P)) { - Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI") - << MatchTable::IntValue(Condition->getInsnVarID()) - << MatchTable::Comment("Op") - << MatchTable::IntValue(Condition->getOpIdx()); - return; - } - - llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a " - "predicate type that is claimed to be supported"); -} - -void SwitchMatcher::emit(MatchTable &Table) { - assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); - if (empty()) - return; - assert(Condition != nullptr && - "Broken SwitchMatcher, hasn't been finalized?"); - - std::vector LabelIDs(Values.size()); - std::generate(LabelIDs.begin(), LabelIDs.end(), - [&Table]() { return Table.allocateLabelID(); }); - const unsigned Default = Table.allocateLabelID(); - - const int64_t LowerBound = Values.begin()->getRawValue(); - const int64_t UpperBound = Values.rbegin()->getRawValue() + 1; - - emitPredicateSpecificOpcodes(*Condition, Table); - - Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound) - << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")") - << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default); - - int64_t J = LowerBound; - auto VI = Values.begin(); - for (unsigned I = 0, E = Values.size(); I < E; ++I) { - auto V = *VI++; - while (J++ < V.getRawValue()) - Table << MatchTable::IntValue(0); - V.turnIntoComment(); - Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]); - } - Table << MatchTable::LineBreak; - - for (unsigned I = 0, E = Values.size(); I < E; ++I) { - Table << MatchTable::Label(LabelIDs[I]); - Matchers[I]->emit(Table); - Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; - } - Table << MatchTable::Label(Default); -} - -unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); } - } // end anonymous namespace //===----------------------------------------------------------------------===// diff --git a/llvm/utils/TableGen/GlobalISelMatchTable.h b/llvm/utils/TableGen/GlobalISelMatchTable.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISelMatchTable.h @@ -0,0 +1,2141 @@ +//===- GlobalISelMatchTable.h ---------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +/// \file +/// This file contains the code related to the GlobalISel Match Table emitted by +/// GlobalISelEmitter.cpp. The generated match table is interpreted at runtime +/// by `InstructionSelectorImpl.h` to match & apply ISel patterns. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H +#define LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H + +#include "CodeGenDAGPatterns.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/CodeGen/LowLevelType.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/SaveAndRestore.h" +#include +#include +#include +#include +#include +#include +#include +#include + +namespace llvm { + +class raw_ostream; +class Record; +class SMLoc; +class CodeGenRegisterClass; + +// Use a namespace to avoid conflicts because there's some fairly generic names +// in there (e.g. Matcher). +namespace gi { +class MatchTable; +class Matcher; +class OperandMatcher; +class MatchAction; +class PredicateMatcher; +class InstructionMatcher; + +enum { + GISF_IgnoreCopies = 0x1, +}; + +using GISelFlags = std::uint16_t; + +//===- Helper functions ---------------------------------------------------===// + +std::string getNameForFeatureBitset(const std::vector &FeatureBitset); + +/// Takes a sequence of \p Rules and group them based on the predicates +/// they share. \p MatcherStorage is used as a memory container +/// for the group that are created as part of this process. +/// +/// What this optimization does looks like if GroupT = GroupMatcher: +/// Output without optimization: +/// \verbatim +/// # R1 +/// # predicate A +/// # predicate B +/// ... +/// # R2 +/// # predicate A // <-- effectively this is going to be checked twice. +/// // Once in R1 and once in R2. +/// # predicate C +/// \endverbatim +/// Output with optimization: +/// \verbatim +/// # Group1_2 +/// # predicate A // <-- Check is now shared. +/// # R1 +/// # predicate B +/// # R2 +/// # predicate C +/// \endverbatim +template +std::vector +optimizeRules(ArrayRef Rules, + std::vector> &MatcherStorage); + +/// A record to be stored in a MatchTable. +/// +/// This class represents any and all output that may be required to emit the +/// MatchTable. Instances are most often configured to represent an opcode or +/// value that will be emitted to the table with some formatting but it can also +/// represent commas, comments, and other formatting instructions. +struct MatchTableRecord { + enum RecordFlagsBits { + MTRF_None = 0x0, + /// Causes EmitStr to be formatted as comment when emitted. + MTRF_Comment = 0x1, + /// Causes the record value to be followed by a comma when emitted. + MTRF_CommaFollows = 0x2, + /// Causes the record value to be followed by a line break when emitted. + MTRF_LineBreakFollows = 0x4, + /// Indicates that the record defines a label and causes an additional + /// comment to be emitted containing the index of the label. + MTRF_Label = 0x8, + /// Causes the record to be emitted as the index of the label specified by + /// LabelID along with a comment indicating where that label is. + MTRF_JumpTarget = 0x10, + /// Causes the formatter to add a level of indentation before emitting the + /// record. + MTRF_Indent = 0x20, + /// Causes the formatter to remove a level of indentation after emitting the + /// record. + MTRF_Outdent = 0x40, + }; + + /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to + /// reference or define. + unsigned LabelID; + /// The string to emit. Depending on the MTRF_* flags it may be a comment, a + /// value, a label name. + std::string EmitStr; + +private: + /// The number of MatchTable elements described by this record. Comments are 0 + /// while values are typically 1. Values >1 may occur when we need to emit + /// values that exceed the size of a MatchTable element. + unsigned NumElements; + +public: + /// A bitfield of RecordFlagsBits flags. + unsigned Flags; + + /// The actual run-time value, if known + int64_t RawValue; + + MatchTableRecord(std::optional LabelID_, StringRef EmitStr, + unsigned NumElements, unsigned Flags, + int64_t RawValue = std::numeric_limits::min()) + : LabelID(LabelID_.value_or(~0u)), EmitStr(EmitStr), + NumElements(NumElements), Flags(Flags), RawValue(RawValue) { + assert((!LabelID_ || LabelID != ~0u) && + "This value is reserved for non-labels"); + } + MatchTableRecord(const MatchTableRecord &Other) = default; + MatchTableRecord(MatchTableRecord &&Other) = default; + + /// Useful if a Match Table Record gets optimized out + void turnIntoComment() { + Flags |= MTRF_Comment; + Flags &= ~MTRF_CommaFollows; + NumElements = 0; + } + + /// For Jump Table generation purposes + bool operator<(const MatchTableRecord &Other) const { + return RawValue < Other.RawValue; + } + int64_t getRawValue() const { return RawValue; } + + void emit(raw_ostream &OS, bool LineBreakNextAfterThis, + const MatchTable &Table) const; + unsigned size() const { return NumElements; } +}; + +/// Holds the contents of a generated MatchTable to enable formatting and the +/// necessary index tracking needed to support GIM_Try. +class MatchTable { + /// An unique identifier for the table. The generated table will be named + /// MatchTable${ID}. + unsigned ID; + /// The records that make up the table. Also includes comments describing the + /// values being emitted and line breaks to format it. + std::vector Contents; + /// The currently defined labels. + DenseMap LabelMap; + /// Tracks the sum of MatchTableRecord::NumElements as the table is built. + unsigned CurrentSize = 0; + /// A unique identifier for a MatchTable label. + unsigned CurrentLabelID = 0; + /// Determines if the table should be instrumented for rule coverage tracking. + bool IsWithCoverage; + +public: + static MatchTableRecord LineBreak; + static MatchTableRecord Comment(StringRef Comment); + static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0); + static MatchTableRecord NamedValue(StringRef NamedValue); + static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue); + static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue); + static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue, + int64_t RawValue); + static MatchTableRecord IntValue(int64_t IntValue); + static MatchTableRecord Label(unsigned LabelID); + static MatchTableRecord JumpTarget(unsigned LabelID); + + static MatchTable buildTable(ArrayRef Rules, bool WithCoverage); + + MatchTable(bool WithCoverage, unsigned ID = 0) + : ID(ID), IsWithCoverage(WithCoverage) {} + + bool isWithCoverage() const { return IsWithCoverage; } + + void push_back(const MatchTableRecord &Value) { + if (Value.Flags & MatchTableRecord::MTRF_Label) + defineLabel(Value.LabelID); + Contents.push_back(Value); + CurrentSize += Value.size(); + } + + unsigned allocateLabelID() { return CurrentLabelID++; } + + void defineLabel(unsigned LabelID) { + LabelMap.insert(std::make_pair(LabelID, CurrentSize)); + } + + unsigned getLabelIndex(unsigned LabelID) const { + const auto I = LabelMap.find(LabelID); + assert(I != LabelMap.end() && "Use of undeclared label"); + return I->second; + } + + void emitUse(raw_ostream &OS) const; + void emitDeclaration(raw_ostream &OS) const; +}; + +inline MatchTable &operator<<(MatchTable &Table, + const MatchTableRecord &Value) { + Table.push_back(Value); + return Table; +} + +/// This class stands in for LLT wherever we want to tablegen-erate an +/// equivalent at compiler run-time. +class LLTCodeGen { +private: + LLT Ty; + +public: + LLTCodeGen() = default; + LLTCodeGen(const LLT &Ty) : Ty(Ty) {} + + std::string getCxxEnumValue() const; + + void emitCxxEnumValue(raw_ostream &OS) const; + void emitCxxConstructorCall(raw_ostream &OS) const; + + const LLT &get() const { return Ty; } + + /// This ordering is used for std::unique() and llvm::sort(). There's no + /// particular logic behind the order but either A < B or B < A must be + /// true if A != B. + bool operator<(const LLTCodeGen &Other) const; + bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; } +}; + +// Track all types that are used so we can emit the corresponding enum. +extern std::set KnownTypes; + +/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for +/// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...). +std::optional MVTToLLT(MVT::SimpleValueType SVT); + +//===- Matchers -----------------------------------------------------------===// +class Matcher { +public: + virtual ~Matcher(); + virtual void optimize(); + virtual void emit(MatchTable &Table) = 0; + + virtual bool hasFirstCondition() const = 0; + virtual const PredicateMatcher &getFirstCondition() const = 0; + virtual std::unique_ptr popFirstCondition() = 0; +}; + +class GroupMatcher final : public Matcher { + /// Conditions that form a common prefix of all the matchers contained. + SmallVector, 1> Conditions; + + /// All the nested matchers, sharing a common prefix. + std::vector Matchers; + + /// An owning collection for any auxiliary matchers created while optimizing + /// nested matchers contained. + std::vector> MatcherStorage; + +public: + /// Add a matcher to the collection of nested matchers if it meets the + /// requirements, and return true. If it doesn't, do nothing and return false. + /// + /// Expected to preserve its argument, so it could be moved out later on. + bool addMatcher(Matcher &Candidate); + + /// Mark the matcher as fully-built and ensure any invariants expected by both + /// optimize() and emit(...) methods. Generally, both sequences of calls + /// are expected to lead to a sensible result: + /// + /// addMatcher(...)*; finalize(); optimize(); emit(...); and + /// addMatcher(...)*; finalize(); emit(...); + /// + /// or generally + /// + /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }* + /// + /// Multiple calls to optimize() are expected to be handled gracefully, though + /// optimize() is not expected to be idempotent. Multiple calls to finalize() + /// aren't generally supported. emit(...) is expected to be non-mutating and + /// producing the exact same results upon repeated calls. + /// + /// addMatcher() calls after the finalize() call are not supported. + /// + /// finalize() and optimize() are both allowed to mutate the contained + /// matchers, so moving them out after finalize() is not supported. + void finalize(); + void optimize() override; + void emit(MatchTable &Table) override; + + /// Could be used to move out the matchers added previously, unless finalize() + /// has been already called. If any of the matchers are moved out, the group + /// becomes safe to destroy, but not safe to re-use for anything else. + iterator_range::iterator> matchers() { + return make_range(Matchers.begin(), Matchers.end()); + } + size_t size() const { return Matchers.size(); } + bool empty() const { return Matchers.empty(); } + + std::unique_ptr popFirstCondition() override { + assert(!Conditions.empty() && + "Trying to pop a condition from a condition-less group"); + std::unique_ptr P = std::move(Conditions.front()); + Conditions.erase(Conditions.begin()); + return P; + } + const PredicateMatcher &getFirstCondition() const override { + assert(!Conditions.empty() && + "Trying to get a condition from a condition-less group"); + return *Conditions.front(); + } + bool hasFirstCondition() const override { return !Conditions.empty(); } + +private: + /// See if a candidate matcher could be added to this group solely by + /// analyzing its first condition. + bool candidateConditionMatches(const PredicateMatcher &Predicate) const; +}; + +class SwitchMatcher : public Matcher { + /// All the nested matchers, representing distinct switch-cases. The first + /// conditions (as Matcher::getFirstCondition() reports) of all the nested + /// matchers must share the same type and path to a value they check, in other + /// words, be isIdenticalDownToValue, but have different values they check + /// against. + std::vector Matchers; + + /// The representative condition, with a type and a path (InsnVarID and OpIdx + /// in most cases) shared by all the matchers contained. + std::unique_ptr Condition = nullptr; + + /// Temporary set used to check that the case values don't repeat within the + /// same switch. + std::set Values; + + /// An owning collection for any auxiliary matchers created while optimizing + /// nested matchers contained. + std::vector> MatcherStorage; + +public: + bool addMatcher(Matcher &Candidate); + + void finalize(); + void emit(MatchTable &Table) override; + + iterator_range::iterator> matchers() { + return make_range(Matchers.begin(), Matchers.end()); + } + size_t size() const { return Matchers.size(); } + bool empty() const { return Matchers.empty(); } + + std::unique_ptr popFirstCondition() override { + // SwitchMatcher doesn't have a common first condition for its cases, as all + // the cases only share a kind of a value (a type and a path to it) they + // match, but deliberately differ in the actual value they match. + llvm_unreachable("Trying to pop a condition from a condition-less group"); + } + + const PredicateMatcher &getFirstCondition() const override { + llvm_unreachable("Trying to pop a condition from a condition-less group"); + } + + bool hasFirstCondition() const override { return false; } + +private: + /// See if the predicate type has a Switch-implementation for it. + static bool isSupportedPredicateType(const PredicateMatcher &Predicate); + + bool candidateConditionMatches(const PredicateMatcher &Predicate) const; + + /// emit()-helper + static void emitPredicateSpecificOpcodes(const PredicateMatcher &P, + MatchTable &Table); +}; + +/// Generates code to check that a match rule matches. +class RuleMatcher : public Matcher { +public: + using ActionList = std::list>; + using action_iterator = ActionList::iterator; + +protected: + /// A list of matchers that all need to succeed for the current rule to match. + /// FIXME: This currently supports a single match position but could be + /// extended to support multiple positions to support div/rem fusion or + /// load-multiple instructions. + using MatchersTy = std::vector>; + MatchersTy Matchers; + + /// A list of actions that need to be taken when all predicates in this rule + /// have succeeded. + ActionList Actions; + + using DefinedInsnVariablesMap = std::map; + + /// A map of instruction matchers to the local variables + DefinedInsnVariablesMap InsnVariableIDs; + + using MutatableInsnSet = SmallPtrSet; + + // The set of instruction matchers that have not yet been claimed for mutation + // by a BuildMI. + MutatableInsnSet MutatableInsns; + + /// A map of named operands defined by the matchers that may be referenced by + /// the renderers. + StringMap DefinedOperands; + + /// A map of anonymous physical register operands defined by the matchers that + /// may be referenced by the renderers. + DenseMap PhysRegOperands; + + /// ID for the next instruction variable defined with + /// implicitlyDefineInsnVar() + unsigned NextInsnVarID; + + /// ID for the next output instruction allocated with allocateOutputInsnID() + unsigned NextOutputInsnID; + + /// ID for the next temporary register ID allocated with allocateTempRegID() + unsigned NextTempRegID; + + /// Current GISelFlags + GISelFlags Flags = 0; + + std::vector RequiredFeatures; + std::vector> EpilogueMatchers; + + ArrayRef SrcLoc; + + typedef std::tuple + DefinedComplexPatternSubOperand; + typedef StringMap + DefinedComplexPatternSubOperandMap; + /// A map of Symbolic Names to ComplexPattern sub-operands. + DefinedComplexPatternSubOperandMap ComplexSubOperands; + /// A map used to for multiple referenced error check of ComplexSubOperand. + /// ComplexSubOperand can't be referenced multiple from different operands, + /// however multiple references from same operand are allowed since that is + /// how 'same operand checks' are generated. + StringMap ComplexSubOperandsParentName; + + uint64_t RuleID; + static uint64_t NextRuleID; + + GISelFlags updateGISelFlag(GISelFlags CurFlags, const Record *R, + StringRef FlagName, GISelFlags FlagBit); + +public: + RuleMatcher(ArrayRef SrcLoc) + : NextInsnVarID(0), NextOutputInsnID(0), NextTempRegID(0), SrcLoc(SrcLoc), + RuleID(NextRuleID++) {} + RuleMatcher(RuleMatcher &&Other) = default; + RuleMatcher &operator=(RuleMatcher &&Other) = default; + + uint64_t getRuleID() const { return RuleID; } + + InstructionMatcher &addInstructionMatcher(StringRef SymbolicName); + void addRequiredFeature(Record *Feature); + const std::vector &getRequiredFeatures() const; + + // Emplaces an action of the specified Kind at the end of the action list. + // + // Returns a reference to the newly created action. + // + // Like std::vector::emplace_back(), may invalidate all iterators if the new + // size exceeds the capacity. Otherwise, only invalidates the past-the-end + // iterator. + template Kind &addAction(Args &&...args) { + Actions.emplace_back(std::make_unique(std::forward(args)...)); + return *static_cast(Actions.back().get()); + } + + // Emplaces an action of the specified Kind before the given insertion point. + // + // Returns an iterator pointing at the newly created instruction. + // + // Like std::vector::insert(), may invalidate all iterators if the new size + // exceeds the capacity. Otherwise, only invalidates the iterators from the + // insertion point onwards. + template + action_iterator insertAction(action_iterator InsertPt, Args &&...args) { + return Actions.emplace(InsertPt, + std::make_unique(std::forward(args)...)); + } + + // Update the active GISelFlags based on the GISelFlags Record R. + // A SaveAndRestore object is returned so the old GISelFlags are restored + // at the end of the scope. + SaveAndRestore setGISelFlags(const Record *R); + GISelFlags getGISelFlags() const { return Flags; } + + /// Define an instruction without emitting any code to do so. + unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher); + + unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const; + DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const { + return InsnVariableIDs.begin(); + } + DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const { + return InsnVariableIDs.end(); + } + iterator_range + defined_insn_vars() const { + return make_range(defined_insn_vars_begin(), defined_insn_vars_end()); + } + + MutatableInsnSet::const_iterator mutatable_insns_begin() const { + return MutatableInsns.begin(); + } + MutatableInsnSet::const_iterator mutatable_insns_end() const { + return MutatableInsns.end(); + } + iterator_range + mutatable_insns() const { + return make_range(mutatable_insns_begin(), mutatable_insns_end()); + } + void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) { + bool R = MutatableInsns.erase(InsnMatcher); + assert(R && "Reserving a mutatable insn that isn't available"); + (void)R; + } + + action_iterator actions_begin() { return Actions.begin(); } + action_iterator actions_end() { return Actions.end(); } + iterator_range actions() { + return make_range(actions_begin(), actions_end()); + } + + void defineOperand(StringRef SymbolicName, OperandMatcher &OM); + + void definePhysRegOperand(Record *Reg, OperandMatcher &OM); + + Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern, + unsigned RendererID, unsigned SubOperandID, + StringRef ParentSymbolicName); + + std::optional + getComplexSubOperand(StringRef SymbolicName) const { + const auto &I = ComplexSubOperands.find(SymbolicName); + if (I == ComplexSubOperands.end()) + return std::nullopt; + return I->second; + } + + InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const; + const OperandMatcher &getOperandMatcher(StringRef Name) const; + const OperandMatcher &getPhysRegOperandMatcher(Record *) const; + + void optimize() override; + void emit(MatchTable &Table) override; + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(const RuleMatcher &B) const; + + /// Report the maximum number of temporary operands needed by the rule + /// matcher. + unsigned countRendererFns() const; + + std::unique_ptr popFirstCondition() override; + const PredicateMatcher &getFirstCondition() const override; + LLTCodeGen getFirstConditionAsRootType(); + bool hasFirstCondition() const override; + unsigned getNumOperands() const; + StringRef getOpcode() const; + + // FIXME: Remove this as soon as possible + InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); } + + unsigned allocateOutputInsnID() { return NextOutputInsnID++; } + unsigned allocateTempRegID() { return NextTempRegID++; } + + iterator_range insnmatchers() { + return make_range(Matchers.begin(), Matchers.end()); + } + bool insnmatchers_empty() const { return Matchers.empty(); } + void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); } +}; + +template class PredicateListMatcher { +private: + /// Template instantiations should specialize this to return a string to use + /// for the comment emitted when there are no predicates. + std::string getNoPredicateComment() const; + +protected: + using PredicatesTy = std::deque>; + PredicatesTy Predicates; + + /// Track if the list of predicates was manipulated by one of the optimization + /// methods. + bool Optimized = false; + +public: + typename PredicatesTy::iterator predicates_begin() { + return Predicates.begin(); + } + typename PredicatesTy::iterator predicates_end() { return Predicates.end(); } + iterator_range predicates() { + return make_range(predicates_begin(), predicates_end()); + } + typename PredicatesTy::size_type predicates_size() const { + return Predicates.size(); + } + bool predicates_empty() const { return Predicates.empty(); } + + std::unique_ptr predicates_pop_front() { + std::unique_ptr Front = std::move(Predicates.front()); + Predicates.pop_front(); + Optimized = true; + return Front; + } + + void prependPredicate(std::unique_ptr &&Predicate) { + Predicates.push_front(std::move(Predicate)); + } + + void eraseNullPredicates() { + const auto NewEnd = + std::stable_partition(Predicates.begin(), Predicates.end(), + std::logical_not>()); + if (NewEnd != Predicates.begin()) { + Predicates.erase(Predicates.begin(), NewEnd); + Optimized = true; + } + } + + /// Emit MatchTable opcodes that tests whether all the predicates are met. + template + void emitPredicateListOpcodes(MatchTable &Table, Args &&...args) { + if (Predicates.empty() && !Optimized) { + Table << MatchTable::Comment(getNoPredicateComment()) + << MatchTable::LineBreak; + return; + } + + for (const auto &Predicate : predicates()) + Predicate->emitPredicateOpcodes(Table, std::forward(args)...); + } + + /// Provide a function to avoid emitting certain predicates. This is used to + /// defer some predicate checks until after others + using PredicateFilterFunc = std::function; + + /// Emit MatchTable opcodes for predicates which satisfy \p + /// ShouldEmitPredicate. This should be called multiple times to ensure all + /// predicates are eventually added to the match table. + template + void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate, + MatchTable &Table, Args &&...args) { + if (Predicates.empty() && !Optimized) { + Table << MatchTable::Comment(getNoPredicateComment()) + << MatchTable::LineBreak; + return; + } + + for (const auto &Predicate : predicates()) { + if (ShouldEmitPredicate(*Predicate)) + Predicate->emitPredicateOpcodes(Table, std::forward(args)...); + } + } +}; + +class PredicateMatcher { +public: + /// This enum is used for RTTI and also defines the priority that is given to + /// the predicate when generating the matcher code. Kinds with higher priority + /// must be tested first. + /// + /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter + /// but OPM_Int must have priority over OPM_RegBank since constant integers + /// are represented by a virtual register defined by a G_CONSTANT instruction. + /// + /// Note: The relative priority between IPM_ and OPM_ does not matter, they + /// are currently not compared between each other. + enum PredicateKind { + IPM_Opcode, + IPM_NumOperands, + IPM_ImmPredicate, + IPM_Imm, + IPM_AtomicOrderingMMO, + IPM_MemoryLLTSize, + IPM_MemoryVsLLTSize, + IPM_MemoryAddressSpace, + IPM_MemoryAlignment, + IPM_VectorSplatImm, + IPM_NoUse, + IPM_GenericPredicate, + OPM_SameOperand, + OPM_ComplexPattern, + OPM_IntrinsicID, + OPM_CmpPredicate, + OPM_Instruction, + OPM_Int, + OPM_LiteralInt, + OPM_LLT, + OPM_PointerToAny, + OPM_RegBank, + OPM_MBB, + OPM_RecordNamedOperand, + }; + +protected: + PredicateKind Kind; + unsigned InsnVarID; + unsigned OpIdx; + +public: + PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0) + : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {} + virtual ~PredicateMatcher(); + + unsigned getInsnVarID() const { return InsnVarID; } + unsigned getOpIdx() const { return OpIdx; } + + /// Emit MatchTable opcodes that check the predicate for the given operand. + virtual void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const = 0; + + PredicateKind getKind() const { return Kind; } + + bool dependsOnOperands() const { + // Custom predicates really depend on the context pattern of the + // instruction, not just the individual instruction. This therefore + // implicitly depends on all other pattern constraints. + return Kind == IPM_GenericPredicate; + } + + virtual bool isIdentical(const PredicateMatcher &B) const { + return B.getKind() == getKind() && InsnVarID == B.InsnVarID && + OpIdx == B.OpIdx; + } + + virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const { + return hasValue() && PredicateMatcher::isIdentical(B); + } + + virtual MatchTableRecord getValue() const { + assert(hasValue() && "Can not get a value of a value-less predicate!"); + llvm_unreachable("Not implemented yet"); + } + virtual bool hasValue() const { return false; } + + /// Report the maximum number of temporary operands needed by the predicate + /// matcher. + virtual unsigned countRendererFns() const { return 0; } +}; + +/// Generates code to check a predicate of an operand. +/// +/// Typical predicates include: +/// * Operand is a particular register. +/// * Operand is assigned a particular register bank. +/// * Operand is an MBB. +class OperandPredicateMatcher : public PredicateMatcher { +public: + OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID, + unsigned OpIdx) + : PredicateMatcher(Kind, InsnVarID, OpIdx) {} + virtual ~OperandPredicateMatcher(); + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const; +}; + +template <> +inline std::string +PredicateListMatcher::getNoPredicateComment() const { + return "No operand predicates"; +} + +/// Generates code to check that a register operand is defined by the same exact +/// one as another. +class SameOperandMatcher : public OperandPredicateMatcher { + std::string MatchingName; + unsigned OrigOpIdx; + + GISelFlags Flags; + +public: + SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName, + unsigned OrigOpIdx, GISelFlags Flags) + : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx), + MatchingName(MatchingName), OrigOpIdx(OrigOpIdx), Flags(Flags) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_SameOperand; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + OrigOpIdx == cast(&B)->OrigOpIdx && + MatchingName == cast(&B)->MatchingName; + } +}; + +/// Generates code to check that an operand is a particular LLT. +class LLTOperandMatcher : public OperandPredicateMatcher { +protected: + LLTCodeGen Ty; + +public: + static std::map TypeIDValues; + + static void initTypeIDValuesMap() { + TypeIDValues.clear(); + + unsigned ID = 0; + for (const LLTCodeGen &LLTy : KnownTypes) + TypeIDValues[LLTy] = ID++; + } + + LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty) + : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) { + KnownTypes.insert(Ty); + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_LLT; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + Ty == cast(&B)->Ty; + } + + MatchTableRecord getValue() const override; + bool hasValue() const override; + + LLTCodeGen getTy() const { return Ty; } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is a pointer to any address space. +/// +/// In SelectionDAG, the types did not describe pointers or address spaces. As a +/// result, iN is used to describe a pointer of N bits to any address space and +/// PatFrag predicates are typically used to constrain the address space. +/// There's no reliable means to derive the missing type information from the +/// pattern so imported rules must test the components of a pointer separately. +/// +/// If SizeInBits is zero, then the pointer size will be obtained from the +/// subtarget. +class PointerToAnyOperandMatcher : public OperandPredicateMatcher { +protected: + unsigned SizeInBits; + +public: + PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + unsigned SizeInBits) + : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx), + SizeInBits(SizeInBits) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_PointerToAny; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + SizeInBits == cast(&B)->SizeInBits; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to record named operand in RecordedOperands list at StoreIdx. +/// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as +/// an argument to predicate's c++ code once all operands have been matched. +class RecordNamedOperandMatcher : public OperandPredicateMatcher { +protected: + unsigned StoreIdx; + std::string Name; + +public: + RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + unsigned StoreIdx, StringRef Name) + : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx), + StoreIdx(StoreIdx), Name(Name) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_RecordNamedOperand; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + StoreIdx == cast(&B)->StoreIdx && + Name == cast(&B)->Name; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is a particular target constant. +class ComplexPatternOperandMatcher : public OperandPredicateMatcher { +protected: + const OperandMatcher &Operand; + const Record &TheDef; + + unsigned getAllocatedTemporariesBaseID() const; + +public: + bool isIdentical(const PredicateMatcher &B) const override { return false; } + + ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + const OperandMatcher &Operand, + const Record &TheDef) + : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx), + Operand(Operand), TheDef(TheDef) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_ComplexPattern; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; + unsigned countRendererFns() const override { return 1; } +}; + +/// Generates code to check that an operand is in a particular register bank. +class RegisterBankOperandMatcher : public OperandPredicateMatcher { +protected: + const CodeGenRegisterClass &RC; + +public: + RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + const CodeGenRegisterClass &RC) + : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {} + + bool isIdentical(const PredicateMatcher &B) const override; + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_RegBank; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is a basic block. +class MBBOperandMatcher : public OperandPredicateMatcher { +public: + MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx) + : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_MBB; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +class ImmOperandMatcher : public OperandPredicateMatcher { +public: + ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx) + : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_Imm; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is a G_CONSTANT with a particular +/// int. +class ConstantIntOperandMatcher : public OperandPredicateMatcher { +protected: + int64_t Value; + +public: + ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) + : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {} + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + Value == cast(&B)->Value; + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_Int; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is a raw int (where MO.isImm() or +/// MO.isCImm() is true). +class LiteralIntOperandMatcher : public OperandPredicateMatcher { +protected: + int64_t Value; + +public: + LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value) + : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx), + Value(Value) {} + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + Value == cast(&B)->Value; + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_LiteralInt; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is an CmpInst predicate +class CmpPredicateOperandMatcher : public OperandPredicateMatcher { +protected: + std::string PredName; + +public: + CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx, std::string P) + : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), + PredName(P) {} + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + PredName == cast(&B)->PredName; + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_CmpPredicate; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that an operand is an intrinsic ID. +class IntrinsicIDOperandMatcher : public OperandPredicateMatcher { +protected: + const CodeGenIntrinsic *II; + +public: + IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + const CodeGenIntrinsic *II) + : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {} + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + II == cast(&B)->II; + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_IntrinsicID; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that this operand is an immediate whose value meets +/// an immediate predicate. +class OperandImmPredicateMatcher : public OperandPredicateMatcher { +protected: + TreePredicateFn Predicate; + +public: + OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx, + const TreePredicateFn &Predicate) + : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx), + Predicate(Predicate) {} + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + Predicate.getOrigPatFragRecord() == + cast(&B) + ->Predicate.getOrigPatFragRecord(); + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_ImmPredicate; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that a set of predicates match for a particular +/// operand. +class OperandMatcher : public PredicateListMatcher { +protected: + InstructionMatcher &Insn; + unsigned OpIdx; + std::string SymbolicName; + + /// The index of the first temporary variable allocated to this operand. The + /// number of allocated temporaries can be found with + /// countRendererFns(). + unsigned AllocatedTemporariesBaseID; + +public: + OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx, + const std::string &SymbolicName, + unsigned AllocatedTemporariesBaseID) + : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName), + AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {} + + bool hasSymbolicName() const { return !SymbolicName.empty(); } + StringRef getSymbolicName() const { return SymbolicName; } + void setSymbolicName(StringRef Name) { + assert(SymbolicName.empty() && "Operand already has a symbolic name"); + SymbolicName = std::string(Name); + } + + /// Construct a new operand predicate and add it to the matcher. + template + std::optional addPredicate(Args &&...args) { + if (isSameAsAnotherOperand()) + return std::nullopt; + Predicates.emplace_back(std::make_unique( + getInsnVarID(), getOpIdx(), std::forward(args)...)); + return static_cast(Predicates.back().get()); + } + + unsigned getOpIdx() const { return OpIdx; } + unsigned getInsnVarID() const; + + std::string getOperandExpr(unsigned InsnVarID) const; + + InstructionMatcher &getInstructionMatcher() const { return Insn; } + + Error addTypeCheckPredicate(const TypeSetByHwMode &VTy, + bool OperandIsAPointer); + + /// Emit MatchTable opcodes that test whether the instruction named in + /// InsnVarID matches all the predicates and all the operands. + void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule); + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(OperandMatcher &B); + + /// Report the maximum number of temporary operands needed by the operand + /// matcher. + unsigned countRendererFns(); + + unsigned getAllocatedTemporariesBaseID() const { + return AllocatedTemporariesBaseID; + } + + bool isSameAsAnotherOperand() { + for (const auto &Predicate : predicates()) + if (isa(Predicate)) + return true; + return false; + } +}; + +/// Generates code to check a predicate on an instruction. +/// +/// Typical predicates include: +/// * The opcode of the instruction is a particular value. +/// * The nsw/nuw flag is/isn't set. +class InstructionPredicateMatcher : public PredicateMatcher { +public: + InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID) + : PredicateMatcher(Kind, InsnVarID) {} + virtual ~InstructionPredicateMatcher() {} + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + virtual bool + isHigherPriorityThan(const InstructionPredicateMatcher &B) const { + return Kind < B.Kind; + }; +}; + +template <> +inline std::string +PredicateListMatcher::getNoPredicateComment() const { + return "No instruction predicates"; +} + +/// Generates code to check the opcode of an instruction. +class InstructionOpcodeMatcher : public InstructionPredicateMatcher { +protected: + // Allow matching one to several, similar opcodes that share properties. This + // is to handle patterns where one SelectionDAG operation maps to multiple + // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first + // is treated as the canonical opcode. + SmallVector Insts; + + static DenseMap OpcodeValues; + + MatchTableRecord getInstValue(const CodeGenInstruction *I) const; + +public: + static void initOpcodeValuesMap(const CodeGenTarget &Target); + + InstructionOpcodeMatcher(unsigned InsnVarID, + ArrayRef I) + : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), + Insts(I.begin(), I.end()) { + assert((Insts.size() == 1 || Insts.size() == 2) && + "unexpected number of opcode alternatives"); + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_Opcode; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + Insts == cast(&B)->Insts; + } + + bool hasValue() const override { + return Insts.size() == 1 && OpcodeValues.count(Insts[0]); + } + + // TODO: This is used for the SwitchMatcher optimization. We should be able to + // return a list of the opcodes to match. + MatchTableRecord getValue() const override; + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool + isHigherPriorityThan(const InstructionPredicateMatcher &B) const override; + + bool isConstantInstruction() const; + + // The first opcode is the canonical opcode, and later are alternatives. + StringRef getOpcode() const; + ArrayRef getAlternativeOpcodes() { return Insts; } + bool isVariadicNumOperands() const; + StringRef getOperandType(unsigned OpIdx) const; +}; + +class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher { + unsigned NumOperands = 0; + +public: + InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands) + : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID), + NumOperands(NumOperands) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_NumOperands; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + NumOperands == cast(&B)->NumOperands; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that this instruction is a constant whose value +/// meets an immediate predicate. +/// +/// Immediates are slightly odd since they are typically used like an operand +/// but are represented as an operator internally. We typically write simm8:$src +/// in a tablegen pattern, but this is just syntactic sugar for +/// (imm:i32)<>:$imm which more directly describes the nodes +/// that will be matched and the predicate (which is attached to the imm +/// operator) that will be tested. In SelectionDAG this describes a +/// ConstantSDNode whose internal value will be tested using the simm8 +/// predicate. +/// +/// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In +/// this representation, the immediate could be tested with an +/// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a +/// OperandPredicateMatcher-subclass to check the Value meets the predicate but +/// there are two implementation issues with producing that matcher +/// configuration from the SelectionDAG pattern: +/// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that +/// were we to sink the immediate predicate to the operand we would have to +/// have two partial implementations of PatFrag support, one for immediates +/// and one for non-immediates. +/// * At the point we handle the predicate, the OperandMatcher hasn't been +/// created yet. If we were to sink the predicate to the OperandMatcher we +/// would also have to complicate (or duplicate) the code that descends and +/// creates matchers for the subtree. +/// Overall, it's simpler to handle it in the place it was found. +class InstructionImmPredicateMatcher : public InstructionPredicateMatcher { +protected: + TreePredicateFn Predicate; + +public: + InstructionImmPredicateMatcher(unsigned InsnVarID, + const TreePredicateFn &Predicate) + : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID), + Predicate(Predicate) {} + + bool isIdentical(const PredicateMatcher &B) const override; + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_ImmPredicate; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that a memory instruction has a atomic ordering +/// MachineMemoryOperand. +class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher { +public: + enum AOComparator { + AO_Exactly, + AO_OrStronger, + AO_WeakerThan, + }; + +protected: + StringRef Order; + AOComparator Comparator; + +public: + AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order, + AOComparator Comparator = AO_Exactly) + : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID), + Order(Order), Comparator(Comparator) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_AtomicOrderingMMO; + } + + bool isIdentical(const PredicateMatcher &B) const override; + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that the size of an MMO is exactly N bytes. +class MemorySizePredicateMatcher : public InstructionPredicateMatcher { +protected: + unsigned MMOIdx; + uint64_t Size; + +public: + MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size) + : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID), + MMOIdx(MMOIdx), Size(Size) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryLLTSize; + } + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + MMOIdx == cast(&B)->MMOIdx && + Size == cast(&B)->Size; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher { +protected: + unsigned MMOIdx; + SmallVector AddrSpaces; + +public: + MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, + ArrayRef AddrSpaces) + : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID), + MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryAddressSpace; + } + + bool isIdentical(const PredicateMatcher &B) const override; + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher { +protected: + unsigned MMOIdx; + int MinAlign; + +public: + MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, + int MinAlign) + : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID), + MMOIdx(MMOIdx), MinAlign(MinAlign) { + assert(MinAlign > 0); + } + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryAlignment; + } + + bool isIdentical(const PredicateMatcher &B) const override; + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check that the size of an MMO is less-than, equal-to, or +/// greater than a given LLT. +class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher { +public: + enum RelationKind { + GreaterThan, + EqualTo, + LessThan, + }; + +protected: + unsigned MMOIdx; + RelationKind Relation; + unsigned OpIdx; + +public: + MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, + enum RelationKind Relation, unsigned OpIdx) + : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID), + MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryVsLLTSize; + } + bool isIdentical(const PredicateMatcher &B) const override; + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +// Matcher for immAllOnesV/immAllZerosV +class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher { +public: + enum SplatKind { AllZeros, AllOnes }; + +private: + SplatKind Kind; + +public: + VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K) + : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_VectorSplatImm; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + Kind == static_cast(B).Kind; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check an arbitrary C++ instruction predicate. +class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher { +protected: + TreePredicateFn Predicate; + +public: + GenericInstructionPredicateMatcher(unsigned InsnVarID, + TreePredicateFn Predicate) + : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID), + Predicate(Predicate) {} + + static bool classof(const InstructionPredicateMatcher *P) { + return P->getKind() == IPM_GenericPredicate; + } + bool isIdentical(const PredicateMatcher &B) const override; + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override; +}; + +/// Generates code to check for the absence of use of the result. +// TODO? Generalize this to support checking for one use. +class NoUsePredicateMatcher : public InstructionPredicateMatcher { +public: + NoUsePredicateMatcher(unsigned InsnVarID) + : InstructionPredicateMatcher(IPM_NoUse, InsnVarID) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_NoUse; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B); + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIM_CheckHasNoUse") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::LineBreak; + } +}; + +/// Generates code to check that a set of predicates and operands match for a +/// particular instruction. +/// +/// Typical predicates include: +/// * Has a specific opcode. +/// * Has an nsw/nuw flag or doesn't. +class InstructionMatcher final : public PredicateListMatcher { +protected: + typedef std::vector> OperandVec; + + RuleMatcher &Rule; + + /// The operands to match. All rendered operands must be present even if the + /// condition is always true. + OperandVec Operands; + bool NumOperandsCheck = true; + + std::string SymbolicName; + unsigned InsnVarID; + + /// PhysRegInputs - List list has an entry for each explicitly specified + /// physreg input to the pattern. The first elt is the Register node, the + /// second is the recorded slot number the input pattern match saved it in. + SmallVector, 2> PhysRegInputs; + +public: + InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName, + bool NumOpsCheck = true) + : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) { + // We create a new instruction matcher. + // Get a new ID for that instruction. + InsnVarID = Rule.implicitlyDefineInsnVar(*this); + } + + /// Construct a new instruction predicate and add it to the matcher. + template + std::optional addPredicate(Args &&...args) { + Predicates.emplace_back( + std::make_unique(getInsnVarID(), std::forward(args)...)); + return static_cast(Predicates.back().get()); + } + + RuleMatcher &getRuleMatcher() const { return Rule; } + + unsigned getInsnVarID() const { return InsnVarID; } + + /// Add an operand to the matcher. + OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName, + unsigned AllocatedTemporariesBaseID); + OperandMatcher &getOperand(unsigned OpIdx); + OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx, + unsigned TempOpIdx); + + ArrayRef> getPhysRegInputs() const { + return PhysRegInputs; + } + + StringRef getSymbolicName() const { return SymbolicName; } + unsigned getNumOperands() const { return Operands.size(); } + OperandVec::iterator operands_begin() { return Operands.begin(); } + OperandVec::iterator operands_end() { return Operands.end(); } + iterator_range operands() { + return make_range(operands_begin(), operands_end()); + } + OperandVec::const_iterator operands_begin() const { return Operands.begin(); } + OperandVec::const_iterator operands_end() const { return Operands.end(); } + iterator_range operands() const { + return make_range(operands_begin(), operands_end()); + } + bool operands_empty() const { return Operands.empty(); } + + void pop_front() { Operands.erase(Operands.begin()); } + + void optimize(); + + /// Emit MatchTable opcodes that test whether the instruction named in + /// InsnVarName matches all the predicates and all the operands. + void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule); + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(InstructionMatcher &B); + + /// Report the maximum number of temporary operands needed by the instruction + /// matcher. + unsigned countRendererFns(); + + InstructionOpcodeMatcher &getOpcodeMatcher() { + for (auto &P : predicates()) + if (auto *OpMatcher = dyn_cast(P.get())) + return *OpMatcher; + llvm_unreachable("Didn't find an opcode matcher"); + } + + bool isConstantInstruction() { + return getOpcodeMatcher().isConstantInstruction(); + } + + StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); } +}; + +/// Generates code to check that the operand is a register defined by an +/// instruction that matches the given instruction matcher. +/// +/// For example, the pattern: +/// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3)) +/// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match +/// the: +/// (G_ADD $src1, $src2) +/// subpattern. +class InstructionOperandMatcher : public OperandPredicateMatcher { +protected: + std::unique_ptr InsnMatcher; + + GISelFlags Flags; + +public: + InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx, + RuleMatcher &Rule, StringRef SymbolicName, + bool NumOpsCheck = true) + : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx), + InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)), + Flags(Rule.getGISelFlags()) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == OPM_Instruction; + } + + InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; } + + void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const; + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + emitCaptureOpcodes(Table, Rule); + InsnMatcher->emitPredicateOpcodes(Table, Rule); + } + + bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override; + + /// Report the maximum number of temporary operands needed by the predicate + /// matcher. + unsigned countRendererFns() const override { + return InsnMatcher->countRendererFns(); + } +}; + +//===- Actions ------------------------------------------------------------===// +class OperandRenderer { +public: + enum RendererKind { + OR_Copy, + OR_CopyOrAddZeroReg, + OR_CopySubReg, + OR_CopyPhysReg, + OR_CopyConstantAsImm, + OR_CopyFConstantAsFPImm, + OR_Imm, + OR_SubRegIndex, + OR_Register, + OR_TempRegister, + OR_ComplexPattern, + OR_Custom, + OR_CustomOperand + }; + +protected: + RendererKind Kind; + +public: + OperandRenderer(RendererKind Kind) : Kind(Kind) {} + virtual ~OperandRenderer(); + + RendererKind getKind() const { return Kind; } + + virtual void emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const = 0; +}; + +/// A CopyRenderer emits code to copy a single operand from an existing +/// instruction to the one being built. +class CopyRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + /// The name of the operand. + const StringRef SymbolicName; + +public: + CopyRenderer(unsigned NewInsnID, StringRef SymbolicName) + : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), + SymbolicName(SymbolicName) { + assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); + } + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Copy; + } + + StringRef getSymbolicName() const { return SymbolicName; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// A CopyRenderer emits code to copy a virtual register to a specific physical +/// register. +class CopyPhysRegRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + Record *PhysReg; + +public: + CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg) + : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID), PhysReg(Reg) { + assert(PhysReg); + } + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CopyPhysReg; + } + + Record *getPhysReg() const { return PhysReg; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an +/// existing instruction to the one being built. If the operand turns out to be +/// a 'G_CONSTANT 0' then it replaces the operand with a zero register. +class CopyOrAddZeroRegRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + /// The name of the operand. + const StringRef SymbolicName; + const Record *ZeroRegisterDef; + +public: + CopyOrAddZeroRegRenderer(unsigned NewInsnID, StringRef SymbolicName, + Record *ZeroRegisterDef) + : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID), + SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) { + assert(!SymbolicName.empty() && "Cannot copy from an unspecified source"); + } + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CopyOrAddZeroReg; + } + + StringRef getSymbolicName() const { return SymbolicName; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to +/// an extended immediate operand. +class CopyConstantAsImmRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + /// The name of the operand. + const std::string SymbolicName; + bool Signed; + +public: + CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName) + : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID), + SymbolicName(SymbolicName), Signed(true) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CopyConstantAsImm; + } + + StringRef getSymbolicName() const { return SymbolicName; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT +/// instruction to an extended immediate operand. +class CopyFConstantAsFPImmRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + /// The name of the operand. + const std::string SymbolicName; + +public: + CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName) + : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID), + SymbolicName(SymbolicName) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CopyFConstantAsFPImm; + } + + StringRef getSymbolicName() const { return SymbolicName; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// A CopySubRegRenderer emits code to copy a single register operand from an +/// existing instruction to the one being built and indicate that only a +/// subregister should be copied. +class CopySubRegRenderer : public OperandRenderer { +protected: + unsigned NewInsnID; + /// The name of the operand. + const StringRef SymbolicName; + /// The subregister to extract. + const CodeGenSubRegIndex *SubReg; + +public: + CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName, + const CodeGenSubRegIndex *SubReg) + : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), + SymbolicName(SymbolicName), SubReg(SubReg) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CopySubReg; + } + + StringRef getSymbolicName() const { return SymbolicName; } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Adds a specific physical register to the instruction being built. +/// This is typically useful for WZR/XZR on AArch64. +class AddRegisterRenderer : public OperandRenderer { +protected: + unsigned InsnID; + const Record *RegisterDef; + bool IsDef; + const CodeGenTarget &Target; + +public: + AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target, + const Record *RegisterDef, bool IsDef = false) + : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef), + IsDef(IsDef), Target(Target) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Register; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Adds a specific temporary virtual register to the instruction being built. +/// This is used to chain instructions together when emitting multiple +/// instructions. +class TempRegRenderer : public OperandRenderer { +protected: + unsigned InsnID; + unsigned TempRegID; + const CodeGenSubRegIndex *SubRegIdx; + bool IsDef; + bool IsDead; + +public: + TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false, + const CodeGenSubRegIndex *SubReg = nullptr, + bool IsDead = false) + : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID), + SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_TempRegister; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Adds a specific immediate to the instruction being built. +class ImmRenderer : public OperandRenderer { +protected: + unsigned InsnID; + int64_t Imm; + +public: + ImmRenderer(unsigned InsnID, int64_t Imm) + : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Imm; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID") + << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm") + << MatchTable::IntValue(Imm) << MatchTable::LineBreak; + } +}; + +/// Adds an enum value for a subreg index to the instruction being built. +class SubRegIndexRenderer : public OperandRenderer { +protected: + unsigned InsnID; + const CodeGenSubRegIndex *SubRegIdx; + +public: + SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI) + : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_SubRegIndex; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Adds operands by calling a renderer function supplied by the ComplexPattern +/// matcher function. +class RenderComplexPatternOperand : public OperandRenderer { +private: + unsigned InsnID; + const Record &TheDef; + /// The name of the operand. + const StringRef SymbolicName; + /// The renderer number. This must be unique within a rule since it's used to + /// identify a temporary variable to hold the renderer function. + unsigned RendererID; + /// When provided, this is the suboperand of the ComplexPattern operand to + /// render. Otherwise all the suboperands will be rendered. + std::optional SubOperand; + /// The subregister to extract. Render the whole register if not specified. + const CodeGenSubRegIndex *SubReg; + + unsigned getNumOperands() const { + return TheDef.getValueAsDag("Operands")->getNumArgs(); + } + +public: + RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef, + StringRef SymbolicName, unsigned RendererID, + std::optional SubOperand = std::nullopt, + const CodeGenSubRegIndex *SubReg = nullptr) + : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef), + SymbolicName(SymbolicName), RendererID(RendererID), + SubOperand(SubOperand), SubReg(SubReg) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_ComplexPattern; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +class CustomRenderer : public OperandRenderer { +protected: + unsigned InsnID; + const Record &Renderer; + /// The name of the operand. + const std::string SymbolicName; + +public: + CustomRenderer(unsigned InsnID, const Record &Renderer, + StringRef SymbolicName) + : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer), + SymbolicName(SymbolicName) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Custom; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +class CustomOperandRenderer : public OperandRenderer { +protected: + unsigned InsnID; + const Record &Renderer; + /// The name of the operand. + const std::string SymbolicName; + +public: + CustomOperandRenderer(unsigned InsnID, const Record &Renderer, + StringRef SymbolicName) + : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer), + SymbolicName(SymbolicName) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_CustomOperand; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// An action taken when all Matcher predicates succeeded for a parent rule. +/// +/// Typical actions include: +/// * Changing the opcode of an instruction. +/// * Adding an operand to an instruction. +class MatchAction { +public: + virtual ~MatchAction() {} + + /// Emit the MatchTable opcodes to implement the action. + virtual void emitActionOpcodes(MatchTable &Table, + RuleMatcher &Rule) const = 0; +}; + +/// Generates a comment describing the matched rule being acted upon. +class DebugCommentAction : public MatchAction { +private: + std::string S; + +public: + DebugCommentAction(StringRef S) : S(std::string(S)) {} + + void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { + Table << MatchTable::Comment(S) << MatchTable::LineBreak; + } +}; + +/// Generates code to build an instruction or mutate an existing instruction +/// into the desired instruction when this is possible. +class BuildMIAction : public MatchAction { +private: + unsigned InsnID; + const CodeGenInstruction *I; + InstructionMatcher *Matched; + std::vector> OperandRenderers; + + /// True if the instruction can be built solely by mutating the opcode. + bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const; + +public: + BuildMIAction(unsigned InsnID, const CodeGenInstruction *I) + : InsnID(InsnID), I(I), Matched(nullptr) {} + + unsigned getInsnID() const { return InsnID; } + const CodeGenInstruction *getCGI() const { return I; } + + void chooseInsnToMutate(RuleMatcher &Rule); + + template Kind &addRenderer(Args &&...args) { + OperandRenderers.emplace_back( + std::make_unique(InsnID, std::forward(args)...)); + return *static_cast(OperandRenderers.back().get()); + } + + void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Generates code to constrain the operands of an output instruction to the +/// register classes specified by the definition of that instruction. +class ConstrainOperandsToDefinitionAction : public MatchAction { + unsigned InsnID; + +public: + ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {} + + void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::LineBreak; + } +}; + +/// Generates code to constrain the specified operand of an output instruction +/// to the specified register class. +class ConstrainOperandToRegClassAction : public MatchAction { + unsigned InsnID; + unsigned OpIdx; + const CodeGenRegisterClass &RC; + +public: + ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx, + const CodeGenRegisterClass &RC) + : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {} + + void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +/// Generates code to create a temporary register which can be used to chain +/// instructions together. +class MakeTempRegisterAction : public MatchAction { +private: + LLTCodeGen Ty; + unsigned TempRegID; + +public: + MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID) + : Ty(Ty), TempRegID(TempRegID) { + KnownTypes.insert(Ty); + } + + void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; +}; + +} // namespace gi +} // namespace llvm + +#endif diff --git a/llvm/utils/TableGen/GlobalISelMatchTable.cpp b/llvm/utils/TableGen/GlobalISelMatchTable.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISelMatchTable.cpp @@ -0,0 +1,1990 @@ +//===- GlobalISelMatchTable.cpp -------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GlobalISelMatchTable.h" +#include "CodeGenInstruction.h" +#include "CodeGenRegisters.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ScopedPrinter.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/TableGen/Error.h" + +#define DEBUG_TYPE "gi-match-table" + +STATISTIC(NumPatternEmitted, "Number of patterns emitted"); + +namespace llvm { +namespace gi { + +namespace { + +Error failUnsupported(const Twine &Reason) { + return make_error(Reason, inconvertibleErrorCode()); +} + +/// Get the name of the enum value used to number the predicate function. +std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) { + if (Predicate.hasGISelPredicateCode()) + return "GIPFP_MI_" + Predicate.getFnName(); + return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" + + Predicate.getFnName(); +} + +std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) { + return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate"; +} +} // namespace + +//===- Helpers ------------------------------------------------------------===// + +std::string +getNameForFeatureBitset(const std::vector &FeatureBitset) { + std::string Name = "GIFBS"; + for (const auto &Feature : FeatureBitset) + Name += ("_" + Feature->getName()).str(); + return Name; +} + +template +std::vector +optimizeRules(ArrayRef Rules, + std::vector> &MatcherStorage) { + + std::vector OptRules; + std::unique_ptr CurrentGroup = std::make_unique(); + assert(CurrentGroup->empty() && "Newly created group isn't empty!"); + unsigned NumGroups = 0; + + auto ProcessCurrentGroup = [&]() { + if (CurrentGroup->empty()) + // An empty group is good to be reused: + return; + + // If the group isn't large enough to provide any benefit, move all the + // added rules out of it and make sure to re-create the group to properly + // re-initialize it: + if (CurrentGroup->size() < 2) + append_range(OptRules, CurrentGroup->matchers()); + else { + CurrentGroup->finalize(); + OptRules.push_back(CurrentGroup.get()); + MatcherStorage.emplace_back(std::move(CurrentGroup)); + ++NumGroups; + } + CurrentGroup = std::make_unique(); + }; + for (Matcher *Rule : Rules) { + // Greedily add as many matchers as possible to the current group: + if (CurrentGroup->addMatcher(*Rule)) + continue; + + ProcessCurrentGroup(); + assert(CurrentGroup->empty() && "A group wasn't properly re-initialized"); + + // Try to add the pending matcher to a newly created empty group: + if (!CurrentGroup->addMatcher(*Rule)) + // If we couldn't add the matcher to an empty group, that group type + // doesn't support that kind of matchers at all, so just skip it: + OptRules.push_back(Rule); + } + ProcessCurrentGroup(); + + LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n"); + (void)NumGroups; + assert(CurrentGroup->empty() && "The last group wasn't properly processed"); + return OptRules; +} + +template std::vector optimizeRules( + ArrayRef Rules, + std::vector> &MatcherStorage); + +template std::vector optimizeRules( + ArrayRef Rules, + std::vector> &MatcherStorage); + +//===- Global Data --------------------------------------------------------===// + +std::set KnownTypes; + +//===- MatchTableRecord ---------------------------------------------------===// + +void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis, + const MatchTable &Table) const { + bool UseLineComment = + LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows); + if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows)) + UseLineComment = false; + + if (Flags & MTRF_Comment) + OS << (UseLineComment ? "// " : "/*"); + + OS << EmitStr; + if (Flags & MTRF_Label) + OS << ": @" << Table.getLabelIndex(LabelID); + + if ((Flags & MTRF_Comment) && !UseLineComment) + OS << "*/"; + + if (Flags & MTRF_JumpTarget) { + if (Flags & MTRF_Comment) + OS << " "; + OS << Table.getLabelIndex(LabelID); + } + + if (Flags & MTRF_CommaFollows) { + OS << ","; + if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows)) + OS << " "; + } + + if (Flags & MTRF_LineBreakFollows) + OS << "\n"; +} + +//===- MatchTable ---------------------------------------------------------===// + +MatchTableRecord MatchTable::LineBreak = { + std::nullopt, "" /* Emit String */, 0 /* Elements */, + MatchTableRecord::MTRF_LineBreakFollows}; + +MatchTableRecord MatchTable::Comment(StringRef Comment) { + return MatchTableRecord(std::nullopt, Comment, 0, + MatchTableRecord::MTRF_Comment); +} + +MatchTableRecord MatchTable::Opcode(StringRef Opcode, int IndentAdjust) { + unsigned ExtraFlags = 0; + if (IndentAdjust > 0) + ExtraFlags |= MatchTableRecord::MTRF_Indent; + if (IndentAdjust < 0) + ExtraFlags |= MatchTableRecord::MTRF_Outdent; + + return MatchTableRecord(std::nullopt, Opcode, 1, + MatchTableRecord::MTRF_CommaFollows | ExtraFlags); +} + +MatchTableRecord MatchTable::NamedValue(StringRef NamedValue) { + return MatchTableRecord(std::nullopt, NamedValue, 1, + MatchTableRecord::MTRF_CommaFollows); +} + +MatchTableRecord MatchTable::NamedValue(StringRef NamedValue, + int64_t RawValue) { + return MatchTableRecord(std::nullopt, NamedValue, 1, + MatchTableRecord::MTRF_CommaFollows, RawValue); +} + +MatchTableRecord MatchTable::NamedValue(StringRef Namespace, + StringRef NamedValue) { + return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(), + 1, MatchTableRecord::MTRF_CommaFollows); +} + +MatchTableRecord MatchTable::NamedValue(StringRef Namespace, + StringRef NamedValue, + int64_t RawValue) { + return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(), + 1, MatchTableRecord::MTRF_CommaFollows, RawValue); +} + +MatchTableRecord MatchTable::IntValue(int64_t IntValue) { + return MatchTableRecord(std::nullopt, llvm::to_string(IntValue), 1, + MatchTableRecord::MTRF_CommaFollows); +} + +MatchTableRecord MatchTable::Label(unsigned LabelID) { + return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0, + MatchTableRecord::MTRF_Label | + MatchTableRecord::MTRF_Comment | + MatchTableRecord::MTRF_LineBreakFollows); +} + +MatchTableRecord MatchTable::JumpTarget(unsigned LabelID) { + return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1, + MatchTableRecord::MTRF_JumpTarget | + MatchTableRecord::MTRF_Comment | + MatchTableRecord::MTRF_CommaFollows); +} + +void MatchTable::emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; } + +void MatchTable::emitDeclaration(raw_ostream &OS) const { + unsigned Indentation = 4; + OS << " constexpr static int64_t MatchTable" << ID << "[] = {"; + LineBreak.emit(OS, true, *this); + OS << std::string(Indentation, ' '); + + for (auto I = Contents.begin(), E = Contents.end(); I != E; ++I) { + bool LineBreakIsNext = false; + const auto &NextI = std::next(I); + + if (NextI != E) { + if (NextI->EmitStr == "" && + NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows) + LineBreakIsNext = true; + } + + if (I->Flags & MatchTableRecord::MTRF_Indent) + Indentation += 2; + + I->emit(OS, LineBreakIsNext, *this); + if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows) + OS << std::string(Indentation, ' '); + + if (I->Flags & MatchTableRecord::MTRF_Outdent) + Indentation -= 2; + } + OS << "};\n"; +} + +MatchTable MatchTable::buildTable(ArrayRef Rules, + bool WithCoverage) { + MatchTable Table(WithCoverage); + for (Matcher *Rule : Rules) + Rule->emit(Table); + + return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; +} + +//===- LLTCodeGen ---------------------------------------------------------===// + +std::string LLTCodeGen::getCxxEnumValue() const { + std::string Str; + raw_string_ostream OS(Str); + + emitCxxEnumValue(OS); + return Str; +} + +void LLTCodeGen::emitCxxEnumValue(raw_ostream &OS) const { + if (Ty.isScalar()) { + OS << "GILLT_s" << Ty.getSizeInBits(); + return; + } + if (Ty.isVector()) { + OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v") + << Ty.getElementCount().getKnownMinValue() << "s" + << Ty.getScalarSizeInBits(); + return; + } + if (Ty.isPointer()) { + OS << "GILLT_p" << Ty.getAddressSpace(); + if (Ty.getSizeInBits() > 0) + OS << "s" << Ty.getSizeInBits(); + return; + } + llvm_unreachable("Unhandled LLT"); +} + +void LLTCodeGen::emitCxxConstructorCall(raw_ostream &OS) const { + if (Ty.isScalar()) { + OS << "LLT::scalar(" << Ty.getSizeInBits() << ")"; + return; + } + if (Ty.isVector()) { + OS << "LLT::vector(" + << (Ty.isScalable() ? "ElementCount::getScalable(" + : "ElementCount::getFixed(") + << Ty.getElementCount().getKnownMinValue() << "), " + << Ty.getScalarSizeInBits() << ")"; + return; + } + if (Ty.isPointer() && Ty.getSizeInBits() > 0) { + OS << "LLT::pointer(" << Ty.getAddressSpace() << ", " << Ty.getSizeInBits() + << ")"; + return; + } + llvm_unreachable("Unhandled LLT"); +} + +/// This ordering is used for std::unique() and llvm::sort(). There's no +/// particular logic behind the order but either A < B or B < A must be +/// true if A != B. +bool LLTCodeGen::operator<(const LLTCodeGen &Other) const { + if (Ty.isValid() != Other.Ty.isValid()) + return Ty.isValid() < Other.Ty.isValid(); + if (!Ty.isValid()) + return false; + + if (Ty.isVector() != Other.Ty.isVector()) + return Ty.isVector() < Other.Ty.isVector(); + if (Ty.isScalar() != Other.Ty.isScalar()) + return Ty.isScalar() < Other.Ty.isScalar(); + if (Ty.isPointer() != Other.Ty.isPointer()) + return Ty.isPointer() < Other.Ty.isPointer(); + + if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace()) + return Ty.getAddressSpace() < Other.Ty.getAddressSpace(); + + if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount()) + return std::make_tuple(Ty.isScalable(), + Ty.getElementCount().getKnownMinValue()) < + std::make_tuple(Other.Ty.isScalable(), + Other.Ty.getElementCount().getKnownMinValue()); + + assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) && + "Unexpected mismatch of scalable property"); + return Ty.isVector() + ? std::make_tuple(Ty.isScalable(), + Ty.getSizeInBits().getKnownMinValue()) < + std::make_tuple(Other.Ty.isScalable(), + Other.Ty.getSizeInBits().getKnownMinValue()) + : Ty.getSizeInBits().getFixedValue() < + Other.Ty.getSizeInBits().getFixedValue(); +} + +//===- LLTCodeGen Helpers -------------------------------------------------===// + +std::optional MVTToLLT(MVT::SimpleValueType SVT) { + MVT VT(SVT); + + if (VT.isVector() && !VT.getVectorElementCount().isScalar()) + return LLTCodeGen( + LLT::vector(VT.getVectorElementCount(), VT.getScalarSizeInBits())); + + if (VT.isInteger() || VT.isFloatingPoint()) + return LLTCodeGen(LLT::scalar(VT.getSizeInBits())); + + return std::nullopt; +} + +//===- Matcher ------------------------------------------------------------===// + +void Matcher::optimize() {} + +Matcher::~Matcher() {} + +//===- GroupMatcher -------------------------------------------------------===// + +bool GroupMatcher::candidateConditionMatches( + const PredicateMatcher &Predicate) const { + + if (empty()) { + // Sharing predicates for nested instructions is not supported yet as we + // currently don't hoist the GIM_RecordInsn's properly, therefore we can + // only work on the original root instruction (InsnVarID == 0): + if (Predicate.getInsnVarID() != 0) + return false; + // ... otherwise an empty group can handle any predicate with no specific + // requirements: + return true; + } + + const Matcher &Representative = **Matchers.begin(); + const auto &RepresentativeCondition = Representative.getFirstCondition(); + // ... if not empty, the group can only accomodate matchers with the exact + // same first condition: + return Predicate.isIdentical(RepresentativeCondition); +} + +bool GroupMatcher::addMatcher(Matcher &Candidate) { + if (!Candidate.hasFirstCondition()) + return false; + + const PredicateMatcher &Predicate = Candidate.getFirstCondition(); + if (!candidateConditionMatches(Predicate)) + return false; + + Matchers.push_back(&Candidate); + return true; +} + +void GroupMatcher::finalize() { + assert(Conditions.empty() && "Already finalized?"); + if (empty()) + return; + + Matcher &FirstRule = **Matchers.begin(); + for (;;) { + // All the checks are expected to succeed during the first iteration: + for (const auto &Rule : Matchers) + if (!Rule->hasFirstCondition()) + return; + const auto &FirstCondition = FirstRule.getFirstCondition(); + for (unsigned I = 1, E = Matchers.size(); I < E; ++I) + if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition)) + return; + + Conditions.push_back(FirstRule.popFirstCondition()); + for (unsigned I = 1, E = Matchers.size(); I < E; ++I) + Matchers[I]->popFirstCondition(); + } +} + +void GroupMatcher::emit(MatchTable &Table) { + unsigned LabelID = ~0U; + if (!Conditions.empty()) { + LabelID = Table.allocateLabelID(); + Table << MatchTable::Opcode("GIM_Try", +1) + << MatchTable::Comment("On fail goto") + << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak; + } + for (auto &Condition : Conditions) + Condition->emitPredicateOpcodes( + Table, *static_cast(*Matchers.begin())); + + for (const auto &M : Matchers) + M->emit(Table); + + // Exit the group + if (!Conditions.empty()) + Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak + << MatchTable::Label(LabelID); +} + +void GroupMatcher::optimize() { + // Make sure we only sort by a specific predicate within a range of rules that + // all have that predicate checked against a specific value (not a wildcard): + auto F = Matchers.begin(); + auto T = F; + auto E = Matchers.end(); + while (T != E) { + while (T != E) { + auto *R = static_cast(*T); + if (!R->getFirstConditionAsRootType().get().isValid()) + break; + ++T; + } + std::stable_sort(F, T, [](Matcher *A, Matcher *B) { + auto *L = static_cast(A); + auto *R = static_cast(B); + return L->getFirstConditionAsRootType() < + R->getFirstConditionAsRootType(); + }); + if (T != E) + F = ++T; + } + optimizeRules(Matchers, MatcherStorage).swap(Matchers); + optimizeRules(Matchers, MatcherStorage).swap(Matchers); +} + +//===- SwitchMatcher ------------------------------------------------------===// + +bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) { + return isa(P) || isa(P); +} + +bool SwitchMatcher::candidateConditionMatches( + const PredicateMatcher &Predicate) const { + + if (empty()) { + // Sharing predicates for nested instructions is not supported yet as we + // currently don't hoist the GIM_RecordInsn's properly, therefore we can + // only work on the original root instruction (InsnVarID == 0): + if (Predicate.getInsnVarID() != 0) + return false; + // ... while an attempt to add even a root matcher to an empty SwitchMatcher + // could fail as not all the types of conditions are supported: + if (!isSupportedPredicateType(Predicate)) + return false; + // ... or the condition might not have a proper implementation of + // getValue() / isIdenticalDownToValue() yet: + if (!Predicate.hasValue()) + return false; + // ... otherwise an empty Switch can accomodate the condition with no + // further requirements: + return true; + } + + const Matcher &CaseRepresentative = **Matchers.begin(); + const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition(); + // Switch-cases must share the same kind of condition and path to the value it + // checks: + if (!Predicate.isIdenticalDownToValue(RepresentativeCondition)) + return false; + + const auto Value = Predicate.getValue(); + // ... but be unique with respect to the actual value they check: + return Values.count(Value) == 0; +} + +bool SwitchMatcher::addMatcher(Matcher &Candidate) { + if (!Candidate.hasFirstCondition()) + return false; + + const PredicateMatcher &Predicate = Candidate.getFirstCondition(); + if (!candidateConditionMatches(Predicate)) + return false; + const auto Value = Predicate.getValue(); + Values.insert(Value); + + Matchers.push_back(&Candidate); + return true; +} + +void SwitchMatcher::finalize() { + assert(Condition == nullptr && "Already finalized"); + assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); + if (empty()) + return; + + llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) { + return L->getFirstCondition().getValue() < + R->getFirstCondition().getValue(); + }); + Condition = Matchers[0]->popFirstCondition(); + for (unsigned I = 1, E = Values.size(); I < E; ++I) + Matchers[I]->popFirstCondition(); +} + +void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P, + MatchTable &Table) { + assert(isSupportedPredicateType(P) && "Predicate type is not supported"); + + if (const auto *Condition = dyn_cast(&P)) { + Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI") + << MatchTable::IntValue(Condition->getInsnVarID()); + return; + } + if (const auto *Condition = dyn_cast(&P)) { + Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI") + << MatchTable::IntValue(Condition->getInsnVarID()) + << MatchTable::Comment("Op") + << MatchTable::IntValue(Condition->getOpIdx()); + return; + } + + llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a " + "predicate type that is claimed to be supported"); +} + +void SwitchMatcher::emit(MatchTable &Table) { + assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); + if (empty()) + return; + assert(Condition != nullptr && + "Broken SwitchMatcher, hasn't been finalized?"); + + std::vector LabelIDs(Values.size()); + std::generate(LabelIDs.begin(), LabelIDs.end(), + [&Table]() { return Table.allocateLabelID(); }); + const unsigned Default = Table.allocateLabelID(); + + const int64_t LowerBound = Values.begin()->getRawValue(); + const int64_t UpperBound = Values.rbegin()->getRawValue() + 1; + + emitPredicateSpecificOpcodes(*Condition, Table); + + Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound) + << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")") + << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default); + + int64_t J = LowerBound; + auto VI = Values.begin(); + for (unsigned I = 0, E = Values.size(); I < E; ++I) { + auto V = *VI++; + while (J++ < V.getRawValue()) + Table << MatchTable::IntValue(0); + V.turnIntoComment(); + Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]); + } + Table << MatchTable::LineBreak; + + for (unsigned I = 0, E = Values.size(); I < E; ++I) { + Table << MatchTable::Label(LabelIDs[I]); + Matchers[I]->emit(Table); + Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; + } + Table << MatchTable::Label(Default); +} + +//===- RuleMatcher --------------------------------------------------------===// + +uint64_t RuleMatcher::NextRuleID = 0; + +StringRef RuleMatcher::getOpcode() const { + return Matchers.front()->getOpcode(); +} + +unsigned RuleMatcher::getNumOperands() const { + return Matchers.front()->getNumOperands(); +} + +LLTCodeGen RuleMatcher::getFirstConditionAsRootType() { + InstructionMatcher &InsnMatcher = *Matchers.front(); + if (!InsnMatcher.predicates_empty()) + if (const auto *TM = + dyn_cast(&**InsnMatcher.predicates_begin())) + if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0) + return TM->getTy(); + return {}; +} + +void RuleMatcher::optimize() { + for (auto &Item : InsnVariableIDs) { + InstructionMatcher &InsnMatcher = *Item.first; + for (auto &OM : InsnMatcher.operands()) { + // Complex Patterns are usually expensive and they relatively rarely fail + // on their own: more often we end up throwing away all the work done by a + // matching part of a complex pattern because some other part of the + // enclosing pattern didn't match. All of this makes it beneficial to + // delay complex patterns until the very end of the rule matching, + // especially for targets having lots of complex patterns. + for (auto &OP : OM->predicates()) + if (isa(OP)) + EpilogueMatchers.emplace_back(std::move(OP)); + OM->eraseNullPredicates(); + } + InsnMatcher.optimize(); + } + llvm::sort(EpilogueMatchers, [](const std::unique_ptr &L, + const std::unique_ptr &R) { + return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) < + std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx()); + }); +} + +bool RuleMatcher::hasFirstCondition() const { + if (insnmatchers_empty()) + return false; + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + return true; + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa(OP)) + return true; + return false; +} + +const PredicateMatcher &RuleMatcher::getFirstCondition() const { + assert(!insnmatchers_empty() && + "Trying to get a condition from an empty RuleMatcher"); + + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + return **Matcher.predicates_begin(); + // If there is no more predicate on the instruction itself, look at its + // operands. + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa(OP)) + return *OP; + + llvm_unreachable("Trying to get a condition from an InstructionMatcher with " + "no conditions"); +} + +std::unique_ptr RuleMatcher::popFirstCondition() { + assert(!insnmatchers_empty() && + "Trying to pop a condition from an empty RuleMatcher"); + + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + return Matcher.predicates_pop_front(); + // If there is no more predicate on the instruction itself, look at its + // operands. + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa(OP)) { + std::unique_ptr Result = std::move(OP); + OM->eraseNullPredicates(); + return Result; + } + + llvm_unreachable("Trying to pop a condition from an InstructionMatcher with " + "no conditions"); +} + +GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R, + StringRef FlagName, + GISelFlags FlagBit) { + // If the value of a flag is unset, ignore it. + // If it's set, it always takes precedence over the existing value so + // clear/set the corresponding bit. + bool Unset = false; + bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset); + if (!Unset) + return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit); + return CurFlags; +} + +SaveAndRestore RuleMatcher::setGISelFlags(const Record *R) { + if (!R || !R->isSubClassOf("GISelFlags")) + return {Flags, Flags}; + + assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) && + "GISelFlags is only expected on Pattern/PatFrags!"); + + GISelFlags NewFlags = + updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies); + return {Flags, NewFlags}; +} + +Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName, + Record *ComplexPattern, + unsigned RendererID, + unsigned SubOperandID, + StringRef ParentSymbolicName) { + std::string ParentName(ParentSymbolicName); + if (ComplexSubOperands.count(SymbolicName)) { + const std::string &RecordedParentName = + ComplexSubOperandsParentName[SymbolicName]; + if (RecordedParentName != ParentName) + return failUnsupported("Error: Complex suboperand " + SymbolicName + + " referenced by different operands: " + + RecordedParentName + " and " + ParentName + "."); + // Complex suboperand referenced more than once from same the operand is + // used to generate 'same operand check'. Emitting of + // GIR_ComplexSubOperandRenderer for them is already handled. + return Error::success(); + } + + ComplexSubOperands[SymbolicName] = + std::make_tuple(ComplexPattern, RendererID, SubOperandID); + ComplexSubOperandsParentName[SymbolicName] = ParentName; + + return Error::success(); +} + +InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) { + Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName)); + MutatableInsns.insert(Matchers.back().get()); + return *Matchers.back(); +} + +void RuleMatcher::addRequiredFeature(Record *Feature) { + RequiredFeatures.push_back(Feature); +} + +const std::vector &RuleMatcher::getRequiredFeatures() const { + return RequiredFeatures; +} + +unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) { + unsigned NewInsnVarID = NextInsnVarID++; + InsnVariableIDs[&Matcher] = NewInsnVarID; + return NewInsnVarID; +} + +unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const { + const auto &I = InsnVariableIDs.find(&InsnMatcher); + if (I != InsnVariableIDs.end()) + return I->second; + llvm_unreachable("Matched Insn was not captured in a local variable"); +} + +void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) { + if (!DefinedOperands.contains(SymbolicName)) { + DefinedOperands[SymbolicName] = &OM; + return; + } + + // If the operand is already defined, then we must ensure both references in + // the matcher have the exact same node. + RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher(); + OM.addPredicate( + OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(), + RM.getGISelFlags()); +} + +void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) { + if (!PhysRegOperands.contains(Reg)) { + PhysRegOperands[Reg] = &OM; + return; + } +} + +inline InstructionMatcher & +RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const { + for (const auto &I : InsnVariableIDs) + if (I.first->getSymbolicName() == SymbolicName) + return *I.first; + llvm_unreachable( + ("Failed to lookup instruction " + SymbolicName).str().c_str()); +} + +inline const OperandMatcher & +RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const { + const auto &I = PhysRegOperands.find(Reg); + + if (I == PhysRegOperands.end()) { + PrintFatalError(SrcLoc, "Register " + Reg->getName() + + " was not declared in matcher"); + } + + return *I->second; +} + +const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const { + const auto &I = DefinedOperands.find(Name); + + if (I == DefinedOperands.end()) + PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher"); + + return *I->second; +} + +void RuleMatcher::emit(MatchTable &Table) { + if (Matchers.empty()) + llvm_unreachable("Unexpected empty matcher!"); + + // The representation supports rules that require multiple roots such as: + // %ptr(p0) = ... + // %elt0(s32) = G_LOAD %ptr + // %1(p0) = G_ADD %ptr, 4 + // %elt1(s32) = G_LOAD p0 %1 + // which could be usefully folded into: + // %ptr(p0) = ... + // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr + // on some targets but we don't need to make use of that yet. + assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); + + unsigned LabelID = Table.allocateLabelID(); + Table << MatchTable::Opcode("GIM_Try", +1) + << MatchTable::Comment("On fail goto") + << MatchTable::JumpTarget(LabelID) + << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str()) + << MatchTable::LineBreak; + + if (!RequiredFeatures.empty()) { + Table << MatchTable::Opcode("GIM_CheckFeatures") + << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures)) + << MatchTable::LineBreak; + } + + Matchers.front()->emitPredicateOpcodes(Table, *this); + + // We must also check if it's safe to fold the matched instructions. + if (InsnVariableIDs.size() >= 2) { + // Invert the map to create stable ordering (by var names) + SmallVector InsnIDs; + for (const auto &Pair : InsnVariableIDs) { + // Skip the root node since it isn't moving anywhere. Everything else is + // sinking to meet it. + if (Pair.first == Matchers.front().get()) + continue; + + InsnIDs.push_back(Pair.second); + } + llvm::sort(InsnIDs); + + for (const auto &InsnID : InsnIDs) { + // Reject the difficult cases until we have a more accurate check. + Table << MatchTable::Opcode("GIM_CheckIsSafeToFold") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::LineBreak; + + // FIXME: Emit checks to determine it's _actually_ safe to fold and/or + // account for unsafe cases. + // + // Example: + // MI1--> %0 = ... + // %1 = ... %0 + // MI0--> %2 = ... %0 + // It's not safe to erase MI1. We currently handle this by not + // erasing %0 (even when it's dead). + // + // Example: + // MI1--> %0 = load volatile @a + // %1 = load volatile @a + // MI0--> %2 = ... %0 + // It's not safe to sink %0's def past %1. We currently handle + // this by rejecting all loads. + // + // Example: + // MI1--> %0 = load @a + // %1 = store @a + // MI0--> %2 = ... %0 + // It's not safe to sink %0's def past %1. We currently handle + // this by rejecting all loads. + // + // Example: + // G_CONDBR %cond, @BB1 + // BB0: + // MI1--> %0 = load @a + // G_BR @BB1 + // BB1: + // MI0--> %2 = ... %0 + // It's not always safe to sink %0 across control flow. In this + // case it may introduce a memory fault. We currentl handle this + // by rejecting all loads. + } + } + + for (const auto &PM : EpilogueMatchers) + PM->emitPredicateOpcodes(Table, *this); + + for (const auto &MA : Actions) + MA->emitActionOpcodes(Table, *this); + + if (Table.isWithCoverage()) + Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID) + << MatchTable::LineBreak; + else + Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str()) + << MatchTable::LineBreak; + + Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak + << MatchTable::Label(LabelID); + ++NumPatternEmitted; +} + +bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const { + // Rules involving more match roots have higher priority. + if (Matchers.size() > B.Matchers.size()) + return true; + if (Matchers.size() < B.Matchers.size()) + return false; + + for (auto Matcher : zip(Matchers, B.Matchers)) { + if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher))) + return true; + if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher))) + return false; + } + + return false; +} + +unsigned RuleMatcher::countRendererFns() const { + return std::accumulate( + Matchers.begin(), Matchers.end(), 0, + [](unsigned A, const std::unique_ptr &Matcher) { + return A + Matcher->countRendererFns(); + }); +} + +//===- PredicateMatcher ---------------------------------------------------===// + +PredicateMatcher::~PredicateMatcher() {} + +//===- OperandPredicateMatcher --------------------------------------------===// + +OperandPredicateMatcher::~OperandPredicateMatcher() {} + +bool OperandPredicateMatcher::isHigherPriorityThan( + const OperandPredicateMatcher &B) const { + // Generally speaking, an instruction is more important than an Int or a + // LiteralInt because it can cover more nodes but theres an exception to + // this. G_CONSTANT's are less important than either of those two because they + // are more permissive. + + const InstructionOperandMatcher *AOM = + dyn_cast(this); + const InstructionOperandMatcher *BOM = + dyn_cast(&B); + bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction(); + bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction(); + + if (AOM && BOM) { + // The relative priorities between a G_CONSTANT and any other instruction + // don't actually matter but this code is needed to ensure a strict weak + // ordering. This is particularly important on Windows where the rules will + // be incorrectly sorted without it. + if (AIsConstantInsn != BIsConstantInsn) + return AIsConstantInsn < BIsConstantInsn; + return false; + } + + if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt)) + return false; + if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt)) + return true; + + return Kind < B.Kind; +} + +//===- SameOperandMatcher -------------------------------------------------===// + +void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName); + unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher()); + assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID()); + const bool IgnoreCopies = Flags & GISF_IgnoreCopies; + Table << MatchTable::Opcode(IgnoreCopies + ? "GIM_CheckIsSameOperandIgnoreCopies" + : "GIM_CheckIsSameOperand") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("OtherMI") + << MatchTable::IntValue(OtherInsnVarID) + << MatchTable::Comment("OtherOpIdx") + << MatchTable::IntValue(OtherOM.getOpIdx()) << MatchTable::LineBreak; +} + +//===- LLTOperandMatcher --------------------------------------------------===// + +std::map LLTOperandMatcher::TypeIDValues; + +MatchTableRecord LLTOperandMatcher::getValue() const { + const auto VI = TypeIDValues.find(Ty); + if (VI == TypeIDValues.end()) + return MatchTable::NamedValue(getTy().getCxxEnumValue()); + return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second); +} + +bool LLTOperandMatcher::hasValue() const { + if (TypeIDValues.size() != KnownTypes.size()) + initTypeIDValuesMap(); + return TypeIDValues.count(Ty); +} + +void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI") + << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") + << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type") + << getValue() << MatchTable::LineBreak; +} + +//===- PointerToAnyOperandMatcher -----------------------------------------===// + +void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckPointerToAny") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("SizeInBits") << MatchTable::IntValue(SizeInBits) + << MatchTable::LineBreak; +} + +//===- RecordNamedOperandMatcher ------------------------------------------===// + +void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_RecordNamedOperand") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("StoreIdx") << MatchTable::IntValue(StoreIdx) + << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak; +} + +//===- ComplexPatternOperandMatcher ---------------------------------------===// + +void ComplexPatternOperandMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + unsigned ID = getAllocatedTemporariesBaseID(); + Table << MatchTable::Opcode("GIM_CheckComplexPattern") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID) + << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str()) + << MatchTable::LineBreak; +} + +unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const { + return Operand.getAllocatedTemporariesBaseID(); +} + +//===- RegisterBankOperandMatcher -----------------------------------------===// + +bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const { + return OperandPredicateMatcher::isIdentical(B) && + RC.getDef() == cast(&B)->RC.getDef(); +} + +void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckRegBankForClass") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("RC") + << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID") + << MatchTable::LineBreak; +} + +//===- MBBOperandMatcher --------------------------------------------------===// + +void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI") + << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") + << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak; +} + +//===- ImmOperandMatcher --------------------------------------------------===// + +void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI") + << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") + << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak; +} + +//===- ConstantIntOperandMatcher ------------------------------------------===// + +void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckConstantInt") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::IntValue(Value) << MatchTable::LineBreak; +} + +//===- LiteralIntOperandMatcher -------------------------------------------===// + +void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckLiteralInt") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::IntValue(Value) << MatchTable::LineBreak; +} + +//===- CmpPredicateOperandMatcher -----------------------------------------===// + +void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckCmpPredicate") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("Predicate") + << MatchTable::NamedValue("CmpInst", PredName) << MatchTable::LineBreak; +} + +//===- IntrinsicIDOperandMatcher ------------------------------------------===// + +void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckIntrinsicID") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::NamedValue("Intrinsic::" + II->EnumName) + << MatchTable::LineBreak; +} + +//===- OperandImmPredicateMatcher -----------------------------------------===// + +void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MO") << MatchTable::IntValue(OpIdx) + << MatchTable::Comment("Predicate") + << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) + << MatchTable::LineBreak; +} + +//===- OperandMatcher -----------------------------------------------------===// + +std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const { + return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" + + llvm::to_string(OpIdx) + ")"; +} + +unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); } + +void OperandMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) { + if (!Optimized) { + std::string Comment; + raw_string_ostream CommentOS(Comment); + CommentOS << "MIs[" << getInsnVarID() << "] "; + if (SymbolicName.empty()) + CommentOS << "Operand " << OpIdx; + else + CommentOS << SymbolicName; + Table << MatchTable::Comment(Comment) << MatchTable::LineBreak; + } + + emitPredicateListOpcodes(Table, Rule); +} + +bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) { + // Operand matchers involving more predicates have higher priority. + if (predicates_size() > B.predicates_size()) + return true; + if (predicates_size() < B.predicates_size()) + return false; + + // This assumes that predicates are added in a consistent order. + for (auto &&Predicate : zip(predicates(), B.predicates())) { + if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) + return true; + if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) + return false; + } + + return false; +} + +unsigned OperandMatcher::countRendererFns() { + return std::accumulate( + predicates().begin(), predicates().end(), 0, + [](unsigned A, + const std::unique_ptr &Predicate) { + return A + Predicate->countRendererFns(); + }); +} + +Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy, + bool OperandIsAPointer) { + if (!VTy.isMachineValueType()) + return failUnsupported("unsupported typeset"); + + if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) { + addPredicate(0); + return Error::success(); + } + + auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy); + if (!OpTyOrNone) + return failUnsupported("unsupported type"); + + if (OperandIsAPointer) + addPredicate(OpTyOrNone->get().getSizeInBits()); + else if (VTy.isPointer()) + addPredicate( + LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits())); + else + addPredicate(*OpTyOrNone); + return Error::success(); +} + +//===- InstructionOpcodeMatcher -------------------------------------------===// + +DenseMap + InstructionOpcodeMatcher::OpcodeValues; + +MatchTableRecord +InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const { + const auto VI = OpcodeValues.find(I); + if (VI != OpcodeValues.end()) + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(), + VI->second); + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName()); +} + +void InstructionOpcodeMatcher::initOpcodeValuesMap( + const CodeGenTarget &Target) { + OpcodeValues.clear(); + + unsigned OpcodeValue = 0; + for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue()) + OpcodeValues[I] = OpcodeValue++; +} + +MatchTableRecord InstructionOpcodeMatcher::getValue() const { + assert(Insts.size() == 1); + + const CodeGenInstruction *I = Insts[0]; + const auto VI = OpcodeValues.find(I); + if (VI != OpcodeValues.end()) + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(), + VI->second); + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName()); +} + +void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + StringRef CheckType = + Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither"; + Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI") + << MatchTable::IntValue(InsnVarID); + + for (const CodeGenInstruction *I : Insts) + Table << getInstValue(I); + Table << MatchTable::LineBreak; +} + +bool InstructionOpcodeMatcher::isHigherPriorityThan( + const InstructionPredicateMatcher &B) const { + if (InstructionPredicateMatcher::isHigherPriorityThan(B)) + return true; + if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this)) + return false; + + // Prioritize opcodes for cosmetic reasons in the generated source. Although + // this is cosmetic at the moment, we may want to drive a similar ordering + // using instruction frequency information to improve compile time. + if (const InstructionOpcodeMatcher *BO = + dyn_cast(&B)) + return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName(); + + return false; +} + +bool InstructionOpcodeMatcher::isConstantInstruction() const { + return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT"; +} + +StringRef InstructionOpcodeMatcher::getOpcode() const { + return Insts[0]->TheDef->getName(); +} + +bool InstructionOpcodeMatcher::isVariadicNumOperands() const { + // If one is variadic, they all should be. + return Insts[0]->Operands.isVariadic; +} + +StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const { + // Types expected to be uniform for all alternatives. + return Insts[0]->Operands[OpIdx].OperandType; +} + +//===- InstructionNumOperandsMatcher --------------------------------------===// + +void InstructionNumOperandsMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckNumOperands") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Expected") << MatchTable::IntValue(NumOperands) + << MatchTable::LineBreak; +} + +//===- InstructionImmPredicateMatcher -------------------------------------===// + +bool InstructionImmPredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + return InstructionPredicateMatcher::isIdentical(B) && + Predicate.getOrigPatFragRecord() == + cast(&B) + ->Predicate.getOrigPatFragRecord(); +} + +void InstructionImmPredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate)) + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Predicate") + << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) + << MatchTable::LineBreak; +} + +//===- AtomicOrderingMMOPredicateMatcher ----------------------------------===// + +bool AtomicOrderingMMOPredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + if (!InstructionPredicateMatcher::isIdentical(B)) + return false; + const auto &R = *cast(&B); + return Order == R.Order && Comparator == R.Comparator; +} + +void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + StringRef Opcode = "GIM_CheckAtomicOrdering"; + + if (Comparator == AO_OrStronger) + Opcode = "GIM_CheckAtomicOrderingOrStrongerThan"; + if (Comparator == AO_WeakerThan) + Opcode = "GIM_CheckAtomicOrderingWeakerThan"; + + Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI") + << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order") + << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str()) + << MatchTable::LineBreak; +} + +//===- MemorySizePredicateMatcher -----------------------------------------===// + +void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) + << MatchTable::Comment("Size") << MatchTable::IntValue(Size) + << MatchTable::LineBreak; +} + +//===- MemoryAddressSpacePredicateMatcher ---------------------------------===// + +bool MemoryAddressSpacePredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + if (!InstructionPredicateMatcher::isIdentical(B)) + return false; + auto *Other = cast(&B); + return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces; +} + +void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") + << MatchTable::IntValue(MMOIdx) + // Encode number of address spaces to expect. + << MatchTable::Comment("NumAddrSpace") + << MatchTable::IntValue(AddrSpaces.size()); + for (unsigned AS : AddrSpaces) + Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS); + + Table << MatchTable::LineBreak; +} + +//===- MemoryAlignmentPredicateMatcher ------------------------------------===// + +bool MemoryAlignmentPredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + if (!InstructionPredicateMatcher::isIdentical(B)) + return false; + auto *Other = cast(&B); + return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign; +} + +void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckMemoryAlignment") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) + << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign) + << MatchTable::LineBreak; +} + +//===- MemoryVsLLTSizePredicateMatcher ------------------------------------===// + +bool MemoryVsLLTSizePredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + return InstructionPredicateMatcher::isIdentical(B) && + MMOIdx == cast(&B)->MMOIdx && + Relation == cast(&B)->Relation && + OpIdx == cast(&B)->OpIdx; +} + +void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode( + Relation == EqualTo ? "GIM_CheckMemorySizeEqualToLLT" + : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT" + : "GIM_CheckMemorySizeLessThanLLT") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) + << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) + << MatchTable::LineBreak; +} + +//===- VectorSplatImmPredicateMatcher -------------------------------------===// + +void VectorSplatImmPredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + if (Kind == AllOnes) + Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes"); + else + Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros"); + + Table << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID); + Table << MatchTable::LineBreak; +} + +//===- GenericInstructionPredicateMatcher ---------------------------------===// + +bool GenericInstructionPredicateMatcher::isIdentical( + const PredicateMatcher &B) const { + return InstructionPredicateMatcher::isIdentical(B) && + Predicate == static_cast(B) + .Predicate; +} +void GenericInstructionPredicateMatcher::emitPredicateOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("FnId") + << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) + << MatchTable::LineBreak; +} + +//===- InstructionMatcher -------------------------------------------------===// + +OperandMatcher & +InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName, + unsigned AllocatedTemporariesBaseID) { + Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName, + AllocatedTemporariesBaseID)); + if (!SymbolicName.empty()) + Rule.defineOperand(SymbolicName, *Operands.back()); + + return *Operands.back(); +} + +OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) { + auto I = llvm::find_if(Operands, + [&OpIdx](const std::unique_ptr &X) { + return X->getOpIdx() == OpIdx; + }); + if (I != Operands.end()) + return **I; + llvm_unreachable("Failed to lookup operand"); +} + +OperandMatcher &InstructionMatcher::addPhysRegInput(Record *Reg, unsigned OpIdx, + unsigned TempOpIdx) { + assert(SymbolicName.empty()); + OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx); + Operands.emplace_back(OM); + Rule.definePhysRegOperand(Reg, *OM); + PhysRegInputs.emplace_back(Reg, OpIdx); + return *OM; +} + +void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) { + if (NumOperandsCheck) + InstructionNumOperandsMatcher(InsnVarID, getNumOperands()) + .emitPredicateOpcodes(Table, Rule); + + // First emit all instruction level predicates need to be verified before we + // can verify operands. + emitFilteredPredicateListOpcodes( + [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table, + Rule); + + // Emit all operand constraints. + for (const auto &Operand : Operands) + Operand->emitPredicateOpcodes(Table, Rule); + + // All of the tablegen defined predicates should now be matched. Now emit + // any custom predicates that rely on all generated checks. + emitFilteredPredicateListOpcodes( + [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table, + Rule); +} + +bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) { + // Instruction matchers involving more operands have higher priority. + if (Operands.size() > B.Operands.size()) + return true; + if (Operands.size() < B.Operands.size()) + return false; + + for (auto &&P : zip(predicates(), B.predicates())) { + auto L = static_cast(std::get<0>(P).get()); + auto R = static_cast(std::get<1>(P).get()); + if (L->isHigherPriorityThan(*R)) + return true; + if (R->isHigherPriorityThan(*L)) + return false; + } + + for (auto Operand : zip(Operands, B.Operands)) { + if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand))) + return true; + if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand))) + return false; + } + + return false; +} + +unsigned InstructionMatcher::countRendererFns() { + return std::accumulate( + predicates().begin(), predicates().end(), 0, + [](unsigned A, + const std::unique_ptr &Predicate) { + return A + Predicate->countRendererFns(); + }) + + std::accumulate( + Operands.begin(), Operands.end(), 0, + [](unsigned A, const std::unique_ptr &Operand) { + return A + Operand->countRendererFns(); + }); +} + +void InstructionMatcher::optimize() { + SmallVector, 8> Stash; + const auto &OpcMatcher = getOpcodeMatcher(); + + Stash.push_back(predicates_pop_front()); + if (Stash.back().get() == &OpcMatcher) { + if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands()) + Stash.emplace_back( + new InstructionNumOperandsMatcher(InsnVarID, getNumOperands())); + NumOperandsCheck = false; + + for (auto &OM : Operands) + for (auto &OP : OM->predicates()) + if (isa(OP)) { + Stash.push_back(std::move(OP)); + OM->eraseNullPredicates(); + break; + } + } + + if (InsnVarID > 0) { + assert(!Operands.empty() && "Nested instruction is expected to def a vreg"); + for (auto &OP : Operands[0]->predicates()) + OP.reset(); + Operands[0]->eraseNullPredicates(); + } + for (auto &OM : Operands) { + for (auto &OP : OM->predicates()) + if (isa(OP)) + Stash.push_back(std::move(OP)); + OM->eraseNullPredicates(); + } + while (!Stash.empty()) + prependPredicate(Stash.pop_back_val()); +} + +//===- InstructionOperandMatcher ------------------------------------------===// + +void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const unsigned NewInsnVarID = InsnMatcher->getInsnVarID(); + const bool IgnoreCopies = Flags & GISF_IgnoreCopies; + Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies" + : "GIM_RecordInsn") + << MatchTable::Comment("DefineMI") << MatchTable::IntValue(NewInsnVarID) + << MatchTable::Comment("MI") << MatchTable::IntValue(getInsnVarID()) + << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx()) + << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]") + << MatchTable::LineBreak; +} + +bool InstructionOperandMatcher::isHigherPriorityThan( + const OperandPredicateMatcher &B) const { + if (OperandPredicateMatcher::isHigherPriorityThan(B)) + return true; + if (B.OperandPredicateMatcher::isHigherPriorityThan(*this)) + return false; + + if (const InstructionOperandMatcher *BP = + dyn_cast(&B)) + if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher)) + return true; + return false; +} + +//===- OperandRenderer ----------------------------------------------------===// + +OperandRenderer::~OperandRenderer() {} + +//===- CopyRenderer -------------------------------------------------------===// + +void CopyRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); + Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID") + << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") + << MatchTable::IntValue(Operand.getOpIdx()) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CopyPhysRegRenderer ------------------------------------------------===// + +void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg); + unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); + Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID") + << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") + << MatchTable::IntValue(Operand.getOpIdx()) + << MatchTable::Comment(PhysReg->getName()) << MatchTable::LineBreak; +} + +//===- CopyOrAddZeroRegRenderer -------------------------------------------===// + +void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); + Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg") + << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") + << MatchTable::IntValue(Operand.getOpIdx()) + << MatchTable::NamedValue( + (ZeroRegisterDef->getValue("Namespace") + ? ZeroRegisterDef->getValueAsString("Namespace") + : ""), + ZeroRegisterDef->getName()) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CopyConstantAsImmRenderer ------------------------------------------===// + +void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); + Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm" + : "GIR_CopyConstantAsUImm") + << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CopyFConstantAsFPImmRenderer ---------------------------------------===// + +void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); + Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm") + << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CopySubRegRenderer -------------------------------------------------===// + +void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); + Table << MatchTable::Opcode("GIR_CopySubReg") + << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") + << MatchTable::IntValue(Operand.getOpIdx()) + << MatchTable::Comment("SubRegIdx") + << MatchTable::IntValue(SubReg->EnumValue) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- AddRegisterRenderer ------------------------------------------------===// + +void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIR_AddRegister") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID); + if (RegisterDef->getName() != "zero_reg") { + Table << MatchTable::NamedValue( + (RegisterDef->getValue("Namespace") + ? RegisterDef->getValueAsString("Namespace") + : ""), + RegisterDef->getName()); + } else { + Table << MatchTable::NamedValue(Target.getRegNamespace(), "NoRegister"); + } + Table << MatchTable::Comment("AddRegisterRegFlags"); + + // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are + // really needed for a physical register reference. We can pack the + // register and flags in a single field. + if (IsDef) + Table << MatchTable::NamedValue("RegState::Define"); + else + Table << MatchTable::IntValue(0); + Table << MatchTable::LineBreak; +} + +//===- TempRegRenderer ----------------------------------------------------===// + +void TempRegRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + if (SubRegIdx) { + assert(!IsDef); + Table << MatchTable::Opcode("GIR_AddTempSubRegister"); + } else + Table << MatchTable::Opcode("GIR_AddTempRegister"); + + Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID) + << MatchTable::Comment("TempRegFlags"); + + if (IsDef) { + SmallString<32> RegFlags; + RegFlags += "RegState::Define"; + if (IsDead) + RegFlags += "|RegState::Dead"; + Table << MatchTable::NamedValue(RegFlags); + } else + Table << MatchTable::IntValue(0); + + if (SubRegIdx) + Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName()); + Table << MatchTable::LineBreak; +} + +//===- SubRegIndexRenderer ------------------------------------------------===// + +void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID") + << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex") + << MatchTable::IntValue(SubRegIdx->EnumValue) << MatchTable::LineBreak; +} + +//===- RenderComplexPatternOperand ----------------------------------------===// + +void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode( + SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer" + : "GIR_ComplexSubOperandRenderer") + : "GIR_ComplexRenderer") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("RendererID") + << MatchTable::IntValue(RendererID); + if (SubOperand) + Table << MatchTable::Comment("SubOperand") + << MatchTable::IntValue(*SubOperand); + if (SubReg) + Table << MatchTable::Comment("SubRegIdx") + << MatchTable::IntValue(SubReg->EnumValue); + Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CustomRenderer -----------------------------------------------------===// + +void CustomRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); + Table << MatchTable::Opcode("GIR_CustomRenderer") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("Renderer") + << MatchTable::NamedValue("GICR_" + + Renderer.getValueAsString("RendererFn").str()) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- CustomOperandRenderer ----------------------------------------------===// + +void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName); + Table << MatchTable::Opcode("GIR_CustomOperandRenderer") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OpdMatcher.getInsnVarID()) + << MatchTable::Comment("OpIdx") + << MatchTable::IntValue(OpdMatcher.getOpIdx()) + << MatchTable::Comment("OperandRenderer") + << MatchTable::NamedValue("GICR_" + + Renderer.getValueAsString("RendererFn").str()) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; +} + +//===- BuildMIAction ------------------------------------------------------===// + +bool BuildMIAction::canMutate(RuleMatcher &Rule, + const InstructionMatcher *Insn) const { + if (!Insn) + return false; + + if (OperandRenderers.size() != Insn->getNumOperands()) + return false; + + for (const auto &Renderer : enumerate(OperandRenderers)) { + if (const auto *Copy = dyn_cast(&*Renderer.value())) { + const OperandMatcher &OM = + Rule.getOperandMatcher(Copy->getSymbolicName()); + if (Insn != &OM.getInstructionMatcher() || + OM.getOpIdx() != Renderer.index()) + return false; + } else + return false; + } + + return true; +} + +void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) { + for (auto *MutateCandidate : Rule.mutatable_insns()) { + if (canMutate(Rule, MutateCandidate)) { + // Take the first one we're offered that we're able to mutate. + Rule.reserveInsnMatcherForMutation(MutateCandidate); + Matched = MutateCandidate; + return; + } + } +} + +void BuildMIAction::emitActionOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + if (Matched) { + assert(canMutate(Rule, Matched) && + "Arranged to mutate an insn that isn't mutatable"); + + unsigned RecycleInsnID = Rule.getInsnVarID(*Matched); + Table << MatchTable::Opcode("GIR_MutateOpcode") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("RecycleInsnID") + << MatchTable::IntValue(RecycleInsnID) + << MatchTable::Comment("Opcode") + << MatchTable::NamedValue(I->Namespace, I->TheDef->getName()) + << MatchTable::LineBreak; + + if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) { + for (auto *Def : I->ImplicitDefs) { + auto Namespace = Def->getValue("Namespace") + ? Def->getValueAsString("Namespace") + : ""; + Table << MatchTable::Opcode("GIR_AddImplicitDef") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::NamedValue(Namespace, Def->getName()) + << MatchTable::LineBreak; + } + for (auto *Use : I->ImplicitUses) { + auto Namespace = Use->getValue("Namespace") + ? Use->getValueAsString("Namespace") + : ""; + Table << MatchTable::Opcode("GIR_AddImplicitUse") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::NamedValue(Namespace, Use->getName()) + << MatchTable::LineBreak; + } + } + return; + } + + // TODO: Simple permutation looks like it could be almost as common as + // mutation due to commutative operations. + + Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID") + << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode") + << MatchTable::NamedValue(I->Namespace, I->TheDef->getName()) + << MatchTable::LineBreak; + for (const auto &Renderer : OperandRenderers) + Renderer->emitRenderOpcodes(Table, Rule); + + if (I->mayLoad || I->mayStore) { + Table << MatchTable::Opcode("GIR_MergeMemOperands") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("MergeInsnID's"); + // Emit the ID's for all the instructions that are matched by this rule. + // TODO: Limit this to matched instructions that mayLoad/mayStore or have + // some other means of having a memoperand. Also limit this to + // emitted instructions that expect to have a memoperand too. For + // example, (G_SEXT (G_LOAD x)) that results in separate load and + // sign-extend instructions shouldn't put the memoperand on the + // sign-extend since it has no effect there. + std::vector MergeInsnIDs; + for (const auto &IDMatcherPair : Rule.defined_insn_vars()) + MergeInsnIDs.push_back(IDMatcherPair.second); + llvm::sort(MergeInsnIDs); + for (const auto &MergeInsnID : MergeInsnIDs) + Table << MatchTable::IntValue(MergeInsnID); + Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList") + << MatchTable::LineBreak; + } + + // FIXME: This is a hack but it's sufficient for ISel. We'll need to do + // better for combines. Particularly when there are multiple match + // roots. + if (InsnID == 0) + Table << MatchTable::Opcode("GIR_EraseFromParent") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::LineBreak; +} + +//===- ConstrainOperandToRegClassAction -----------------------------------===// + +void ConstrainOperandToRegClassAction::emitActionOpcodes( + MatchTable &Table, RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIR_ConstrainOperandRC") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) + << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID") + << MatchTable::LineBreak; +} + +//===- MakeTempRegisterAction ---------------------------------------------===// + +void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table, + RuleMatcher &Rule) const { + Table << MatchTable::Opcode("GIR_MakeTempReg") + << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID) + << MatchTable::Comment("TypeID") + << MatchTable::NamedValue(Ty.getCxxEnumValue()) + << MatchTable::LineBreak; +} + +} // namespace gi +} // namespace llvm