GIMatchTableExecutorImpl.h

Go to the documentation of this file.

//===- llvm/CodeGen/GlobalISel/GIMatchTableExecutorImpl.h -------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file This file implements GIMatchTableExecutor's `executeMatchTable`
/// function. This is implemented in a separate file because the function is
/// quite large.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTORIMPL_H
#define LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTORIMPL_H
 
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h"
#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
#include "llvm/CodeGen/GlobalISel/Utils.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterBankInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/CodeGenCoverage.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/LEB128.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstddef>
#include <cstdint>
 
namespace llvm {
 
template <class TgtExecutor, class PredicateBitset, class ComplexMatcherMemFn,
          class CustomRendererFn>
bool GIMatchTableExecutor::executeMatchTable(
    TgtExecutor &Exec, MatcherState &State,
    const ExecInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
        &ExecInfo,
    MachineIRBuilder &Builder, const uint8_t *MatchTable,
    const TargetInstrInfo &TII, MachineRegisterInfo &MRI,
    const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI,
    const PredicateBitset &AvailableFeatures,
    CodeGenCoverage *CoverageInfo) const {
 
  uint64_t CurrentIdx = 0;
  SmallVector<uint64_t, 4> OnFailResumeAt;
  NewMIVector OutMIs;
 
  GISelChangeObserver *Observer = Builder.getObserver();
  // Bypass the flag check on the instruction, and only look at the MCInstrDesc.
  bool NoFPException = !State.MIs[0]->getDesc().mayRaiseFPException();
 
  const uint16_t Flags = State.MIs[0]->getFlags();
 
  enum RejectAction { RejectAndGiveUp, RejectAndResume };
  auto handleReject = [&]() -> RejectAction {
    DEBUG_WITH_TYPE(TgtExecutor::getName(),
                    dbgs() << CurrentIdx << ": Rejected\n");
    if (OnFailResumeAt.empty())
      return RejectAndGiveUp;
    CurrentIdx = OnFailResumeAt.pop_back_val();
    DEBUG_WITH_TYPE(TgtExecutor::getName(),
                    dbgs() << CurrentIdx << ": Resume at " << CurrentIdx << " ("
                           << OnFailResumeAt.size() << " try-blocks remain)\n");
    return RejectAndResume;
  };
 
  const auto propagateFlags = [&]() {
    for (auto MIB : OutMIs) {
      // Set the NoFPExcept flag when no original matched instruction could
      // raise an FP exception, but the new instruction potentially might.
      uint16_t MIBFlags = Flags;
      if (NoFPException && MIB->mayRaiseFPException())
        MIBFlags |= MachineInstr::NoFPExcept;
      if (Observer)
        Observer->changingInstr(*MIB);
      MIB.setMIFlags(MIBFlags);
      if (Observer)
        Observer->changedInstr(*MIB);
    }
  };
 
  // If the index is >= 0, it's an index in the type objects generated by
  // TableGen. If the index is <0, it's an index in the recorded types object.
  const auto getTypeFromIdx = [&](int64_t Idx) -> LLT {
    if (Idx >= 0)
      return ExecInfo.TypeObjects[Idx];
    return State.RecordedTypes[1 - Idx];
  };
 
  const auto readULEB = [&]() {
    return fastDecodeULEB128(MatchTable, CurrentIdx);
  };
 
  // Convenience function to return a signed value. This avoids
  // us forgetting to first cast to int8_t before casting to a
  // wider signed int type.
  // if we casted uint8 directly to a wider type we'd lose
  // negative values.
  const auto readS8 = [&]() { return (int8_t)MatchTable[CurrentIdx++]; };
 
  const auto readU16 = [&]() {
    auto V = readBytesAs<uint16_t>(MatchTable + CurrentIdx);
    CurrentIdx += 2;
    return V;
  };
 
  const auto readU32 = [&]() {
    auto V = readBytesAs<uint32_t>(MatchTable + CurrentIdx);
    CurrentIdx += 4;
    return V;
  };
 
  const auto readU64 = [&]() {
    auto V = readBytesAs<uint64_t>(MatchTable + CurrentIdx);
    CurrentIdx += 8;
    return V;
  };
 
  const auto eraseImpl = [&](MachineInstr *MI) {
    // If we're erasing the insertion point, ensure we don't leave a dangling
    // pointer in the builder.
    if (Builder.getInsertPt() == MI)
      Builder.setInsertPt(*MI->getParent(), ++MI->getIterator());
    if (Observer)
      Observer->erasingInstr(*MI);
    MI->eraseFromParent();
  };
 
  while (true) {
    assert(CurrentIdx != ~0u && "Invalid MatchTable index");
    uint8_t MatcherOpcode = MatchTable[CurrentIdx++];
    switch (MatcherOpcode) {
    case GIM_Try: {
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": Begin try-block\n");
      OnFailResumeAt.push_back(readU32());
      break;
    }
 
    case GIM_RecordInsn:
    case GIM_RecordInsnIgnoreCopies: {
      uint64_t NewInsnID = readULEB();
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
 
      // As an optimisation we require that MIs[0] is always the root. Refuse
      // any attempt to modify it.
      assert(NewInsnID != 0 && "Refusing to modify MIs[0]");
 
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isReg()) {
        DEBUG_WITH_TYPE(TgtExecutor::getName(),
                        dbgs() << CurrentIdx << ": Not a register\n");
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
      if (MO.getReg().isPhysical()) {
        DEBUG_WITH_TYPE(TgtExecutor::getName(),
                        dbgs() << CurrentIdx << ": Is a physical register\n");
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      MachineInstr *NewMI;
      if (MatcherOpcode == GIM_RecordInsnIgnoreCopies)
        NewMI = getDefIgnoringCopies(MO.getReg(), MRI);
      else
        NewMI = MRI.getVRegDef(MO.getReg());
 
      if ((size_t)NewInsnID < State.MIs.size())
        State.MIs[NewInsnID] = NewMI;
      else {
        assert((size_t)NewInsnID == State.MIs.size() &&
               "Expected to store MIs in order");
        State.MIs.push_back(NewMI);
      }
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": MIs[" << NewInsnID
                             << "] = GIM_RecordInsn(" << InsnID << ", " << OpIdx
                             << ")\n");
      break;
    }
 
    case GIM_CheckFeatures: {
      uint16_t ExpectedBitsetID = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIM_CheckFeatures(ExpectedBitsetID="
                             << ExpectedBitsetID << ")\n");
      if ((AvailableFeatures & ExecInfo.FeatureBitsets[ExpectedBitsetID]) !=
          ExecInfo.FeatureBitsets[ExpectedBitsetID]) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckOpcode:
    case GIM_CheckOpcodeIsEither: {
      uint64_t InsnID = readULEB();
      uint16_t Expected0 = readU16();
      uint16_t Expected1 = -1;
      if (MatcherOpcode == GIM_CheckOpcodeIsEither)
        Expected1 = readU16();
 
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      unsigned Opcode = State.MIs[InsnID]->getOpcode();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckOpcode(MIs[" << InsnID
                             << "], ExpectedOpcode=" << Expected0;
                      if (MatcherOpcode == GIM_CheckOpcodeIsEither) dbgs()
                      << " || " << Expected1;
                      dbgs() << ") // Got=" << Opcode << "\n";);
 
      if (Opcode != Expected0 && Opcode != Expected1) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_SwitchOpcode: {
      uint64_t InsnID = readULEB();
      uint16_t LowerBound = readU16();
      uint16_t UpperBound = readU16();
      uint32_t Default = readU32();
 
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      const int64_t Opcode = State.MIs[InsnID]->getOpcode();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(), {
        dbgs() << CurrentIdx << ": GIM_SwitchOpcode(MIs[" << InsnID << "], ["
               << LowerBound << ", " << UpperBound << "), Default=" << Default
               << ", JumpTable...) // Got=" << Opcode << "\n";
      });
      if (Opcode < LowerBound || UpperBound <= Opcode) {
        CurrentIdx = Default;
        break;
      }
      const auto EntryIdx = (Opcode - LowerBound);
      // Each entry is 4 bytes
      CurrentIdx =
          readBytesAs<uint32_t>(MatchTable + CurrentIdx + (EntryIdx * 4));
      if (!CurrentIdx) {
        CurrentIdx = Default;
        break;
      }
      OnFailResumeAt.push_back(Default);
      break;
    }
 
    case GIM_SwitchType: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t LowerBound = readU16();
      uint16_t UpperBound = readU16();
      int64_t Default = readU32();
 
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(), {
        dbgs() << CurrentIdx << ": GIM_SwitchType(MIs[" << InsnID
               << "]->getOperand(" << OpIdx << "), [" << LowerBound << ", "
               << UpperBound << "), Default=" << Default
               << ", JumpTable...) // Got=";
        if (!MO.isReg())
          dbgs() << "Not a VReg\n";
        else
          dbgs() << MRI.getType(MO.getReg()) << "\n";
      });
      if (!MO.isReg()) {
        CurrentIdx = Default;
        break;
      }
      const LLT Ty = MRI.getType(MO.getReg());
      const auto TyI = ExecInfo.TypeIDMap.find(Ty);
      if (TyI == ExecInfo.TypeIDMap.end()) {
        CurrentIdx = Default;
        break;
      }
      const int64_t TypeID = TyI->second;
      if (TypeID < LowerBound || UpperBound <= TypeID) {
        CurrentIdx = Default;
        break;
      }
      const auto NumEntry = (TypeID - LowerBound);
      // Each entry is 4 bytes
      CurrentIdx =
          readBytesAs<uint32_t>(MatchTable + CurrentIdx + (NumEntry * 4));
      if (!CurrentIdx) {
        CurrentIdx = Default;
        break;
      }
      OnFailResumeAt.push_back(Default);
      break;
    }
 
    case GIM_CheckNumOperandsGE:
    case GIM_CheckNumOperandsLE: {
      uint64_t InsnID = readULEB();
      uint64_t Expected = readULEB();
      const bool IsLE = (MatcherOpcode == GIM_CheckNumOperandsLE);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckNumOperands"
                             << (IsLE ? "LE" : "GE") << "(MIs[" << InsnID
                             << "], Expected=" << Expected << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      const unsigned NumOps = State.MIs[InsnID]->getNumOperands();
      if (IsLE ? (NumOps > Expected) : (NumOps < Expected)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckNumOperands: {
      uint64_t InsnID = readULEB();
      uint64_t Expected = readULEB();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckNumOperands(MIs["
                             << InsnID << "], Expected=" << Expected << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (State.MIs[InsnID]->getNumOperands() != Expected) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckI64ImmPredicate:
    case GIM_CheckImmOperandPredicate: {
      uint64_t InsnID = readULEB();
      unsigned OpIdx =
          MatcherOpcode == GIM_CheckImmOperandPredicate ? readULEB() : 1;
      uint16_t Predicate = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckImmPredicate(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), Predicate=" << Predicate << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert((State.MIs[InsnID]->getOperand(OpIdx).isImm() ||
              State.MIs[InsnID]->getOperand(OpIdx).isCImm()) &&
             "Expected immediate operand");
      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
      int64_t Value = 0;
      if (State.MIs[InsnID]->getOperand(OpIdx).isCImm())
        Value = State.MIs[InsnID]->getOperand(OpIdx).getCImm()->getSExtValue();
      else if (State.MIs[InsnID]->getOperand(OpIdx).isImm())
        Value = State.MIs[InsnID]->getOperand(OpIdx).getImm();
      else
        llvm_unreachable("Expected Imm or CImm operand");
 
      if (!testImmPredicate_I64(Predicate, Value))
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckAPIntImmPredicate: {
      uint64_t InsnID = readULEB();
      uint16_t Predicate = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIM_CheckAPIntImmPredicate(MIs["
                          << InsnID << "], Predicate=" << Predicate << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_CONSTANT &&
             "Expected G_CONSTANT");
      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
      if (!State.MIs[InsnID]->getOperand(1).isCImm())
        llvm_unreachable("Expected Imm or CImm operand");
 
      const APInt &Value =
          State.MIs[InsnID]->getOperand(1).getCImm()->getValue();
      if (!testImmPredicate_APInt(Predicate, Value))
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckAPFloatImmPredicate: {
      uint64_t InsnID = readULEB();
      uint16_t Predicate = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIM_CheckAPFloatImmPredicate(MIs["
                          << InsnID << "], Predicate=" << Predicate << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_FCONSTANT &&
             "Expected G_FCONSTANT");
      assert(State.MIs[InsnID]->getOperand(1).isFPImm() &&
             "Expected FPImm operand");
      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
      const APFloat &Value =
          State.MIs[InsnID]->getOperand(1).getFPImm()->getValueAPF();
 
      if (!testImmPredicate_APFloat(Predicate, Value))
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckIsBuildVectorAllOnes:
    case GIM_CheckIsBuildVectorAllZeros: {
      uint64_t InsnID = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIM_CheckBuildVectorAll{Zeros|Ones}(MIs["
                             << InsnID << "])\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
 
      const MachineInstr *MI = State.MIs[InsnID];
      assert((MI->getOpcode() == TargetOpcode::G_BUILD_VECTOR ||
              MI->getOpcode() == TargetOpcode::G_BUILD_VECTOR_TRUNC) &&
             "Expected G_BUILD_VECTOR or G_BUILD_VECTOR_TRUNC");
 
      if (MatcherOpcode == GIM_CheckIsBuildVectorAllOnes) {
        if (!isBuildVectorAllOnes(*MI, MRI)) {
          if (handleReject() == RejectAndGiveUp)
            return false;
        }
      } else {
        if (!isBuildVectorAllZeros(*MI, MRI)) {
          if (handleReject() == RejectAndGiveUp)
            return false;
        }
      }
 
      break;
    }
    case GIM_CheckSimplePredicate: {
      // Note: we don't check for invalid here because this is purely a hook to
      // allow some executors (such as the combiner) to check arbitrary,
      // contextless predicates, such as whether a rule is enabled or not.
      uint16_t Predicate = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIM_CheckSimplePredicate(Predicate="
                             << Predicate << ")\n");
      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
      if (!testSimplePredicate(Predicate)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckCxxInsnPredicate: {
      uint64_t InsnID = readULEB();
      uint16_t Predicate = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIM_CheckCxxPredicate(MIs["
                          << InsnID << "], Predicate=" << Predicate << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
 
      if (!testMIPredicate_MI(Predicate, *State.MIs[InsnID], State))
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckHasNoUse: {
      uint64_t InsnID = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckHasNoUse(MIs["
                             << InsnID << "]\n");
 
      const MachineInstr *MI = State.MIs[InsnID];
      assert(MI && "Used insn before defined");
      assert(MI->getNumDefs() > 0 && "No defs");
      const Register Res = MI->getOperand(0).getReg();
 
      if (!MRI.use_nodbg_empty(Res)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckHasOneUse: {
      uint64_t InsnID = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckHasOneUse(MIs["
                             << InsnID << "]\n");
 
      const MachineInstr *MI = State.MIs[InsnID];
      assert(MI && "Used insn before defined");
      assert(MI->getNumDefs() > 0 && "No defs");
      const Register Res = MI->getOperand(0).getReg();
 
      if (!MRI.hasOneNonDBGUse(Res)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckAtomicOrdering: {
      uint64_t InsnID = readULEB();
      auto Ordering = (AtomicOrdering)MatchTable[CurrentIdx++];
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckAtomicOrdering(MIs["
                             << InsnID << "], " << (uint64_t)Ordering << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (!State.MIs[InsnID]->hasOneMemOperand())
        if (handleReject() == RejectAndGiveUp)
          return false;
 
      for (const auto &MMO : State.MIs[InsnID]->memoperands())
        if (MMO->getMergedOrdering() != Ordering)
          if (handleReject() == RejectAndGiveUp)
            return false;
      break;
    }
    case GIM_CheckAtomicOrderingOrStrongerThan: {
      uint64_t InsnID = readULEB();
      auto Ordering = (AtomicOrdering)MatchTable[CurrentIdx++];
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIM_CheckAtomicOrderingOrStrongerThan(MIs["
                             << InsnID << "], " << (uint64_t)Ordering << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (!State.MIs[InsnID]->hasOneMemOperand())
        if (handleReject() == RejectAndGiveUp)
          return false;
 
      for (const auto &MMO : State.MIs[InsnID]->memoperands())
        if (!isAtLeastOrStrongerThan(MMO->getMergedOrdering(), Ordering))
          if (handleReject() == RejectAndGiveUp)
            return false;
      break;
    }
    case GIM_CheckAtomicOrderingWeakerThan: {
      uint64_t InsnID = readULEB();
      auto Ordering = (AtomicOrdering)MatchTable[CurrentIdx++];
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIM_CheckAtomicOrderingWeakerThan(MIs["
                             << InsnID << "], " << (uint64_t)Ordering << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (!State.MIs[InsnID]->hasOneMemOperand())
        if (handleReject() == RejectAndGiveUp)
          return false;
 
      for (const auto &MMO : State.MIs[InsnID]->memoperands())
        if (!isStrongerThan(Ordering, MMO->getMergedOrdering()))
          if (handleReject() == RejectAndGiveUp)
            return false;
      break;
    }
    case GIM_CheckMemoryAddressSpace: {
      uint64_t InsnID = readULEB();
      uint64_t MMOIdx = readULEB();
      // This accepts a list of possible address spaces.
      const uint64_t NumAddrSpace = MatchTable[CurrentIdx++];
 
      if (State.MIs[InsnID]->getNumMemOperands() <= MMOIdx) {
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      // Need to still jump to the end of the list of address spaces if we find
      // a match earlier.
      const uint64_t LastIdx = CurrentIdx + NumAddrSpace;
 
      const MachineMemOperand *MMO =
          *(State.MIs[InsnID]->memoperands_begin() + MMOIdx);
      const unsigned MMOAddrSpace = MMO->getAddrSpace();
 
      bool Success = false;
      for (unsigned I = 0; I != NumAddrSpace; ++I) {
        uint64_t AddrSpace = readULEB();
        DEBUG_WITH_TYPE(TgtExecutor::getName(),
                        dbgs() << "addrspace(" << MMOAddrSpace << ") vs "
                               << AddrSpace << '\n');
 
        if (AddrSpace == MMOAddrSpace) {
          Success = true;
          break;
        }
      }
 
      CurrentIdx = LastIdx;
      if (!Success && handleReject() == RejectAndGiveUp)
        return false;
      break;
    }
    case GIM_CheckMemoryAlignment: {
      uint64_t InsnID = readULEB();
      uint64_t MMOIdx = readULEB();
      uint64_t MinAlign = MatchTable[CurrentIdx++];
 
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
 
      if (State.MIs[InsnID]->getNumMemOperands() <= MMOIdx) {
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      MachineMemOperand *MMO =
          *(State.MIs[InsnID]->memoperands_begin() + MMOIdx);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckMemoryAlignment"
                             << "(MIs[" << InsnID << "]->memoperands() + "
                             << MMOIdx << ")->getAlignment() >= " << MinAlign
                             << ")\n");
      if (MMO->getAlign() < MinAlign && handleReject() == RejectAndGiveUp)
        return false;
 
      break;
    }
    case GIM_CheckMemorySizeEqualTo: {
      uint64_t InsnID = readULEB();
      uint64_t MMOIdx = readULEB();
      uint32_t Size = readU32();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckMemorySizeEqual(MIs["
                             << InsnID << "]->memoperands() + " << MMOIdx
                             << ", Size=" << Size << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
 
      if (State.MIs[InsnID]->getNumMemOperands() <= MMOIdx) {
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      MachineMemOperand *MMO =
          *(State.MIs[InsnID]->memoperands_begin() + MMOIdx);
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(), dbgs() << MMO->getSize()
                                                     << " bytes vs " << Size
                                                     << " bytes\n");
      if (MMO->getSize() != Size)
        if (handleReject() == RejectAndGiveUp)
          return false;
 
      break;
    }
    case GIM_CheckMemorySizeEqualToLLT:
    case GIM_CheckMemorySizeLessThanLLT:
    case GIM_CheckMemorySizeGreaterThanLLT: {
      uint64_t InsnID = readULEB();
      uint64_t MMOIdx = readULEB();
      uint64_t OpIdx = readULEB();
 
      DEBUG_WITH_TYPE(
          TgtExecutor::getName(),
          dbgs() << CurrentIdx << ": GIM_CheckMemorySize"
                 << (MatcherOpcode == GIM_CheckMemorySizeEqualToLLT ? "EqualTo"
                     : MatcherOpcode == GIM_CheckMemorySizeGreaterThanLLT
                         ? "GreaterThan"
                         : "LessThan")
                 << "LLT(MIs[" << InsnID << "]->memoperands() + " << MMOIdx
                 << ", OpIdx=" << OpIdx << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
 
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isReg()) {
        DEBUG_WITH_TYPE(TgtExecutor::getName(),
                        dbgs() << CurrentIdx << ": Not a register\n");
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      if (State.MIs[InsnID]->getNumMemOperands() <= MMOIdx) {
        if (handleReject() == RejectAndGiveUp)
          return false;
        break;
      }
 
      MachineMemOperand *MMO =
          *(State.MIs[InsnID]->memoperands_begin() + MMOIdx);
 
      const TypeSize Size = MRI.getType(MO.getReg()).getSizeInBits();
      if (MatcherOpcode == GIM_CheckMemorySizeEqualToLLT &&
          MMO->getSizeInBits() != Size) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      } else if (MatcherOpcode == GIM_CheckMemorySizeLessThanLLT &&
                 TypeSize::isKnownGE(MMO->getSizeInBits().getValue(), Size)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      } else if (MatcherOpcode == GIM_CheckMemorySizeGreaterThanLLT &&
                 TypeSize::isKnownLE(MMO->getSizeInBits().getValue(), Size))
        if (handleReject() == RejectAndGiveUp)
          return false;
 
      break;
    }
    case GIM_RootCheckType:
    case GIM_CheckType: {
      uint64_t InsnID = (MatcherOpcode == GIM_RootCheckType) ? 0 : readULEB();
      uint64_t OpIdx = readULEB();
      int TypeID = readS8();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckType(MIs[" << InsnID
                             << "]->getOperand(" << OpIdx
                             << "), TypeID=" << TypeID << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isReg() || MRI.getType(MO.getReg()) != getTypeFromIdx(TypeID)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckPointerToAny: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint64_t SizeInBits = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckPointerToAny(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), SizeInBits=" << SizeInBits << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      const LLT Ty = MRI.getType(MO.getReg());
 
      // iPTR must be looked up in the target.
      if (SizeInBits == 0) {
        MachineFunction *MF = State.MIs[InsnID]->getParent()->getParent();
        const unsigned AddrSpace = Ty.getAddressSpace();
        SizeInBits = MF->getDataLayout().getPointerSizeInBits(AddrSpace);
      }
 
      assert(SizeInBits != 0 && "Pointer size must be known");
 
      if (MO.isReg()) {
        if (!Ty.isPointer() || Ty.getSizeInBits() != SizeInBits)
          if (handleReject() == RejectAndGiveUp)
            return false;
      } else if (handleReject() == RejectAndGiveUp)
        return false;
 
      break;
    }
    case GIM_RecordNamedOperand: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint64_t StoreIdx = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_RecordNamedOperand(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), StoreIdx=" << StoreIdx << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(StoreIdx < State.RecordedOperands.size() && "Index out of range");
      State.RecordedOperands[StoreIdx] = &State.MIs[InsnID]->getOperand(OpIdx);
      break;
    }
    case GIM_RecordRegType: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      int TypeIdx = readS8();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_RecordRegType(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), TypeIdx=" << TypeIdx << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(TypeIdx < 0 && "Temp types always have negative indexes!");
      // Indexes start at -1.
      TypeIdx = 1 - TypeIdx;
      const auto &Op = State.MIs[InsnID]->getOperand(OpIdx);
      if (State.RecordedTypes.size() <= (uint64_t)TypeIdx)
        State.RecordedTypes.resize(TypeIdx + 1, LLT());
      State.RecordedTypes[TypeIdx] = MRI.getType(Op.getReg());
      break;
    }
 
    case GIM_RootCheckRegBankForClass:
    case GIM_CheckRegBankForClass: {
      uint64_t InsnID =
          (MatcherOpcode == GIM_RootCheckRegBankForClass) ? 0 : readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t RCEnum = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckRegBankForClass(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), RCEnum=" << RCEnum << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isReg() ||
          &RBI.getRegBankFromRegClass(*TRI.getRegClass(RCEnum),
                                      MRI.getType(MO.getReg())) !=
              RBI.getRegBank(MO.getReg(), MRI, TRI)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
 
    case GIM_CheckComplexPattern: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t RendererID = readU16();
      uint16_t ComplexPredicateID = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": State.Renderers[" << RendererID
                             << "] = GIM_CheckComplexPattern(MIs[" << InsnID
                             << "]->getOperand(" << OpIdx
                             << "), ComplexPredicateID=" << ComplexPredicateID
                             << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      // FIXME: Use std::invoke() when it's available.
      ComplexRendererFns Renderer =
          (Exec.*ExecInfo.ComplexPredicates[ComplexPredicateID])(
              State.MIs[InsnID]->getOperand(OpIdx));
      if (Renderer)
        State.Renderers[RendererID] = *Renderer;
      else if (handleReject() == RejectAndGiveUp)
        return false;
      break;
    }
 
    case GIM_CheckConstantInt:
    case GIM_CheckConstantInt8: {
      const bool IsInt8 = (MatcherOpcode == GIM_CheckConstantInt8);
 
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint64_t Value = IsInt8 ? (int64_t)readS8() : readU64();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckConstantInt(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), Value=" << Value << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (MO.isReg()) {
        // isOperandImmEqual() will sign-extend to 64-bits, so should we.
        LLT Ty = MRI.getType(MO.getReg());
        // If the type is > 64 bits, it can't be a constant int, so we bail
        // early because SignExtend64 will assert otherwise.
        if (Ty.getScalarSizeInBits() > 64) {
          if (handleReject() == RejectAndGiveUp)
            return false;
          break;
        }
 
        Value = SignExtend64(Value, Ty.getScalarSizeInBits());
        if (!isOperandImmEqual(MO, Value, MRI, /*Splat=*/true)) {
          if (handleReject() == RejectAndGiveUp)
            return false;
        }
      } else if (handleReject() == RejectAndGiveUp)
        return false;
 
      break;
    }
 
    case GIM_CheckLiteralInt: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      int64_t Value = readU64();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckLiteralInt(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), Value=" << Value << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (MO.isImm() && MO.getImm() == Value)
        break;
 
      if (MO.isCImm() && MO.getCImm()->equalsInt(Value))
        break;
 
      if (handleReject() == RejectAndGiveUp)
        return false;
 
      break;
    }
 
    case GIM_CheckIntrinsicID: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t Value = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckIntrinsicID(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), Value=" << Value << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isIntrinsicID() || MO.getIntrinsicID() != Value)
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckCmpPredicate: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t Value = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckCmpPredicate(MIs["
                             << InsnID << "]->getOperand(" << OpIdx
                             << "), Value=" << Value << ")\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
      if (!MO.isPredicate() || MO.getPredicate() != Value)
        if (handleReject() == RejectAndGiveUp)
          return false;
      break;
    }
    case GIM_CheckIsMBB: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckIsMBB(MIs[" << InsnID
                             << "]->getOperand(" << OpIdx << "))\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (!State.MIs[InsnID]->getOperand(OpIdx).isMBB()) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckIsImm: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckIsImm(MIs[" << InsnID
                             << "]->getOperand(" << OpIdx << "))\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      if (!State.MIs[InsnID]->getOperand(OpIdx).isImm()) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckIsSafeToFold: {
      uint64_t NumInsn = MatchTable[CurrentIdx++];
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckIsSafeToFold(N = "
                             << NumInsn << ")\n");
      MachineInstr &Root = *State.MIs[0];
      for (unsigned K = 1, E = NumInsn + 1; K < E; ++K) {
        if (!isObviouslySafeToFold(*State.MIs[K], Root)) {
          if (handleReject() == RejectAndGiveUp)
            return false;
        }
      }
      break;
    }
    case GIM_CheckIsSameOperand:
    case GIM_CheckIsSameOperandIgnoreCopies: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint64_t OtherInsnID = readULEB();
      uint64_t OtherOpIdx = readULEB();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckIsSameOperand(MIs["
                             << InsnID << "][" << OpIdx << "], MIs["
                             << OtherInsnID << "][" << OtherOpIdx << "])\n");
      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
      assert(State.MIs[OtherInsnID] != nullptr && "Used insn before defined");
 
      MachineOperand &Op = State.MIs[InsnID]->getOperand(OpIdx);
      MachineOperand &OtherOp = State.MIs[OtherInsnID]->getOperand(OtherOpIdx);
 
      if (MatcherOpcode == GIM_CheckIsSameOperandIgnoreCopies) {
        if (Op.isReg() && OtherOp.isReg()) {
          if (getSrcRegIgnoringCopies(Op.getReg(), MRI) ==
              getSrcRegIgnoringCopies(OtherOp.getReg(), MRI))
            break;
        }
      }
 
      if (!Op.isIdenticalTo(OtherOp)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_CheckCanReplaceReg: {
      uint64_t OldInsnID = readULEB();
      uint64_t OldOpIdx = readULEB();
      uint64_t NewInsnID = readULEB();
      uint64_t NewOpIdx = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_CheckCanReplaceReg(MIs["
                             << OldInsnID << "][" << OldOpIdx << "] = MIs["
                             << NewInsnID << "][" << NewOpIdx << "])\n");
 
      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
      Register New = State.MIs[NewInsnID]->getOperand(NewOpIdx).getReg();
      if (!canReplaceReg(Old, New, MRI)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_MIFlags: {
      uint64_t InsnID = readULEB();
      uint32_t Flags = readU32();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_MIFlags(MIs[" << InsnID
                             << "], " << Flags << ")\n");
      if ((State.MIs[InsnID]->getFlags() & Flags) != Flags) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_MIFlagsNot: {
      uint64_t InsnID = readULEB();
      uint32_t Flags = readU32();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_MIFlagsNot(MIs[" << InsnID
                             << "], " << Flags << ")\n");
      if ((State.MIs[InsnID]->getFlags() & Flags)) {
        if (handleReject() == RejectAndGiveUp)
          return false;
      }
      break;
    }
    case GIM_Reject:
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIM_Reject\n");
      if (handleReject() == RejectAndGiveUp)
        return false;
      break;
    case GIR_MutateOpcode: {
      uint64_t OldInsnID = readULEB();
      uint64_t NewInsnID = readULEB();
      uint16_t NewOpcode = readU16();
      if (NewInsnID >= OutMIs.size())
        OutMIs.resize(NewInsnID + 1);
 
      MachineInstr *OldMI = State.MIs[OldInsnID];
      if (Observer)
        Observer->changingInstr(*OldMI);
      OutMIs[NewInsnID] = MachineInstrBuilder(*OldMI->getMF(), OldMI);
      OutMIs[NewInsnID]->setDesc(TII.get(NewOpcode));
      if (Observer)
        Observer->changedInstr(*OldMI);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_MutateOpcode(OutMIs["
                             << NewInsnID << "], MIs[" << OldInsnID << "], "
                             << NewOpcode << ")\n");
      break;
    }
 
    case GIR_BuildRootMI:
    case GIR_BuildMI: {
      uint64_t NewInsnID = (MatcherOpcode == GIR_BuildRootMI) ? 0 : readULEB();
      uint16_t Opcode = readU16();
      if (NewInsnID >= OutMIs.size())
        OutMIs.resize(NewInsnID + 1);
 
      OutMIs[NewInsnID] = Builder.buildInstr(Opcode);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_BuildMI(OutMIs["
                             << NewInsnID << "], " << Opcode << ")\n");
      break;
    }
 
    case GIR_BuildConstant: {
      uint64_t TempRegID = readULEB();
      uint64_t Imm = readU64();
      Builder.buildConstant(State.TempRegisters[TempRegID], Imm);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_BuildConstant(TempReg["
                             << TempRegID << "], Imm=" << Imm << ")\n");
      break;
    }
 
    case GIR_RootToRootCopy:
    case GIR_Copy: {
      uint64_t NewInsnID =
          (MatcherOpcode == GIR_RootToRootCopy) ? 0 : readULEB();
      uint64_t OldInsnID =
          (MatcherOpcode == GIR_RootToRootCopy) ? 0 : readULEB();
      uint64_t OpIdx = readULEB();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      OutMIs[NewInsnID].add(State.MIs[OldInsnID]->getOperand(OpIdx));
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIR_Copy(OutMIs[" << NewInsnID
                          << "], MIs[" << OldInsnID << "], " << OpIdx << ")\n");
      break;
    }
 
    case GIR_CopyRemaining: {
      uint64_t NewInsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      uint64_t OpIdx = readULEB();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      MachineInstr &OldMI = *State.MIs[OldInsnID];
      MachineInstrBuilder &NewMI = OutMIs[NewInsnID];
      for (const auto &Op : drop_begin(OldMI.operands(), OpIdx))
        NewMI.add(Op);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CopyRemaining(OutMIs["
                             << NewInsnID << "], MIs[" << OldInsnID
                             << "], /*start=*/" << OpIdx << ")\n");
      break;
    }
 
    case GIR_CopyOrAddZeroReg: {
      uint64_t NewInsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t ZeroReg = readU16();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      MachineOperand &MO = State.MIs[OldInsnID]->getOperand(OpIdx);
      if (isOperandImmEqual(MO, 0, MRI))
        OutMIs[NewInsnID].addReg(ZeroReg);
      else
        OutMIs[NewInsnID].add(MO);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CopyOrAddZeroReg(OutMIs["
                             << NewInsnID << "], MIs[" << OldInsnID << "], "
                             << OpIdx << ", " << ZeroReg << ")\n");
      break;
    }
 
    case GIR_CopySubReg: {
      uint64_t NewInsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t SubRegIdx = readU16();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      OutMIs[NewInsnID].addReg(State.MIs[OldInsnID]->getOperand(OpIdx).getReg(),
                               0, SubRegIdx);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CopySubReg(OutMIs["
                             << NewInsnID << "], MIs[" << OldInsnID << "], "
                             << OpIdx << ", " << SubRegIdx << ")\n");
      break;
    }
 
    case GIR_AddImplicitDef: {
      uint64_t InsnID = readULEB();
      uint16_t RegNum = readU16();
      uint16_t Flags = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      Flags |= RegState::Implicit;
      OutMIs[InsnID].addDef(RegNum, Flags);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_AddImplicitDef(OutMIs["
                             << InsnID << "], " << RegNum << ")\n");
      break;
    }
 
    case GIR_AddImplicitUse: {
      uint64_t InsnID = readULEB();
      uint16_t RegNum = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      OutMIs[InsnID].addUse(RegNum, RegState::Implicit);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_AddImplicitUse(OutMIs["
                             << InsnID << "], " << RegNum << ")\n");
      break;
    }
 
    case GIR_AddRegister: {
      uint64_t InsnID = readULEB();
      uint16_t RegNum = readU16();
      uint16_t RegFlags = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      OutMIs[InsnID].addReg(RegNum, RegFlags);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIR_AddRegister(OutMIs[" << InsnID
                          << "], " << RegNum << ", " << RegFlags << ")\n");
      break;
    }
    case GIR_AddIntrinsicID: {
      uint64_t InsnID = readULEB();
      uint16_t Value = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      OutMIs[InsnID].addIntrinsicID((Intrinsic::ID)Value);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_AddIntrinsicID(OutMIs["
                             << InsnID << "], " << Value << ")\n");
      break;
    }
    case GIR_SetImplicitDefDead: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_SetImplicitDefDead(OutMIs["
                             << InsnID << "], OpIdx=" << OpIdx << ")\n");
      MachineInstr *MI = OutMIs[InsnID];
      assert(MI && "Modifying undefined instruction");
      MI->getOperand(MI->getNumExplicitOperands() + OpIdx).setIsDead();
      break;
    }
    case GIR_SetMIFlags: {
      uint64_t InsnID = readULEB();
      uint32_t Flags = readU32();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_SetMIFlags(OutMIs["
                             << InsnID << "], " << Flags << ")\n");
      MachineInstr *MI = OutMIs[InsnID];
      MI->setFlags(MI->getFlags() | Flags);
      break;
    }
    case GIR_UnsetMIFlags: {
      uint64_t InsnID = readULEB();
      uint32_t Flags = readU32();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_UnsetMIFlags(OutMIs["
                             << InsnID << "], " << Flags << ")\n");
      MachineInstr *MI = OutMIs[InsnID];
      MI->setFlags(MI->getFlags() & ~Flags);
      break;
    }
    case GIR_CopyMIFlags: {
      uint64_t InsnID = readULEB();
      uint64_t OldInsnID = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CopyMIFlags(OutMIs["
                             << InsnID << "], MIs[" << OldInsnID << "])\n");
      MachineInstr *MI = OutMIs[InsnID];
      MI->setFlags(MI->getFlags() | State.MIs[OldInsnID]->getFlags());
      break;
    }
    case GIR_AddSimpleTempRegister:
    case GIR_AddTempRegister:
    case GIR_AddTempSubRegister: {
      uint64_t InsnID = readULEB();
      uint64_t TempRegID = readULEB();
      uint16_t TempRegFlags = 0;
      if (MatcherOpcode != GIR_AddSimpleTempRegister)
        TempRegFlags = readU16();
      uint16_t SubReg = 0;
      if (MatcherOpcode == GIR_AddTempSubRegister)
        SubReg = readU16();
 
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
 
      OutMIs[InsnID].addReg(State.TempRegisters[TempRegID], TempRegFlags,
                            SubReg);
      DEBUG_WITH_TYPE(
          TgtExecutor::getName(),
          dbgs() << CurrentIdx << ": GIR_AddTempRegister(OutMIs[" << InsnID
                 << "], TempRegisters[" << TempRegID << "]";
          if (SubReg) dbgs() << '.' << TRI.getSubRegIndexName(SubReg);
          dbgs() << ", " << TempRegFlags << ")\n");
      break;
    }
 
    case GIR_AddImm8:
    case GIR_AddImm: {
      const bool IsAdd8 = (MatcherOpcode == GIR_AddImm8);
      uint64_t InsnID = readULEB();
      uint64_t Imm = IsAdd8 ? (int64_t)readS8() : readU64();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      OutMIs[InsnID].addImm(Imm);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_AddImm(OutMIs[" << InsnID
                             << "], " << Imm << ")\n");
      break;
    }
 
    case GIR_AddCImm: {
      uint64_t InsnID = readULEB();
      int TypeID = readS8();
      uint64_t Imm = readU64();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
 
      unsigned Width = ExecInfo.TypeObjects[TypeID].getScalarSizeInBits();
      LLVMContext &Ctx = MF->getFunction().getContext();
      OutMIs[InsnID].addCImm(
          ConstantInt::get(IntegerType::get(Ctx, Width), Imm, /*signed*/ true));
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_AddCImm(OutMIs[" << InsnID
                             << "], TypeID=" << TypeID << ", Imm=" << Imm
                             << ")\n");
      break;
    }
 
    case GIR_ComplexRenderer: {
      uint64_t InsnID = readULEB();
      uint16_t RendererID = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      for (const auto &RenderOpFn : State.Renderers[RendererID])
        RenderOpFn(OutMIs[InsnID]);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_ComplexRenderer(OutMIs["
                             << InsnID << "], " << RendererID << ")\n");
      break;
    }
    case GIR_ComplexSubOperandRenderer: {
      uint64_t InsnID = readULEB();
      uint16_t RendererID = readU16();
      uint64_t RenderOpID = readULEB();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      State.Renderers[RendererID][RenderOpID](OutMIs[InsnID]);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIR_ComplexSubOperandRenderer(OutMIs["
                             << InsnID << "], " << RendererID << ", "
                             << RenderOpID << ")\n");
      break;
    }
    case GIR_ComplexSubOperandSubRegRenderer: {
      uint64_t InsnID = readULEB();
      uint16_t RendererID = readU16();
      uint64_t RenderOpID = readULEB();
      uint16_t SubRegIdx = readU16();
      MachineInstrBuilder &MI = OutMIs[InsnID];
      assert(MI && "Attempted to add to undefined instruction");
      State.Renderers[RendererID][RenderOpID](MI);
      MI->getOperand(MI->getNumOperands() - 1).setSubReg(SubRegIdx);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIR_ComplexSubOperandSubRegRenderer(OutMIs["
                             << InsnID << "], " << RendererID << ", "
                             << RenderOpID << ", " << SubRegIdx << ")\n");
      break;
    }
 
    case GIR_CopyConstantAsSImm: {
      uint64_t NewInsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      assert(State.MIs[OldInsnID]->getOpcode() == TargetOpcode::G_CONSTANT &&
             "Expected G_CONSTANT");
      if (State.MIs[OldInsnID]->getOperand(1).isCImm()) {
        OutMIs[NewInsnID].addImm(
            State.MIs[OldInsnID]->getOperand(1).getCImm()->getSExtValue());
      } else if (State.MIs[OldInsnID]->getOperand(1).isImm())
        OutMIs[NewInsnID].add(State.MIs[OldInsnID]->getOperand(1));
      else
        llvm_unreachable("Expected Imm or CImm operand");
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CopyConstantAsSImm(OutMIs["
                             << NewInsnID << "], MIs[" << OldInsnID << "])\n");
      break;
    }
 
    // TODO: Needs a test case once we have a pattern that uses this.
    case GIR_CopyFConstantAsFPImm: {
      uint64_t NewInsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
      assert(State.MIs[OldInsnID]->getOpcode() == TargetOpcode::G_FCONSTANT &&
             "Expected G_FCONSTANT");
      if (State.MIs[OldInsnID]->getOperand(1).isFPImm())
        OutMIs[NewInsnID].addFPImm(
            State.MIs[OldInsnID]->getOperand(1).getFPImm());
      else
        llvm_unreachable("Expected FPImm operand");
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIR_CopyFPConstantAsFPImm(OutMIs["
                          << NewInsnID << "], MIs[" << OldInsnID << "])\n");
      break;
    }
 
    case GIR_CustomRenderer: {
      uint64_t InsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      uint16_t RendererFnID = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_CustomRenderer(OutMIs["
                             << InsnID << "], MIs[" << OldInsnID << "], "
                             << RendererFnID << ")\n");
      (Exec.*ExecInfo.CustomRenderers[RendererFnID])(
          OutMIs[InsnID], *State.MIs[OldInsnID],
          -1); // Not a source operand of the old instruction.
      break;
    }
    case GIR_DoneWithCustomAction: {
      uint16_t FnID = readU16();
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_DoneWithCustomAction(FnID="
                             << FnID << ")\n");
      assert(FnID > GICXXCustomAction_Invalid && "Expected a valid FnID");
      if (runCustomAction(FnID, State, OutMIs)) {
        propagateFlags();
        return true;
      }
 
      if (handleReject() == RejectAndGiveUp)
        return false;
      break;
    }
    case GIR_CustomOperandRenderer: {
      uint64_t InsnID = readULEB();
      uint64_t OldInsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t RendererFnID = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIR_CustomOperandRenderer(OutMIs[" << InsnID
                             << "], MIs[" << OldInsnID << "]->getOperand("
                             << OpIdx << "), " << RendererFnID << ")\n");
      (Exec.*ExecInfo.CustomRenderers[RendererFnID])(
          OutMIs[InsnID], *State.MIs[OldInsnID], OpIdx);
      break;
    }
    case GIR_ConstrainOperandRC: {
      uint64_t InsnID = readULEB();
      uint64_t OpIdx = readULEB();
      uint16_t RCEnum = readU16();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      MachineInstr &I = *OutMIs[InsnID].getInstr();
      MachineFunction &MF = *I.getParent()->getParent();
      MachineRegisterInfo &MRI = MF.getRegInfo();
      const TargetRegisterClass &RC = *TRI.getRegClass(RCEnum);
      MachineOperand &MO = I.getOperand(OpIdx);
      constrainOperandRegClass(MF, TRI, MRI, TII, RBI, I, RC, MO);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_ConstrainOperandRC(OutMIs["
                             << InsnID << "], " << OpIdx << ", " << RCEnum
                             << ")\n");
      break;
    }
 
    case GIR_RootConstrainSelectedInstOperands:
    case GIR_ConstrainSelectedInstOperands: {
      uint64_t InsnID = (MatcherOpcode == GIR_RootConstrainSelectedInstOperands)
                            ? 0
                            : readULEB();
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
      constrainSelectedInstRegOperands(*OutMIs[InsnID].getInstr(), TII, TRI,
                                       RBI);
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx
                             << ": GIR_ConstrainSelectedInstOperands(OutMIs["
                             << InsnID << "])\n");
      break;
    }
    case GIR_MergeMemOperands: {
      uint64_t InsnID = readULEB();
      uint64_t NumInsn = MatchTable[CurrentIdx++];
      assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_MergeMemOperands(OutMIs["
                             << InsnID << "]");
      for (unsigned K = 0; K < NumInsn; ++K) {
        uint64_t NextID = readULEB();
        DEBUG_WITH_TYPE(TgtExecutor::getName(),
                        dbgs() << ", MIs[" << NextID << "]");
        for (const auto &MMO : State.MIs[NextID]->memoperands())
          OutMIs[InsnID].addMemOperand(MMO);
      }
      DEBUG_WITH_TYPE(TgtExecutor::getName(), dbgs() << ")\n");
      break;
    }
    case GIR_EraseFromParent: {
      uint64_t InsnID = readULEB();
      MachineInstr *MI = State.MIs[InsnID];
      assert(MI && "Attempted to erase an undefined instruction");
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_EraseFromParent(MIs["
                             << InsnID << "])\n");
      eraseImpl(MI);
      break;
    }
    case GIR_EraseRootFromParent_Done: {
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs()
                          << CurrentIdx << ": GIR_EraseRootFromParent_Done\n");
      eraseImpl(State.MIs[0]);
      propagateFlags();
      return true;
    }
    case GIR_MakeTempReg: {
      uint64_t TempRegID = readULEB();
      int TypeID = readS8();
 
      State.TempRegisters[TempRegID] =
          MRI.createGenericVirtualRegister(getTypeFromIdx(TypeID));
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": TempRegs[" << TempRegID
                             << "] = GIR_MakeTempReg(" << TypeID << ")\n");
      break;
    }
    case GIR_ReplaceReg: {
      uint64_t OldInsnID = readULEB();
      uint64_t OldOpIdx = readULEB();
      uint64_t NewInsnID = readULEB();
      uint64_t NewOpIdx = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_ReplaceReg(MIs["
                             << OldInsnID << "][" << OldOpIdx << "] = MIs["
                             << NewInsnID << "][" << NewOpIdx << "])\n");
 
      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
      Register New = State.MIs[NewInsnID]->getOperand(NewOpIdx).getReg();
      if (Observer)
        Observer->changingAllUsesOfReg(MRI, Old);
      MRI.replaceRegWith(Old, New);
      if (Observer)
        Observer->finishedChangingAllUsesOfReg();
      break;
    }
    case GIR_ReplaceRegWithTempReg: {
      uint64_t OldInsnID = readULEB();
      uint64_t OldOpIdx = readULEB();
      uint64_t TempRegID = readULEB();
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_ReplaceRegWithTempReg(MIs["
                             << OldInsnID << "][" << OldOpIdx << "] = TempRegs["
                             << TempRegID << "])\n");
 
      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
      Register New = State.TempRegisters[TempRegID];
      if (Observer)
        Observer->changingAllUsesOfReg(MRI, Old);
      MRI.replaceRegWith(Old, New);
      if (Observer)
        Observer->finishedChangingAllUsesOfReg();
      break;
    }
    case GIR_Coverage: {
      uint32_t RuleID = readU32();
      assert(CoverageInfo);
      CoverageInfo->setCovered(RuleID);
 
      DEBUG_WITH_TYPE(TgtExecutor::getName(), dbgs() << CurrentIdx
                                                     << ": GIR_Coverage("
                                                     << RuleID << ")");
      break;
    }
 
    case GIR_Done:
      DEBUG_WITH_TYPE(TgtExecutor::getName(),
                      dbgs() << CurrentIdx << ": GIR_Done\n");
      propagateFlags();
      return true;
    default:
      llvm_unreachable("Unexpected command");
    }
  }
}
 
} // end namespace llvm
 
#endif // LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTORIMPL_H