diff options
Diffstat (limited to 'llvm/utils/TableGen/Common/GlobalISel/Patterns.h')
| -rw-r--r-- | llvm/utils/TableGen/Common/GlobalISel/Patterns.h | 706 |
1 files changed, 706 insertions, 0 deletions
diff --git a/llvm/utils/TableGen/Common/GlobalISel/Patterns.h b/llvm/utils/TableGen/Common/GlobalISel/Patterns.h new file mode 100644 index 000000000000..dac092556548 --- /dev/null +++ b/llvm/utils/TableGen/Common/GlobalISel/Patterns.h @@ -0,0 +1,706 @@ +//===- Patterns.h ----------------------------------------------*- C++ -*-===// +// +// 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 Contains the Pattern hierarchy alongside helper classes such as +/// PatFrag, MIFlagsInfo, PatternType, etc. +/// +/// These classes are used by the GlobalISel Combiner backend to help parse, +/// process and emit MIR patterns. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_GLOBALISEL_PATTERNS_H +#define LLVM_UTILS_GLOBALISEL_PATTERNS_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Twine.h" +#include <memory> +#include <optional> +#include <string> + +namespace llvm { + +class Record; +class SMLoc; +class StringInit; +class CodeExpansions; +class CodeGenInstruction; +struct CodeGenIntrinsic; + +namespace gi { + +class CXXPredicateCode; +class LLTCodeGen; +class LLTCodeGenOrTempType; +class RuleMatcher; + +//===- PatternType --------------------------------------------------------===// + +/// Represent the type of a Pattern Operand. +/// +/// Types have two form: +/// - LLTs, which are straightforward. +/// - Special types, e.g. GITypeOf +class PatternType { +public: + static constexpr StringLiteral SpecialTyClassName = "GISpecialType"; + static constexpr StringLiteral TypeOfClassName = "GITypeOf"; + + enum PTKind : uint8_t { + PT_None, + + PT_ValueType, + PT_TypeOf, + }; + + PatternType() : Kind(PT_None), Data() {} + + static std::optional<PatternType> get(ArrayRef<SMLoc> DiagLoc, + const Record *R, Twine DiagCtx); + static PatternType getTypeOf(StringRef OpName); + + bool isNone() const { return Kind == PT_None; } + bool isLLT() const { return Kind == PT_ValueType; } + bool isSpecial() const { return isTypeOf(); } + bool isTypeOf() const { return Kind == PT_TypeOf; } + + StringRef getTypeOfOpName() const; + const Record *getLLTRecord() const; + + explicit operator bool() const { return !isNone(); } + + bool operator==(const PatternType &Other) const; + bool operator!=(const PatternType &Other) const { return !operator==(Other); } + + std::string str() const; + +private: + PatternType(PTKind Kind) : Kind(Kind), Data() {} + + PTKind Kind; + union DataT { + DataT() : Str() {} + + /// PT_ValueType -> ValueType Def. + const Record *Def; + + /// PT_TypeOf -> Operand name (without the '$') + StringRef Str; + } Data; +}; + +//===- Pattern Base Class -------------------------------------------------===// + +/// Base class for all patterns that can be written in an `apply`, `match` or +/// `pattern` DAG operator. +/// +/// For example: +/// +/// (apply (G_ZEXT $x, $y), (G_ZEXT $y, $z), "return isFoo(${z})") +/// +/// Creates 3 Pattern objects: +/// - Two CodeGenInstruction Patterns +/// - A CXXPattern +class Pattern { +public: + enum { + K_AnyOpcode, + K_CXX, + + K_CodeGenInstruction, + K_PatFrag, + K_Builtin, + }; + + virtual ~Pattern() = default; + + unsigned getKind() const { return Kind; } + const char *getKindName() const; + + bool hasName() const { return !Name.empty(); } + StringRef getName() const { return Name; } + + virtual void print(raw_ostream &OS, bool PrintName = true) const = 0; + void dump() const; + +protected: + Pattern(unsigned Kind, StringRef Name) : Kind(Kind), Name(Name) { + assert(!Name.empty() && "unnamed pattern!"); + } + + void printImpl(raw_ostream &OS, bool PrintName, + function_ref<void()> ContentPrinter) const; + +private: + unsigned Kind; + StringRef Name; +}; + +//===- AnyOpcodePattern ---------------------------------------------------===// + +/// `wip_match_opcode` patterns. +/// This matches one or more opcodes, and does not check any operands +/// whatsoever. +/// +/// TODO: Long-term, this needs to be removed. It's a hack around MIR +/// pattern matching limitations. +class AnyOpcodePattern : public Pattern { +public: + AnyOpcodePattern(StringRef Name) : Pattern(K_AnyOpcode, Name) {} + + static bool classof(const Pattern *P) { return P->getKind() == K_AnyOpcode; } + + void addOpcode(const CodeGenInstruction *I) { Insts.push_back(I); } + const auto &insts() const { return Insts; } + + void print(raw_ostream &OS, bool PrintName = true) const override; + +private: + SmallVector<const CodeGenInstruction *, 4> Insts; +}; + +//===- CXXPattern ---------------------------------------------------------===// + +/// Represents raw C++ code which may need some expansions. +/// +/// e.g. [{ return isFooBux(${src}.getReg()); }] +/// +/// For the expanded code, \see CXXPredicateCode. CXXPredicateCode objects are +/// created through `expandCode`. +/// +/// \see CodeExpander and \see CodeExpansions for more information on code +/// expansions. +/// +/// This object has two purposes: +/// - Represent C++ code as a pattern entry. +/// - Be a factory for expanded C++ code. +/// - It's immutable and only holds the raw code so we can expand the same +/// CXX pattern multiple times if we need to. +/// +/// Note that the code is always trimmed in the constructor, so leading and +/// trailing whitespaces are removed. This removes bloat in the output, avoids +/// formatting issues, but also allows us to check things like +/// `.startswith("return")` trivially without worrying about spaces. +class CXXPattern : public Pattern { +public: + CXXPattern(const StringInit &Code, StringRef Name); + + CXXPattern(StringRef Code, StringRef Name) + : Pattern(K_CXX, Name), RawCode(Code.trim().str()) {} + + static bool classof(const Pattern *P) { return P->getKind() == K_CXX; } + + void setIsApply(bool Value = true) { IsApply = Value; } + StringRef getRawCode() const { return RawCode; } + + /// Expands raw code, replacing things such as `${foo}` with their + /// substitution in \p CE. + /// + /// \param CE Map of Code Expansions + /// \param Locs SMLocs for the Code Expander, in case it needs to emit + /// diagnostics. + /// \param AddComment Optionally called to emit a comment before the expanded + /// code. + /// + /// \return A CXXPredicateCode object that contains the expanded code. Note + /// that this may or may not insert a new object. All CXXPredicateCode objects + /// are held in a set to avoid emitting duplicate C++ code. + const CXXPredicateCode & + expandCode(const CodeExpansions &CE, ArrayRef<SMLoc> Locs, + function_ref<void(raw_ostream &)> AddComment = {}) const; + + void print(raw_ostream &OS, bool PrintName = true) const override; + +private: + bool IsApply = false; + std::string RawCode; +}; + +//===- InstructionPattern ---------------------------------------------===// + +/// An operand for an InstructionPattern. +/// +/// Operands are composed of three elements: +/// - (Optional) Value +/// - (Optional) Name +/// - (Optional) Type +/// +/// Some examples: +/// (i32 0):$x -> V=int(0), Name='x', Type=i32 +/// 0:$x -> V=int(0), Name='x' +/// $x -> Name='x' +/// i32:$x -> Name='x', Type = i32 +class InstructionOperand { +public: + using IntImmTy = int64_t; + + InstructionOperand(IntImmTy Imm, StringRef Name, PatternType Type) + : Value(Imm), Name(Name), Type(Type) {} + + InstructionOperand(StringRef Name, PatternType Type) + : Name(Name), Type(Type) {} + + bool isNamedImmediate() const { return hasImmValue() && isNamedOperand(); } + + bool hasImmValue() const { return Value.has_value(); } + IntImmTy getImmValue() const { return *Value; } + + bool isNamedOperand() const { return !Name.empty(); } + StringRef getOperandName() const { + assert(isNamedOperand() && "Operand is unnamed"); + return Name; + } + + InstructionOperand withNewName(StringRef NewName) const { + InstructionOperand Result = *this; + Result.Name = NewName; + return Result; + } + + void setIsDef(bool Value = true) { Def = Value; } + bool isDef() const { return Def; } + + void setType(PatternType NewType) { + assert((!Type || (Type == NewType)) && "Overwriting type!"); + Type = NewType; + } + PatternType getType() const { return Type; } + + std::string describe() const; + void print(raw_ostream &OS) const; + + void dump() const; + +private: + std::optional<int64_t> Value; + StringRef Name; + PatternType Type; + bool Def = false; +}; + +/// Base class for CodeGenInstructionPattern & PatFragPattern, which handles all +/// the boilerplate for patterns that have a list of operands for some (pseudo) +/// instruction. +class InstructionPattern : public Pattern { +public: + virtual ~InstructionPattern() = default; + + static bool classof(const Pattern *P) { + return P->getKind() == K_CodeGenInstruction || P->getKind() == K_PatFrag || + P->getKind() == K_Builtin; + } + + template <typename... Ty> void addOperand(Ty &&...Init) { + Operands.emplace_back(std::forward<Ty>(Init)...); + } + + auto &operands() { return Operands; } + const auto &operands() const { return Operands; } + unsigned operands_size() const { return Operands.size(); } + InstructionOperand &getOperand(unsigned K) { return Operands[K]; } + const InstructionOperand &getOperand(unsigned K) const { return Operands[K]; } + + /// When this InstructionPattern is used as the match root, returns the + /// operands that must be redefined in the 'apply' pattern for the rule to be + /// valid. + /// + /// For most patterns, this just returns the defs. + /// For PatFrag this only returns the root of the PF. + /// + /// Returns an empty array on error. + virtual ArrayRef<InstructionOperand> getApplyDefsNeeded() const { + return {operands().begin(), getNumInstDefs()}; + } + + auto named_operands() { + return make_filter_range(Operands, + [&](auto &O) { return O.isNamedOperand(); }); + } + + auto named_operands() const { + return make_filter_range(Operands, + [&](auto &O) { return O.isNamedOperand(); }); + } + + virtual bool isVariadic() const { return false; } + virtual unsigned getNumInstOperands() const = 0; + virtual unsigned getNumInstDefs() const = 0; + + bool hasAllDefs() const { return operands_size() >= getNumInstDefs(); } + + virtual StringRef getInstName() const = 0; + + /// Diagnoses all uses of special types in this Pattern and returns true if at + /// least one diagnostic was emitted. + bool diagnoseAllSpecialTypes(ArrayRef<SMLoc> Loc, Twine Msg) const; + + void reportUnreachable(ArrayRef<SMLoc> Locs) const; + virtual bool checkSemantics(ArrayRef<SMLoc> Loc); + + void print(raw_ostream &OS, bool PrintName = true) const override; + +protected: + InstructionPattern(unsigned K, StringRef Name) : Pattern(K, Name) {} + + virtual void printExtras(raw_ostream &OS) const {} + + SmallVector<InstructionOperand, 4> Operands; +}; + +//===- OperandTable -------------------------------------------------------===// + +/// Maps InstructionPattern operands to their definitions. This allows us to tie +/// different patterns of a (apply), (match) or (patterns) set of patterns +/// together. +class OperandTable { +public: + bool addPattern(InstructionPattern *P, + function_ref<void(StringRef)> DiagnoseRedef); + + struct LookupResult { + LookupResult() = default; + LookupResult(InstructionPattern *Def) : Found(true), Def(Def) {} + + bool Found = false; + InstructionPattern *Def = nullptr; + + bool isLiveIn() const { return Found && !Def; } + }; + + LookupResult lookup(StringRef OpName) const { + if (auto It = Table.find(OpName); It != Table.end()) + return LookupResult(It->second); + return LookupResult(); + } + + InstructionPattern *getDef(StringRef OpName) const { + return lookup(OpName).Def; + } + + void print(raw_ostream &OS, StringRef Name = "", StringRef Indent = "") const; + + auto begin() const { return Table.begin(); } + auto end() const { return Table.end(); } + + void dump() const; + +private: + StringMap<InstructionPattern *> Table; +}; + +//===- MIFlagsInfo --------------------------------------------------------===// + +/// Helper class to contain data associated with a MIFlags operand. +class MIFlagsInfo { +public: + void addSetFlag(const Record *R); + void addUnsetFlag(const Record *R); + void addCopyFlag(StringRef InstName); + + const auto &set_flags() const { return SetF; } + const auto &unset_flags() const { return UnsetF; } + const auto ©_flags() const { return CopyF; } + +private: + SetVector<StringRef> SetF, UnsetF, CopyF; +}; + +//===- CodeGenInstructionPattern ------------------------------------------===// + +/// Matches an instruction or intrinsic: +/// e.g. `G_ADD $x, $y, $z` or `int_amdgcn_cos $a` +/// +/// Intrinsics are just normal instructions with a special operand for intrinsic +/// ID. Despite G_INTRINSIC opcodes being variadic, we consider that the +/// Intrinsic's info takes priority. This means we return: +/// - false for isVariadic() and other variadic-related queries. +/// - getNumInstDefs and getNumInstOperands use the intrinsic's in/out +/// operands. +class CodeGenInstructionPattern : public InstructionPattern { +public: + CodeGenInstructionPattern(const CodeGenInstruction &I, StringRef Name) + : InstructionPattern(K_CodeGenInstruction, Name), I(I) {} + + static bool classof(const Pattern *P) { + return P->getKind() == K_CodeGenInstruction; + } + + bool is(StringRef OpcodeName) const; + + void setIntrinsic(const CodeGenIntrinsic *I) { IntrinInfo = I; } + const CodeGenIntrinsic *getIntrinsic() const { return IntrinInfo; } + bool isIntrinsic() const { return IntrinInfo; } + + bool hasVariadicDefs() const; + bool isVariadic() const override; + unsigned getNumInstDefs() const override; + unsigned getNumInstOperands() const override; + + MIFlagsInfo &getOrCreateMIFlagsInfo(); + const MIFlagsInfo *getMIFlagsInfo() const { return FI.get(); } + + const CodeGenInstruction &getInst() const { return I; } + StringRef getInstName() const override; + +private: + void printExtras(raw_ostream &OS) const override; + + const CodeGenInstruction &I; + const CodeGenIntrinsic *IntrinInfo = nullptr; + std::unique_ptr<MIFlagsInfo> FI; +}; + +//===- OperandTypeChecker -------------------------------------------------===// + +/// This is a trivial type checker for all operands in a set of +/// InstructionPatterns. +/// +/// It infers the type of each operand, check it's consistent with the known +/// type of the operand, and then sets all of the types in all operands in +/// propagateTypes. +/// +/// It also handles verifying correctness of special types. +class OperandTypeChecker { +public: + OperandTypeChecker(ArrayRef<SMLoc> DiagLoc) : DiagLoc(DiagLoc) {} + + /// Step 1: Check each pattern one by one. All patterns that pass through here + /// are added to a common worklist so propagateTypes can access them. + bool check(InstructionPattern &P, + std::function<bool(const PatternType &)> VerifyTypeOfOperand); + + /// Step 2: Propagate all types. e.g. if one use of "$a" has type i32, make + /// all uses of "$a" have type i32. + void propagateTypes(); + +protected: + ArrayRef<SMLoc> DiagLoc; + +private: + using InconsistentTypeDiagFn = std::function<void()>; + + void PrintSeenWithTypeIn(InstructionPattern &P, StringRef OpName, + PatternType Ty) const; + + struct OpTypeInfo { + PatternType Type; + InconsistentTypeDiagFn PrintTypeSrcNote = []() {}; + }; + + StringMap<OpTypeInfo> Types; + + SmallVector<InstructionPattern *, 16> Pats; +}; + +//===- PatFrag ------------------------------------------------------------===// + +/// Represents a parsed GICombinePatFrag. This can be thought of as the +/// equivalent of a CodeGenInstruction, but for PatFragPatterns. +/// +/// PatFrags are made of 3 things: +/// - Out parameters (defs) +/// - In parameters +/// - A set of pattern lists (alternatives). +/// +/// If the PatFrag uses instruction patterns, the root must be one of the defs. +/// +/// Note that this DOES NOT represent the use of the PatFrag, only its +/// definition. The use of the PatFrag in a Pattern is represented by +/// PatFragPattern. +/// +/// PatFrags use the term "parameter" instead of operand because they're +/// essentially macros, and using that name avoids confusion. Other than that, +/// they're structured similarly to a MachineInstruction - all parameters +/// (operands) are in the same list, with defs at the start. This helps mapping +/// parameters to values, because, param N of a PatFrag is always operand N of a +/// PatFragPattern. +class PatFrag { +public: + static constexpr StringLiteral ClassName = "GICombinePatFrag"; + + enum ParamKind { + PK_Root, + PK_MachineOperand, + PK_Imm, + }; + + struct Param { + StringRef Name; + ParamKind Kind; + }; + + using ParamVec = SmallVector<Param, 4>; + using ParamIt = ParamVec::const_iterator; + + /// Represents an alternative of the PatFrag. When parsing a GICombinePatFrag, + /// this is created from its "Alternatives" list. Each alternative is a list + /// of patterns written wrapped in a `(pattern ...)` dag init. + /// + /// Each argument to the `pattern` DAG operator is parsed into a Pattern + /// instance. + struct Alternative { + OperandTable OpTable; + SmallVector<std::unique_ptr<Pattern>, 4> Pats; + }; + + explicit PatFrag(const Record &Def); + + static StringRef getParamKindStr(ParamKind OK); + + StringRef getName() const; + + const Record &getDef() const { return Def; } + ArrayRef<SMLoc> getLoc() const; + + Alternative &addAlternative() { return Alts.emplace_back(); } + const Alternative &getAlternative(unsigned K) const { return Alts[K]; } + unsigned num_alternatives() const { return Alts.size(); } + + void addInParam(StringRef Name, ParamKind Kind); + iterator_range<ParamIt> in_params() const; + unsigned num_in_params() const { return Params.size() - NumOutParams; } + + void addOutParam(StringRef Name, ParamKind Kind); + iterator_range<ParamIt> out_params() const; + unsigned num_out_params() const { return NumOutParams; } + + unsigned num_roots() const; + unsigned num_params() const { return num_in_params() + num_out_params(); } + + /// Finds the operand \p Name and returns its index or -1 if not found. + /// Remember that all params are part of the same list, with out params at the + /// start. This means that the index returned can be used to access operands + /// of InstructionPatterns. + unsigned getParamIdx(StringRef Name) const; + const Param &getParam(unsigned K) const { return Params[K]; } + + bool canBeMatchRoot() const { return num_roots() == 1; } + + void print(raw_ostream &OS, StringRef Indent = "") const; + void dump() const; + + /// Checks if the in-param \p ParamName can be unbound or not. + /// \p ArgName is the name of the argument passed to the PatFrag. + /// + /// An argument can be unbound only if, for all alternatives: + /// - There is no CXX pattern, OR: + /// - There is an InstructionPattern that binds the parameter. + /// + /// e.g. in (MyPatFrag $foo), if $foo has never been seen before (= it's + /// unbound), this checks if MyPatFrag supports it or not. + bool handleUnboundInParam(StringRef ParamName, StringRef ArgName, + ArrayRef<SMLoc> DiagLoc) const; + + bool checkSemantics(); + bool buildOperandsTables(); + +private: + static void printParamsList(raw_ostream &OS, iterator_range<ParamIt> Params); + + void PrintError(Twine Msg) const; + + const Record &Def; + unsigned NumOutParams = 0; + ParamVec Params; + SmallVector<Alternative, 2> Alts; +}; + +//===- PatFragPattern -----------------------------------------------------===// + +/// Represents a use of a GICombinePatFrag. +class PatFragPattern : public InstructionPattern { +public: + PatFragPattern(const PatFrag &PF, StringRef Name) + : InstructionPattern(K_PatFrag, Name), PF(PF) {} + + static bool classof(const Pattern *P) { return P->getKind() == K_PatFrag; } + + const PatFrag &getPatFrag() const { return PF; } + StringRef getInstName() const override { return PF.getName(); } + + unsigned getNumInstDefs() const override { return PF.num_out_params(); } + unsigned getNumInstOperands() const override { return PF.num_params(); } + + ArrayRef<InstructionOperand> getApplyDefsNeeded() const override; + + bool checkSemantics(ArrayRef<SMLoc> DiagLoc) override; + + /// Before emitting the patterns inside the PatFrag, add all necessary code + /// expansions to \p PatFragCEs imported from \p ParentCEs. + /// + /// For a MachineOperand PatFrag parameter, this will fetch the expansion for + /// that operand from \p ParentCEs and add it to \p PatFragCEs. Errors can be + /// emitted if the MachineOperand reference is unbound. + /// + /// For an Immediate PatFrag parameter this simply adds the integer value to + /// \p PatFragCEs as an expansion. + /// + /// \param ParentCEs Contains all of the code expansions declared by the other + /// patterns emitted so far in the pattern list containing + /// this PatFragPattern. + /// \param PatFragCEs Output Code Expansions (usually empty) + /// \param DiagLoc Diagnostic loc in case an error occurs. + /// \return `true` on success, `false` on failure. + bool mapInputCodeExpansions(const CodeExpansions &ParentCEs, + CodeExpansions &PatFragCEs, + ArrayRef<SMLoc> DiagLoc) const; + +private: + const PatFrag &PF; +}; + +//===- BuiltinPattern -----------------------------------------------------===// + +/// Represents builtin instructions such as "GIReplaceReg" and "GIEraseRoot". +enum BuiltinKind { + BI_ReplaceReg, + BI_EraseRoot, +}; + +class BuiltinPattern : public InstructionPattern { + struct BuiltinInfo { + StringLiteral DefName; + BuiltinKind Kind; + unsigned NumOps; + unsigned NumDefs; + }; + + static constexpr std::array<BuiltinInfo, 2> KnownBuiltins = {{ + {"GIReplaceReg", BI_ReplaceReg, 2, 1}, + {"GIEraseRoot", BI_EraseRoot, 0, 0}, + }}; + +public: + static constexpr StringLiteral ClassName = "GIBuiltinInst"; + + BuiltinPattern(const Record &Def, StringRef Name) + : InstructionPattern(K_Builtin, Name), I(getBuiltinInfo(Def)) {} + + static bool classof(const Pattern *P) { return P->getKind() == K_Builtin; } + + unsigned getNumInstOperands() const override { return I.NumOps; } + unsigned getNumInstDefs() const override { return I.NumDefs; } + StringRef getInstName() const override { return I.DefName; } + BuiltinKind getBuiltinKind() const { return I.Kind; } + + bool checkSemantics(ArrayRef<SMLoc> Loc) override; + +private: + static BuiltinInfo getBuiltinInfo(const Record &Def); + + BuiltinInfo I; +}; + +} // namespace gi +} // end namespace llvm + +#endif // ifndef LLVM_UTILS_GLOBALISEL_PATTERNS_H |
