llvm/llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp

//===- GlobalISelCombinerMatchTableEmitter.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
//
//===----------------------------------------------------------------------===//
//
/// \file Generate a combiner implementation for GlobalISel from a declarative
/// syntax using GlobalISelMatchTable.
///
/// Usually, TableGen backends use "assert is an error" as a means to report
/// invalid input. They try to diagnose common case but don't try very hard and
/// crashes can be common. This backend aims to behave closer to how a language
/// compiler frontend would behave: we try extra hard to diagnose invalid inputs
/// early, and any crash should be considered a bug (= a feature or diagnostic
/// is missing).
///
/// While this can make the backend a bit more complex than it needs to be, it
/// pays off because MIR patterns can get complicated. Giving useful error
/// messages to combine writers can help boost their productivity.
///
/// As with anything, a good balance has to be found. We also don't want to
/// write hundreds of lines of code to detect edge cases. In practice, crashing
/// very occasionally, or giving poor errors in some rare instances, is fine.
///
//===----------------------------------------------------------------------===//

#include "Basic/CodeGenIntrinsics.h"
#include "Common/CodeGenInstruction.h"
#include "Common/CodeGenTarget.h"
#include "Common/GlobalISel/CXXPredicates.h"
#include "Common/GlobalISel/CodeExpander.h"
#include "Common/GlobalISel/CodeExpansions.h"
#include "Common/GlobalISel/CombinerUtils.h"
#include "Common/GlobalISel/GlobalISelMatchTable.h"
#include "Common/GlobalISel/GlobalISelMatchTableExecutorEmitter.h"
#include "Common/GlobalISel/PatternParser.h"
#include "Common/GlobalISel/Patterns.h"
#include "Common/SubtargetFeatureInfo.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/PrettyStackTrace.h"
#include "llvm/Support/ScopedPrinter.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/StringMatcher.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <cstdint>

usingnamespacellvm;
usingnamespacellvm::gi;

#define DEBUG_TYPE …

namespace {
cl::OptionCategory
    GICombinerEmitterCat("Options for -gen-global-isel-combiner");
cl::opt<bool> StopAfterParse(
    "gicombiner-stop-after-parse",
    cl::desc("Stop processing after parsing rules and dump state"),
    cl::cat(GICombinerEmitterCat));
cl::list<std::string>
    SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
                      cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
cl::opt<bool> DebugCXXPreds(
    "gicombiner-debug-cxxpreds",
    cl::desc("Add Contextual/Debug comments to all C++ predicates"),
    cl::cat(GICombinerEmitterCat));
cl::opt<bool> DebugTypeInfer("gicombiner-debug-typeinfer",
                             cl::desc("Print type inference debug logs"),
                             cl::cat(GICombinerEmitterCat));

constexpr StringLiteral CXXCustomActionPrefix = …;
constexpr StringLiteral CXXPredPrefix = …;
constexpr StringLiteral MatchDataClassName = …;

//===- CodeExpansions Helpers  --------------------------------------------===//

void declareInstExpansion(CodeExpansions &CE, const InstructionMatcher &IM,
                          StringRef Name) { … }

void declareInstExpansion(CodeExpansions &CE, const BuildMIAction &A,
                          StringRef Name) { … }

void declareOperandExpansion(CodeExpansions &CE, const OperandMatcher &OM,
                             StringRef Name) { … }

void declareTempRegExpansion(CodeExpansions &CE, unsigned TempRegID,
                             StringRef Name) { … }

//===- Misc. Helpers  -----------------------------------------------------===//

template <typename Container> auto keys(Container &&C) { … }

template <typename Container> auto values(Container &&C) { … }

std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) { … }

//===- MatchTable Helpers  ------------------------------------------------===//

LLTCodeGen getLLTCodeGen(const PatternType &PT) { … }

//===- PrettyStackTrace Helpers  ------------------------------------------===//

class PrettyStackTraceParse : public PrettyStackTraceEntry { … };

class PrettyStackTraceEmit : public PrettyStackTraceEntry { … };

//===- CombineRuleOperandTypeChecker --------------------------------------===//

/// This is a wrapper around OperandTypeChecker specialized for Combiner Rules.
/// On top of doing the same things as OperandTypeChecker, this also attempts to
/// infer as many types as possible for temporary register defs & immediates in
/// apply patterns.
///
/// The inference is trivial and leverages the MCOI OperandTypes encoded in
/// CodeGenInstructions to infer types across patterns in a CombineRule. It's
/// thus very limited and only supports CodeGenInstructions (but that's the main
/// use case so it's fine).
///
/// We only try to infer untyped operands in apply patterns when they're temp
/// reg defs, or immediates. Inference always outputs a `TypeOf<$x>` where $x is
/// a named operand from a match pattern.
class CombineRuleOperandTypeChecker : private OperandTypeChecker { … };

bool CombineRuleOperandTypeChecker::processMatchPattern(InstructionPattern &P) { … }

bool CombineRuleOperandTypeChecker::processApplyPattern(InstructionPattern &P) { … }

void CombineRuleOperandTypeChecker::propagateAndInferTypes() { … }

PatternType CombineRuleOperandTypeChecker::inferImmediateType(
    const InstructionPattern &IP, unsigned ImmOpIdx,
    const TypeEquivalenceClasses &TECs) const { … }

PatternType CombineRuleOperandTypeChecker::inferNamedOperandType(
    const InstructionPattern &IP, StringRef OpName,
    const TypeEquivalenceClasses &TECs, bool AllowSelf) const { … }

std::vector<std::string> CombineRuleOperandTypeChecker::getMCOIOperandTypes(
    const CodeGenInstructionPattern &CGP) { … }

void CombineRuleOperandTypeChecker::getInstEqClasses(
    const InstructionPattern &P, TypeEquivalenceClasses &OutTECs) const { … }

CombineRuleOperandTypeChecker::TypeEquivalenceClasses
CombineRuleOperandTypeChecker::getRuleEqClasses() const { … }

//===- MatchData Handling -------------------------------------------------===//
struct MatchDataDef { … };

//===- CombineRuleBuilder -------------------------------------------------===//

/// Parses combine rule and builds a small intermediate representation to tie
/// patterns together and emit RuleMatchers to match them. This may emit more
/// than one RuleMatcher, e.g. for `wip_match_opcode`.
///
/// Memory management for `Pattern` objects is done through `std::unique_ptr`.
/// In most cases, there are two stages to a pattern's lifetime:
///   - Creation in a `parse` function
///     - The unique_ptr is stored in a variable, and may be destroyed if the
///       pattern is found to be semantically invalid.
///   - Ownership transfer into a `PatternMap`
///     - Once a pattern is moved into either the map of Match or Apply
///       patterns, it is known to be valid and it never moves back.
class CombineRuleBuilder { … };

bool CombineRuleBuilder::parseAll() { … }

bool CombineRuleBuilder::emitRuleMatchers() { … }

void CombineRuleBuilder::print(raw_ostream &OS) const { … }

#ifndef NDEBUG
void CombineRuleBuilder::verify() const {
  const auto VerifyPats = [&](const PatternMap &Pats) {
    for (const auto &[Name, Pat] : Pats) {
      if (!Pat)
        PrintFatalError("null pattern in pattern map!");

      if (Name != Pat->getName()) {
        Pat->dump();
        PrintFatalError("Pattern name mismatch! Map name: " + Name +
                        ", Pat name: " + Pat->getName());
      }

      // Sanity check: the map should point to the same data as the Pattern.
      // Both strings are allocated in the pool using insertStrRef.
      if (Name.data() != Pat->getName().data()) {
        dbgs() << "Map StringRef: '" << Name << "' @ "
               << (const void *)Name.data() << '\n';
        dbgs() << "Pat String: '" << Pat->getName() << "' @ "
               << (const void *)Pat->getName().data() << '\n';
        PrintFatalError("StringRef stored in the PatternMap is not referencing "
                        "the same string as its Pattern!");
      }
    }
  };

  VerifyPats(MatchPats);
  VerifyPats(ApplyPats);

  // Check there are no wip_match_opcode patterns in the "apply" patterns.
  if (any_of(ApplyPats,
             [&](auto &E) { return isa<AnyOpcodePattern>(E.second.get()); })) {
    dump();
    PrintFatalError(
        "illegal wip_match_opcode pattern in the 'apply' patterns!");
  }

  // Check there are no nullptrs in ApplyRoots.
  if (ApplyRoots.contains(nullptr)) {
    PrintFatalError(
        "CombineRuleBuilder's ApplyRoots set contains a null pointer!");
  }
}
#endif

std::optional<LLTCodeGenOrTempType>
CombineRuleBuilder::getLLTCodeGenOrTempType(const PatternType &PT,
                                            RuleMatcher &RM) { … }

void CombineRuleBuilder::print(raw_ostream &OS,
                               const PatternAlternatives &Alts) const { … }

bool CombineRuleBuilder::addApplyPattern(std::unique_ptr<Pattern> Pat) { … }

bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) { … }

void CombineRuleBuilder::declareAllMatchDatasExpansions(
    CodeExpansions &CE) const { … }

void CombineRuleBuilder::addCXXPredicate(RuleMatcher &M,
                                         const CodeExpansions &CE,
                                         const CXXPattern &P,
                                         const PatternAlternatives &Alts) { … }

bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const { … }

bool CombineRuleBuilder::hasEraseRoot() const { … }

bool CombineRuleBuilder::typecheckPatterns() { … }

bool CombineRuleBuilder::buildPermutationsToEmit() { … }

bool CombineRuleBuilder::checkSemantics() { … }

RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,
                                                Twine AdditionalComment) { … }

bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) { … }

bool CombineRuleBuilder::findRoots() { … }

bool CombineRuleBuilder::buildRuleOperandsTable() { … }

bool CombineRuleBuilder::parseDefs(const DagInit &Def) { … }

bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
                                          const PatternAlternatives &Alts,
                                          const InstructionPattern &IP) { … }

bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
                                          const PatternAlternatives &Alts,
                                          const AnyOpcodePattern &AOP) { … }

bool CombineRuleBuilder::emitPatFragMatchPattern(
    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &RM,
    InstructionMatcher *IM, const PatFragPattern &PFP,
    DenseSet<const Pattern *> &SeenPats) { … }

bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) { … }

bool CombineRuleBuilder::emitCXXMatchApply(CodeExpansions &CE, RuleMatcher &M,
                                           ArrayRef<CXXPattern *> Matchers) { … }

bool CombineRuleBuilder::emitInstructionApplyPattern(
    CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,
    DenseSet<const Pattern *> &SeenPats,
    StringMap<unsigned> &OperandToTempRegID) { … }

bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(
    RuleMatcher &M, BuildMIAction &DstMI, const CodeGenInstructionPattern &P,
    const InstructionOperand &O) { … }

bool CombineRuleBuilder::emitBuiltinApplyPattern(
    CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,
    StringMap<unsigned> &OperandToTempRegID) { … }

bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) { … }

bool CombineRuleBuilder::emitCodeGenInstructionMatchPattern(
    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
    InstructionMatcher &IM, const CodeGenInstructionPattern &P,
    DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
    OperandMapperFnRef OperandMapper) { … }

//===- GICombinerEmitter --------------------------------------------------===//

/// Main implementation class. This emits the tablegenerated output.
///
/// It collects rules, uses `CombineRuleBuilder` to parse them and accumulate
/// RuleMatchers, then takes all the necessary state/data from the various
/// static storage pools and wires them together to emit the match table &
/// associated function/data structures.
class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter { … };

void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) { … }

void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) { … }

void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) { … }

void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) { … }

void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) { … }

void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) { … }

void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) { … }

void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) { … }

GICombinerEmitter::GICombinerEmitter(const RecordKeeper &RK,
                                     const CodeGenTarget &Target,
                                     StringRef Name, const Record *Combiner)
    : … { … }

MatchTable
GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) { … }

/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
void GICombinerEmitter::gatherRules(std::vector<RuleMatcher> &ActiveRules,
                                    ArrayRef<const Record *> RulesAndGroups) { … }

void GICombinerEmitter::run(raw_ostream &OS) { … }

} // end anonymous namespace

//===----------------------------------------------------------------------===//

static void EmitGICombiner(const RecordKeeper &RK, raw_ostream &OS) { … }

static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
                                "Generate GlobalISel Combiner");