text: //===- AArch64LegalizerInfo.cpp ----------------------------------*- 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 the targeting of the Machinelegalizer class for
  /// AArch64.
  /// \todo This should be generated by TableGen.
  //===----------------------------------------------------------------------===//
  
  #include "AArch64LegalizerInfo.h"
  #include "AArch64Subtarget.h"
  #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
  #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  #include "llvm/CodeGen/GlobalISel/Utils.h"
  #include "llvm/CodeGen/MachineInstr.h"
  #include "llvm/CodeGen/MachineRegisterInfo.h"
  #include "llvm/CodeGen/TargetOpcodes.h"
  #include "llvm/CodeGen/ValueTypes.h"
  #include "llvm/IR/DerivedTypes.h"
  #include "llvm/IR/Type.h"
  #include <initializer_list>
  #include "llvm/Support/MathExtras.h"
  
  #define DEBUG_TYPE "aarch64-legalinfo"
  
  using namespace llvm;
  using namespace LegalizeActions;
  using namespace LegalizeMutations;
  using namespace LegalityPredicates;
  
  AArch64LegalizerInfo::AArch64LegalizerInfo(const AArch64Subtarget &ST)
      : ST(&ST) {
    using namespace TargetOpcode;
    const LLT p0 = LLT::pointer(0, 64);
    const LLT s1 = LLT::scalar(1);
    const LLT s8 = LLT::scalar(8);
    const LLT s16 = LLT::scalar(16);
    const LLT s32 = LLT::scalar(32);
    const LLT s64 = LLT::scalar(64);
    const LLT s128 = LLT::scalar(128);
    const LLT s256 = LLT::scalar(256);
    const LLT s512 = LLT::scalar(512);
    const LLT v16s8 = LLT::vector(16, 8);
    const LLT v8s8 = LLT::vector(8, 8);
    const LLT v4s8 = LLT::vector(4, 8);
    const LLT v8s16 = LLT::vector(8, 16);
    const LLT v4s16 = LLT::vector(4, 16);
    const LLT v2s16 = LLT::vector(2, 16);
    const LLT v2s32 = LLT::vector(2, 32);
    const LLT v4s32 = LLT::vector(4, 32);
    const LLT v2s64 = LLT::vector(2, 64);
    const LLT v2p0 = LLT::vector(2, p0);
  
    std::initializer_list<LLT> PackedVectorAllTypeList = {/* Begin 128bit types */
                                                          v16s8, v8s16, v4s32,
                                                          v2s64, v2p0,
                                                          /* End 128bit types */
                                                          /* Begin 64bit types */
                                                          v8s8, v4s16, v2s32};
  
    const TargetMachine &TM = ST.getTargetLowering()->getTargetMachine();
  
    // FIXME: support subtargets which have neon/fp-armv8 disabled.
    if (!ST.hasNEON() || !ST.hasFPARMv8()) {
      computeTables();
      return;
    }
  
    // Some instructions only support s16 if the subtarget has full 16-bit FP
    // support.
    const bool HasFP16 = ST.hasFullFP16();
    const LLT &MinFPScalar = HasFP16 ? s16 : s32;
  
    getActionDefinitionsBuilder({G_IMPLICIT_DEF, G_FREEZE})
        .legalFor({p0, s1, s8, s16, s32, s64})
        .legalFor(PackedVectorAllTypeList)
        .clampScalar(0, s1, s64)
        .widenScalarToNextPow2(0, 8)
        .fewerElementsIf(
            [=](const LegalityQuery &Query) {
              return Query.Types[0].isVector() &&
                     (Query.Types[0].getElementType() != s64 ||
                      Query.Types[0].getNumElements() != 2);
            },
            [=](const LegalityQuery &Query) {
              LLT EltTy = Query.Types[0].getElementType();
              if (EltTy == s64)
                return std::make_pair(0, LLT::vector(2, 64));
              return std::make_pair(0, EltTy);
            });
  
    getActionDefinitionsBuilder(G_PHI).legalFor({p0, s16, s32, s64})
        .legalFor(PackedVectorAllTypeList)
        .clampScalar(0, s16, s64)
        .widenScalarToNextPow2(0);
  
    getActionDefinitionsBuilder(G_BSWAP)
        .legalFor({s32, s64, v4s32, v2s32, v2s64})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0);
  
    getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR})
        .legalFor({s32, s64, v2s32, v4s32, v4s16, v8s16, v16s8, v8s8})
        .scalarizeIf(
            [=](const LegalityQuery &Query) {
              return Query.Opcode == G_MUL && Query.Types[0] == v2s64;
            },
            0)
        .legalFor({v2s64})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .clampNumElements(0, v2s32, v4s32)
        .clampNumElements(0, v2s64, v2s64)
        .moreElementsToNextPow2(0);
  
    getActionDefinitionsBuilder({G_SHL, G_ASHR, G_LSHR})
        .customIf([=](const LegalityQuery &Query) {
          const auto &SrcTy = Query.Types[0];
          const auto &AmtTy = Query.Types[1];
          return !SrcTy.isVector() && SrcTy.getSizeInBits() == 32 &&
                 AmtTy.getSizeInBits() == 32;
        })
        .legalFor({
            {s32, s32},
            {s32, s64},
            {s64, s64},
            {v8s8, v8s8},
            {v16s8, v16s8},
            {v4s16, v4s16},
            {v8s16, v8s16},
            {v2s32, v2s32},
            {v4s32, v4s32},
            {v2s64, v2s64},
        })
        .clampScalar(1, s32, s64)
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .clampNumElements(0, v2s32, v4s32)
        .clampNumElements(0, v2s64, v2s64)
        .moreElementsToNextPow2(0)
        .minScalarSameAs(1, 0);
  
    getActionDefinitionsBuilder(G_PTR_ADD)
        .legalFor({{p0, s64}, {v2p0, v2s64}})
        .clampScalar(1, s64, s64);
  
    getActionDefinitionsBuilder(G_PTRMASK).legalFor({{p0, s64}});
  
    getActionDefinitionsBuilder({G_SDIV, G_UDIV})
        .legalFor({s32, s64})
        .libcallFor({s128})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .scalarize(0);
  
    getActionDefinitionsBuilder({G_SREM, G_UREM})
        .lowerFor({s1, s8, s16, s32, s64});
  
    getActionDefinitionsBuilder({G_SMULO, G_UMULO}).lowerFor({{s64, s1}});
  
    getActionDefinitionsBuilder({G_SMULH, G_UMULH}).legalFor({s32, s64});
  
    getActionDefinitionsBuilder({G_SMIN, G_SMAX, G_UMIN, G_UMAX})
        .lowerIf([=](const LegalityQuery &Q) { return Q.Types[0].isScalar(); });
  
    getActionDefinitionsBuilder(
        {G_SADDE, G_SSUBE, G_UADDE, G_USUBE, G_SADDO, G_SSUBO, G_UADDO, G_USUBO})
        .legalFor({{s32, s1}, {s64, s1}})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0);
  
    getActionDefinitionsBuilder({G_FADD, G_FSUB, G_FMUL, G_FDIV, G_FNEG})
        .legalFor({s32, s64, v2s64, v4s32, v2s32})
        .clampNumElements(0, v2s32, v4s32)
        .clampNumElements(0, v2s64, v2s64);
  
    getActionDefinitionsBuilder(G_FREM).libcallFor({s32, s64});
  
    getActionDefinitionsBuilder({G_FCEIL, G_FABS, G_FSQRT, G_FFLOOR, G_FRINT,
                                 G_FMA, G_INTRINSIC_TRUNC, G_INTRINSIC_ROUND,
                                 G_FNEARBYINT, G_INTRINSIC_LRINT})
        // If we don't have full FP16 support, then scalarize the elements of
        // vectors containing fp16 types.
        .fewerElementsIf(
            [=, &ST](const LegalityQuery &Query) {
              const auto &Ty = Query.Types[0];
              return Ty.isVector() && Ty.getElementType() == s16 &&
                     !ST.hasFullFP16();
            },
            [=](const LegalityQuery &Query) { return std::make_pair(0, s16); })
        // If we don't have full FP16 support, then widen s16 to s32 if we
        // encounter it.
        .widenScalarIf(
            [=, &ST](const LegalityQuery &Query) {
              return Query.Types[0] == s16 && !ST.hasFullFP16();
            },
            [=](const LegalityQuery &Query) { return std::make_pair(0, s32); })
        .legalFor({s16, s32, s64, v2s32, v4s32, v2s64, v2s16, v4s16, v8s16});
  
    getActionDefinitionsBuilder(
        {G_FCOS, G_FSIN, G_FLOG10, G_FLOG, G_FLOG2, G_FEXP, G_FEXP2, G_FPOW})
        // We need a call for these, so we always need to scalarize.
        .scalarize(0)
        // Regardless of FP16 support, widen 16-bit elements to 32-bits.
        .minScalar(0, s32)
        .libcallFor({s32, s64, v2s32, v4s32, v2s64});
  
    getActionDefinitionsBuilder(G_INSERT)
        .unsupportedIf([=](const LegalityQuery &Query) {
          return Query.Types[0].getSizeInBits() <= Query.Types[1].getSizeInBits();
        })
        .legalIf([=](const LegalityQuery &Query) {
          const LLT &Ty0 = Query.Types[0];
          const LLT &Ty1 = Query.Types[1];
          if (Ty0 != s32 && Ty0 != s64 && Ty0 != p0)
            return false;
          return isPowerOf2_32(Ty1.getSizeInBits()) &&
                 (Ty1.getSizeInBits() == 1 || Ty1.getSizeInBits() >= 8);
        })
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .maxScalarIf(typeInSet(0, {s32}), 1, s16)
        .maxScalarIf(typeInSet(0, {s64}), 1, s32)
        .widenScalarToNextPow2(1);
  
    getActionDefinitionsBuilder(G_EXTRACT)
        .unsupportedIf([=](const LegalityQuery &Query) {
          return Query.Types[0].getSizeInBits() >= Query.Types[1].getSizeInBits();
        })
        .legalIf([=](const LegalityQuery &Query) {
          const LLT &Ty0 = Query.Types[0];
          const LLT &Ty1 = Query.Types[1];
          if (Ty1 != s32 && Ty1 != s64 && Ty1 != s128)
            return false;
          if (Ty1 == p0)
            return true;
          return isPowerOf2_32(Ty0.getSizeInBits()) &&
                 (Ty0.getSizeInBits() == 1 || Ty0.getSizeInBits() >= 8);
        })
        .clampScalar(1, s32, s128)
        .widenScalarToNextPow2(1)
        .maxScalarIf(typeInSet(1, {s32}), 0, s16)
        .maxScalarIf(typeInSet(1, {s64}), 0, s32)
        .widenScalarToNextPow2(0);
  
    getActionDefinitionsBuilder({G_SEXTLOAD, G_ZEXTLOAD})
        .legalForTypesWithMemDesc({{s32, p0, 8, 8},
                                   {s32, p0, 16, 8},
                                   {s32, p0, 32, 8},
                                   {s64, p0, 8, 2},
                                   {s64, p0, 16, 2},
                                   {s64, p0, 32, 4},
                                   {s64, p0, 64, 8},
                                   {p0, p0, 64, 8},
                                   {v2s32, p0, 64, 8}})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        // TODO: We could support sum-of-pow2's but the lowering code doesn't know
        //       how to do that yet.
        .unsupportedIfMemSizeNotPow2()
        // Lower anything left over into G_*EXT and G_LOAD
        .lower();
  
    auto IsPtrVecPred = [=](const LegalityQuery &Query) {
      const LLT &ValTy = Query.Types[0];
      if (!ValTy.isVector())
        return false;
      const LLT EltTy = ValTy.getElementType();
      return EltTy.isPointer() && EltTy.getAddressSpace() == 0;
    };
  
    getActionDefinitionsBuilder(G_LOAD)
        .legalForTypesWithMemDesc({{s8, p0, 8, 8},
                                   {s16, p0, 16, 8},
                                   {s32, p0, 32, 8},
                                   {s64, p0, 64, 8},
                                   {p0, p0, 64, 8},
                                   {s128, p0, 128, 8},
                                   {v8s8, p0, 64, 8},
                                   {v16s8, p0, 128, 8},
                                   {v4s16, p0, 64, 8},
                                   {v8s16, p0, 128, 8},
                                   {v2s32, p0, 64, 8},
                                   {v4s32, p0, 128, 8},
                                   {v2s64, p0, 128, 8}})
        // These extends are also legal
        .legalForTypesWithMemDesc({{s32, p0, 8, 8}, {s32, p0, 16, 8}})
        .clampScalar(0, s8, s64)
        .lowerIfMemSizeNotPow2()
        // Lower any any-extending loads left into G_ANYEXT and G_LOAD
        .lowerIf([=](const LegalityQuery &Query) {
          return Query.Types[0].getSizeInBits() != Query.MMODescrs[0].SizeInBits;
        })
        .widenScalarToNextPow2(0)
        .clampMaxNumElements(0, s8, 16)
        .clampMaxNumElements(0, s16, 8)
        .clampMaxNumElements(0, s32, 4)
        .clampMaxNumElements(0, s64, 2)
        .customIf(IsPtrVecPred);
  
    getActionDefinitionsBuilder(G_STORE)
        .legalForTypesWithMemDesc({{s8, p0, 8, 8},
                                   {s16, p0, 16, 8},
                                   {s32, p0, 8, 8},
                                   {s32, p0, 16, 8},
                                   {s32, p0, 32, 8},
                                   {s64, p0, 64, 8},
                                   {p0, p0, 64, 8},
                                   {s128, p0, 128, 8},
                                   {v16s8, p0, 128, 8},
                                   {v8s8, p0, 64, 8},
                                   {v4s16, p0, 64, 8},
                                   {v8s16, p0, 128, 8},
                                   {v2s32, p0, 64, 8},
                                   {v4s32, p0, 128, 8},
                                   {v2s64, p0, 128, 8}})
        .clampScalar(0, s8, s64)
        .lowerIfMemSizeNotPow2()
        .lowerIf([=](const LegalityQuery &Query) {
          return Query.Types[0].isScalar() &&
                 Query.Types[0].getSizeInBits() != Query.MMODescrs[0].SizeInBits;
        })
        // Maximum: sN * k = 128
        .clampMaxNumElements(0, s8, 16)
        .clampMaxNumElements(0, s16, 8)
        .clampMaxNumElements(0, s32, 4)
        .clampMaxNumElements(0, s64, 2)
        .customIf(IsPtrVecPred);
  
    // Constants
    getActionDefinitionsBuilder(G_CONSTANT)
        .legalFor({p0, s8, s16, s32, s64})
        .clampScalar(0, s8, s64)
        .widenScalarToNextPow2(0);
    getActionDefinitionsBuilder(G_FCONSTANT)
        .legalIf([=](const LegalityQuery &Query) {
          const auto &Ty = Query.Types[0];
          if (HasFP16 && Ty == s16)
            return true;
          return Ty == s32 || Ty == s64 || Ty == s128;
        })
        .clampScalar(0, MinFPScalar, s128);
  
    getActionDefinitionsBuilder({G_ICMP, G_FCMP})
        .legalFor({{s32, s32},
                   {s32, s64},
                   {s32, p0},
                   {v4s32, v4s32},
                   {v2s32, v2s32},
                   {v2s64, v2s64},
                   {v2s64, v2p0},
                   {v4s16, v4s16},
                   {v8s16, v8s16},
                   {v8s8, v8s8},
                   {v16s8, v16s8}})
        .clampScalar(1, s32, s64)
        .clampScalar(0, s32, s32)
        .minScalarEltSameAsIf(
            [=](const LegalityQuery &Query) {
              const LLT &Ty = Query.Types[0];
              const LLT &SrcTy = Query.Types[1];
              return Ty.isVector() && !SrcTy.getElementType().isPointer() &&
                     Ty.getElementType() != SrcTy.getElementType();
            },
            0, 1)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) { return Query.Types[1] == v2s16; },
            1, s32)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) { return Query.Types[1] == v2p0; }, 0,
            s64)
        .widenScalarOrEltToNextPow2(1)
        .clampNumElements(0, v2s32, v4s32);
  
    // Extensions
    auto ExtLegalFunc = [=](const LegalityQuery &Query) {
      unsigned DstSize = Query.Types[0].getSizeInBits();
  
      if (DstSize == 128 && !Query.Types[0].isVector())
        return false; // Extending to a scalar s128 needs narrowing.
  
      // Make sure that we have something that will fit in a register, and
      // make sure it's a power of 2.
      if (DstSize < 8 || DstSize > 128 || !isPowerOf2_32(DstSize))
        return false;
  
      const LLT &SrcTy = Query.Types[1];
  
      // Special case for s1.
      if (SrcTy == s1)
        return true;
  
      // Make sure we fit in a register otherwise. Don't bother checking that
      // the source type is below 128 bits. We shouldn't be allowing anything
      // through which is wider than the destination in the first place.
      unsigned SrcSize = SrcTy.getSizeInBits();
      if (SrcSize < 8 || !isPowerOf2_32(SrcSize))
        return false;
  
      return true;
    };
    getActionDefinitionsBuilder({G_ZEXT, G_SEXT, G_ANYEXT})
        .legalIf(ExtLegalFunc)
        .clampScalar(0, s64, s64); // Just for s128, others are handled above.
  
    getActionDefinitionsBuilder(G_TRUNC)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) { return Query.Types[0].isVector(); },
            0, s8)
        .customIf([=](const LegalityQuery &Query) {
          LLT DstTy = Query.Types[0];
          LLT SrcTy = Query.Types[1];
          return DstTy == v8s8 && SrcTy.getSizeInBits() > 128;
        })
        .alwaysLegal();
  
    getActionDefinitionsBuilder(G_SEXT_INREG).legalFor({s32, s64}).lower();
  
    // FP conversions
    getActionDefinitionsBuilder(G_FPTRUNC)
        .legalFor(
            {{s16, s32}, {s16, s64}, {s32, s64}, {v4s16, v4s32}, {v2s32, v2s64}})
        .clampMaxNumElements(0, s32, 2);
    getActionDefinitionsBuilder(G_FPEXT)
        .legalFor(
            {{s32, s16}, {s64, s16}, {s64, s32}, {v4s32, v4s16}, {v2s64, v2s32}})
        .clampMaxNumElements(0, s64, 2);
  
    // Conversions
    getActionDefinitionsBuilder({G_FPTOSI, G_FPTOUI})
        .legalForCartesianProduct({s32, s64, v2s64, v4s32, v2s32})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .clampScalar(1, s32, s64)
        .widenScalarToNextPow2(1);
  
    getActionDefinitionsBuilder({G_SITOFP, G_UITOFP})
        .legalForCartesianProduct({s32, s64, v2s64, v4s32, v2s32})
        .clampScalar(1, s32, s64)
        .minScalarSameAs(1, 0)
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0);
  
    // Control-flow
    getActionDefinitionsBuilder(G_BRCOND).legalFor({s1, s8, s16, s32});
    getActionDefinitionsBuilder(G_BRINDIRECT).legalFor({p0});
  
    getActionDefinitionsBuilder(G_SELECT)
        .legalFor({{s32, s1}, {s64, s1}, {p0, s1}})
        .clampScalar(0, s32, s64)
        .widenScalarToNextPow2(0)
        .minScalarEltSameAsIf(all(isVector(0), isVector(1)), 1, 0)
        .lowerIf(isVector(0));
  
    // Pointer-handling
    getActionDefinitionsBuilder(G_FRAME_INDEX).legalFor({p0});
  
    if (TM.getCodeModel() == CodeModel::Small)
      getActionDefinitionsBuilder(G_GLOBAL_VALUE).custom();
    else
      getActionDefinitionsBuilder(G_GLOBAL_VALUE).legalFor({p0});
  
    getActionDefinitionsBuilder(G_PTRTOINT)
        .legalForCartesianProduct({s1, s8, s16, s32, s64}, {p0})
        .maxScalar(0, s64)
        .widenScalarToNextPow2(0, /*Min*/ 8);
  
    getActionDefinitionsBuilder(G_INTTOPTR)
        .unsupportedIf([&](const LegalityQuery &Query) {
          return Query.Types[0].getSizeInBits() != Query.Types[1].getSizeInBits();
        })
        .legalFor({{p0, s64}});
  
    // Casts for 32 and 64-bit width type are just copies.
    // Same for 128-bit width type, except they are on the FPR bank.
    getActionDefinitionsBuilder(G_BITCAST)
        // FIXME: This is wrong since G_BITCAST is not allowed to change the
        // number of bits but it's what the previous code described and fixing
        // it breaks tests.
        .legalForCartesianProduct({s1, s8, s16, s32, s64, s128, v16s8, v8s8, v4s8,
                                   v8s16, v4s16, v2s16, v4s32, v2s32, v2s64,
                                   v2p0});
  
    getActionDefinitionsBuilder(G_VASTART).legalFor({p0});
  
    // va_list must be a pointer, but most sized types are pretty easy to handle
    // as the destination.
    getActionDefinitionsBuilder(G_VAARG)
        .customForCartesianProduct({s8, s16, s32, s64, p0}, {p0})
        .clampScalar(0, s8, s64)
        .widenScalarToNextPow2(0, /*Min*/ 8);
  
    if (ST.hasLSE()) {
      getActionDefinitionsBuilder(G_ATOMIC_CMPXCHG_WITH_SUCCESS)
          .lowerIf(all(
              typeInSet(0, {s8, s16, s32, s64}), typeIs(1, s1), typeIs(2, p0),
              atomicOrderingAtLeastOrStrongerThan(0, AtomicOrdering::Monotonic)));
  
      getActionDefinitionsBuilder(
          {G_ATOMICRMW_XCHG, G_ATOMICRMW_ADD, G_ATOMICRMW_SUB, G_ATOMICRMW_AND,
           G_ATOMICRMW_OR, G_ATOMICRMW_XOR, G_ATOMICRMW_MIN, G_ATOMICRMW_MAX,
           G_ATOMICRMW_UMIN, G_ATOMICRMW_UMAX, G_ATOMIC_CMPXCHG})
          .legalIf(all(
              typeInSet(0, {s8, s16, s32, s64}), typeIs(1, p0),
              atomicOrderingAtLeastOrStrongerThan(0, AtomicOrdering::Monotonic)));
    }
  
    getActionDefinitionsBuilder(G_BLOCK_ADDR).legalFor({p0});
  
    // Merge/Unmerge
    for (unsigned Op : {G_MERGE_VALUES, G_UNMERGE_VALUES}) {
      unsigned BigTyIdx = Op == G_MERGE_VALUES ? 0 : 1;
      unsigned LitTyIdx = Op == G_MERGE_VALUES ? 1 : 0;
  
      auto notValidElt = [](const LegalityQuery &Query, unsigned TypeIdx) {
        const LLT &Ty = Query.Types[TypeIdx];
        if (Ty.isVector()) {
          const LLT &EltTy = Ty.getElementType();
          if (EltTy.getSizeInBits() < 8 || EltTy.getSizeInBits() > 64)
            return true;
          if (!isPowerOf2_32(EltTy.getSizeInBits()))
            return true;
        }
        return false;
      };
  
      // FIXME: This rule is horrible, but specifies the same as what we had
      // before with the particularly strange definitions removed (e.g.
      // s8 = G_MERGE_VALUES s32, s32).
      // Part of the complexity comes from these ops being extremely flexible. For
      // example, you can build/decompose vectors with it, concatenate vectors,
      // etc. and in addition to this you can also bitcast with it at the same
      // time. We've been considering breaking it up into multiple ops to make it
      // more manageable throughout the backend.
      getActionDefinitionsBuilder(Op)
          // Break up vectors with weird elements into scalars
          .fewerElementsIf(
              [=](const LegalityQuery &Query) { return notValidElt(Query, 0); },
              scalarize(0))
          .fewerElementsIf(
              [=](const LegalityQuery &Query) { return notValidElt(Query, 1); },
              scalarize(1))
          // Clamp the big scalar to s8-s512 and make it either a power of 2, 192,
          // or 384.
          .clampScalar(BigTyIdx, s8, s512)
          .widenScalarIf(
              [=](const LegalityQuery &Query) {
                const LLT &Ty = Query.Types[BigTyIdx];
                return !isPowerOf2_32(Ty.getSizeInBits()) &&
                       Ty.getSizeInBits() % 64 != 0;
              },
              [=](const LegalityQuery &Query) {
                // Pick the next power of 2, or a multiple of 64 over 128.
                // Whichever is smaller.
                const LLT &Ty = Query.Types[BigTyIdx];
                unsigned NewSizeInBits = 1
                                         << Log2_32_Ceil(Ty.getSizeInBits() + 1);
                if (NewSizeInBits >= 256) {
                  unsigned RoundedTo = alignTo<64>(Ty.getSizeInBits() + 1);
                  if (RoundedTo < NewSizeInBits)
                    NewSizeInBits = RoundedTo;
                }
                return std::make_pair(BigTyIdx, LLT::scalar(NewSizeInBits));
              })
          // Clamp the little scalar to s8-s256 and make it a power of 2. It's not
          // worth considering the multiples of 64 since 2*192 and 2*384 are not
          // valid.
          .clampScalar(LitTyIdx, s8, s256)
          .widenScalarToNextPow2(LitTyIdx, /*Min*/ 8)
          // So at this point, we have s8, s16, s32, s64, s128, s192, s256, s384,
          // s512, <X x s8>, <X x s16>, <X x s32>, or <X x s64>.
          // At this point it's simple enough to accept the legal types.
          .legalIf([=](const LegalityQuery &Query) {
            const LLT &BigTy = Query.Types[BigTyIdx];
            const LLT &LitTy = Query.Types[LitTyIdx];
            if (BigTy.isVector() && BigTy.getSizeInBits() < 32)
              return false;
            if (LitTy.isVector() && LitTy.getSizeInBits() < 32)
              return false;
            return BigTy.getSizeInBits() % LitTy.getSizeInBits() == 0;
          })
          // Any vectors left are the wrong size. Scalarize them.
          .scalarize(0)
          .scalarize(1);
    }
  
    getActionDefinitionsBuilder(G_EXTRACT_VECTOR_ELT)
        .unsupportedIf([=](const LegalityQuery &Query) {
          const LLT &EltTy = Query.Types[1].getElementType();
          return Query.Types[0] != EltTy;
        })
        .minScalar(2, s64)
        .legalIf([=](const LegalityQuery &Query) {
          const LLT &VecTy = Query.Types[1];
          return VecTy == v2s16 || VecTy == v4s16 || VecTy == v8s16 ||
                 VecTy == v4s32 || VecTy == v2s64 || VecTy == v2s32 ||
                 VecTy == v16s8 || VecTy == v2s32 || VecTy == v2p0;
        })
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) {
              // We want to promote to <M x s1> to <M x s64> if that wouldn't
              // cause the total vec size to be > 128b.
              return Query.Types[1].getNumElements() <= 2;
            },
            0, s64)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) {
              return Query.Types[1].getNumElements() <= 4;
            },
            0, s32)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) {
              return Query.Types[1].getNumElements() <= 8;
            },
            0, s16)
        .minScalarOrEltIf(
            [=](const LegalityQuery &Query) {
              return Query.Types[1].getNumElements() <= 16;
            },
            0, s8)
        .minScalarOrElt(0, s8); // Worst case, we need at least s8.
  
    getActionDefinitionsBuilder(G_INSERT_VECTOR_ELT)
        .legalIf(typeInSet(0, {v8s16, v2s32, v4s32, v2s64}));
  
    getActionDefinitionsBuilder(G_BUILD_VECTOR)
        .legalFor({{v8s8, s8},
                   {v16s8, s8},
                   {v4s16, s16},
                   {v8s16, s16},
                   {v2s32, s32},
                   {v4s32, s32},
                   {v2p0, p0},
                   {v2s64, s64}})
        .clampNumElements(0, v4s32, v4s32)
        .clampNumElements(0, v2s64, v2s64)
        .minScalarSameAs(1, 0);
  
    getActionDefinitionsBuilder(G_BUILD_VECTOR_TRUNC).lower();
  
    getActionDefinitionsBuilder(G_CTLZ)
        .legalForCartesianProduct(
            {s32, s64, v8s8, v16s8, v4s16, v8s16, v2s32, v4s32})
        .scalarize(1);
    getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF).lower();
  
    getActionDefinitionsBuilder(G_SHUFFLE_VECTOR)
        .legalIf([=](const LegalityQuery &Query) {
          const LLT &DstTy = Query.Types[0];
          const LLT &SrcTy = Query.Types[1];
          // For now just support the TBL2 variant which needs the source vectors
          // to be the same size as the dest.
          if (DstTy != SrcTy)
            return false;
          for (auto &Ty : {v2s32, v4s32, v2s64, v2p0, v16s8, v8s16}) {
            if (DstTy == Ty)
              return true;
          }
          return false;
        })
        // G_SHUFFLE_VECTOR can have scalar sources (from 1 x s vectors), we
        // just want those lowered into G_BUILD_VECTOR
        .lowerIf([=](const LegalityQuery &Query) {
          return !Query.Types[1].isVector();
        })
        .clampNumElements(0, v4s32, v4s32)
        .clampNumElements(0, v2s64, v2s64);
  
    getActionDefinitionsBuilder(G_CONCAT_VECTORS)
        .legalFor({{v4s32, v2s32}, {v8s16, v4s16}});
  
    getActionDefinitionsBuilder(G_JUMP_TABLE).legalFor({{p0}, {s64}});
  
    getActionDefinitionsBuilder(G_BRJT).legalIf([=](const LegalityQuery &Query) {
      return Query.Types[0] == p0 && Query.Types[1] == s64;
    });
  
    getActionDefinitionsBuilder(G_DYN_STACKALLOC).lower();
  
    getActionDefinitionsBuilder({G_BZERO, G_MEMCPY, G_MEMMOVE, G_MEMSET})
        .libcall();
  
    getActionDefinitionsBuilder(G_ABS).lowerIf(
        [=](const LegalityQuery &Query) { return Query.Types[0].isScalar(); });
  
    getActionDefinitionsBuilder(G_VECREDUCE_FADD)
        // We only have FADDP to do reduction-like operations. Lower the rest.
        .legalFor({{s32, v2s32}, {s64, v2s64}})
        .clampMaxNumElements(1, s64, 2)
        .clampMaxNumElements(1, s32, 2)
        .lower();
  
    getActionDefinitionsBuilder(G_VECREDUCE_ADD)
        .legalFor(
            {{s8, v16s8}, {s16, v8s16}, {s32, v4s32}, {s32, v2s32}, {s64, v2s64}})
        .clampMaxNumElements(1, s64, 2)
        .clampMaxNumElements(1, s32, 4)
        .lower();
  
    getActionDefinitionsBuilder({G_UADDSAT, G_USUBSAT})
        .lowerIf([=](const LegalityQuery &Q) { return Q.Types[0].isScalar(); });
  
    getActionDefinitionsBuilder({G_FSHL, G_FSHR}).lower();
  
    getActionDefinitionsBuilder(G_ROTR)
        .legalFor({{s32, s64}, {s64, s64}})
        .customIf([=](const LegalityQuery &Q) {
          return Q.Types[0].isScalar() && Q.Types[1].getScalarSizeInBits() < 64;
        })
        .lower();
    getActionDefinitionsBuilder(G_ROTL).lower();
  
    getActionDefinitionsBuilder({G_SBFX, G_UBFX})
        .customFor({{s32, s32}, {s64, s64}});
  
    computeTables();
    verify(*ST.getInstrInfo());
  }
  
  bool AArch64LegalizerInfo::legalizeCustom(LegalizerHelper &Helper,
                                            MachineInstr &MI) const {
    MachineIRBuilder &MIRBuilder = Helper.MIRBuilder;
    MachineRegisterInfo &MRI = *MIRBuilder.getMRI();
    GISelChangeObserver &Observer = Helper.Observer;
    switch (MI.getOpcode()) {
    default:
      // No idea what to do.
      return false;
    case TargetOpcode::G_VAARG:
      return legalizeVaArg(MI, MRI, MIRBuilder);
    case TargetOpcode::G_LOAD:
    case TargetOpcode::G_STORE:
      return legalizeLoadStore(MI, MRI, MIRBuilder, Observer);
    case TargetOpcode::G_SHL:
    case TargetOpcode::G_ASHR:
    case TargetOpcode::G_LSHR:
      return legalizeShlAshrLshr(MI, MRI, MIRBuilder, Observer);
    case TargetOpcode::G_GLOBAL_VALUE:
      return legalizeSmallCMGlobalValue(MI, MRI, MIRBuilder, Observer);
    case TargetOpcode::G_TRUNC:
      return legalizeVectorTrunc(MI, Helper);
    case TargetOpcode::G_SBFX:
    case TargetOpcode::G_UBFX:
      return legalizeBitfieldExtract(MI, MRI, Helper);
    case TargetOpcode::G_ROTR:
      return legalizeRotate(MI, MRI, Helper);
    }
  
    llvm_unreachable("expected switch to return");
  }
  
  bool AArch64LegalizerInfo::legalizeRotate(MachineInstr &MI,
                                            MachineRegisterInfo &MRI,
                                            LegalizerHelper &Helper) const {
    // To allow for imported patterns to match, we ensure that the rotate amount
    // is 64b with an extension.
    Register AmtReg = MI.getOperand(2).getReg();
    LLT AmtTy = MRI.getType(AmtReg);
    (void)AmtTy;
    assert(AmtTy.isScalar() && "Expected a scalar rotate");
    assert(AmtTy.getSizeInBits() < 64 && "Expected this rotate to be legal");
    auto NewAmt = Helper.MIRBuilder.buildSExt(LLT::scalar(64), AmtReg);
    Helper.Observer.changingInstr(MI);
    MI.getOperand(2).setReg(NewAmt.getReg(0));
    Helper.Observer.changedInstr(MI);
    return true;
  }
  
  static void extractParts(Register Reg, MachineRegisterInfo &MRI,
                           MachineIRBuilder &MIRBuilder, LLT Ty, int NumParts,
                           SmallVectorImpl<Register> &VRegs) {
    for (int I = 0; I < NumParts; ++I)
      VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
    MIRBuilder.buildUnmerge(VRegs, Reg);
  }
  
  bool AArch64LegalizerInfo::legalizeVectorTrunc(
      MachineInstr &MI, LegalizerHelper &Helper) const {
    MachineIRBuilder &MIRBuilder = Helper.MIRBuilder;
    MachineRegisterInfo &MRI = *MIRBuilder.getMRI();
    // Similar to how operand splitting is done in SelectiondDAG, we can handle
    // %res(v8s8) = G_TRUNC %in(v8s32) by generating:
    //   %inlo(<4x s32>), %inhi(<4 x s32>) = G_UNMERGE %in(<8 x s32>)
    //   %lo16(<4 x s16>) = G_TRUNC %inlo
    //   %hi16(<4 x s16>) = G_TRUNC %inhi
    //   %in16(<8 x s16>) = G_CONCAT_VECTORS %lo16, %hi16
    //   %res(<8 x s8>) = G_TRUNC %in16
  
    Register DstReg = MI.getOperand(0).getReg();
    Register SrcReg = MI.getOperand(1).getReg();
    LLT DstTy = MRI.getType(DstReg);
    LLT SrcTy = MRI.getType(SrcReg);
    assert(isPowerOf2_32(DstTy.getSizeInBits()) &&
           isPowerOf2_32(SrcTy.getSizeInBits()));
  
    // Split input type.
    LLT SplitSrcTy = SrcTy.changeNumElements(SrcTy.getNumElements() / 2);
    // First, split the source into two smaller vectors.
    SmallVector<Register, 2> SplitSrcs;
    extractParts(SrcReg, MRI, MIRBuilder, SplitSrcTy, 2, SplitSrcs);
  
    // Truncate the splits into intermediate narrower elements.
    LLT InterTy = SplitSrcTy.changeElementSize(DstTy.getScalarSizeInBits() * 2);
    for (unsigned I = 0; I < SplitSrcs.size(); ++I)
      SplitSrcs[I] = MIRBuilder.buildTrunc(InterTy, SplitSrcs[I]).getReg(0);
  
    auto Concat = MIRBuilder.buildConcatVectors(
        DstTy.changeElementSize(DstTy.getScalarSizeInBits() * 2), SplitSrcs);
  
    Helper.Observer.changingInstr(MI);
    MI.getOperand(1).setReg(Concat.getReg(0));
    Helper.Observer.changedInstr(MI);
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeSmallCMGlobalValue(
      MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder,
      GISelChangeObserver &Observer) const {
    assert(MI.getOpcode() == TargetOpcode::G_GLOBAL_VALUE);
    // We do this custom legalization to convert G_GLOBAL_VALUE into target ADRP +
    // G_ADD_LOW instructions.
    // By splitting this here, we can optimize accesses in the small code model by
    // folding in the G_ADD_LOW into the load/store offset.
    auto &GlobalOp = MI.getOperand(1);
    const auto* GV = GlobalOp.getGlobal();
    if (GV->isThreadLocal())
      return true; // Don't want to modify TLS vars.
  
    auto &TM = ST->getTargetLowering()->getTargetMachine();
    unsigned OpFlags = ST->ClassifyGlobalReference(GV, TM);
  
    if (OpFlags & AArch64II::MO_GOT)
      return true;
  
    auto Offset = GlobalOp.getOffset();
    Register DstReg = MI.getOperand(0).getReg();
    auto ADRP = MIRBuilder.buildInstr(AArch64::ADRP, {LLT::pointer(0, 64)}, {})
                    .addGlobalAddress(GV, Offset, OpFlags | AArch64II::MO_PAGE);
    // Set the regclass on the dest reg too.
    MRI.setRegClass(ADRP.getReg(0), &AArch64::GPR64RegClass);
  
    // MO_TAGGED on the page indicates a tagged address. Set the tag now. We do so
    // by creating a MOVK that sets bits 48-63 of the register to (global address
    // + 0x100000000 - PC) >> 48. The additional 0x100000000 offset here is to
    // prevent an incorrect tag being generated during relocation when the the
    // global appears before the code section. Without the offset, a global at
    // `0x0f00'0000'0000'1000` (i.e. at `0x1000` with tag `0xf`) that's referenced
    // by code at `0x2000` would result in `0x0f00'0000'0000'1000 - 0x2000 =
    // 0x0eff'ffff'ffff'f000`, meaning the tag would be incorrectly set to `0xe`
    // instead of `0xf`.
    // This assumes that we're in the small code model so we can assume a binary
    // size of <= 4GB, which makes the untagged PC relative offset positive. The
    // binary must also be loaded into address range [0, 2^48). Both of these
    // properties need to be ensured at runtime when using tagged addresses.
    if (OpFlags & AArch64II::MO_TAGGED) {
      assert(!Offset &&
             "Should not have folded in an offset for a tagged global!");
      ADRP = MIRBuilder.buildInstr(AArch64::MOVKXi, {LLT::pointer(0, 64)}, {ADRP})
                 .addGlobalAddress(GV, 0x100000000,
                                   AArch64II::MO_PREL | AArch64II::MO_G3)
                 .addImm(48);
      MRI.setRegClass(ADRP.getReg(0), &AArch64::GPR64RegClass);
    }
  
    MIRBuilder.buildInstr(AArch64::G_ADD_LOW, {DstReg}, {ADRP})
        .addGlobalAddress(GV, Offset,
                          OpFlags | AArch64II::MO_PAGEOFF | AArch64II::MO_NC);
    MI.eraseFromParent();
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeIntrinsic(LegalizerHelper &Helper,
                                               MachineInstr &MI) const {
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeShlAshrLshr(
      MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder,
      GISelChangeObserver &Observer) const {
    assert(MI.getOpcode() == TargetOpcode::G_ASHR ||
           MI.getOpcode() == TargetOpcode::G_LSHR ||
           MI.getOpcode() == TargetOpcode::G_SHL);
    // If the shift amount is a G_CONSTANT, promote it to a 64 bit type so the
    // imported patterns can select it later. Either way, it will be legal.
    Register AmtReg = MI.getOperand(2).getReg();
    auto VRegAndVal = getConstantVRegValWithLookThrough(AmtReg, MRI);
    if (!VRegAndVal)
      return true;
    // Check the shift amount is in range for an immediate form.
    int64_t Amount = VRegAndVal->Value.getSExtValue();
    if (Amount > 31)
      return true; // This will have to remain a register variant.
    auto ExtCst = MIRBuilder.buildConstant(LLT::scalar(64), Amount);
    Observer.changingInstr(MI);
    MI.getOperand(2).setReg(ExtCst.getReg(0));
    Observer.changedInstr(MI);
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeLoadStore(
      MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder,
      GISelChangeObserver &Observer) const {
    assert(MI.getOpcode() == TargetOpcode::G_STORE ||
           MI.getOpcode() == TargetOpcode::G_LOAD);
    // Here we just try to handle vector loads/stores where our value type might
    // have pointer elements, which the SelectionDAG importer can't handle. To
    // allow the existing patterns for s64 to fire for p0, we just try to bitcast
    // the value to use s64 types.
  
    // Custom legalization requires the instruction, if not deleted, must be fully
    // legalized. In order to allow further legalization of the inst, we create
    // a new instruction and erase the existing one.
  
    Register ValReg = MI.getOperand(0).getReg();
    const LLT ValTy = MRI.getType(ValReg);
  
    if (!ValTy.isVector() || !ValTy.getElementType().isPointer() ||
        ValTy.getElementType().getAddressSpace() != 0) {
      LLVM_DEBUG(dbgs() << "Tried to do custom legalization on wrong load/store");
      return false;
    }
  
    unsigned PtrSize = ValTy.getElementType().getSizeInBits();
    const LLT NewTy = LLT::vector(ValTy.getNumElements(), PtrSize);
    auto &MMO = **MI.memoperands_begin();
    if (MI.getOpcode() == TargetOpcode::G_STORE) {
      auto Bitcast = MIRBuilder.buildBitcast(NewTy, ValReg);
      MIRBuilder.buildStore(Bitcast.getReg(0), MI.getOperand(1), MMO);
    } else {
      auto NewLoad = MIRBuilder.buildLoad(NewTy, MI.getOperand(1), MMO);
      MIRBuilder.buildBitcast(ValReg, NewLoad);
    }
    MI.eraseFromParent();
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeVaArg(MachineInstr &MI,
                                           MachineRegisterInfo &MRI,
                                           MachineIRBuilder &MIRBuilder) const {
    MachineFunction &MF = MIRBuilder.getMF();
    Align Alignment(MI.getOperand(2).getImm());
    Register Dst = MI.getOperand(0).getReg();
    Register ListPtr = MI.getOperand(1).getReg();
  
    LLT PtrTy = MRI.getType(ListPtr);
    LLT IntPtrTy = LLT::scalar(PtrTy.getSizeInBits());
  
    const unsigned PtrSize = PtrTy.getSizeInBits() / 8;
    const Align PtrAlign = Align(PtrSize);
    auto List = MIRBuilder.buildLoad(
        PtrTy, ListPtr,
        *MF.getMachineMemOperand(MachinePointerInfo(), MachineMemOperand::MOLoad,
                                 PtrSize, PtrAlign));
  
    MachineInstrBuilder DstPtr;
    if (Alignment > PtrAlign) {
      // Realign the list to the actual required alignment.
      auto AlignMinus1 =
          MIRBuilder.buildConstant(IntPtrTy, Alignment.value() - 1);
      auto ListTmp = MIRBuilder.buildPtrAdd(PtrTy, List, AlignMinus1.getReg(0));
      DstPtr = MIRBuilder.buildMaskLowPtrBits(PtrTy, ListTmp, Log2(Alignment));
    } else
      DstPtr = List;
  
    uint64_t ValSize = MRI.getType(Dst).getSizeInBits() / 8;
    MIRBuilder.buildLoad(
        Dst, DstPtr,
        *MF.getMachineMemOperand(MachinePointerInfo(), MachineMemOperand::MOLoad,
                                 ValSize, std::max(Alignment, PtrAlign)));
  
    auto Size = MIRBuilder.buildConstant(IntPtrTy, alignTo(ValSize, PtrAlign));
  
    auto NewList = MIRBuilder.buildPtrAdd(PtrTy, DstPtr, Size.getReg(0));
  
    MIRBuilder.buildStore(NewList, ListPtr,
                          *MF.getMachineMemOperand(MachinePointerInfo(),
                                                   MachineMemOperand::MOStore,
                                                   PtrSize, PtrAlign));
  
    MI.eraseFromParent();
    return true;
  }
  
  bool AArch64LegalizerInfo::legalizeBitfieldExtract(
      MachineInstr &MI, MachineRegisterInfo &MRI, LegalizerHelper &Helper) const {
    // Only legal if we can select immediate forms.
    // TODO: Lower this otherwise.
    return getConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI) &&
           getConstantVRegValWithLookThrough(MI.getOperand(3).getReg(), MRI);
  }
  