brintos / llvm-project-archived public Read only

1//===- GlobalISelCombinerMatchTableEmitter.cpp - --------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9/// \file Generate a combiner implementation for GlobalISel from a declarative10/// syntax using GlobalISelMatchTable.11///12/// Usually, TableGen backends use "assert is an error" as a means to report13/// invalid input. They try to diagnose common case but don't try very hard and14/// crashes can be common. This backend aims to behave closer to how a language15/// compiler frontend would behave: we try extra hard to diagnose invalid inputs16/// early, and any crash should be considered a bug (= a feature or diagnostic17/// is missing).18///19/// While this can make the backend a bit more complex than it needs to be, it20/// pays off because MIR patterns can get complicated. Giving useful error21/// messages to combine writers can help boost their productivity.22///23/// As with anything, a good balance has to be found. We also don't want to24/// write hundreds of lines of code to detect edge cases. In practice, crashing25/// very occasionally, or giving poor errors in some rare instances, is fine.26///27//===----------------------------------------------------------------------===//28 29#include "Basic/CodeGenIntrinsics.h"30#include "Common/CodeGenInstruction.h"31#include "Common/CodeGenTarget.h"32#include "Common/GlobalISel/CXXPredicates.h"33#include "Common/GlobalISel/CodeExpander.h"34#include "Common/GlobalISel/CodeExpansions.h"35#include "Common/GlobalISel/CombinerUtils.h"36#include "Common/GlobalISel/GlobalISelMatchTable.h"37#include "Common/GlobalISel/GlobalISelMatchTableExecutorEmitter.h"38#include "Common/GlobalISel/PatternParser.h"39#include "Common/GlobalISel/Patterns.h"40#include "Common/SubtargetFeatureInfo.h"41#include "llvm/ADT/APInt.h"42#include "llvm/ADT/EquivalenceClasses.h"43#include "llvm/ADT/MapVector.h"44#include "llvm/ADT/Statistic.h"45#include "llvm/ADT/StringExtras.h"46#include "llvm/ADT/StringSet.h"47#include "llvm/Support/CommandLine.h"48#include "llvm/Support/Debug.h"49#include "llvm/Support/PrettyStackTrace.h"50#include "llvm/Support/ScopedPrinter.h"51#include "llvm/TableGen/Error.h"52#include "llvm/TableGen/Record.h"53#include "llvm/TableGen/StringMatcher.h"54#include "llvm/TableGen/TGTimer.h"55#include "llvm/TableGen/TableGenBackend.h"56#include <cstdint>57 58using namespace llvm;59using namespace llvm::gi;60 61#define DEBUG_TYPE "gicombiner-emitter"62 63static cl::OptionCategory64    GICombinerEmitterCat("Options for -gen-global-isel-combiner");65static cl::opt<bool> StopAfterParse(66    "gicombiner-stop-after-parse",67    cl::desc("Stop processing after parsing rules and dump state"),68    cl::cat(GICombinerEmitterCat));69static cl::list<std::string>70    SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),71                      cl::cat(GICombinerEmitterCat), cl::CommaSeparated);72static cl::opt<bool> DebugCXXPreds(73    "gicombiner-debug-cxxpreds",74    cl::desc("Add Contextual/Debug comments to all C++ predicates"),75    cl::cat(GICombinerEmitterCat));76static cl::opt<bool> DebugTypeInfer("gicombiner-debug-typeinfer",77                                    cl::desc("Print type inference debug logs"),78                                    cl::cat(GICombinerEmitterCat));79 80constexpr StringLiteral CXXCustomActionPrefix = "GICXXCustomAction_";81constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";82constexpr StringLiteral MatchDataClassName = "GIDefMatchData";83 84//===- CodeExpansions Helpers  --------------------------------------------===//85 86static void declareInstExpansion(CodeExpansions &CE,87                                 const InstructionMatcher &IM, StringRef Name) {88  CE.declare(Name, "State.MIs[" + to_string(IM.getInsnVarID()) + "]");89}90 91static void declareInstExpansion(CodeExpansions &CE, const BuildMIAction &A,92                                 StringRef Name) {93  // Note: we use redeclare here because this may overwrite a matcher inst94  // expansion.95  CE.redeclare(Name, "OutMIs[" + to_string(A.getInsnID()) + "]");96}97 98static void declareOperandExpansion(CodeExpansions &CE,99                                    const OperandMatcher &OM, StringRef Name) {100  if (OM.isVariadic()) {101    CE.declare(Name, "getRemainingOperands(*State.MIs[" +102                         to_string(OM.getInsnVarID()) + "], " +103                         to_string(OM.getOpIdx()) + ")");104  } else {105    CE.declare(Name, "State.MIs[" + to_string(OM.getInsnVarID()) +106                         "]->getOperand(" + to_string(OM.getOpIdx()) + ")");107  }108}109 110static void declareTempRegExpansion(CodeExpansions &CE, unsigned TempRegID,111                                    StringRef Name) {112  CE.declare(Name, "State.TempRegisters[" + to_string(TempRegID) + "]");113}114 115//===- Misc. Helpers  -----------------------------------------------------===//116 117template <typename Container> static auto keys(Container &&C) {118  return map_range(C, [](auto &Entry) -> auto & { return Entry.first; });119}120 121template <typename Container> static auto values(Container &&C) {122  return map_range(C, [](auto &Entry) -> auto & { return Entry.second; });123}124 125static std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {126  return "GICXXPred_Simple_IsRule" + to_string(CombinerRuleID) + "Enabled";127}128 129//===- MatchTable Helpers  ------------------------------------------------===//130 131static LLTCodeGen getLLTCodeGen(const PatternType &PT) {132  return *MVTToLLT(getValueType(PT.getLLTRecord()));133}134 135//===- PrettyStackTrace Helpers  ------------------------------------------===//136 137namespace {138class PrettyStackTraceParse : public PrettyStackTraceEntry {139  const Record &Def;140 141public:142  PrettyStackTraceParse(const Record &Def) : Def(Def) {}143 144  void print(raw_ostream &OS) const override {145    if (Def.isSubClassOf("GICombineRule"))146      OS << "Parsing GICombineRule '" << Def.getName() << "'";147    else if (Def.isSubClassOf(PatFrag::ClassName))148      OS << "Parsing " << PatFrag::ClassName << " '" << Def.getName() << "'";149    else150      OS << "Parsing '" << Def.getName() << "'";151    OS << '\n';152  }153};154 155class PrettyStackTraceEmit : public PrettyStackTraceEntry {156  const Record &Def;157  const Pattern *Pat = nullptr;158 159public:160  PrettyStackTraceEmit(const Record &Def, const Pattern *Pat = nullptr)161      : Def(Def), Pat(Pat) {}162 163  void print(raw_ostream &OS) const override {164    if (Def.isSubClassOf("GICombineRule"))165      OS << "Emitting GICombineRule '" << Def.getName() << "'";166    else if (Def.isSubClassOf(PatFrag::ClassName))167      OS << "Emitting " << PatFrag::ClassName << " '" << Def.getName() << "'";168    else169      OS << "Emitting '" << Def.getName() << "'";170 171    if (Pat)172      OS << " [" << Pat->getKindName() << " '" << Pat->getName() << "']";173    OS << '\n';174  }175};176 177//===- CombineRuleOperandTypeChecker --------------------------------------===//178 179/// This is a wrapper around OperandTypeChecker specialized for Combiner Rules.180/// On top of doing the same things as OperandTypeChecker, this also attempts to181/// infer as many types as possible for temporary register defs & immediates in182/// apply patterns.183///184/// The inference is trivial and leverages the MCOI OperandTypes encoded in185/// CodeGenInstructions to infer types across patterns in a CombineRule. It's186/// thus very limited and only supports CodeGenInstructions (but that's the main187/// use case so it's fine).188///189/// We only try to infer untyped operands in apply patterns when they're temp190/// reg defs, or immediates. Inference always outputs a `TypeOf<$x>` where $x is191/// a named operand from a match pattern.192class CombineRuleOperandTypeChecker : private OperandTypeChecker {193public:194  CombineRuleOperandTypeChecker(const Record &RuleDef,195                                const OperandTable &MatchOpTable)196      : OperandTypeChecker(RuleDef.getLoc()), RuleDef(RuleDef),197        MatchOpTable(MatchOpTable) {}198 199  /// Records and checks a 'match' pattern.200  bool processMatchPattern(InstructionPattern &P);201 202  /// Records and checks an 'apply' pattern.203  bool processApplyPattern(InstructionPattern &P);204 205  /// Propagates types, then perform type inference and do a second round of206  /// propagation in the apply patterns only if any types were inferred.207  void propagateAndInferTypes();208 209private:210  /// TypeEquivalenceClasses are groups of operands of an instruction that share211  /// a common type.212  ///213  /// e.g. [[a, b], [c, d]] means a and b have the same type, and c and214  /// d have the same type too. b/c and a/d don't have to have the same type,215  /// though.216  using TypeEquivalenceClasses = EquivalenceClasses<StringRef>;217 218  /// \returns true for `OPERAND_GENERIC_` 0 through 5.219  /// These are the MCOI types that can be registers. The other MCOI types are220  /// either immediates, or fancier operands used only post-ISel, so we don't221  /// care about them for combiners.222  static bool canMCOIOperandTypeBeARegister(StringRef MCOIType) {223    // Assume OPERAND_GENERIC_0 through 5 can be registers. The other MCOI224    // OperandTypes are either never used in gMIR, or not relevant (e.g.225    // OPERAND_GENERIC_IMM, which is definitely never a register).226    return MCOIType.drop_back(1).ends_with("OPERAND_GENERIC_");227  }228 229  /// Finds the "MCOI::"" operand types for each operand of \p CGP.230  ///231  /// This is a bit trickier than it looks because we need to handle variadic232  /// in/outs.233  ///234  /// e.g. for235  ///   (G_BUILD_VECTOR $vec, $x, $y) ->236  ///   [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,237  ///    MCOI::OPERAND_GENERIC_1]238  ///239  /// For unknown types (which can happen in variadics where varargs types are240  /// inconsistent), a unique name is given, e.g. "unknown_type_0".241  static std::vector<std::string>242  getMCOIOperandTypes(const CodeGenInstructionPattern &CGP);243 244  /// Adds the TypeEquivalenceClasses for \p P in \p OutTECs.245  void getInstEqClasses(const InstructionPattern &P,246                        TypeEquivalenceClasses &OutTECs) const;247 248  /// Calls `getInstEqClasses` on all patterns of the rule to produce the whole249  /// rule's TypeEquivalenceClasses.250  TypeEquivalenceClasses getRuleEqClasses() const;251 252  /// Tries to infer the type of the \p ImmOpIdx -th operand of \p IP using \p253  /// TECs.254  ///255  /// This is achieved by trying to find a named operand in \p IP that shares256  /// the same type as \p ImmOpIdx, and using \ref inferNamedOperandType on that257  /// operand instead.258  ///259  /// \returns the inferred type or an empty PatternType if inference didn't260  /// succeed.261  PatternType inferImmediateType(const InstructionPattern &IP,262                                 unsigned ImmOpIdx,263                                 const TypeEquivalenceClasses &TECs) const;264 265  /// Looks inside \p TECs to infer \p OpName's type.266  ///267  /// \returns the inferred type or an empty PatternType if inference didn't268  /// succeed.269  PatternType inferNamedOperandType(const InstructionPattern &IP,270                                    StringRef OpName,271                                    const TypeEquivalenceClasses &TECs,272                                    bool AllowSelf = false) const;273 274  const Record &RuleDef;275  SmallVector<InstructionPattern *, 8> MatchPats;276  SmallVector<InstructionPattern *, 8> ApplyPats;277 278  const OperandTable &MatchOpTable;279};280} // namespace281 282bool CombineRuleOperandTypeChecker::processMatchPattern(InstructionPattern &P) {283  MatchPats.push_back(&P);284  return check(P, /*CheckTypeOf*/ [](const auto &) {285    // GITypeOf in 'match' is currently always rejected by the286    // CombineRuleBuilder after inference is done.287    return true;288  });289}290 291bool CombineRuleOperandTypeChecker::processApplyPattern(InstructionPattern &P) {292  ApplyPats.push_back(&P);293  return check(P, /*CheckTypeOf*/ [&](const PatternType &Ty) {294    // GITypeOf<"$x"> can only be used if "$x" is a matched operand.295    const auto OpName = Ty.getTypeOfOpName();296    if (MatchOpTable.lookup(OpName).Found)297      return true;298 299    PrintError(RuleDef.getLoc(), "'" + OpName + "' ('" + Ty.str() +300                                     "') does not refer to a matched operand!");301    return false;302  });303}304 305void CombineRuleOperandTypeChecker::propagateAndInferTypes() {306  /// First step here is to propagate types using the OperandTypeChecker. That307  /// way we ensure all uses of a given register have consistent types.308  propagateTypes();309 310  /// Build the TypeEquivalenceClasses for the whole rule.311  const TypeEquivalenceClasses TECs = getRuleEqClasses();312 313  /// Look at the apply patterns and find operands that need to be314  /// inferred. We then try to find an equivalence class that they're a part of315  /// and select the best operand to use for the `GITypeOf` type. We prioritize316  /// defs of matched instructions because those are guaranteed to be registers.317  bool InferredAny = false;318  for (auto *Pat : ApplyPats) {319    for (unsigned K = 0; K < Pat->operands_size(); ++K) {320      auto &Op = Pat->getOperand(K);321 322      // We only want to take a look at untyped defs or immediates.323      if ((!Op.isDef() && !Op.hasImmValue()) || Op.getType())324        continue;325 326      // Infer defs & named immediates.327      if (Op.isDef() || Op.isNamedImmediate()) {328        // Check it's not a redefinition of a matched operand.329        // In such cases, inference is not necessary because we just copy330        // operands and don't create temporary registers.331        if (MatchOpTable.lookup(Op.getOperandName()).Found)332          continue;333 334        // Inference is needed here, so try to do it.335        if (PatternType Ty =336                inferNamedOperandType(*Pat, Op.getOperandName(), TECs)) {337          if (DebugTypeInfer)338            errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';339          Op.setType(Ty);340          InferredAny = true;341        }342 343        continue;344      }345 346      // Infer immediates347      if (Op.hasImmValue()) {348        if (PatternType Ty = inferImmediateType(*Pat, K, TECs)) {349          if (DebugTypeInfer)350            errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';351          Op.setType(Ty);352          InferredAny = true;353        }354        continue;355      }356    }357  }358 359  // If we've inferred any types, we want to propagate them across the apply360  // patterns. Type inference only adds GITypeOf types that point to Matched361  // operands, so we definitely don't want to propagate types into the match362  // patterns as well, otherwise bad things happen.363  if (InferredAny) {364    OperandTypeChecker OTC(RuleDef.getLoc());365    for (auto *Pat : ApplyPats) {366      if (!OTC.check(*Pat, [&](const auto &) { return true; }))367        PrintFatalError(RuleDef.getLoc(),368                        "OperandTypeChecker unexpectedly failed on '" +369                            Pat->getName() + "' during Type Inference");370    }371    OTC.propagateTypes();372 373    if (DebugTypeInfer) {374      errs() << "Apply patterns for rule " << RuleDef.getName()375             << " after inference:\n";376      for (auto *Pat : ApplyPats) {377        errs() << "  ";378        Pat->print(errs(), /*PrintName*/ true);379        errs() << '\n';380      }381      errs() << '\n';382    }383  }384}385 386PatternType CombineRuleOperandTypeChecker::inferImmediateType(387    const InstructionPattern &IP, unsigned ImmOpIdx,388    const TypeEquivalenceClasses &TECs) const {389  // We can only infer CGPs (except intrinsics).390  const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&IP);391  if (!CGP || CGP->isIntrinsic())392    return {};393 394  // For CGPs, we try to infer immediates by trying to infer another named395  // operand that shares its type.396  //397  // e.g.398  //    Pattern: G_BUILD_VECTOR $x, $y, 0399  //    MCOIs:   [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,400  //              MCOI::OPERAND_GENERIC_1]401  //    $y has the same type as 0, so we can infer $y and get the type 0 should402  //    have.403 404  // We infer immediates by looking for a named operand that shares the same405  // MCOI type.406  const auto MCOITypes = getMCOIOperandTypes(*CGP);407  StringRef ImmOpTy = MCOITypes[ImmOpIdx];408 409  for (const auto &[Idx, Ty] : enumerate(MCOITypes)) {410    if (Idx != ImmOpIdx && Ty == ImmOpTy) {411      const auto &Op = IP.getOperand(Idx);412      if (!Op.isNamedOperand())413        continue;414 415      // Named operand with the same name, try to infer that.416      if (PatternType InferTy = inferNamedOperandType(IP, Op.getOperandName(),417                                                      TECs, /*AllowSelf=*/true))418        return InferTy;419    }420  }421 422  return {};423}424 425PatternType CombineRuleOperandTypeChecker::inferNamedOperandType(426    const InstructionPattern &IP, StringRef OpName,427    const TypeEquivalenceClasses &TECs, bool AllowSelf) const {428  // This is the simplest possible case, we just need to find a TEC that429  // contains OpName. Look at all operands in equivalence class and try to430  // find a suitable one. If `AllowSelf` is true, the operand itself is also431  // considered suitable.432 433  // Check for a def of a matched pattern. This is guaranteed to always434  // be a register so we can blindly use that.435  StringRef GoodOpName;436  for (auto It = TECs.findLeader(OpName); It != TECs.member_end(); ++It) {437    if (!AllowSelf && *It == OpName)438      continue;439 440    const auto LookupRes = MatchOpTable.lookup(*It);441    if (LookupRes.Def) // Favor defs442      return PatternType::getTypeOf(*It);443 444    // Otherwise just save this in case we don't find any def.445    if (GoodOpName.empty() && LookupRes.Found)446      GoodOpName = *It;447  }448 449  if (!GoodOpName.empty())450    return PatternType::getTypeOf(GoodOpName);451 452  // No good operand found, give up.453  return {};454}455 456std::vector<std::string> CombineRuleOperandTypeChecker::getMCOIOperandTypes(457    const CodeGenInstructionPattern &CGP) {458  // FIXME?: Should we cache this? We call it twice when inferring immediates.459 460  static unsigned UnknownTypeIdx = 0;461 462  std::vector<std::string> OpTypes;463  auto &CGI = CGP.getInst();464  const Record *VarArgsTy =465      CGI.TheDef->isSubClassOf("GenericInstruction")466          ? CGI.TheDef->getValueAsOptionalDef("variadicOpsType")467          : nullptr;468  std::string VarArgsTyName =469      VarArgsTy ? ("MCOI::" + VarArgsTy->getValueAsString("OperandType")).str()470                : ("unknown_type_" + Twine(UnknownTypeIdx++)).str();471 472  // First, handle defs.473  for (unsigned K = 0; K < CGI.Operands.NumDefs; ++K)474    OpTypes.push_back(CGI.Operands[K].OperandType);475 476  // Then, handle variadic defs if there are any.477  if (CGP.hasVariadicDefs()) {478    for (unsigned K = CGI.Operands.NumDefs; K < CGP.getNumInstDefs(); ++K)479      OpTypes.push_back(VarArgsTyName);480  }481 482  // If we had variadic defs, the op idx in the pattern won't match the op idx483  // in the CGI anymore.484  int CGIOpOffset = int(CGI.Operands.NumDefs) - CGP.getNumInstDefs();485  assert(CGP.hasVariadicDefs() ? (CGIOpOffset <= 0) : (CGIOpOffset == 0));486 487  // Handle all remaining use operands, including variadic ones.488  for (unsigned K = CGP.getNumInstDefs(); K < CGP.getNumInstOperands(); ++K) {489    unsigned CGIOpIdx = K + CGIOpOffset;490    if (CGIOpIdx >= CGI.Operands.size()) {491      assert(CGP.isVariadic());492      OpTypes.push_back(VarArgsTyName);493    } else {494      OpTypes.push_back(CGI.Operands[CGIOpIdx].OperandType);495    }496  }497 498  assert(OpTypes.size() == CGP.operands_size());499  return OpTypes;500}501 502void CombineRuleOperandTypeChecker::getInstEqClasses(503    const InstructionPattern &P, TypeEquivalenceClasses &OutTECs) const {504  // Determine the TypeEquivalenceClasses by:505  //    - Getting the MCOI Operand Types.506  //    - Creating a Map of MCOI Type -> [Operand Indexes]507  //    - Iterating over the map, filtering types we don't like, and just adding508  //      the array of Operand Indexes to \p OutTECs.509 510  // We can only do this on CodeGenInstructions that aren't intrinsics. Other511  // InstructionPatterns have no type inference information associated with512  // them.513  // TODO: We could try to extract some info from CodeGenIntrinsic to514  //       guide inference.515 516  // TODO: Could we add some inference information to builtins at least? e.g.517  // ReplaceReg should always replace with a reg of the same type, for instance.518  // Though, those patterns are often used alone so it might not be worth the519  // trouble to infer their types.520  auto *CGP = dyn_cast<CodeGenInstructionPattern>(&P);521  if (!CGP || CGP->isIntrinsic())522    return;523 524  const auto MCOITypes = getMCOIOperandTypes(*CGP);525  assert(MCOITypes.size() == P.operands_size());526 527  MapVector<StringRef, SmallVector<unsigned, 0>> TyToOpIdx;528  for (const auto &[Idx, Ty] : enumerate(MCOITypes))529    TyToOpIdx[Ty].push_back(Idx);530 531  if (DebugTypeInfer)532    errs() << "\tGroups for " << P.getName() << ":\t";533 534  for (const auto &[Ty, Idxs] : TyToOpIdx) {535    if (!canMCOIOperandTypeBeARegister(Ty))536      continue;537 538    if (DebugTypeInfer)539      errs() << '[';540    StringRef Sep = "";541 542    // We only collect named operands.543    StringRef Leader;544    for (unsigned Idx : Idxs) {545      const auto &Op = P.getOperand(Idx);546      if (!Op.isNamedOperand())547        continue;548 549      const auto OpName = Op.getOperandName();550      if (DebugTypeInfer) {551        errs() << Sep << OpName;552        Sep = ", ";553      }554 555      if (Leader.empty())556        OutTECs.insert((Leader = OpName));557      else558        OutTECs.unionSets(Leader, OpName);559    }560 561    if (DebugTypeInfer)562      errs() << "] ";563  }564 565  if (DebugTypeInfer)566    errs() << '\n';567}568 569CombineRuleOperandTypeChecker::TypeEquivalenceClasses570CombineRuleOperandTypeChecker::getRuleEqClasses() const {571  TypeEquivalenceClasses TECs;572 573  if (DebugTypeInfer)574    errs() << "Rule Operand Type Equivalence Classes for " << RuleDef.getName()575           << ":\n";576 577  for (const auto *Pat : MatchPats)578    getInstEqClasses(*Pat, TECs);579  for (const auto *Pat : ApplyPats)580    getInstEqClasses(*Pat, TECs);581 582  if (DebugTypeInfer) {583    errs() << "Final Type Equivalence Classes: ";584    for (const auto &Class : TECs) {585      // only print non-empty classes.586      if (auto MembIt = TECs.member_begin(*Class);587          MembIt != TECs.member_end()) {588        errs() << '[';589        StringRef Sep = "";590        for (; MembIt != TECs.member_end(); ++MembIt) {591          errs() << Sep << *MembIt;592          Sep = ", ";593        }594        errs() << "] ";595      }596    }597    errs() << '\n';598  }599 600  return TECs;601}602 603//===- MatchData Handling -------------------------------------------------===//604struct MatchDataDef {605  MatchDataDef(StringRef Symbol, StringRef Type) : Symbol(Symbol), Type(Type) {}606 607  StringRef Symbol;608  StringRef Type;609 610  /// \returns the desired variable name for this MatchData.611  std::string getVarName() const {612    // Add a prefix in case the symbol name is very generic and conflicts with613    // something else.614    return "GIMatchData_" + Symbol.str();615  }616};617 618//===- CombineRuleBuilder -------------------------------------------------===//619 620/// Parses combine rule and builds a small intermediate representation to tie621/// patterns together and emit RuleMatchers to match them. This may emit more622/// than one RuleMatcher, e.g. for `wip_match_opcode`.623///624/// Memory management for `Pattern` objects is done through `std::unique_ptr`.625/// In most cases, there are two stages to a pattern's lifetime:626///   - Creation in a `parse` function627///     - The unique_ptr is stored in a variable, and may be destroyed if the628///       pattern is found to be semantically invalid.629///   - Ownership transfer into a `PatternMap`630///     - Once a pattern is moved into either the map of Match or Apply631///       patterns, it is known to be valid and it never moves back.632class CombineRuleBuilder {633public:634  using PatternMap = MapVector<StringRef, std::unique_ptr<Pattern>>;635  using PatternAlternatives = DenseMap<const Pattern *, unsigned>;636 637  CombineRuleBuilder(const CodeGenTarget &CGT,638                     SubtargetFeatureInfoMap &SubtargetFeatures,639                     const Record &RuleDef, unsigned ID,640                     std::vector<RuleMatcher> &OutRMs)641      : Parser(CGT, RuleDef.getLoc()), CGT(CGT),642        SubtargetFeatures(SubtargetFeatures), RuleDef(RuleDef), RuleID(ID),643        OutRMs(OutRMs) {}644 645  /// Parses all fields in the RuleDef record.646  bool parseAll();647 648  /// Emits all RuleMatchers into the vector of RuleMatchers passed in the649  /// constructor.650  bool emitRuleMatchers();651 652  void print(raw_ostream &OS) const;653  void dump() const { print(dbgs()); }654 655  /// Debug-only verification of invariants.656#ifndef NDEBUG657  void verify() const;658#endif659 660private:661  const CodeGenInstruction &getGConstant() const {662    return CGT.getInstruction(RuleDef.getRecords().getDef("G_CONSTANT"));663  }664 665  std::optional<LLTCodeGenOrTempType>666  getLLTCodeGenOrTempType(const PatternType &PT, RuleMatcher &RM);667 668  void PrintError(Twine Msg) const { ::PrintError(&RuleDef, Msg); }669  void PrintWarning(Twine Msg) const { ::PrintWarning(RuleDef.getLoc(), Msg); }670  void PrintNote(Twine Msg) const { ::PrintNote(RuleDef.getLoc(), Msg); }671 672  void print(raw_ostream &OS, const PatternAlternatives &Alts) const;673 674  bool addApplyPattern(std::unique_ptr<Pattern> Pat);675  bool addMatchPattern(std::unique_ptr<Pattern> Pat);676 677  /// Adds the expansions from \see MatchDatas to \p CE.678  void declareAllMatchDatasExpansions(CodeExpansions &CE) const;679 680  /// Adds a matcher \p P to \p IM, expanding its code using \p CE.681  /// Note that the predicate is added on the last InstructionMatcher.682  ///683  /// \p Alts is only used if DebugCXXPreds is enabled.684  void addCXXPredicate(RuleMatcher &M, const CodeExpansions &CE,685                       const CXXPattern &P, const PatternAlternatives &Alts);686 687  bool hasOnlyCXXApplyPatterns() const;688  bool hasEraseRoot() const;689 690  // Infer machine operand types and check their consistency.691  bool typecheckPatterns();692 693  /// For all PatFragPatterns, add a new entry in PatternAlternatives for each694  /// PatternList it contains. This is multiplicative, so if we have 2695  /// PatFrags with 3 alternatives each, we get 2*3 permutations added to696  /// PermutationsToEmit. The "MaxPermutations" field controls how many697  /// permutations are allowed before an error is emitted and this function698  /// returns false. This is a simple safeguard to prevent combination of699  /// PatFrags from generating enormous amounts of rules.700  bool buildPermutationsToEmit();701 702  /// Checks additional semantics of the Patterns.703  bool checkSemantics();704 705  /// Creates a new RuleMatcher with some boilerplate706  /// settings/actions/predicates, and and adds it to \p OutRMs.707  /// \see addFeaturePredicates too.708  ///709  /// \param Alts Current set of alternatives, for debug comment.710  /// \param AdditionalComment Comment string to be added to the711  ///        `DebugCommentAction`.712  RuleMatcher &addRuleMatcher(const PatternAlternatives &Alts,713                              Twine AdditionalComment = "");714  bool addFeaturePredicates(RuleMatcher &M);715 716  bool findRoots();717  bool buildRuleOperandsTable();718 719  bool parseDefs(const DagInit &Def);720 721  bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,722                        const InstructionPattern &IP);723  bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,724                        const AnyOpcodePattern &AOP);725 726  bool emitPatFragMatchPattern(CodeExpansions &CE,727                               const PatternAlternatives &Alts, RuleMatcher &RM,728                               InstructionMatcher *IM,729                               const PatFragPattern &PFP,730                               DenseSet<const Pattern *> &SeenPats);731 732  bool emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M);733  bool emitCXXMatchApply(CodeExpansions &CE, RuleMatcher &M,734                         ArrayRef<CXXPattern *> Matchers);735 736  // Recursively visits InstructionPatterns from P to build up the737  // RuleMatcher actions.738  bool emitInstructionApplyPattern(CodeExpansions &CE, RuleMatcher &M,739                                   const InstructionPattern &P,740                                   DenseSet<const Pattern *> &SeenPats,741                                   StringMap<unsigned> &OperandToTempRegID);742 743  bool emitCodeGenInstructionApplyImmOperand(RuleMatcher &M,744                                             BuildMIAction &DstMI,745                                             const CodeGenInstructionPattern &P,746                                             const InstructionOperand &O);747 748  bool emitBuiltinApplyPattern(CodeExpansions &CE, RuleMatcher &M,749                               const BuiltinPattern &P,750                               StringMap<unsigned> &OperandToTempRegID);751 752  // Recursively visits CodeGenInstructionPattern from P to build up the753  // RuleMatcher/InstructionMatcher. May create new InstructionMatchers as754  // needed.755  using OperandMapperFnRef =756      function_ref<InstructionOperand(const InstructionOperand &)>;757  using OperandDefLookupFn =758      function_ref<const InstructionPattern *(StringRef)>;759  bool emitCodeGenInstructionMatchPattern(760      CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,761      InstructionMatcher &IM, const CodeGenInstructionPattern &P,762      DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,763      OperandMapperFnRef OperandMapper = [](const auto &O) { return O; });764 765  PatternParser Parser;766  const CodeGenTarget &CGT;767  SubtargetFeatureInfoMap &SubtargetFeatures;768  const Record &RuleDef;769  const unsigned RuleID;770  std::vector<RuleMatcher> &OutRMs;771 772  // For InstructionMatcher::addOperand773  unsigned AllocatedTemporariesBaseID = 0;774 775  /// The root of the pattern.776  StringRef RootName;777 778  /// These maps have ownership of the actual Pattern objects.779  /// They both map a Pattern's name to the Pattern instance.780  PatternMap MatchPats;781  PatternMap ApplyPats;782 783  /// Operand tables to tie match/apply patterns together.784  OperandTable MatchOpTable;785  OperandTable ApplyOpTable;786 787  /// Set by findRoots.788  Pattern *MatchRoot = nullptr;789  SmallDenseSet<InstructionPattern *, 2> ApplyRoots;790 791  SmallVector<MatchDataDef, 2> MatchDatas;792  SmallVector<PatternAlternatives, 1> PermutationsToEmit;793};794 795bool CombineRuleBuilder::parseAll() {796  auto StackTrace = PrettyStackTraceParse(RuleDef);797 798  if (!parseDefs(*RuleDef.getValueAsDag("Defs")))799    return false;800 801  const DagInit &Act0 = *RuleDef.getValueAsDag("Action0");802  const DagInit &Act1 = *RuleDef.getValueAsDag("Action1");803 804  StringRef Act0Op = Act0.getOperatorAsDef(RuleDef.getLoc())->getName();805  StringRef Act1Op = Act1.getOperatorAsDef(RuleDef.getLoc())->getName();806 807  if (Act0Op == "match" && Act1Op == "apply") {808    if (!Parser.parsePatternList(809            Act0, [this](auto Pat) { return addMatchPattern(std::move(Pat)); },810            "match", (RuleDef.getName() + "_match").str()))811      return false;812 813    if (!Parser.parsePatternList(814            Act1, [this](auto Pat) { return addApplyPattern(std::move(Pat)); },815            "apply", (RuleDef.getName() + "_apply").str()))816      return false;817 818  } else if (Act0Op == "combine" && Act1Op == "empty_action") {819    // combine: everything is a "match" except C++ code which is an apply.820    const auto AddCombinePat = [this](std::unique_ptr<Pattern> Pat) {821      if (isa<CXXPattern>(Pat.get()))822        return addApplyPattern(std::move(Pat));823      return addMatchPattern(std::move(Pat));824    };825 826    if (!Parser.parsePatternList(Act0, AddCombinePat, "combine",827                                 (RuleDef.getName() + "_combine").str()))828      return false;829 830    if (MatchPats.empty() || ApplyPats.empty()) {831      PrintError("'combine' action needs at least one pattern to match, and "832                 "C++ code to apply");833      return false;834    }835  } else {836    PrintError("expected both a 'match' and 'apply' action in combine rule, "837               "or a single 'combine' action");838    return false;839  }840 841  if (!buildRuleOperandsTable() || !typecheckPatterns() || !findRoots() ||842      !checkSemantics() || !buildPermutationsToEmit())843    return false;844  LLVM_DEBUG(verify());845  return true;846}847 848bool CombineRuleBuilder::emitRuleMatchers() {849  auto StackTrace = PrettyStackTraceEmit(RuleDef);850 851  assert(MatchRoot);852  CodeExpansions CE;853 854  assert(!PermutationsToEmit.empty());855  for (const auto &Alts : PermutationsToEmit) {856    switch (MatchRoot->getKind()) {857    case Pattern::K_AnyOpcode: {858      if (!emitMatchPattern(CE, Alts, *cast<AnyOpcodePattern>(MatchRoot)))859        return false;860      break;861    }862    case Pattern::K_PatFrag:863    case Pattern::K_Builtin:864    case Pattern::K_CodeGenInstruction:865      if (!emitMatchPattern(CE, Alts, *cast<InstructionPattern>(MatchRoot)))866        return false;867      break;868    case Pattern::K_CXX:869      PrintError("C++ code cannot be the root of a rule!");870      return false;871    default:872      llvm_unreachable("unknown pattern kind!");873    }874  }875 876  return true;877}878 879void CombineRuleBuilder::print(raw_ostream &OS) const {880  OS << "(CombineRule name:" << RuleDef.getName() << " id:" << RuleID881     << " root:" << RootName << '\n';882 883  if (!MatchDatas.empty()) {884    OS << "  (MatchDatas\n";885    for (const auto &MD : MatchDatas) {886      OS << "    (MatchDataDef symbol:" << MD.Symbol << " type:" << MD.Type887         << ")\n";888    }889    OS << "  )\n";890  }891 892  const auto &SeenPFs = Parser.getSeenPatFrags();893  if (!SeenPFs.empty()) {894    OS << "  (PatFrags\n";895    for (const auto *PF : Parser.getSeenPatFrags()) {896      PF->print(OS, /*Indent=*/"    ");897      OS << '\n';898    }899    OS << "  )\n";900  }901 902  const auto DumpPats = [&](StringRef Name, const PatternMap &Pats) {903    OS << "  (" << Name << " ";904    if (Pats.empty()) {905      OS << "<empty>)\n";906      return;907    }908 909    OS << '\n';910    for (const auto &[Name, Pat] : Pats) {911      OS << "    ";912      if (Pat.get() == MatchRoot)913        OS << "<match_root>";914      if (isa<InstructionPattern>(Pat.get()) &&915          ApplyRoots.contains(cast<InstructionPattern>(Pat.get())))916        OS << "<apply_root>";917      OS << Name << ":";918      Pat->print(OS, /*PrintName=*/false);919      OS << '\n';920    }921    OS << "  )\n";922  };923 924  DumpPats("MatchPats", MatchPats);925  DumpPats("ApplyPats", ApplyPats);926 927  MatchOpTable.print(OS, "MatchPats", /*Indent*/ "  ");928  ApplyOpTable.print(OS, "ApplyPats", /*Indent*/ "  ");929 930  if (PermutationsToEmit.size() > 1) {931    OS << "  (PermutationsToEmit\n";932    for (const auto &Perm : PermutationsToEmit) {933      OS << "    ";934      print(OS, Perm);935      OS << ",\n";936    }937    OS << "  )\n";938  }939 940  OS << ")\n";941}942 943#ifndef NDEBUG944void CombineRuleBuilder::verify() const {945  const auto VerifyPats = [&](const PatternMap &Pats) {946    for (const auto &[Name, Pat] : Pats) {947      if (!Pat)948        PrintFatalError("null pattern in pattern map!");949 950      if (Name != Pat->getName()) {951        Pat->dump();952        PrintFatalError("Pattern name mismatch! Map name: " + Name +953                        ", Pat name: " + Pat->getName());954      }955 956      // Sanity check: the map should point to the same data as the Pattern.957      // Both strings are allocated in the pool using insertStrRef.958      if (Name.data() != Pat->getName().data()) {959        dbgs() << "Map StringRef: '" << Name << "' @ "960               << (const void *)Name.data() << '\n';961        dbgs() << "Pat String: '" << Pat->getName() << "' @ "962               << (const void *)Pat->getName().data() << '\n';963        PrintFatalError("StringRef stored in the PatternMap is not referencing "964                        "the same string as its Pattern!");965      }966    }967  };968 969  VerifyPats(MatchPats);970  VerifyPats(ApplyPats);971 972  // Check there are no wip_match_opcode patterns in the "apply" patterns.973  if (any_of(ApplyPats,974             [&](auto &E) { return isa<AnyOpcodePattern>(E.second.get()); })) {975    dump();976    PrintFatalError(977        "illegal wip_match_opcode pattern in the 'apply' patterns!");978  }979 980  // Check there are no nullptrs in ApplyRoots.981  if (ApplyRoots.contains(nullptr)) {982    PrintFatalError(983        "CombineRuleBuilder's ApplyRoots set contains a null pointer!");984  }985}986#endif987 988std::optional<LLTCodeGenOrTempType>989CombineRuleBuilder::getLLTCodeGenOrTempType(const PatternType &PT,990                                            RuleMatcher &RM) {991  assert(!PT.isNone());992 993  if (PT.isLLT())994    return getLLTCodeGen(PT);995 996  assert(PT.isTypeOf());997  auto &OM = RM.getOperandMatcher(PT.getTypeOfOpName());998  if (OM.isVariadic()) {999    PrintError("type '" + PT.str() + "' is ill-formed: '" +1000               OM.getSymbolicName() + "' is a variadic pack operand");1001    return std::nullopt;1002  }1003  return OM.getTempTypeIdx(RM);1004}1005 1006void CombineRuleBuilder::print(raw_ostream &OS,1007                               const PatternAlternatives &Alts) const {1008  SmallVector<std::string, 1> Strings(1009      map_range(Alts, [](const auto &PatAndPerm) {1010        return PatAndPerm.first->getName().str() + "[" +1011               to_string(PatAndPerm.second) + "]";1012      }));1013  // Sort so output is deterministic for tests. Otherwise it's sorted by pointer1014  // values.1015  sort(Strings);1016  OS << "[" << join(Strings, ", ") << "]";1017}1018 1019bool CombineRuleBuilder::addApplyPattern(std::unique_ptr<Pattern> Pat) {1020  StringRef Name = Pat->getName();1021  if (ApplyPats.contains(Name)) {1022    PrintError("'" + Name + "' apply pattern defined more than once!");1023    return false;1024  }1025 1026  if (isa<AnyOpcodePattern>(Pat.get())) {1027    PrintError("'" + Name +1028               "': wip_match_opcode is not supported in apply patterns");1029    return false;1030  }1031 1032  if (isa<PatFragPattern>(Pat.get())) {1033    PrintError("'" + Name + "': using " + PatFrag::ClassName +1034               " is not supported in apply patterns");1035    return false;1036  }1037 1038  if (auto *CXXPat = dyn_cast<CXXPattern>(Pat.get()))1039    CXXPat->setIsApply();1040 1041  ApplyPats[Name] = std::move(Pat);1042  return true;1043}1044 1045bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) {1046  StringRef Name = Pat->getName();1047  if (MatchPats.contains(Name)) {1048    PrintError("'" + Name + "' match pattern defined more than once!");1049    return false;1050  }1051 1052  // For now, none of the builtins can appear in 'match'.1053  if (const auto *BP = dyn_cast<BuiltinPattern>(Pat.get())) {1054    PrintError("'" + BP->getInstName() +1055               "' cannot be used in a 'match' pattern");1056    return false;1057  }1058 1059  MatchPats[Name] = std::move(Pat);1060  return true;1061}1062 1063void CombineRuleBuilder::declareAllMatchDatasExpansions(1064    CodeExpansions &CE) const {1065  for (const auto &MD : MatchDatas)1066    CE.declare(MD.Symbol, MD.getVarName());1067}1068 1069void CombineRuleBuilder::addCXXPredicate(RuleMatcher &M,1070                                         const CodeExpansions &CE,1071                                         const CXXPattern &P,1072                                         const PatternAlternatives &Alts) {1073  // FIXME: Hack so C++ code is executed last. May not work for more complex1074  // patterns.1075  auto &IM = *std::prev(M.insnmatchers().end());1076  auto Loc = RuleDef.getLoc();1077  const auto AddComment = [&](raw_ostream &OS) {1078    OS << "// Pattern Alternatives: ";1079    print(OS, Alts);1080    OS << '\n';1081  };1082  const auto &ExpandedCode =1083      DebugCXXPreds ? P.expandCode(CE, Loc, AddComment) : P.expandCode(CE, Loc);1084  IM->addPredicate<GenericInstructionPredicateMatcher>(1085      ExpandedCode.getEnumNameWithPrefix(CXXPredPrefix));1086}1087 1088bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const {1089  return all_of(ApplyPats, [&](auto &Entry) {1090    return isa<CXXPattern>(Entry.second.get());1091  });1092}1093 1094bool CombineRuleBuilder::hasEraseRoot() const {1095  return any_of(ApplyPats, [&](auto &Entry) {1096    if (const auto *BP = dyn_cast<BuiltinPattern>(Entry.second.get()))1097      return BP->getBuiltinKind() == BI_EraseRoot;1098    return false;1099  });1100}1101 1102bool CombineRuleBuilder::typecheckPatterns() {1103  CombineRuleOperandTypeChecker OTC(RuleDef, MatchOpTable);1104 1105  for (auto &Pat : values(MatchPats)) {1106    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {1107      if (!OTC.processMatchPattern(*IP))1108        return false;1109    }1110  }1111 1112  for (auto &Pat : values(ApplyPats)) {1113    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {1114      if (!OTC.processApplyPattern(*IP))1115        return false;1116    }1117  }1118 1119  OTC.propagateAndInferTypes();1120 1121  // Always check this after in case inference adds some special types to the1122  // match patterns.1123  for (auto &Pat : values(MatchPats)) {1124    if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {1125      bool HasDiag = false;1126      for (const auto &[Idx, Op] : enumerate(IP->operands())) {1127        if (Op.getType().isTypeOf()) {1128          PrintError(PatternType::TypeOfClassName +1129                     " is not supported in 'match' patterns");1130          PrintNote("operand " + Twine(Idx) + " of '" + IP->getName() +1131                    "' has type '" + Op.getType().str() + "'");1132          HasDiag = true;1133        }1134      }1135      if (HasDiag)1136        return false;1137    }1138  }1139  return true;1140}1141 1142bool CombineRuleBuilder::buildPermutationsToEmit() {1143  PermutationsToEmit.clear();1144 1145  // Start with one empty set of alternatives.1146  PermutationsToEmit.emplace_back();1147  for (const auto &Pat : values(MatchPats)) {1148    unsigned NumAlts = 0;1149    // Note: technically, AnyOpcodePattern also needs permutations, but:1150    //    - We only allow a single one of them in the root.1151    //    - They cannot be mixed with any other pattern other than C++ code.1152    // So we don't really need to take them into account here. We could, but1153    // that pattern is a hack anyway and the less it's involved, the better.1154    if (const auto *PFP = dyn_cast<PatFragPattern>(Pat.get()))1155      NumAlts = PFP->getPatFrag().num_alternatives();1156    else1157      continue;1158 1159    // For each pattern that needs permutations, multiply the current set of1160    // alternatives.1161    auto CurPerms = PermutationsToEmit;1162    PermutationsToEmit.clear();1163 1164    for (const auto &Perm : CurPerms) {1165      assert(!Perm.contains(Pat.get()) && "Pattern already emitted?");1166      for (unsigned K = 0; K < NumAlts; ++K) {1167        PatternAlternatives NewPerm = Perm;1168        NewPerm[Pat.get()] = K;1169        PermutationsToEmit.emplace_back(std::move(NewPerm));1170      }1171    }1172  }1173 1174  if (int64_t MaxPerms = RuleDef.getValueAsInt("MaxPermutations");1175      MaxPerms > 0) {1176    if ((int64_t)PermutationsToEmit.size() > MaxPerms) {1177      PrintError("cannot emit rule '" + RuleDef.getName() + "'; " +1178                 Twine(PermutationsToEmit.size()) +1179                 " permutations would be emitted, but the max is " +1180                 Twine(MaxPerms));1181      return false;1182    }1183  }1184 1185  // Ensure we always have a single empty entry, it simplifies the emission1186  // logic so it doesn't need to handle the case where there are no perms.1187  if (PermutationsToEmit.empty()) {1188    PermutationsToEmit.emplace_back();1189    return true;1190  }1191 1192  return true;1193}1194 1195bool CombineRuleBuilder::checkSemantics() {1196  assert(MatchRoot && "Cannot call this before findRoots()");1197 1198  const auto CheckVariadicOperands = [&](const InstructionPattern &IP,1199                                         bool IsMatch) {1200    bool HasVariadic = false;1201    for (auto &Op : IP.operands()) {1202      if (!Op.getType().isVariadicPack())1203        continue;1204 1205      HasVariadic = true;1206 1207      if (IsMatch && &Op != &IP.operands_back()) {1208        PrintError("'" + IP.getInstName() +1209                   "': " + PatternType::VariadicClassName +1210                   " can only be used on the last operand");1211        return false;1212      }1213 1214      if (Op.isDef()) {1215        PrintError("'" + IP.getInstName() + "': " +1216                   PatternType::VariadicClassName + " cannot be used on defs");1217        return false;1218      }1219    }1220 1221    if (HasVariadic && !IP.isVariadic()) {1222      PrintError("cannot use a " + PatternType::VariadicClassName +1223                 " operand on non-variadic instruction '" + IP.getInstName() +1224                 "'");1225      return false;1226    }1227 1228    return true;1229  };1230 1231  bool UsesWipMatchOpcode = false;1232  for (const auto &Match : MatchPats) {1233    const auto *Pat = Match.second.get();1234 1235    if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat)) {1236      if (!CXXPat->getRawCode().contains("return "))1237        PrintWarning("'match' C++ code does not seem to return!");1238      continue;1239    }1240 1241    if (const auto IP = dyn_cast<InstructionPattern>(Pat)) {1242      if (!CheckVariadicOperands(*IP, /*IsMatch=*/true))1243        return false;1244 1245      // MIFlags in match cannot use the following syntax: (MIFlags $mi)1246      if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Pat)) {1247        if (auto *FI = CGP->getMIFlagsInfo()) {1248          if (!FI->copy_flags().empty()) {1249            PrintError("'match' patterns cannot refer to flags from other "1250                       "instructions");1251            PrintNote("MIFlags in '" + CGP->getName() +1252                      "' refer to: " + join(FI->copy_flags(), ", "));1253            return false;1254          }1255        }1256      }1257      continue;1258    }1259 1260    const auto *AOP = dyn_cast<AnyOpcodePattern>(Pat);1261    if (!AOP)1262      continue;1263 1264    if (UsesWipMatchOpcode) {1265      PrintError("wip_opcode_match can only be present once");1266      return false;1267    }1268 1269    UsesWipMatchOpcode = true;1270  }1271 1272  std::optional<bool> IsUsingCXXPatterns;1273  for (const auto &Apply : ApplyPats) {1274    Pattern *Pat = Apply.second.get();1275    if (IsUsingCXXPatterns) {1276      if (*IsUsingCXXPatterns != isa<CXXPattern>(Pat)) {1277        PrintError("'apply' patterns cannot mix C++ code with other types of "1278                   "patterns");1279        return false;1280      }1281    } else {1282      IsUsingCXXPatterns = isa<CXXPattern>(Pat);1283    }1284 1285    assert(Pat);1286    const auto *IP = dyn_cast<InstructionPattern>(Pat);1287    if (!IP)1288      continue;1289 1290    if (!CheckVariadicOperands(*IP, /*IsMatch=*/false))1291      return false;1292 1293    if (UsesWipMatchOpcode) {1294      PrintError("cannot use wip_match_opcode in combination with apply "1295                 "instruction patterns!");1296      return false;1297    }1298 1299    // Check that the insts mentioned in copy_flags exist.1300    if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(IP)) {1301      if (auto *FI = CGP->getMIFlagsInfo()) {1302        for (auto InstName : FI->copy_flags()) {1303          auto It = MatchPats.find(InstName);1304          if (It == MatchPats.end()) {1305            PrintError("unknown instruction '$" + InstName +1306                       "' referenced in MIFlags of '" + CGP->getName() + "'");1307            return false;1308          }1309 1310          if (!isa<CodeGenInstructionPattern>(It->second.get())) {1311            PrintError(1312                "'$" + InstName +1313                "' does not refer to a CodeGenInstruction in MIFlags of '" +1314                CGP->getName() + "'");1315            return false;1316          }1317        }1318      }1319    }1320 1321    const auto *BIP = dyn_cast<BuiltinPattern>(IP);1322    if (!BIP)1323      continue;1324    StringRef Name = BIP->getInstName();1325 1326    // (GIEraseInst) has to be the only apply pattern, or it can not be used at1327    // all. The root cannot have any defs either.1328    switch (BIP->getBuiltinKind()) {1329    case BI_EraseRoot: {1330      if (ApplyPats.size() > 1) {1331        PrintError(Name + " must be the only 'apply' pattern");1332        return false;1333      }1334 1335      const auto *IRoot = dyn_cast<CodeGenInstructionPattern>(MatchRoot);1336      if (!IRoot) {1337        PrintError(Name + " can only be used if the root is a "1338                          "CodeGenInstruction or Intrinsic");1339        return false;1340      }1341 1342      if (IRoot->getNumInstDefs() != 0) {1343        PrintError(Name + " can only be used if on roots that do "1344                          "not have any output operand");1345        PrintNote("'" + IRoot->getInstName() + "' has " +1346                  Twine(IRoot->getNumInstDefs()) + " output operands");1347        return false;1348      }1349      break;1350    }1351    case BI_ReplaceReg: {1352      // (GIReplaceReg can only be used on the root instruction)1353      // TODO: When we allow rewriting non-root instructions, also allow this.1354      StringRef OldRegName = BIP->getOperand(0).getOperandName();1355      auto *Def = MatchOpTable.getDef(OldRegName);1356      if (!Def) {1357        PrintError(Name + " cannot find a matched pattern that defines '" +1358                   OldRegName + "'");1359        return false;1360      }1361      if (MatchOpTable.getDef(OldRegName) != MatchRoot) {1362        PrintError(Name + " cannot replace '" + OldRegName +1363                   "': this builtin can only replace a register defined by the "1364                   "match root");1365        return false;1366      }1367      break;1368    }1369    }1370  }1371 1372  // TODO: Diagnose uses of MatchDatas if the Rule doesn't have C++ on both the1373  //       match and apply. It's useless in such cases.1374  if (!hasOnlyCXXApplyPatterns() && !MatchDatas.empty()) {1375    PrintError(MatchDataClassName +1376               " can only be used if 'apply' in entirely written in C++");1377    return false;1378  }1379 1380  return true;1381}1382 1383RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,1384                                                Twine AdditionalComment) {1385  auto &RM = OutRMs.emplace_back(RuleDef.getLoc());1386  addFeaturePredicates(RM);1387  RM.setPermanentGISelFlags(GISF_IgnoreCopies);1388  RM.addRequiredSimplePredicate(getIsEnabledPredicateEnumName(RuleID));1389 1390  std::string Comment;1391  raw_string_ostream CommentOS(Comment);1392  CommentOS << "Combiner Rule #" << RuleID << ": " << RuleDef.getName();1393  if (!Alts.empty()) {1394    CommentOS << " @ ";1395    print(CommentOS, Alts);1396  }1397  if (!AdditionalComment.isTriviallyEmpty())1398    CommentOS << "; " << AdditionalComment;1399  RM.addAction<DebugCommentAction>(Comment);1400  return RM;1401}1402 1403bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {1404  if (!RuleDef.getValue("Predicates"))1405    return true;1406 1407  const ListInit *Preds = RuleDef.getValueAsListInit("Predicates");1408  for (const Init *PI : Preds->getElements()) {1409    const DefInit *Pred = dyn_cast<DefInit>(PI);1410    if (!Pred)1411      continue;1412 1413    const Record *Def = Pred->getDef();1414    if (!Def->isSubClassOf("Predicate")) {1415      ::PrintError(Def, "Unknown 'Predicate' Type");1416      return false;1417    }1418 1419    if (Def->getValueAsString("CondString").empty())1420      continue;1421 1422    if (SubtargetFeatures.count(Def) == 0) {1423      SubtargetFeatures.emplace(1424          Def, SubtargetFeatureInfo(Def, SubtargetFeatures.size()));1425    }1426 1427    M.addRequiredFeature(Def);1428  }1429 1430  return true;1431}1432 1433bool CombineRuleBuilder::findRoots() {1434  const auto Finish = [&]() {1435    assert(MatchRoot);1436 1437    if (hasOnlyCXXApplyPatterns() || hasEraseRoot())1438      return true;1439 1440    auto *IPRoot = dyn_cast<InstructionPattern>(MatchRoot);1441    if (!IPRoot)1442      return true;1443 1444    if (IPRoot->getNumInstDefs() == 0) {1445      // No defs to work with -> find the root using the pattern name.1446      auto It = ApplyPats.find(RootName);1447      if (It == ApplyPats.end()) {1448        PrintError("Cannot find root '" + RootName + "' in apply patterns!");1449        return false;1450      }1451 1452      auto *ApplyRoot = dyn_cast<InstructionPattern>(It->second.get());1453      if (!ApplyRoot) {1454        PrintError("apply pattern root '" + RootName +1455                   "' must be an instruction pattern");1456        return false;1457      }1458 1459      ApplyRoots.insert(ApplyRoot);1460      return true;1461    }1462 1463    // Collect all redefinitions of the MatchRoot's defs and put them in1464    // ApplyRoots.1465    const auto DefsNeeded = IPRoot->getApplyDefsNeeded();1466    for (auto &Op : DefsNeeded) {1467      assert(Op.isDef() && Op.isNamedOperand());1468      StringRef Name = Op.getOperandName();1469 1470      auto *ApplyRedef = ApplyOpTable.getDef(Name);1471      if (!ApplyRedef) {1472        PrintError("'" + Name + "' must be redefined in the 'apply' pattern");1473        return false;1474      }1475 1476      ApplyRoots.insert((InstructionPattern *)ApplyRedef);1477    }1478 1479    if (auto It = ApplyPats.find(RootName); It != ApplyPats.end()) {1480      if (find(ApplyRoots, It->second.get()) == ApplyRoots.end()) {1481        PrintError("apply pattern '" + RootName +1482                   "' is supposed to be a root but it does not redefine any of "1483                   "the defs of the match root");1484        return false;1485      }1486    }1487 1488    return true;1489  };1490 1491  // Look by pattern name, e.g.1492  //    (G_FNEG $x, $y):$root1493  if (auto MatchPatIt = MatchPats.find(RootName);1494      MatchPatIt != MatchPats.end()) {1495    MatchRoot = MatchPatIt->second.get();1496    return Finish();1497  }1498 1499  // Look by def:1500  //    (G_FNEG $root, $y)1501  auto LookupRes = MatchOpTable.lookup(RootName);1502  if (!LookupRes.Found) {1503    PrintError("Cannot find root '" + RootName + "' in match patterns!");1504    return false;1505  }1506 1507  MatchRoot = LookupRes.Def;1508  if (!MatchRoot) {1509    PrintError("Cannot use live-in operand '" + RootName +1510               "' as match pattern root!");1511    return false;1512  }1513 1514  return Finish();1515}1516 1517bool CombineRuleBuilder::buildRuleOperandsTable() {1518  const auto DiagnoseRedefMatch = [&](StringRef OpName) {1519    PrintError("Operand '" + OpName +1520               "' is defined multiple times in the 'match' patterns");1521  };1522 1523  const auto DiagnoseRedefApply = [&](StringRef OpName) {1524    PrintError("Operand '" + OpName +1525               "' is defined multiple times in the 'apply' patterns");1526  };1527 1528  for (auto &Pat : values(MatchPats)) {1529    auto *IP = dyn_cast<InstructionPattern>(Pat.get());1530    if (IP && !MatchOpTable.addPattern(IP, DiagnoseRedefMatch))1531      return false;1532  }1533 1534  for (auto &Pat : values(ApplyPats)) {1535    auto *IP = dyn_cast<InstructionPattern>(Pat.get());1536    if (IP && !ApplyOpTable.addPattern(IP, DiagnoseRedefApply))1537      return false;1538  }1539 1540  return true;1541}1542 1543bool CombineRuleBuilder::parseDefs(const DagInit &Def) {1544  if (Def.getOperatorAsDef(RuleDef.getLoc())->getName() != "defs") {1545    PrintError("Expected defs operator");1546    return false;1547  }1548 1549  SmallVector<StringRef> Roots;1550  for (unsigned I = 0, E = Def.getNumArgs(); I < E; ++I) {1551    if (isSpecificDef(*Def.getArg(I), "root")) {1552      Roots.emplace_back(Def.getArgNameStr(I));1553      continue;1554    }1555 1556    // Subclasses of GIDefMatchData should declare that this rule needs to pass1557    // data from the match stage to the apply stage, and ensure that the1558    // generated matcher has a suitable variable for it to do so.1559    if (const Record *MatchDataRec =1560            getDefOfSubClass(*Def.getArg(I), MatchDataClassName)) {1561      MatchDatas.emplace_back(Def.getArgNameStr(I),1562                              MatchDataRec->getValueAsString("Type"));1563      continue;1564    }1565 1566    // Otherwise emit an appropriate error message.1567    if (getDefOfSubClass(*Def.getArg(I), "GIDefKind"))1568      PrintError("This GIDefKind not implemented in tablegen");1569    else if (getDefOfSubClass(*Def.getArg(I), "GIDefKindWithArgs"))1570      PrintError("This GIDefKindWithArgs not implemented in tablegen");1571    else1572      PrintError("Expected a subclass of GIDefKind or a sub-dag whose "1573                 "operator is of type GIDefKindWithArgs");1574    return false;1575  }1576 1577  if (Roots.size() != 1) {1578    PrintError("Combine rules must have exactly one root");1579    return false;1580  }1581 1582  RootName = Roots.front();1583  return true;1584}1585 1586bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,1587                                          const PatternAlternatives &Alts,1588                                          const InstructionPattern &IP) {1589  auto StackTrace = PrettyStackTraceEmit(RuleDef, &IP);1590 1591  auto &M = addRuleMatcher(Alts);1592  InstructionMatcher &IM = M.addInstructionMatcher(IP.getName());1593  declareInstExpansion(CE, IM, IP.getName());1594 1595  DenseSet<const Pattern *> SeenPats;1596 1597  const auto FindOperandDef = [&](StringRef Op) -> InstructionPattern * {1598    return MatchOpTable.getDef(Op);1599  };1600 1601  if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&IP)) {1602    if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, *CGP, SeenPats,1603                                            FindOperandDef))1604      return false;1605  } else if (const auto *PFP = dyn_cast<PatFragPattern>(&IP)) {1606    if (!PFP->getPatFrag().canBeMatchRoot()) {1607      PrintError("cannot use '" + PFP->getInstName() + " as match root");1608      return false;1609    }1610 1611    if (!emitPatFragMatchPattern(CE, Alts, M, &IM, *PFP, SeenPats))1612      return false;1613  } else if (isa<BuiltinPattern>(&IP)) {1614    llvm_unreachable("No match builtins known!");1615  } else {1616    llvm_unreachable("Unknown kind of InstructionPattern!");1617  }1618 1619  // Emit remaining patterns1620  const bool IsUsingCustomCXXAction = hasOnlyCXXApplyPatterns();1621  SmallVector<CXXPattern *, 2> CXXMatchers;1622  for (auto &Pat : values(MatchPats)) {1623    if (SeenPats.contains(Pat.get()))1624      continue;1625 1626    switch (Pat->getKind()) {1627    case Pattern::K_AnyOpcode:1628      PrintError("wip_match_opcode can not be used with instruction patterns!");1629      return false;1630    case Pattern::K_PatFrag: {1631      if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,1632                                   *cast<PatFragPattern>(Pat.get()), SeenPats))1633        return false;1634      continue;1635    }1636    case Pattern::K_Builtin:1637      PrintError("No known match builtins");1638      return false;1639    case Pattern::K_CodeGenInstruction:1640      cast<InstructionPattern>(Pat.get())->reportUnreachable(RuleDef.getLoc());1641      return false;1642    case Pattern::K_CXX: {1643      // Delay emission for top-level C++ matchers (which can use MatchDatas).1644      if (IsUsingCustomCXXAction)1645        CXXMatchers.push_back(cast<CXXPattern>(Pat.get()));1646      else1647        addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);1648      continue;1649    }1650    default:1651      llvm_unreachable("unknown pattern kind!");1652    }1653  }1654 1655  return IsUsingCustomCXXAction ? emitCXXMatchApply(CE, M, CXXMatchers)1656                                : emitApplyPatterns(CE, M);1657}1658 1659bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,1660                                          const PatternAlternatives &Alts,1661                                          const AnyOpcodePattern &AOP) {1662  auto StackTrace = PrettyStackTraceEmit(RuleDef, &AOP);1663 1664  const bool IsUsingCustomCXXAction = hasOnlyCXXApplyPatterns();1665  for (const CodeGenInstruction *CGI : AOP.insts()) {1666    auto &M = addRuleMatcher(Alts, "wip_match_opcode '" + CGI->getName() + "'");1667 1668    InstructionMatcher &IM = M.addInstructionMatcher(AOP.getName());1669    declareInstExpansion(CE, IM, AOP.getName());1670    // declareInstExpansion needs to be identical, otherwise we need to create a1671    // CodeExpansions object here instead.1672    assert(IM.getInsnVarID() == 0);1673 1674    IM.addPredicate<InstructionOpcodeMatcher>(CGI);1675 1676    // Emit remaining patterns.1677    SmallVector<CXXPattern *, 2> CXXMatchers;1678    for (auto &Pat : values(MatchPats)) {1679      if (Pat.get() == &AOP)1680        continue;1681 1682      switch (Pat->getKind()) {1683      case Pattern::K_AnyOpcode:1684        PrintError("wip_match_opcode can only be present once!");1685        return false;1686      case Pattern::K_PatFrag: {1687        DenseSet<const Pattern *> SeenPats;1688        if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,1689                                     *cast<PatFragPattern>(Pat.get()),1690                                     SeenPats))1691          return false;1692        continue;1693      }1694      case Pattern::K_Builtin:1695        PrintError("No known match builtins");1696        return false;1697      case Pattern::K_CodeGenInstruction:1698        cast<InstructionPattern>(Pat.get())->reportUnreachable(1699            RuleDef.getLoc());1700        return false;1701      case Pattern::K_CXX: {1702        // Delay emission for top-level C++ matchers (which can use MatchDatas).1703        if (IsUsingCustomCXXAction)1704          CXXMatchers.push_back(cast<CXXPattern>(Pat.get()));1705        else1706          addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);1707        break;1708      }1709      default:1710        llvm_unreachable("unknown pattern kind!");1711      }1712    }1713 1714    const bool Res = IsUsingCustomCXXAction1715                         ? emitCXXMatchApply(CE, M, CXXMatchers)1716                         : emitApplyPatterns(CE, M);1717    if (!Res)1718      return false;1719  }1720 1721  return true;1722}1723 1724bool CombineRuleBuilder::emitPatFragMatchPattern(1725    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &RM,1726    InstructionMatcher *IM, const PatFragPattern &PFP,1727    DenseSet<const Pattern *> &SeenPats) {1728  auto StackTrace = PrettyStackTraceEmit(RuleDef, &PFP);1729 1730  if (!SeenPats.insert(&PFP).second)1731    return true;1732 1733  const auto &PF = PFP.getPatFrag();1734 1735  if (!IM) {1736    // When we don't have an IM, this means this PatFrag isn't reachable from1737    // the root. This is only acceptable if it doesn't define anything (e.g. a1738    // pure C++ PatFrag).1739    if (PF.num_out_params() != 0) {1740      PFP.reportUnreachable(RuleDef.getLoc());1741      return false;1742    }1743  } else {1744    // When an IM is provided, this is reachable from the root, and we're1745    // expecting to have output operands.1746    // TODO: If we want to allow for multiple roots we'll need a map of IMs1747    // then, and emission becomes a bit more complicated.1748    assert(PF.num_roots() == 1);1749  }1750 1751  CodeExpansions PatFragCEs;1752  if (!PFP.mapInputCodeExpansions(CE, PatFragCEs, RuleDef.getLoc()))1753    return false;1754 1755  // List of {ParamName, ArgName}.1756  // When all patterns have been emitted, find expansions in PatFragCEs named1757  // ArgName and add their expansion to CE using ParamName as the key.1758  SmallVector<std::pair<std::string, std::string>, 4> CEsToImport;1759 1760  // Map parameter names to the actual argument.1761  const auto OperandMapper =1762      [&](const InstructionOperand &O) -> InstructionOperand {1763    if (!O.isNamedOperand())1764      return O;1765 1766    StringRef ParamName = O.getOperandName();1767 1768    // Not sure what to do with those tbh. They should probably never be here.1769    assert(!O.isNamedImmediate() && "TODO: handle named imms");1770    unsigned PIdx = PF.getParamIdx(ParamName);1771 1772    // Map parameters to the argument values.1773    if (PIdx == (unsigned)-1) {1774      // This is a temp of the PatFragPattern, prefix the name to avoid1775      // conflicts.1776      return O.withNewName(1777          insertStrRef((PFP.getName() + "." + ParamName).str()));1778    }1779 1780    // The operand will be added to PatFragCEs's code expansions using the1781    // parameter's name. If it's bound to some operand during emission of the1782    // patterns, we'll want to add it to CE.1783    auto ArgOp = PFP.getOperand(PIdx);1784    if (ArgOp.isNamedOperand())1785      CEsToImport.emplace_back(ArgOp.getOperandName().str(), ParamName);1786 1787    if (ArgOp.getType() && O.getType() && ArgOp.getType() != O.getType()) {1788      StringRef PFName = PF.getName();1789      PrintWarning("impossible type constraints: operand " + Twine(PIdx) +1790                   " of '" + PFP.getName() + "' has type '" +1791                   ArgOp.getType().str() + "', but '" + PFName +1792                   "' constrains it to '" + O.getType().str() + "'");1793      if (ArgOp.isNamedOperand())1794        PrintNote("operand " + Twine(PIdx) + " of '" + PFP.getName() +1795                  "' is '" + ArgOp.getOperandName() + "'");1796      if (O.isNamedOperand())1797        PrintNote("argument " + Twine(PIdx) + " of '" + PFName + "' is '" +1798                  ParamName + "'");1799    }1800 1801    return ArgOp;1802  };1803 1804  // PatFragPatterns are only made of InstructionPatterns or CXXPatterns.1805  // Emit instructions from the root.1806  const auto &FragAlt = PF.getAlternative(Alts.lookup(&PFP));1807  const auto &FragAltOT = FragAlt.OpTable;1808  const auto LookupOperandDef =1809      [&](StringRef Op) -> const InstructionPattern * {1810    return FragAltOT.getDef(Op);1811  };1812 1813  DenseSet<const Pattern *> PatFragSeenPats;1814  for (const auto &[Idx, InOp] : enumerate(PF.out_params())) {1815    if (InOp.Kind != PatFrag::PK_Root)1816      continue;1817 1818    StringRef ParamName = InOp.Name;1819    const auto *Def = FragAltOT.getDef(ParamName);1820    assert(Def && "PatFrag::checkSemantics should have emitted an error if "1821                  "an out operand isn't defined!");1822    assert(isa<CodeGenInstructionPattern>(Def) &&1823           "Nested PatFrags not supported yet");1824 1825    if (!emitCodeGenInstructionMatchPattern(1826            PatFragCEs, Alts, RM, *IM, *cast<CodeGenInstructionPattern>(Def),1827            PatFragSeenPats, LookupOperandDef, OperandMapper))1828      return false;1829  }1830 1831  // Emit leftovers.1832  for (const auto &Pat : FragAlt.Pats) {1833    if (PatFragSeenPats.contains(Pat.get()))1834      continue;1835 1836    if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat.get())) {1837      addCXXPredicate(RM, PatFragCEs, *CXXPat, Alts);1838      continue;1839    }1840 1841    if (const auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {1842      IP->reportUnreachable(PF.getLoc());1843      return false;1844    }1845 1846    llvm_unreachable("Unexpected pattern kind in PatFrag");1847  }1848 1849  for (const auto &[ParamName, ArgName] : CEsToImport) {1850    // Note: we're find if ParamName already exists. It just means it's been1851    // bound before, so we prefer to keep the first binding.1852    CE.declare(ParamName, PatFragCEs.lookup(ArgName));1853  }1854 1855  return true;1856}1857 1858bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {1859  assert(MatchDatas.empty());1860 1861  DenseSet<const Pattern *> SeenPats;1862  StringMap<unsigned> OperandToTempRegID;1863 1864  for (auto *ApplyRoot : ApplyRoots) {1865    assert(isa<InstructionPattern>(ApplyRoot) &&1866           "Root can only be a InstructionPattern!");1867    if (!emitInstructionApplyPattern(CE, M,1868                                     cast<InstructionPattern>(*ApplyRoot),1869                                     SeenPats, OperandToTempRegID))1870      return false;1871  }1872 1873  for (auto &Pat : values(ApplyPats)) {1874    if (SeenPats.contains(Pat.get()))1875      continue;1876 1877    switch (Pat->getKind()) {1878    case Pattern::K_AnyOpcode:1879      llvm_unreachable("Unexpected pattern in apply!");1880    case Pattern::K_PatFrag:1881      // TODO: We could support pure C++ PatFrags as a temporary thing.1882      llvm_unreachable("Unexpected pattern in apply!");1883    case Pattern::K_Builtin:1884      if (!emitInstructionApplyPattern(CE, M, cast<BuiltinPattern>(*Pat),1885                                       SeenPats, OperandToTempRegID))1886        return false;1887      break;1888    case Pattern::K_CodeGenInstruction:1889      cast<CodeGenInstructionPattern>(*Pat).reportUnreachable(RuleDef.getLoc());1890      return false;1891    case Pattern::K_CXX: {1892      llvm_unreachable(1893          "CXX Pattern Emission should have been handled earlier!");1894    }1895    default:1896      llvm_unreachable("unknown pattern kind!");1897    }1898  }1899 1900  // Erase the root.1901  unsigned RootInsnID =1902      M.getInsnVarID(M.getInstructionMatcher(MatchRoot->getName()));1903  M.addAction<EraseInstAction>(RootInsnID);1904 1905  return true;1906}1907 1908bool CombineRuleBuilder::emitCXXMatchApply(CodeExpansions &CE, RuleMatcher &M,1909                                           ArrayRef<CXXPattern *> Matchers) {1910  assert(hasOnlyCXXApplyPatterns());1911  declareAllMatchDatasExpansions(CE);1912 1913  std::string CodeStr;1914  raw_string_ostream OS(CodeStr);1915 1916  for (auto &MD : MatchDatas)1917    OS << MD.Type << " " << MD.getVarName() << ";\n";1918 1919  if (!Matchers.empty()) {1920    OS << "// Match Patterns\n";1921    for (auto *M : Matchers) {1922      OS << "if(![&](){";1923      CodeExpander Expander(M->getRawCode(), CE, RuleDef.getLoc(),1924                            /*ShowExpansions=*/false);1925      Expander.emit(OS);1926      OS << "}()) {\n"1927         << "  return false;\n}\n";1928    }1929  }1930 1931  OS << "// Apply Patterns\n";1932  ListSeparator LS("\n");1933  for (auto &Pat : ApplyPats) {1934    auto *CXXPat = cast<CXXPattern>(Pat.second.get());1935    CodeExpander Expander(CXXPat->getRawCode(), CE, RuleDef.getLoc(),1936                          /*ShowExpansions=*/false);1937    OS << LS;1938    Expander.emit(OS);1939  }1940 1941  const auto &Code = CXXPredicateCode::getCustomActionCode(CodeStr);1942  M.setCustomCXXAction(Code.getEnumNameWithPrefix(CXXCustomActionPrefix));1943  return true;1944}1945 1946bool CombineRuleBuilder::emitInstructionApplyPattern(1947    CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,1948    DenseSet<const Pattern *> &SeenPats,1949    StringMap<unsigned> &OperandToTempRegID) {1950  auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);1951 1952  if (!SeenPats.insert(&P).second)1953    return true;1954 1955  // First, render the uses.1956  for (auto &Op : P.named_operands()) {1957    if (Op.isDef())1958      continue;1959 1960    StringRef OpName = Op.getOperandName();1961    if (const auto *DefPat = ApplyOpTable.getDef(OpName)) {1962      if (!emitInstructionApplyPattern(CE, M, *DefPat, SeenPats,1963                                       OperandToTempRegID))1964        return false;1965    } else {1966      // If we have no def, check this exists in the MatchRoot.1967      if (!Op.isNamedImmediate() && !MatchOpTable.lookup(OpName).Found) {1968        PrintError("invalid output operand '" + OpName +1969                   "': operand is not a live-in of the match pattern, and it "1970                   "has no definition");1971        return false;1972      }1973    }1974  }1975 1976  if (const auto *BP = dyn_cast<BuiltinPattern>(&P))1977    return emitBuiltinApplyPattern(CE, M, *BP, OperandToTempRegID);1978 1979  if (isa<PatFragPattern>(&P))1980    llvm_unreachable("PatFragPatterns is not supported in 'apply'!");1981 1982  auto &CGIP = cast<CodeGenInstructionPattern>(P);1983 1984  // Now render this inst.1985  auto &DstMI =1986      M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &CGIP.getInst());1987 1988  bool HasEmittedIntrinsicID = false;1989  const auto EmitIntrinsicID = [&]() {1990    assert(CGIP.isIntrinsic());1991    DstMI.addRenderer<IntrinsicIDRenderer>(CGIP.getIntrinsic());1992    HasEmittedIntrinsicID = true;1993  };1994 1995  for (auto &Op : P.operands()) {1996    // Emit the intrinsic ID after the last def.1997    if (CGIP.isIntrinsic() && !Op.isDef() && !HasEmittedIntrinsicID)1998      EmitIntrinsicID();1999 2000    if (Op.isNamedImmediate()) {2001      PrintError("invalid output operand '" + Op.getOperandName() +2002                 "': output immediates cannot be named");2003      PrintNote("while emitting pattern '" + P.getName() + "' (" +2004                P.getInstName() + ")");2005      return false;2006    }2007 2008    if (Op.hasImmValue()) {2009      if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, CGIP, Op))2010        return false;2011      continue;2012    }2013 2014    StringRef OpName = Op.getOperandName();2015 2016    // Uses of operand.2017    if (!Op.isDef()) {2018      if (auto It = OperandToTempRegID.find(OpName);2019          It != OperandToTempRegID.end()) {2020        assert(!MatchOpTable.lookup(OpName).Found &&2021               "Temp reg is also from match pattern?");2022        DstMI.addRenderer<TempRegRenderer>(It->second);2023      } else {2024        // This should be a match live in or a redef of a matched instr.2025        // If it's a use of a temporary register, then we messed up somewhere -2026        // the previous condition should have passed.2027        assert(MatchOpTable.lookup(OpName).Found &&2028               !ApplyOpTable.getDef(OpName) && "Temp reg not emitted yet!");2029        DstMI.addRenderer<CopyRenderer>(OpName);2030      }2031      continue;2032    }2033 2034    // Determine what we're dealing with. Are we replacing a matched2035    // instruction? Creating a new one?2036    auto OpLookupRes = MatchOpTable.lookup(OpName);2037    if (OpLookupRes.Found) {2038      if (OpLookupRes.isLiveIn()) {2039        // live-in of the match pattern.2040        PrintError("Cannot define live-in operand '" + OpName +2041                   "' in the 'apply' pattern");2042        return false;2043      }2044      assert(OpLookupRes.Def);2045 2046      // TODO: Handle this. We need to mutate the instr, or delete the old2047      // one.2048      //       Likewise, we also need to ensure we redef everything, if the2049      //       instr has more than one def, we need to redef all or nothing.2050      if (OpLookupRes.Def != MatchRoot) {2051        PrintError("redefining an instruction other than the root is not "2052                   "supported (operand '" +2053                   OpName + "')");2054        return false;2055      }2056      // redef of a match2057      DstMI.addRenderer<CopyRenderer>(OpName);2058      continue;2059    }2060 2061    // Define a new register unique to the apply patterns (AKA a "temp"2062    // register).2063    unsigned TempRegID;2064    if (auto It = OperandToTempRegID.find(OpName);2065        It != OperandToTempRegID.end()) {2066      TempRegID = It->second;2067    } else {2068      // This is a brand new register.2069      TempRegID = M.allocateTempRegID();2070      OperandToTempRegID[OpName] = TempRegID;2071      const auto Ty = Op.getType();2072      if (!Ty) {2073        PrintError("def of a new register '" + OpName +2074                   "' in the apply patterns must have a type");2075        return false;2076      }2077 2078      declareTempRegExpansion(CE, TempRegID, OpName);2079      // Always insert the action at the beginning, otherwise we may end up2080      // using the temp reg before it's available.2081      auto Result = getLLTCodeGenOrTempType(Ty, M);2082      if (!Result)2083        return false;2084      M.insertAction<MakeTempRegisterAction>(M.actions_begin(), *Result,2085                                             TempRegID);2086    }2087 2088    DstMI.addRenderer<TempRegRenderer>(TempRegID, /*IsDef=*/true);2089  }2090 2091  // Some intrinsics have no in operands, ensure the ID is still emitted in such2092  // cases.2093  if (CGIP.isIntrinsic() && !HasEmittedIntrinsicID)2094    EmitIntrinsicID();2095 2096  // Render MIFlags2097  if (const auto *FI = CGIP.getMIFlagsInfo()) {2098    for (StringRef InstName : FI->copy_flags())2099      DstMI.addCopiedMIFlags(M.getInstructionMatcher(InstName));2100    for (StringRef F : FI->set_flags())2101      DstMI.addSetMIFlags(F);2102    for (StringRef F : FI->unset_flags())2103      DstMI.addUnsetMIFlags(F);2104  }2105 2106  // Don't allow mutating opcodes for GISel combiners. We want a more precise2107  // handling of MIFlags so we require them to be explicitly preserved.2108  //2109  // TODO: We don't mutate very often, if at all in combiners, but it'd be nice2110  // to re-enable this. We'd then need to always clear MIFlags when mutating2111  // opcodes, and never mutate an inst that we copy flags from.2112  // DstMI.chooseInsnToMutate(M);2113  declareInstExpansion(CE, DstMI, P.getName());2114 2115  return true;2116}2117 2118bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(2119    RuleMatcher &M, BuildMIAction &DstMI, const CodeGenInstructionPattern &P,2120    const InstructionOperand &O) {2121  // If we have a type, we implicitly emit a G_CONSTANT, except for G_CONSTANT2122  // itself where we emit a CImm.2123  //2124  // No type means we emit a simple imm.2125  // G_CONSTANT is a special case and needs a CImm though so this is likely a2126  // mistake.2127  const bool isGConstant = P.is("G_CONSTANT");2128  const auto Ty = O.getType();2129  if (!Ty) {2130    if (isGConstant) {2131      PrintError("'G_CONSTANT' immediate must be typed!");2132      PrintNote("while emitting pattern '" + P.getName() + "' (" +2133                P.getInstName() + ")");2134      return false;2135    }2136 2137    DstMI.addRenderer<ImmRenderer>(O.getImmValue());2138    return true;2139  }2140 2141  auto ImmTy = getLLTCodeGenOrTempType(Ty, M);2142  if (!ImmTy)2143    return false;2144 2145  if (isGConstant) {2146    DstMI.addRenderer<ImmRenderer>(O.getImmValue(), *ImmTy);2147    return true;2148  }2149 2150  unsigned TempRegID = M.allocateTempRegID();2151  // Ensure MakeTempReg & the BuildConstantAction occur at the beginning.2152  auto InsertIt = M.insertAction<MakeTempRegisterAction>(M.actions_begin(),2153                                                         *ImmTy, TempRegID);2154  M.insertAction<BuildConstantAction>(++InsertIt, TempRegID, O.getImmValue());2155  DstMI.addRenderer<TempRegRenderer>(TempRegID);2156  return true;2157}2158 2159bool CombineRuleBuilder::emitBuiltinApplyPattern(2160    CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,2161    StringMap<unsigned> &OperandToTempRegID) {2162  const auto Error = [&](Twine Reason) {2163    PrintError("cannot emit '" + P.getInstName() + "' builtin: " + Reason);2164    return false;2165  };2166 2167  switch (P.getBuiltinKind()) {2168  case BI_EraseRoot: {2169    // Root is always inst 0.2170    M.addAction<EraseInstAction>(/*InsnID*/ 0);2171    return true;2172  }2173  case BI_ReplaceReg: {2174    StringRef Old = P.getOperand(0).getOperandName();2175    StringRef New = P.getOperand(1).getOperandName();2176 2177    if (!ApplyOpTable.lookup(New).Found && !MatchOpTable.lookup(New).Found)2178      return Error("unknown operand '" + Old + "'");2179 2180    auto &OldOM = M.getOperandMatcher(Old);2181    if (auto It = OperandToTempRegID.find(New);2182        It != OperandToTempRegID.end()) {2183      // Replace with temp reg.2184      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),2185                                    It->second);2186    } else {2187      // Replace with matched reg.2188      auto &NewOM = M.getOperandMatcher(New);2189      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),2190                                    NewOM.getInsnVarID(), NewOM.getOpIdx());2191    }2192    // checkSemantics should have ensured that we can only rewrite the root.2193    // Ensure we're deleting it.2194    assert(MatchOpTable.getDef(Old) == MatchRoot);2195    return true;2196  }2197  }2198 2199  llvm_unreachable("Unknown BuiltinKind!");2200}2201 2202bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) {2203  if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&P)) {2204    StringRef InstName = CGP->getInst().getName();2205    return (InstName == "G_CONSTANT" || InstName == "G_FCONSTANT") &&2206           OpIdx == 1;2207  }2208 2209  llvm_unreachable("TODO");2210}2211 2212bool CombineRuleBuilder::emitCodeGenInstructionMatchPattern(2213    CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,2214    InstructionMatcher &IM, const CodeGenInstructionPattern &P,2215    DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,2216    OperandMapperFnRef OperandMapper) {2217  auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);2218 2219  if (!SeenPats.insert(&P).second)2220    return true;2221 2222  IM.addPredicate<InstructionOpcodeMatcher>(&P.getInst());2223  declareInstExpansion(CE, IM, P.getName());2224 2225  // If this is an intrinsic, check the intrinsic ID.2226  if (P.isIntrinsic()) {2227    // The IntrinsicID's operand is the first operand after the defs.2228    OperandMatcher &OM = IM.addOperand(P.getNumInstDefs(), "$intrinsic_id",2229                                       AllocatedTemporariesBaseID++);2230    OM.addPredicate<IntrinsicIDOperandMatcher>(P.getIntrinsic());2231  }2232 2233  // Check flags if needed.2234  if (const auto *FI = P.getMIFlagsInfo()) {2235    assert(FI->copy_flags().empty());2236 2237    if (const auto &SetF = FI->set_flags(); !SetF.empty())2238      IM.addPredicate<MIFlagsInstructionPredicateMatcher>(SetF.getArrayRef());2239    if (const auto &UnsetF = FI->unset_flags(); !UnsetF.empty())2240      IM.addPredicate<MIFlagsInstructionPredicateMatcher>(UnsetF.getArrayRef(),2241                                                          /*CheckNot=*/true);2242  }2243 2244  for (auto [Idx, OriginalO] : enumerate(P.operands())) {2245    // Remap the operand. This is used when emitting InstructionPatterns inside2246    // PatFrags, so it can remap them to the arguments passed to the pattern.2247    //2248    // We use the remapped operand to emit immediates, and for the symbolic2249    // operand names (in IM.addOperand). CodeExpansions and OperandTable lookups2250    // still use the original name.2251    //2252    // The "def" flag on the remapped operand is always ignored.2253    auto RemappedO = OperandMapper(OriginalO);2254    assert(RemappedO.isNamedOperand() == OriginalO.isNamedOperand() &&2255           "Cannot remap an unnamed operand to a named one!");2256 2257    const auto Ty = RemappedO.getType();2258 2259    const auto OpName =2260        RemappedO.isNamedOperand() ? RemappedO.getOperandName().str() : "";2261 2262    // For intrinsics, the first use operand is the intrinsic id, so the true2263    // operand index is shifted by 1.2264    //2265    // From now on:2266    //    Idx = index in the pattern operand list.2267    //    RealIdx = expected index in the MachineInstr.2268    const unsigned RealIdx =2269        (P.isIntrinsic() && !OriginalO.isDef()) ? (Idx + 1) : Idx;2270 2271    if (Ty.isVariadicPack() && M.hasOperand(OpName)) {2272      // TODO: We could add some CheckIsSameOperand opcode variant that checks2273      // all operands. We could also just emit a C++ code snippet lazily to do2274      // the check since it's probably fairly rare that we need to do it.2275      //2276      // I'm just not sure it's worth the effort at this stage.2277      PrintError("each instance of a " + PatternType::VariadicClassName +2278                 " operand must have a unique name within the match patterns");2279      PrintNote("'" + OpName + "' is used multiple times");2280      return false;2281    }2282 2283    OperandMatcher &OM =2284        IM.addOperand(RealIdx, OpName, AllocatedTemporariesBaseID++,2285                      /*IsVariadic=*/Ty.isVariadicPack());2286    if (!OpName.empty())2287      declareOperandExpansion(CE, OM, OriginalO.getOperandName());2288 2289    if (Ty.isVariadicPack()) {2290      // In the presence of variadics, the InstructionMatcher won't insert a2291      // InstructionNumOperandsMatcher implicitly, so we have to emit our own.2292      assert((Idx + 1) == P.operands_size() &&2293             "VariadicPack isn't last operand!");2294      auto VPTI = Ty.getVariadicPackTypeInfo();2295      assert(VPTI.Min > 0 && (VPTI.Max == 0 || VPTI.Max > VPTI.Min));2296      IM.addPredicate<InstructionNumOperandsMatcher>(2297          RealIdx + VPTI.Min, InstructionNumOperandsMatcher::CheckKind::GE);2298      if (VPTI.Max) {2299        IM.addPredicate<InstructionNumOperandsMatcher>(2300            RealIdx + VPTI.Max, InstructionNumOperandsMatcher::CheckKind::LE);2301      }2302      break;2303    }2304 2305    // Handle immediates.2306    if (RemappedO.hasImmValue()) {2307      if (isLiteralImm(P, Idx))2308        OM.addPredicate<LiteralIntOperandMatcher>(RemappedO.getImmValue());2309      else2310        OM.addPredicate<ConstantIntOperandMatcher>(RemappedO.getImmValue());2311    }2312 2313    // Handle typed operands, but only bother to check if it hasn't been done2314    // before.2315    //2316    // getOperandMatcher will always return the first OM to have been created2317    // for that Operand. "OM" here is always a new OperandMatcher.2318    //2319    // Always emit a check for unnamed operands.2320    if (Ty && (OpName.empty() ||2321               !M.getOperandMatcher(OpName).contains<LLTOperandMatcher>())) {2322      // TODO: We could support GITypeOf here on the condition that the2323      // OperandMatcher exists already. Though it's clunky to make this work2324      // and isn't all that useful so it's just rejected in typecheckPatterns2325      // at this time.2326      assert(Ty.isLLT());2327      OM.addPredicate<LLTOperandMatcher>(getLLTCodeGen(Ty));2328    }2329 2330    // Stop here if the operand is a def, or if it had no name.2331    if (OriginalO.isDef() || !OriginalO.isNamedOperand())2332      continue;2333 2334    const auto *DefPat = LookupOperandDef(OriginalO.getOperandName());2335    if (!DefPat)2336      continue;2337 2338    if (OriginalO.hasImmValue()) {2339      assert(!OpName.empty());2340      // This is a named immediate that also has a def, that's not okay.2341      // e.g.2342      //    (G_SEXT $y, (i32 0))2343      //    (COPY $x, 42:$y)2344      PrintError("'" + OpName +2345                 "' is a named immediate, it cannot be defined by another "2346                 "instruction");2347      PrintNote("'" + OpName + "' is defined by '" + DefPat->getName() + "'");2348      return false;2349    }2350 2351    // From here we know that the operand defines an instruction, and we need to2352    // emit it.2353    auto InstOpM =2354        OM.addPredicate<InstructionOperandMatcher>(M, DefPat->getName());2355    if (!InstOpM) {2356      // TODO: copy-pasted from GlobalISelEmitter.cpp. Is it still relevant2357      // here?2358      PrintError("Nested instruction '" + DefPat->getName() +2359                 "' cannot be the same as another operand '" +2360                 OriginalO.getOperandName() + "'");2361      return false;2362    }2363 2364    auto &IM = (*InstOpM)->getInsnMatcher();2365    if (const auto *CGIDef = dyn_cast<CodeGenInstructionPattern>(DefPat)) {2366      if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, *CGIDef,2367                                              SeenPats, LookupOperandDef,2368                                              OperandMapper))2369        return false;2370      continue;2371    }2372 2373    if (const auto *PFPDef = dyn_cast<PatFragPattern>(DefPat)) {2374      if (!emitPatFragMatchPattern(CE, Alts, M, &IM, *PFPDef, SeenPats))2375        return false;2376      continue;2377    }2378 2379    llvm_unreachable("unknown type of InstructionPattern");2380  }2381 2382  return true;2383}2384 2385//===- GICombinerEmitter --------------------------------------------------===//2386 2387/// Main implementation class. This emits the tablegenerated output.2388///2389/// It collects rules, uses `CombineRuleBuilder` to parse them and accumulate2390/// RuleMatchers, then takes all the necessary state/data from the various2391/// static storage pools and wires them together to emit the match table &2392/// associated function/data structures.2393class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter {2394  const RecordKeeper &Records;2395  StringRef Name;2396  const CodeGenTarget &Target;2397  const Record *Combiner;2398  unsigned NextRuleID = 0;2399 2400  // List all combine rules (ID, name) imported.2401  // Note that the combiner rule ID is different from the RuleMatcher ID. The2402  // latter is internal to the MatchTable, the former is the canonical ID of the2403  // combine rule used to disable/enable it.2404  std::vector<std::pair<unsigned, std::string>> AllCombineRules;2405 2406  // Keep track of all rules we've seen so far to ensure we don't process2407  // the same rule twice.2408  StringSet<> RulesSeen;2409 2410  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules);2411 2412  void emitRuleConfigImpl(raw_ostream &OS);2413 2414  void emitAdditionalImpl(raw_ostream &OS) override;2415 2416  void emitMIPredicateFns(raw_ostream &OS) override;2417  void emitLeafPredicateFns(raw_ostream &OS) override;2418  void emitI64ImmPredicateFns(raw_ostream &OS) override;2419  void emitAPFloatImmPredicateFns(raw_ostream &OS) override;2420  void emitAPIntImmPredicateFns(raw_ostream &OS) override;2421  void emitTestSimplePredicate(raw_ostream &OS) override;2422  void emitRunCustomAction(raw_ostream &OS) override;2423 2424  const CodeGenTarget &getTarget() const override { return Target; }2425  StringRef getClassName() const override {2426    return Combiner->getValueAsString("Classname");2427  }2428 2429  StringRef getCombineAllMethodName() const {2430    return Combiner->getValueAsString("CombineAllMethodName");2431  }2432 2433  std::string getRuleConfigClassName() const {2434    return getClassName().str() + "RuleConfig";2435  }2436 2437  void gatherRules(std::vector<RuleMatcher> &Rules,2438                   ArrayRef<const Record *> RulesAndGroups);2439 2440public:2441  explicit GICombinerEmitter(const RecordKeeper &RK,2442                             const CodeGenTarget &Target, StringRef Name,2443                             const Record *Combiner);2444  ~GICombinerEmitter() override = default;2445 2446  void run(raw_ostream &OS);2447};2448 2449void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) {2450  OS << "struct " << getRuleConfigClassName() << " {\n"2451     << "  SparseBitVector<> DisabledRules;\n\n"2452     << "  bool isRuleEnabled(unsigned RuleID) const;\n"2453     << "  bool parseCommandLineOption();\n"2454     << "  bool setRuleEnabled(StringRef RuleIdentifier);\n"2455     << "  bool setRuleDisabled(StringRef RuleIdentifier);\n"2456     << "};\n\n";2457 2458  std::vector<std::pair<std::string, std::string>> Cases;2459  Cases.reserve(AllCombineRules.size());2460 2461  for (const auto &[ID, Name] : AllCombineRules)2462    Cases.emplace_back(Name, "return " + to_string(ID) + ";\n");2463 2464  OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "2465        "RuleIdentifier) {\n"2466     << "  uint64_t I;\n"2467     << "  // getAtInteger(...) returns false on success\n"2468     << "  bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"2469     << "  if (Parsed)\n"2470     << "    return I;\n\n"2471     << "#ifndef NDEBUG\n";2472  StringMatcher Matcher("RuleIdentifier", Cases, OS);2473  Matcher.Emit();2474  OS << "#endif // ifndef NDEBUG\n\n"2475     << "  return std::nullopt;\n"2476     << "}\n";2477 2478  OS << "static std::optional<std::pair<uint64_t, uint64_t>> "2479        "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"2480     << "  std::pair<StringRef, StringRef> RangePair = "2481        "RuleIdentifier.split('-');\n"2482     << "  if (!RangePair.second.empty()) {\n"2483     << "    const auto First = "2484        "getRuleIdxForIdentifier(RangePair.first);\n"2485     << "    const auto Last = "2486        "getRuleIdxForIdentifier(RangePair.second);\n"2487     << "    if (!First || !Last)\n"2488     << "      return std::nullopt;\n"2489     << "    if (First >= Last)\n"2490     << "      report_fatal_error(\"Beginning of range should be before "2491        "end of range\");\n"2492     << "    return {{*First, *Last + 1}};\n"2493     << "  }\n"2494     << "  if (RangePair.first == \"*\") {\n"2495     << "    return {{0, " << AllCombineRules.size() << "}};\n"2496     << "  }\n"2497     << "  const auto I = getRuleIdxForIdentifier(RangePair.first);\n"2498     << "  if (!I)\n"2499     << "    return std::nullopt;\n"2500     << "  return {{*I, *I + 1}};\n"2501     << "}\n\n";2502 2503  for (bool Enabled : {true, false}) {2504    OS << "bool " << getRuleConfigClassName() << "::setRule"2505       << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"2506       << "  auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"2507       << "  if (!MaybeRange)\n"2508       << "    return false;\n"2509       << "  for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"2510       << "    DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"2511       << "  return true;\n"2512       << "}\n\n";2513  }2514 2515  OS << "static std::vector<std::string> " << Name << "Option;\n"2516     << "static cl::list<std::string> " << Name << "DisableOption(\n"2517     << "    \"" << Name.lower() << "-disable-rule\",\n"2518     << "    cl::desc(\"Disable one or more combiner rules temporarily in "2519     << "the " << Name << " pass\"),\n"2520     << "    cl::CommaSeparated,\n"2521     << "    cl::Hidden,\n"2522     << "    cl::cat(GICombinerOptionCategory),\n"2523     << "    cl::callback([](const std::string &Str) {\n"2524     << "      " << Name << "Option.push_back(Str);\n"2525     << "    }));\n"2526     << "static cl::list<std::string> " << Name << "OnlyEnableOption(\n"2527     << "    \"" << Name.lower() << "-only-enable-rule\",\n"2528     << "    cl::desc(\"Disable all rules in the " << Name2529     << " pass then re-enable the specified ones\"),\n"2530     << "    cl::Hidden,\n"2531     << "    cl::cat(GICombinerOptionCategory),\n"2532     << "    cl::callback([](const std::string &CommaSeparatedArg) {\n"2533     << "      StringRef Str = CommaSeparatedArg;\n"2534     << "      " << Name << "Option.push_back(\"*\");\n"2535     << "      do {\n"2536     << "        auto X = Str.split(\",\");\n"2537     << "        " << Name << "Option.push_back((\"!\" + X.first).str());\n"2538     << "        Str = X.second;\n"2539     << "      } while (!Str.empty());\n"2540     << "    }));\n"2541     << "\n\n"2542     << "bool " << getRuleConfigClassName()2543     << "::isRuleEnabled(unsigned RuleID) const {\n"2544     << "    return  !DisabledRules.test(RuleID);\n"2545     << "}\n"2546     << "bool " << getRuleConfigClassName() << "::parseCommandLineOption() {\n"2547     << "  for (StringRef Identifier : " << Name << "Option) {\n"2548     << "    bool Enabled = Identifier.consume_front(\"!\");\n"2549     << "    if (Enabled && !setRuleEnabled(Identifier))\n"2550     << "      return false;\n"2551     << "    if (!Enabled && !setRuleDisabled(Identifier))\n"2552     << "      return false;\n"2553     << "  }\n"2554     << "  return true;\n"2555     << "}\n\n";2556}2557 2558void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) {2559  OS << "bool " << getClassName() << "::" << getCombineAllMethodName()2560     << "(MachineInstr &I) const {\n"2561     << "  const TargetSubtargetInfo &ST = MF.getSubtarget();\n"2562     << "  const PredicateBitset AvailableFeatures = "2563        "getAvailableFeatures();\n"2564     << "  B.setInstrAndDebugLoc(I);\n"2565     << "  State.MIs.clear();\n"2566     << "  State.MIs.push_back(&I);\n"2567     << "  if (executeMatchTable(*this, State, ExecInfo, B"2568     << ", getMatchTable(), *ST.getInstrInfo(), MRI, "2569        "*MRI.getTargetRegisterInfo(), *ST.getRegBankInfo(), AvailableFeatures"2570     << ", /*CoverageInfo*/ nullptr)) {\n"2571     << "    return true;\n"2572     << "  }\n\n"2573     << "  return false;\n"2574     << "}\n\n";2575}2576 2577void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) {2578  auto MatchCode = CXXPredicateCode::getAllMatchCode();2579  emitMIPredicateFnsImpl<const CXXPredicateCode *>(2580      OS, "", ArrayRef<const CXXPredicateCode *>(MatchCode),2581      [](const CXXPredicateCode *C) -> StringRef { return C->BaseEnumName; },2582      [](const CXXPredicateCode *C) -> StringRef { return C->Code; });2583}2584 2585void GICombinerEmitter::emitLeafPredicateFns(raw_ostream &OS) {2586  // Unused, but still needs to be called.2587  emitLeafPredicateFnsImpl<unsigned>(2588      OS, "", {}, [](unsigned) { return ""; }, [](unsigned) { return ""; });2589}2590 2591void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {2592  // Unused, but still needs to be called.2593  emitImmPredicateFnsImpl<unsigned>(2594      OS, "I64", "int64_t", {}, [](unsigned) { return ""; },2595      [](unsigned) { return ""; });2596}2597 2598void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {2599  // Unused, but still needs to be called.2600  emitImmPredicateFnsImpl<unsigned>(2601      OS, "APFloat", "const APFloat &", {}, [](unsigned) { return ""; },2602      [](unsigned) { return ""; });2603}2604 2605void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {2606  // Unused, but still needs to be called.2607  emitImmPredicateFnsImpl<unsigned>(2608      OS, "APInt", "const APInt &", {}, [](unsigned) { return ""; },2609      [](unsigned) { return ""; });2610}2611 2612void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) {2613  if (!AllCombineRules.empty()) {2614    OS << "enum {\n";2615    std::string EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";2616    // To avoid emitting a switch, we expect that all those rules are in order.2617    // That way we can just get the RuleID from the enum by subtracting2618    // (GICXXPred_Invalid + 1).2619    [[maybe_unused]] unsigned ExpectedID = 0;2620    for (const auto &ID : keys(AllCombineRules)) {2621      assert(ExpectedID == ID && "combine rules are not ordered!");2622      ++ExpectedID;2623      OS << "  " << getIsEnabledPredicateEnumName(ID) << EnumeratorSeparator;2624      EnumeratorSeparator = ",\n";2625    }2626    OS << "};\n\n";2627  }2628 2629  OS << "bool " << getClassName()2630     << "::testSimplePredicate(unsigned Predicate) const {\n"2631     << "    return RuleConfig.isRuleEnabled(Predicate - "2632        "GICXXPred_Invalid - "2633        "1);\n"2634     << "}\n";2635}2636 2637void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) {2638  const auto CustomActionsCode = CXXPredicateCode::getAllCustomActionsCode();2639 2640  if (!CustomActionsCode.empty()) {2641    OS << "enum {\n";2642    std::string EnumeratorSeparator = " = GICXXCustomAction_Invalid + 1,\n";2643    for (const auto &CA : CustomActionsCode) {2644      OS << "  " << CA->getEnumNameWithPrefix(CXXCustomActionPrefix)2645         << EnumeratorSeparator;2646      EnumeratorSeparator = ",\n";2647    }2648    OS << "};\n";2649  }2650 2651  OS << "bool " << getClassName()2652     << "::runCustomAction(unsigned ApplyID, const MatcherState &State, "2653        "NewMIVector &OutMIs) const "2654        "{\n  Helper.getBuilder().setInstrAndDebugLoc(*State.MIs[0]);\n";2655  if (!CustomActionsCode.empty()) {2656    OS << "  switch(ApplyID) {\n";2657    for (const auto &CA : CustomActionsCode) {2658      OS << "  case " << CA->getEnumNameWithPrefix(CXXCustomActionPrefix)2659         << ":{\n"2660         << "    " << join(split(CA->Code, '\n'), "\n    ") << '\n'2661         << "    return true;\n";2662      OS << "  }\n";2663    }2664    OS << "  }\n";2665  }2666  OS << "  llvm_unreachable(\"Unknown Apply Action\");\n"2667     << "}\n";2668}2669 2670GICombinerEmitter::GICombinerEmitter(const RecordKeeper &RK,2671                                     const CodeGenTarget &Target,2672                                     StringRef Name, const Record *Combiner)2673    : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}2674 2675MatchTable2676GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) {2677  std::vector<Matcher *> InputRules;2678  for (Matcher &Rule : Rules)2679    InputRules.push_back(&Rule);2680 2681  unsigned CurrentOrdering = 0;2682  StringMap<unsigned> OpcodeOrder;2683  for (RuleMatcher &Rule : Rules) {2684    const StringRef Opcode = Rule.getOpcode();2685    assert(!Opcode.empty() && "Didn't expect an undefined opcode");2686    if (OpcodeOrder.try_emplace(Opcode, CurrentOrdering).second)2687      ++CurrentOrdering;2688  }2689 2690  llvm::stable_sort(InputRules, [&OpcodeOrder](const Matcher *A,2691                                               const Matcher *B) {2692    auto *L = static_cast<const RuleMatcher *>(A);2693    auto *R = static_cast<const RuleMatcher *>(B);2694    return std::tuple(OpcodeOrder[L->getOpcode()],2695                      L->insnmatchers_front().getNumOperandMatchers()) <2696           std::tuple(OpcodeOrder[R->getOpcode()],2697                      R->insnmatchers_front().getNumOperandMatchers());2698  });2699 2700  for (Matcher *Rule : InputRules)2701    Rule->optimize();2702 2703  std::vector<std::unique_ptr<Matcher>> MatcherStorage;2704  std::vector<Matcher *> OptRules =2705      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);2706 2707  for (Matcher *Rule : OptRules)2708    Rule->optimize();2709 2710  OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);2711 2712  return MatchTable::buildTable(OptRules, /*WithCoverage*/ false,2713                                /*IsCombiner*/ true);2714}2715 2716/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.2717void GICombinerEmitter::gatherRules(std::vector<RuleMatcher> &ActiveRules,2718                                    ArrayRef<const Record *> RulesAndGroups) {2719  for (const Record *Rec : RulesAndGroups) {2720    if (!Rec->isValueUnset("Rules")) {2721      gatherRules(ActiveRules, Rec->getValueAsListOfDefs("Rules"));2722      continue;2723    }2724 2725    StringRef RuleName = Rec->getName();2726    if (!RulesSeen.insert(RuleName).second) {2727      PrintWarning(Rec->getLoc(),2728                   "skipping rule '" + Rec->getName() +2729                       "' because it has already been processed");2730      continue;2731    }2732 2733    AllCombineRules.emplace_back(NextRuleID, Rec->getName().str());2734    CombineRuleBuilder CRB(Target, SubtargetFeatures, *Rec, NextRuleID++,2735                           ActiveRules);2736 2737    if (!CRB.parseAll()) {2738      assert(ErrorsPrinted && "Parsing failed without errors!");2739      continue;2740    }2741 2742    if (StopAfterParse) {2743      CRB.print(outs());2744      continue;2745    }2746 2747    if (!CRB.emitRuleMatchers()) {2748      assert(ErrorsPrinted && "Emission failed without errors!");2749      continue;2750    }2751  }2752}2753 2754void GICombinerEmitter::run(raw_ostream &OS) {2755  InstructionOpcodeMatcher::initOpcodeValuesMap(Target);2756  LLTOperandMatcher::initTypeIDValuesMap();2757 2758  TGTimer &Timer = Records.getTimer();2759  Timer.startTimer("Gather rules");2760  std::vector<RuleMatcher> Rules;2761  gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));2762  if (ErrorsPrinted)2763    PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");2764 2765  if (StopAfterParse)2766    return;2767 2768  Timer.startTimer("Creating Match Table");2769  unsigned MaxTemporaries = 0;2770  for (const auto &Rule : Rules)2771    MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());2772 2773  llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {2774    if (A.isHigherPriorityThan(B)) {2775      assert(!B.isHigherPriorityThan(A) && "Cannot be more important "2776                                           "and less important at "2777                                           "the same time");2778      return true;2779    }2780    return false;2781  });2782 2783  const MatchTable Table = buildMatchTable(Rules);2784 2785  Timer.startTimer("Emit combiner");2786 2787  emitSourceFileHeader(getClassName().str() + " Combiner Match Table", OS);2788 2789  SmallVector<LLTCodeGen, 16> TypeObjects;2790  append_range(TypeObjects, KnownTypes);2791  llvm::sort(TypeObjects);2792 2793  // Hack: Avoid empty declarator.2794  if (TypeObjects.empty())2795    TypeObjects.push_back(LLT::scalar(1));2796 2797  // GET_GICOMBINER_DEPS, which pulls in extra dependencies.2798  OS << "#ifdef GET_GICOMBINER_DEPS\n"2799     << "#include \"llvm/ADT/SparseBitVector.h\"\n"2800     << "namespace llvm {\n"2801     << "extern cl::OptionCategory GICombinerOptionCategory;\n"2802     << "} // end namespace llvm\n"2803     << "#endif // ifdef GET_GICOMBINER_DEPS\n\n";2804 2805  // GET_GICOMBINER_TYPES, which needs to be included before the declaration of2806  // the class.2807  OS << "#ifdef GET_GICOMBINER_TYPES\n";2808  emitRuleConfigImpl(OS);2809  OS << "#endif // ifdef GET_GICOMBINER_TYPES\n\n";2810  emitPredicateBitset(OS, "GET_GICOMBINER_TYPES");2811 2812  // GET_GICOMBINER_CLASS_MEMBERS, which need to be included inside the class.2813  emitPredicatesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");2814  emitTemporariesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");2815 2816  // GET_GICOMBINER_IMPL, which needs to be included outside the class.2817  emitExecutorImpl(OS, Table, TypeObjects, Rules, {}, {},2818                   "GET_GICOMBINER_IMPL");2819 2820  // GET_GICOMBINER_CONSTRUCTOR_INITS, which are in the constructor's2821  // initializer list.2822  emitPredicatesInit(OS, "GET_GICOMBINER_CONSTRUCTOR_INITS");2823  emitTemporariesInit(OS, MaxTemporaries, "GET_GICOMBINER_CONSTRUCTOR_INITS");2824}2825 2826//===----------------------------------------------------------------------===//2827 2828static void EmitGICombiner(const RecordKeeper &RK, raw_ostream &OS) {2829  EnablePrettyStackTrace();2830  const CodeGenTarget Target(RK);2831 2832  if (SelectedCombiners.empty())2833    PrintFatalError("No combiners selected with -combiners");2834  for (const auto &Combiner : SelectedCombiners) {2835    const Record *CombinerDef = RK.getDef(Combiner);2836    if (!CombinerDef)2837      PrintFatalError("Could not find " + Combiner);2838    GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);2839  }2840}2841 2842static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,2843                                "Generate GlobalISel Combiner");2844