llvm/llvm/utils/TableGen/Common/GlobalISel/GlobalISelMatchTable.h

//===- 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 `GIMatchTableExecutorImpl.h` to match & apply ISel patterns.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_UTILS_TABLEGEN_COMMON_GLOBALISEL_GLOBALISELMATCHTABLE_H
#define LLVM_UTILS_TABLEGEN_COMMON_GLOBALISEL_GLOBALISELMATCHTABLE_H

#include "Common/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/CodeGenTypes/LowLevelType.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/SaveAndRestore.h"
#include <deque>
#include <list>
#include <map>
#include <memory>
#include <optional>
#include <set>
#include <string>
#include <vector>

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 { … };

GISelFlags;

//===- Helper functions ---------------------------------------------------===//

void emitEncodingMacrosDef(raw_ostream &OS);
void emitEncodingMacrosUndef(raw_ostream &OS);

std::string getNameForFeatureBitset(ArrayRef<const Record *> FeatureBitset,
                                    int HwModeIdx);

/// 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 <class GroupT>
std::vector<Matcher *>
optimizeRules(ArrayRef<Matcher *> Rules,
              std::vector<std::unique_ptr<Matcher>> &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 { … };

/// Holds the contents of a generated MatchTable to enable formatting and the
/// necessary index tracking needed to support GIM_Try.
class MatchTable { … };

inline MatchTable &operator<<(MatchTable &Table,
                              const MatchTableRecord &Value) { … }

/// This class stands in for LLT wherever we want to tablegen-erate an
/// equivalent at compiler run-time.
class LLTCodeGen { … };

// Track all types that are used so we can emit the corresponding enum.
extern std::set<LLTCodeGen> 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<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT);

TempTypeIdx;
class LLTCodeGenOrTempType { … };

inline MatchTable &operator<<(MatchTable &Table,
                              const LLTCodeGenOrTempType &Ty) { … }

//===- Matchers -----------------------------------------------------------===//
class Matcher { … };

class GroupMatcher final : public Matcher { … };

class SwitchMatcher : public Matcher { … };

/// Generates code to check that a match rule matches.
class RuleMatcher : public Matcher { … };

template <class PredicateTy> class PredicateListMatcher { … };

class PredicateMatcher { … };

/// 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 { … };

template <>
inline std::string
PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const { … }

/// Generates code to check that a register operand is defined by the same exact
/// one as another.
class SameOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is a particular LLT.
class LLTOperandMatcher : public OperandPredicateMatcher { … };

/// 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 { … };

/// 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 { … };

/// Generates code to store a register operand's type into the set of temporary
/// LLTs.
class RecordRegisterType : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is a particular target constant.
class ComplexPatternOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is in a particular register bank.
class RegisterBankOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is a basic block.
class MBBOperandMatcher : public OperandPredicateMatcher { … };

class ImmOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is a G_CONSTANT with a particular
/// int.
class ConstantIntOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is a raw int (where MO.isImm() or
/// MO.isCImm() is true).
class LiteralIntOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is an CmpInst predicate
class CmpPredicateOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that an operand is an intrinsic ID.
class IntrinsicIDOperandMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that this operand is an immediate whose value meets
/// an immediate predicate.
class OperandImmPredicateMatcher : public OperandPredicateMatcher { … };

/// Generates code to check that a set of predicates match for a particular
/// operand.
class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> { … };

/// 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 { … };

template <>
inline std::string
PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const { … }

/// Generates code to check the opcode of an instruction.
class InstructionOpcodeMatcher : public InstructionPredicateMatcher { … };

class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher { … };

/// 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)<<P:Predicate_simm8>>:$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 { … };

/// Generates code to check that a memory instruction has a atomic ordering
/// MachineMemoryOperand.
class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher { … };

/// Generates code to check that the size of an MMO is exactly N bytes.
class MemorySizePredicateMatcher : public InstructionPredicateMatcher { … };

class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher { … };

class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher { … };

/// 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 { … };

// Matcher for immAllOnesV/immAllZerosV
class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher { … };

/// Generates code to check an arbitrary C++ instruction predicate.
class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher { … };

class MIFlagsInstructionPredicateMatcher : public InstructionPredicateMatcher { … };

/// 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 { … };

/// Generates code to check that the first result has only one use.
class OneUsePredicateMatcher : public InstructionPredicateMatcher { … };

/// 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<PredicateMatcher> { … };

/// 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 { … };

//===- Actions ------------------------------------------------------------===//
class OperandRenderer { … };

/// A CopyRenderer emits code to copy a single operand from an existing
/// instruction to the one being built.
class CopyRenderer : public OperandRenderer { … };

/// A CopyRenderer emits code to copy a virtual register to a specific physical
/// register.
class CopyPhysRegRenderer : public OperandRenderer { … };

/// 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 { … };

/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
/// an extended immediate operand.
class CopyConstantAsImmRenderer : public OperandRenderer { … };

/// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
/// instruction to an extended immediate operand.
class CopyFConstantAsFPImmRenderer : public OperandRenderer { … };

/// 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 { … };

/// Adds a specific physical register to the instruction being built.
/// This is typically useful for WZR/XZR on AArch64.
class AddRegisterRenderer : public OperandRenderer { … };

/// 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 { … };

/// Adds a specific immediate to the instruction being built.
/// If a LLT is passed, a ConstantInt immediate is created instead.
class ImmRenderer : public OperandRenderer { … };

/// Adds an enum value for a subreg index to the instruction being built.
class SubRegIndexRenderer : public OperandRenderer { … };

/// Adds operands by calling a renderer function supplied by the ComplexPattern
/// matcher function.
class RenderComplexPatternOperand : public OperandRenderer { … };

/// Adds an intrinsic ID operand to the instruction being built.
class IntrinsicIDRenderer : public OperandRenderer { … };

class CustomRenderer : public OperandRenderer { … };

class CustomOperandRenderer : public OperandRenderer { … };

/// 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 { … };

/// Generates a comment describing the matched rule being acted upon.
class DebugCommentAction : public MatchAction { … };

/// Generates code to build an instruction or mutate an existing instruction
/// into the desired instruction when this is possible.
class BuildMIAction : public MatchAction { … };

/// Generates code to create a constant that defines a TempReg.
/// The instruction created is usually a G_CONSTANT but it could also be a
/// G_BUILD_VECTOR for vector types.
class BuildConstantAction : public MatchAction { … };

class EraseInstAction : public MatchAction { … };

class ReplaceRegAction : public MatchAction { … };

/// 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 { … };

/// Generates code to constrain the specified operand of an output instruction
/// to the specified register class.
class ConstrainOperandToRegClassAction : public MatchAction { … };

/// Generates code to create a temporary register which can be used to chain
/// instructions together.
class MakeTempRegisterAction : public MatchAction { … };

} // namespace gi
} // namespace llvm

#endif // LLVM_UTILS_TABLEGEN_COMMON_GLOBALISEL_GLOBALISELMATCHTABLE_H