/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

Bug Summary

File:	llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp
Warning:	line 1812, column 62 The result of the right shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AMDGPULegalizerInfo.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/include -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Target/AMDGPU -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-12-07-102640-14763-1 -x c++ /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

→

1//===- AMDGPULegalizerInfo.cpp -----------------------------------*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8/// \file
9/// This file implements the targeting of the Machinelegalizer class for
10/// AMDGPU.
11/// \todo This should be generated by TableGen.
12//===----------------------------------------------------------------------===//

14#if defined(_MSC_VER) || defined(__MINGW32__)
15// According to Microsoft, one must set _USE_MATH_DEFINES in order to get M_PI
16// from the Visual C++ cmath / math.h headers:
17// https://docs.microsoft.com/en-us/cpp/c-runtime-library/math-constants?view=vs-2019
18#define _USE_MATH_DEFINES
19#endif

21#include "AMDGPU.h"
22#include "AMDGPULegalizerInfo.h"
23#include "AMDGPUTargetMachine.h"
24#include "SIMachineFunctionInfo.h"
25#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
26#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
27#include "llvm/CodeGen/TargetOpcodes.h"
28#include "llvm/CodeGen/ValueTypes.h"
29#include "llvm/IR/DerivedTypes.h"
30#include "llvm/IR/DiagnosticInfo.h"
31#include "llvm/IR/Type.h"
32#include "llvm/Support/Debug.h"

34#define DEBUG_TYPE"amdgpu-legalinfo" "amdgpu-legalinfo"

36using namespace llvm;
37using namespace LegalizeActions;
38using namespace LegalizeMutations;
39using namespace LegalityPredicates;


42static LegalityPredicate isMultiple32(unsigned TypeIdx,
                                    unsigned MaxSize = 1024) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  const LLT EltTy = Ty.getScalarType();
  return Ty.getSizeInBits() <= MaxSize && EltTy.getSizeInBits() % 32 == 0;
};
49}

51static LegalityPredicate sizeIs(unsigned TypeIdx, unsigned Size) {
return [=](const LegalityQuery &Query) {
  return Query.Types[TypeIdx].getSizeInBits() == Size;
};
55}

57static LegalityPredicate isSmallOddVector(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  return Ty.isVector() &&
         Ty.getNumElements() % 2 != 0 &&
         Ty.getElementType().getSizeInBits() < 32 &&
         Ty.getSizeInBits() % 32 != 0;
};
65}

67static LegalityPredicate isWideVec16(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  const LLT EltTy = Ty.getScalarType();
  return EltTy.getSizeInBits() == 16 && Ty.getNumElements() > 2;
};
73}

75static LegalizeMutation oneMoreElement(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  const LLT EltTy = Ty.getElementType();
  return std::make_pair(TypeIdx, LLT::vector(Ty.getNumElements() + 1, EltTy));
};
81}

83static LegalizeMutation fewerEltsToSize64Vector(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  const LLT EltTy = Ty.getElementType();
  unsigned Size = Ty.getSizeInBits();
  unsigned Pieces = (Size + 63) / 64;
  unsigned NewNumElts = (Ty.getNumElements() + 1) / Pieces;
  return std::make_pair(TypeIdx, LLT::scalarOrVector(NewNumElts, EltTy));
};
92}

94// Increase the number of vector elements to reach the next multiple of 32-bit
95// type.
96static LegalizeMutation moreEltsToNext32Bit(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];

  const LLT EltTy = Ty.getElementType();
  const int Size = Ty.getSizeInBits();
  const int EltSize = EltTy.getSizeInBits();
  const int NextMul32 = (Size + 31) / 32;

  assert(EltSize < 32)((EltSize < 32) ? static_cast<void> (0) : __assert_fail
 ("EltSize < 32", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 105, __PRETTY_FUNCTION__));

  const int NewNumElts = (32 * NextMul32 + EltSize - 1) / EltSize;
  return std::make_pair(TypeIdx, LLT::vector(NewNumElts, EltTy));
};
110}

112static LegalityPredicate vectorSmallerThan(unsigned TypeIdx, unsigned Size) {
return [=](const LegalityQuery &Query) {
  const LLT QueryTy = Query.Types[TypeIdx];
  return QueryTy.isVector() && QueryTy.getSizeInBits() < Size;
};
117}

119static LegalityPredicate vectorWiderThan(unsigned TypeIdx, unsigned Size) {
return [=](const LegalityQuery &Query) {
  const LLT QueryTy = Query.Types[TypeIdx];
  return QueryTy.isVector() && QueryTy.getSizeInBits() > Size;
};
124}

126static LegalityPredicate numElementsNotEven(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT QueryTy = Query.Types[TypeIdx];
  return QueryTy.isVector() && QueryTy.getNumElements() % 2 != 0;
};
131}

133// Any combination of 32 or 64-bit elements up to 1024 bits, and multiples of
134// v2s16.
135static LegalityPredicate isRegisterType(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  if (Ty.isVector()) {
    const int EltSize = Ty.getElementType().getSizeInBits();
    return EltSize == 32 || EltSize == 64 ||
          (EltSize == 16 && Ty.getNumElements() % 2 == 0) ||
           EltSize == 128 || EltSize == 256;
  }

  return Ty.getSizeInBits() % 32 == 0 && Ty.getSizeInBits() <= 1024;
};
147}

149static LegalityPredicate elementTypeIs(unsigned TypeIdx, LLT Type) {
return [=](const LegalityQuery &Query) {
  return Query.Types[TypeIdx].getElementType() == Type;
};
153}

155static LegalityPredicate isWideScalarTruncStore(unsigned TypeIdx) {
return [=](const LegalityQuery &Query) {
  const LLT Ty = Query.Types[TypeIdx];
  return !Ty.isVector() && Ty.getSizeInBits() > 32 &&
         Query.MMODescrs[0].SizeInBits < Ty.getSizeInBits();
};
161}

163AMDGPULegalizerInfo::AMDGPULegalizerInfo(const GCNSubtarget &ST_,
                                       const GCNTargetMachine &TM)
:  ST(ST_) {
using namespace TargetOpcode;

auto GetAddrSpacePtr = [&TM](unsigned AS) {
  return LLT::pointer(AS, TM.getPointerSizeInBits(AS));
};

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 S96 = LLT::scalar(96);
const LLT S128 = LLT::scalar(128);
const LLT S256 = LLT::scalar(256);
const LLT S1024 = LLT::scalar(1024);

const LLT V2S16 = LLT::vector(2, 16);
const LLT V4S16 = LLT::vector(4, 16);

const LLT V2S32 = LLT::vector(2, 32);
const LLT V3S32 = LLT::vector(3, 32);
const LLT V4S32 = LLT::vector(4, 32);
const LLT V5S32 = LLT::vector(5, 32);
const LLT V6S32 = LLT::vector(6, 32);
const LLT V7S32 = LLT::vector(7, 32);
const LLT V8S32 = LLT::vector(8, 32);
const LLT V9S32 = LLT::vector(9, 32);
const LLT V10S32 = LLT::vector(10, 32);
const LLT V11S32 = LLT::vector(11, 32);
const LLT V12S32 = LLT::vector(12, 32);
const LLT V13S32 = LLT::vector(13, 32);
const LLT V14S32 = LLT::vector(14, 32);
const LLT V15S32 = LLT::vector(15, 32);
const LLT V16S32 = LLT::vector(16, 32);
const LLT V32S32 = LLT::vector(32, 32);

const LLT V2S64 = LLT::vector(2, 64);
const LLT V3S64 = LLT::vector(3, 64);
const LLT V4S64 = LLT::vector(4, 64);
const LLT V5S64 = LLT::vector(5, 64);
const LLT V6S64 = LLT::vector(6, 64);
const LLT V7S64 = LLT::vector(7, 64);
const LLT V8S64 = LLT::vector(8, 64);
const LLT V16S64 = LLT::vector(16, 64);

std::initializer_list<LLT> AllS32Vectors =
  {V2S32, V3S32, V4S32, V5S32, V6S32, V7S32, V8S32,
   V9S32, V10S32, V11S32, V12S32, V13S32, V14S32, V15S32, V16S32, V32S32};
std::initializer_list<LLT> AllS64Vectors =
  {V2S64, V3S64, V4S64, V5S64, V6S64, V7S64, V8S64, V16S64};

const LLT GlobalPtr = GetAddrSpacePtr(AMDGPUAS::GLOBAL_ADDRESS);
const LLT ConstantPtr = GetAddrSpacePtr(AMDGPUAS::CONSTANT_ADDRESS);
const LLT Constant32Ptr = GetAddrSpacePtr(AMDGPUAS::CONSTANT_ADDRESS_32BIT);
const LLT LocalPtr = GetAddrSpacePtr(AMDGPUAS::LOCAL_ADDRESS);
const LLT RegionPtr = GetAddrSpacePtr(AMDGPUAS::REGION_ADDRESS);
const LLT FlatPtr = GetAddrSpacePtr(AMDGPUAS::FLAT_ADDRESS);
const LLT PrivatePtr = GetAddrSpacePtr(AMDGPUAS::PRIVATE_ADDRESS);

const LLT CodePtr = FlatPtr;

const std::initializer_list<LLT> AddrSpaces64 = {
  GlobalPtr, ConstantPtr, FlatPtr
};

const std::initializer_list<LLT> AddrSpaces32 = {
  LocalPtr, PrivatePtr, Constant32Ptr, RegionPtr
};

const std::initializer_list<LLT> FPTypesBase = {
  S32, S64
};

const std::initializer_list<LLT> FPTypes16 = {
  S32, S64, S16
};

const std::initializer_list<LLT> FPTypesPK16 = {
  S32, S64, S16, V2S16
};

setAction({G_BRCOND, S1}, Legal);

// TODO: All multiples of 32, vectors of pointers, all v2s16 pairs, more
// elements for v3s16
getActionDefinitionsBuilder(G_PHI)
  .legalFor({S32, S64, V2S16, V4S16, S1, S128, S256})
  .legalFor(AllS32Vectors)
  .legalFor(AllS64Vectors)
  .legalFor(AddrSpaces64)
  .legalFor(AddrSpaces32)
  .clampScalar(0, S32, S256)
  .widenScalarToNextPow2(0, 32)
  .clampMaxNumElements(0, S32, 16)
  .moreElementsIf(isSmallOddVector(0), oneMoreElement(0))
  .legalIf(isPointer(0));

if (ST.has16BitInsts()) {
  getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL})
    .legalFor({S32, S16})
    .clampScalar(0, S16, S32)
    .scalarize(0);
} else {
  getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL})
    .legalFor({S32})
    .clampScalar(0, S32, S32)
    .scalarize(0);
}

getActionDefinitionsBuilder({G_UMULH, G_SMULH})
  .legalFor({S32})
  .clampScalar(0, S32, S32)
  .scalarize(0);

// Report legal for any types we can handle anywhere. For the cases only legal
// on the SALU, RegBankSelect will be able to re-legalize.
getActionDefinitionsBuilder({G_AND, G_OR, G_XOR})
  .legalFor({S32, S1, S64, V2S32, S16, V2S16, V4S16})
  .clampScalar(0, S32, S64)
  .moreElementsIf(isSmallOddVector(0), oneMoreElement(0))
  .fewerElementsIf(vectorWiderThan(0, 64), fewerEltsToSize64Vector(0))
  .widenScalarToNextPow2(0)
  .scalarize(0);

getActionDefinitionsBuilder({G_UADDO, G_USUBO,
                             G_UADDE, G_SADDE, G_USUBE, G_SSUBE})
  .legalFor({{S32, S1}})
  .clampScalar(0, S32, S32)
  .scalarize(0); // TODO: Implement.

getActionDefinitionsBuilder({G_SADDO, G_SSUBO})
  .lower();

getActionDefinitionsBuilder(G_BITCAST)
  // Don't worry about the size constraint.
  .legalIf(all(isRegisterType(0), isRegisterType(1)))
  // FIXME: Testing hack
  .legalForCartesianProduct({S16, LLT::vector(2, 8), });

getActionDefinitionsBuilder(G_FCONSTANT)
  .legalFor({S32, S64, S16})
  .clampScalar(0, S16, S64);

getActionDefinitionsBuilder(G_IMPLICIT_DEF)
  .legalFor({S1, S32, S64, S16, V2S32, V4S32, V2S16, V4S16, GlobalPtr,
             ConstantPtr, LocalPtr, FlatPtr, PrivatePtr})
  .moreElementsIf(isSmallOddVector(0), oneMoreElement(0))
  .clampScalarOrElt(0, S32, S1024)
  .legalIf(isMultiple32(0))
  .widenScalarToNextPow2(0, 32)
  .clampMaxNumElements(0, S32, 16);


// FIXME: i1 operands to intrinsics should always be legal, but other i1
// values may not be legal.  We need to figure out how to distinguish
// between these two scenarios.
getActionDefinitionsBuilder(G_CONSTANT)
  .legalFor({S1, S32, S64, S16, GlobalPtr,
             LocalPtr, ConstantPtr, PrivatePtr, FlatPtr })
  .clampScalar(0, S32, S64)
  .widenScalarToNextPow2(0)
  .legalIf(isPointer(0));

setAction({G_FRAME_INDEX, PrivatePtr}, Legal);
getActionDefinitionsBuilder(G_GLOBAL_VALUE)
  .customFor({LocalPtr, GlobalPtr, ConstantPtr, Constant32Ptr});


auto &FPOpActions = getActionDefinitionsBuilder(
  { G_FADD, G_FMUL, G_FMA, G_FCANONICALIZE})
  .legalFor({S32, S64});
auto &TrigActions = getActionDefinitionsBuilder({G_FSIN, G_FCOS})
  .customFor({S32, S64});
auto &FDIVActions = getActionDefinitionsBuilder(G_FDIV)
  .customFor({S32, S64});

if (ST.has16BitInsts()) {
  if (ST.hasVOP3PInsts())
    FPOpActions.legalFor({S16, V2S16});
  else
    FPOpActions.legalFor({S16});

  TrigActions.customFor({S16});
  FDIVActions.customFor({S16});
}

auto &MinNumMaxNum = getActionDefinitionsBuilder({
    G_FMINNUM, G_FMAXNUM, G_FMINNUM_IEEE, G_FMAXNUM_IEEE});

if (ST.hasVOP3PInsts()) {
  MinNumMaxNum.customFor(FPTypesPK16)
    .clampMaxNumElements(0, S16, 2)
    .clampScalar(0, S16, S64)
    .scalarize(0);
} else if (ST.has16BitInsts()) {
  MinNumMaxNum.customFor(FPTypes16)
    .clampScalar(0, S16, S64)
    .scalarize(0);
} else {
  MinNumMaxNum.customFor(FPTypesBase)
    .clampScalar(0, S32, S64)
    .scalarize(0);
}

if (ST.hasVOP3PInsts())
  FPOpActions.clampMaxNumElements(0, S16, 2);

FPOpActions
  .scalarize(0)
  .clampScalar(0, ST.has16BitInsts() ? S16 : S32, S64);

TrigActions
  .scalarize(0)
  .clampScalar(0, ST.has16BitInsts() ? S16 : S32, S64);

FDIVActions
  .scalarize(0)
  .clampScalar(0, ST.has16BitInsts() ? S16 : S32, S64);

getActionDefinitionsBuilder({G_FNEG, G_FABS})
  .legalFor(FPTypesPK16)
  .clampMaxNumElements(0, S16, 2)
  .scalarize(0)
  .clampScalar(0, S16, S64);

// TODO: Implement
getActionDefinitionsBuilder({G_FMINIMUM, G_FMAXIMUM}).lower();

if (ST.has16BitInsts()) {
  getActionDefinitionsBuilder({G_FSQRT, G_FFLOOR})
    .legalFor({S32, S64, S16})
    .scalarize(0)
    .clampScalar(0, S16, S64);
} else {
  getActionDefinitionsBuilder({G_FSQRT, G_FFLOOR})
    .legalFor({S32, S64})
    .scalarize(0)
    .clampScalar(0, S32, S64);
}

getActionDefinitionsBuilder(G_FPTRUNC)
  .legalFor({{S32, S64}, {S16, S32}})
  .scalarize(0);

getActionDefinitionsBuilder(G_FPEXT)
  .legalFor({{S64, S32}, {S32, S16}})
  .lowerFor({{S64, S16}}) // FIXME: Implement
  .scalarize(0);

// TODO: Verify V_BFI_B32 is generated from expanded bit ops.
getActionDefinitionsBuilder(G_FCOPYSIGN).lower();

getActionDefinitionsBuilder(G_FSUB)
    // Use actual fsub instruction
    .legalFor({S32})
    // Must use fadd + fneg
    .lowerFor({S64, S16, V2S16})
    .scalarize(0)
    .clampScalar(0, S32, S64);

// Whether this is legal depends on the floating point mode for the function.
auto &FMad = getActionDefinitionsBuilder(G_FMAD);
if (ST.hasMadF16())
  FMad.customFor({S32, S16});
else
  FMad.customFor({S32});
FMad.scalarize(0)
    .lower();

getActionDefinitionsBuilder({G_SEXT, G_ZEXT, G_ANYEXT})
  .legalFor({{S64, S32}, {S32, S16}, {S64, S16},
             {S32, S1}, {S64, S1}, {S16, S1},
             {S96, S32},
             // FIXME: Hack
             {S64, LLT::scalar(33)},
             {S32, S8}, {S128, S32}, {S128, S64}, {S32, LLT::scalar(24)}})
  .scalarize(0);

// TODO: Split s1->s64 during regbankselect for VALU.
auto &IToFP = getActionDefinitionsBuilder({G_SITOFP, G_UITOFP})
  .legalFor({{S32, S32}, {S64, S32}, {S16, S32}, {S32, S1}, {S16, S1}, {S64, S1}})
  .lowerFor({{S32, S64}})
  .customFor({{S64, S64}});
if (ST.has16BitInsts())
  IToFP.legalFor({{S16, S16}});
IToFP.clampScalar(1, S32, S64)
     .scalarize(0);

auto &FPToI = getActionDefinitionsBuilder({G_FPTOSI, G_FPTOUI})
  .legalFor({{S32, S32}, {S32, S64}, {S32, S16}});
if (ST.has16BitInsts())
  FPToI.legalFor({{S16, S16}});
else
  FPToI.minScalar(1, S32);

FPToI.minScalar(0, S32)
     .scalarize(0);

getActionDefinitionsBuilder(G_INTRINSIC_ROUND)
  .legalFor({S32, S64})
  .scalarize(0);

if (ST.getGeneration() >= AMDGPUSubtarget::SEA_ISLANDS) {
  getActionDefinitionsBuilder({G_INTRINSIC_TRUNC, G_FCEIL, G_FRINT})
    .legalFor({S32, S64})
    .clampScalar(0, S32, S64)
    .scalarize(0);
} else {
  getActionDefinitionsBuilder({G_INTRINSIC_TRUNC, G_FCEIL, G_FRINT})
    .legalFor({S32})
    .customFor({S64})
    .clampScalar(0, S32, S64)
    .scalarize(0);
}

getActionDefinitionsBuilder(G_PTR_ADD)
  .legalForCartesianProduct(AddrSpaces64, {S64})
  .legalForCartesianProduct(AddrSpaces32, {S32})
  .scalarize(0);

getActionDefinitionsBuilder(G_PTR_MASK)
  .scalarize(0)
  .alwaysLegal();

setAction({G_BLOCK_ADDR, CodePtr}, Legal);

auto &CmpBuilder =
  getActionDefinitionsBuilder(G_ICMP)
  .legalForCartesianProduct(
    {S1}, {S32, S64, GlobalPtr, LocalPtr, ConstantPtr, PrivatePtr, FlatPtr})
  .legalFor({{S1, S32}, {S1, S64}});
if (ST.has16BitInsts()) {
  CmpBuilder.legalFor({{S1, S16}});
}

CmpBuilder
  .widenScalarToNextPow2(1)
  .clampScalar(1, S32, S64)
  .scalarize(0)
  .legalIf(all(typeIs(0, S1), isPointer(1)));

getActionDefinitionsBuilder(G_FCMP)
  .legalForCartesianProduct({S1}, ST.has16BitInsts() ? FPTypes16 : FPTypesBase)
  .widenScalarToNextPow2(1)
  .clampScalar(1, S32, S64)
  .scalarize(0);

// FIXME: fexp, flog2, flog10 needs to be custom lowered.
getActionDefinitionsBuilder({G_FPOW, G_FEXP, G_FEXP2,
                             G_FLOG, G_FLOG2, G_FLOG10})
  .legalFor({S32})
  .scalarize(0);

// The 64-bit versions produce 32-bit results, but only on the SALU.
getActionDefinitionsBuilder({G_CTLZ, G_CTLZ_ZERO_UNDEF,
                             G_CTTZ, G_CTTZ_ZERO_UNDEF,
                             G_CTPOP})
  .legalFor({{S32, S32}, {S32, S64}})
  .clampScalar(0, S32, S32)
  .clampScalar(1, S32, S64)
  .scalarize(0)
  .widenScalarToNextPow2(0, 32)
  .widenScalarToNextPow2(1, 32);

// TODO: Expand for > s32
getActionDefinitionsBuilder({G_BSWAP, G_BITREVERSE})
  .legalFor({S32})
  .clampScalar(0, S32, S32)
  .scalarize(0);

if (ST.has16BitInsts()) {
  if (ST.hasVOP3PInsts()) {
    getActionDefinitionsBuilder({G_SMIN, G_SMAX, G_UMIN, G_UMAX})
      .legalFor({S32, S16, V2S16})
      .moreElementsIf(isSmallOddVector(0), oneMoreElement(0))
      .clampMaxNumElements(0, S16, 2)
      .clampScalar(0, S16, S32)
      .widenScalarToNextPow2(0)
      .scalarize(0);
  } else {
    getActionDefinitionsBuilder({G_SMIN, G_SMAX, G_UMIN, G_UMAX})
      .legalFor({S32, S16})
      .widenScalarToNextPow2(0)
      .clampScalar(0, S16, S32)
      .scalarize(0);
  }
} else {
  getActionDefinitionsBuilder({G_SMIN, G_SMAX, G_UMIN, G_UMAX})
    .legalFor({S32})
    .clampScalar(0, S32, S32)
    .widenScalarToNextPow2(0)
    .scalarize(0);
}

auto smallerThan = [](unsigned TypeIdx0, unsigned TypeIdx1) {
  return [=](const LegalityQuery &Query) {
    return Query.Types[TypeIdx0].getSizeInBits() <
           Query.Types[TypeIdx1].getSizeInBits();
  };
};

auto greaterThan = [](unsigned TypeIdx0, unsigned TypeIdx1) {
  return [=](const LegalityQuery &Query) {
    return Query.Types[TypeIdx0].getSizeInBits() >
           Query.Types[TypeIdx1].getSizeInBits();
  };
};

getActionDefinitionsBuilder(G_INTTOPTR)
  // List the common cases
  .legalForCartesianProduct(AddrSpaces64, {S64})
  .legalForCartesianProduct(AddrSpaces32, {S32})
  .scalarize(0)
  // Accept any address space as long as the size matches
  .legalIf(sameSize(0, 1))
  .widenScalarIf(smallerThan(1, 0),
    [](const LegalityQuery &Query) {
      return std::make_pair(1, LLT::scalar(Query.Types[0].getSizeInBits()));
    })
  .narrowScalarIf(greaterThan(1, 0),
    [](const LegalityQuery &Query) {
      return std::make_pair(1, LLT::scalar(Query.Types[0].getSizeInBits()));
    });

getActionDefinitionsBuilder(G_PTRTOINT)
  // List the common cases
  .legalForCartesianProduct(AddrSpaces64, {S64})
  .legalForCartesianProduct(AddrSpaces32, {S32})
  .scalarize(0)
  // Accept any address space as long as the size matches
  .legalIf(sameSize(0, 1))
  .widenScalarIf(smallerThan(0, 1),
    [](const LegalityQuery &Query) {
      return std::make_pair(0, LLT::scalar(Query.Types[1].getSizeInBits()));
    })
  .narrowScalarIf(
    greaterThan(0, 1),
    [](const LegalityQuery &Query) {
      return std::make_pair(0, LLT::scalar(Query.Types[1].getSizeInBits()));
    });

getActionDefinitionsBuilder(G_ADDRSPACE_CAST)
  .scalarize(0)
  .custom();

// TODO: Should load to s16 be legal? Most loads extend to 32-bits, but we
// handle some operations by just promoting the register during
// selection. There are also d16 loads on GFX9+ which preserve the high bits.
auto maxSizeForAddrSpace = [this](unsigned AS) -> unsigned {
  switch (AS) {
  // FIXME: Private element size.
  case AMDGPUAS::PRIVATE_ADDRESS:
    return 32;
  // FIXME: Check subtarget
  case AMDGPUAS::LOCAL_ADDRESS:
    return ST.useDS128() ? 128 : 64;

  // Treat constant and global as identical. SMRD loads are sometimes usable
  // for global loads (ideally constant address space should be eliminated)
  // depending on the context. Legality cannot be context dependent, but
  // RegBankSelect can split the load as necessary depending on the pointer
  // register bank/uniformity and if the memory is invariant or not written in
  // a kernel.
  case AMDGPUAS::CONSTANT_ADDRESS:
  case AMDGPUAS::GLOBAL_ADDRESS:
    return 512;
  default:
    return 128;
  }
};

const auto needToSplitLoad = [=](const LegalityQuery &Query) -> bool {
  const LLT DstTy = Query.Types[0];

  // Split vector extloads.
  unsigned MemSize = Query.MMODescrs[0].SizeInBits;
  if (DstTy.isVector() && DstTy.getSizeInBits() > MemSize)
    return true;

  const LLT PtrTy = Query.Types[1];
  unsigned AS = PtrTy.getAddressSpace();
  if (MemSize > maxSizeForAddrSpace(AS))
    return true;

  // Catch weird sized loads that don't evenly divide into the access sizes
  // TODO: May be able to widen depending on alignment etc.
  unsigned NumRegs = MemSize / 32;
  if (NumRegs == 3 && !ST.hasDwordx3LoadStores())
    return true;

  unsigned Align = Query.MMODescrs[0].AlignInBits;
  if (Align < MemSize) {
    const SITargetLowering *TLI = ST.getTargetLowering();
    return !TLI->allowsMisalignedMemoryAccessesImpl(MemSize, AS, Align / 8);
  }

  return false;
};

unsigned GlobalAlign32 = ST.hasUnalignedBufferAccess() ? 0 : 32;
unsigned GlobalAlign16 = ST.hasUnalignedBufferAccess() ? 0 : 16;
unsigned GlobalAlign8 = ST.hasUnalignedBufferAccess() ? 0 : 8;

// TODO: Refine based on subtargets which support unaligned access or 128-bit
// LDS
// TODO: Unsupported flat for SI.

for (unsigned Op : {G_LOAD, G_STORE}) {
  const bool IsStore = Op == G_STORE;

  auto &Actions = getActionDefinitionsBuilder(Op);
  // Whitelist the common cases.
  // TODO: Pointer loads
  // TODO: Wide constant loads
  // TODO: Only CI+ has 3x loads
  // TODO: Loads to s16 on gfx9
  Actions.legalForTypesWithMemDesc({{S32, GlobalPtr, 32, GlobalAlign32},
                                    {V2S32, GlobalPtr, 64, GlobalAlign32},
                                    {V3S32, GlobalPtr, 96, GlobalAlign32},
                                    {S96, GlobalPtr, 96, GlobalAlign32},
                                    {V4S32, GlobalPtr, 128, GlobalAlign32},
                                    {S128, GlobalPtr, 128, GlobalAlign32},
                                    {S64, GlobalPtr, 64, GlobalAlign32},
                                    {V2S64, GlobalPtr, 128, GlobalAlign32},
                                    {V2S16, GlobalPtr, 32, GlobalAlign32},
                                    {S32, GlobalPtr, 8, GlobalAlign8},
                                    {S32, GlobalPtr, 16, GlobalAlign16},

                                    {S32, LocalPtr, 32, 32},
                                    {S64, LocalPtr, 64, 32},
                                    {V2S32, LocalPtr, 64, 32},
                                    {S32, LocalPtr, 8, 8},
                                    {S32, LocalPtr, 16, 16},
                                    {V2S16, LocalPtr, 32, 32},

                                    {S32, PrivatePtr, 32, 32},
                                    {S32, PrivatePtr, 8, 8},
                                    {S32, PrivatePtr, 16, 16},
                                    {V2S16, PrivatePtr, 32, 32},

                                    {S32, FlatPtr, 32, GlobalAlign32},
                                    {S32, FlatPtr, 16, GlobalAlign16},
                                    {S32, FlatPtr, 8, GlobalAlign8},
                                    {V2S16, FlatPtr, 32, GlobalAlign32},

                                    {S32, ConstantPtr, 32, GlobalAlign32},
                                    {V2S32, ConstantPtr, 64, GlobalAlign32},
                                    {V3S32, ConstantPtr, 96, GlobalAlign32},
                                    {V4S32, ConstantPtr, 128, GlobalAlign32},
                                    {S64, ConstantPtr, 64, GlobalAlign32},
                                    {S128, ConstantPtr, 128, GlobalAlign32},
                                    {V2S32, ConstantPtr, 32, GlobalAlign32}});
  Actions
      .customIf(typeIs(1, Constant32Ptr))
      .narrowScalarIf(
          [=](const LegalityQuery &Query) -> bool {
            return !Query.Types[0].isVector() && needToSplitLoad(Query);
          },
          [=](const LegalityQuery &Query) -> std::pair<unsigned, LLT> {
            const LLT DstTy = Query.Types[0];
            const LLT PtrTy = Query.Types[1];

            const unsigned DstSize = DstTy.getSizeInBits();
            unsigned MemSize = Query.MMODescrs[0].SizeInBits;

            // Split extloads.
            if (DstSize > MemSize)
              return std::make_pair(0, LLT::scalar(MemSize));

            if (DstSize > 32 && (DstSize % 32 != 0)) {
              // FIXME: Need a way to specify non-extload of larger size if
              // suitably aligned.
              return std::make_pair(0, LLT::scalar(32 * (DstSize / 32)));
            }

            unsigned MaxSize = maxSizeForAddrSpace(PtrTy.getAddressSpace());
            if (MemSize > MaxSize)
              return std::make_pair(0, LLT::scalar(MaxSize));

            unsigned Align = Query.MMODescrs[0].AlignInBits;
            return std::make_pair(0, LLT::scalar(Align));
          })
      .fewerElementsIf(
          [=](const LegalityQuery &Query) -> bool {
            return Query.Types[0].isVector() && needToSplitLoad(Query);
          },
          [=](const LegalityQuery &Query) -> std::pair<unsigned, LLT> {
            const LLT DstTy = Query.Types[0];
            const LLT PtrTy = Query.Types[1];

            LLT EltTy = DstTy.getElementType();
            unsigned MaxSize = maxSizeForAddrSpace(PtrTy.getAddressSpace());

            // Split if it's too large for the address space.
            if (Query.MMODescrs[0].SizeInBits > MaxSize) {
              unsigned NumElts = DstTy.getNumElements();
              unsigned NumPieces = Query.MMODescrs[0].SizeInBits / MaxSize;

              // FIXME: Refine when odd breakdowns handled
              // The scalars will need to be re-legalized.
              if (NumPieces == 1 || NumPieces >= NumElts ||
                  NumElts % NumPieces != 0)
                return std::make_pair(0, EltTy);

              return std::make_pair(0,
                                    LLT::vector(NumElts / NumPieces, EltTy));
            }

            // Need to split because of alignment.
            unsigned Align = Query.MMODescrs[0].AlignInBits;
            unsigned EltSize = EltTy.getSizeInBits();
            if (EltSize > Align &&
                (EltSize / Align < DstTy.getNumElements())) {
              return std::make_pair(0, LLT::vector(EltSize / Align, EltTy));
            }

            // May need relegalization for the scalars.
            return std::make_pair(0, EltTy);
          })
      .minScalar(0, S32);

  if (IsStore)
    Actions.narrowScalarIf(isWideScalarTruncStore(0), changeTo(0, S32));

  // TODO: Need a bitcast lower option?
  Actions
      .legalIf([=](const LegalityQuery &Query) {
        const LLT Ty0 = Query.Types[0];
        unsigned Size = Ty0.getSizeInBits();
        unsigned MemSize = Query.MMODescrs[0].SizeInBits;
        unsigned Align = Query.MMODescrs[0].AlignInBits;

        // No extending vector loads.
        if (Size > MemSize && Ty0.isVector())
          return false;

        // FIXME: Widening store from alignment not valid.
        if (MemSize < Size)
          MemSize = std::max(MemSize, Align);

        switch (MemSize) {
        case 8:
        case 16:
          return Size == 32;
        case 32:
        case 64:
        case 128:
          return true;
        case 96:
          return ST.hasDwordx3LoadStores();
        case 256:
        case 512:
          return true;
        default:
          return false;
        }
      })
      .widenScalarToNextPow2(0)
      // TODO: v3s32->v4s32 with alignment
      .moreElementsIf(vectorSmallerThan(0, 32), moreEltsToNext32Bit(0));
}

auto &ExtLoads = getActionDefinitionsBuilder({G_SEXTLOAD, G_ZEXTLOAD})
                     .legalForTypesWithMemDesc({{S32, GlobalPtr, 8, 8},
                                                {S32, GlobalPtr, 16, 2 * 8},
                                                {S32, LocalPtr, 8, 8},
                                                {S32, LocalPtr, 16, 16},
                                                {S32, PrivatePtr, 8, 8},
                                                {S32, PrivatePtr, 16, 16},
                                                {S32, ConstantPtr, 8, 8},
                                                {S32, ConstantPtr, 16, 2 * 8}});
if (ST.hasFlatAddressSpace()) {
  ExtLoads.legalForTypesWithMemDesc(
      {{S32, FlatPtr, 8, 8}, {S32, FlatPtr, 16, 16}});
}

ExtLoads.clampScalar(0, S32, S32)
        .widenScalarToNextPow2(0)
        .unsupportedIfMemSizeNotPow2()
        .lower();

auto &Atomics = getActionDefinitionsBuilder(
  {G_ATOMICRMW_XCHG, G_ATOMICRMW_ADD, G_ATOMICRMW_SUB,
   G_ATOMICRMW_AND, G_ATOMICRMW_OR, G_ATOMICRMW_XOR,
   G_ATOMICRMW_MAX, G_ATOMICRMW_MIN, G_ATOMICRMW_UMAX,
   G_ATOMICRMW_UMIN})
  .legalFor({{S32, GlobalPtr}, {S32, LocalPtr},
             {S64, GlobalPtr}, {S64, LocalPtr}});
if (ST.hasFlatAddressSpace()) {
  Atomics.legalFor({{S32, FlatPtr}, {S64, FlatPtr}});
}

getActionDefinitionsBuilder(G_ATOMICRMW_FADD)
  .legalFor({{S32, LocalPtr}});

// BUFFER/FLAT_ATOMIC_CMP_SWAP on GCN GPUs needs input marshalling, and output
// demarshalling
getActionDefinitionsBuilder(G_ATOMIC_CMPXCHG)
  .customFor({{S32, GlobalPtr}, {S64, GlobalPtr},
              {S32, FlatPtr}, {S64, FlatPtr}})
  .legalFor({{S32, LocalPtr}, {S64, LocalPtr},
             {S32, RegionPtr}, {S64, RegionPtr}});

getActionDefinitionsBuilder(G_ATOMIC_CMPXCHG_WITH_SUCCESS)
  .lower();

// TODO: Pointer types, any 32-bit or 64-bit vector
getActionDefinitionsBuilder(G_SELECT)
  .legalForCartesianProduct({S32, S64, S16, V2S32, V2S16, V4S16,
        GlobalPtr, LocalPtr, FlatPtr, PrivatePtr,
        LLT::vector(2, LocalPtr), LLT::vector(2, PrivatePtr)}, {S1})
  .clampScalar(0, S16, S64)
  .moreElementsIf(isSmallOddVector(0), oneMoreElement(0))
  .fewerElementsIf(numElementsNotEven(0), scalarize(0))
  .scalarize(1)
  .clampMaxNumElements(0, S32, 2)
  .clampMaxNumElements(0, LocalPtr, 2)
  .clampMaxNumElements(0, PrivatePtr, 2)
  .scalarize(0)
  .widenScalarToNextPow2(0)
  .legalIf(all(isPointer(0), typeIs(1, S1)));

// TODO: Only the low 4/5/6 bits of the shift amount are observed, so we can
// be more flexible with the shift amount type.
auto &Shifts = getActionDefinitionsBuilder({G_SHL, G_LSHR, G_ASHR})
  .legalFor({{S32, S32}, {S64, S32}});
if (ST.has16BitInsts()) {
  if (ST.hasVOP3PInsts()) {
    Shifts.legalFor({{S16, S32}, {S16, S16}, {V2S16, V2S16}})
          .clampMaxNumElements(0, S16, 2);
  } else
    Shifts.legalFor({{S16, S32}, {S16, S16}});

  Shifts.clampScalar(1, S16, S32);
  Shifts.clampScalar(0, S16, S64);
  Shifts.widenScalarToNextPow2(0, 16);
} else {
  // Make sure we legalize the shift amount type first, as the general
  // expansion for the shifted type will produce much worse code if it hasn't
  // been truncated already.
  Shifts.clampScalar(1, S32, S32);
  Shifts.clampScalar(0, S32, S64);
  Shifts.widenScalarToNextPow2(0, 32);
}
Shifts.scalarize(0);

for (unsigned Op : {G_EXTRACT_VECTOR_ELT, G_INSERT_VECTOR_ELT}) {
  unsigned VecTypeIdx = Op == G_EXTRACT_VECTOR_ELT ? 1 : 0;
  unsigned EltTypeIdx = Op == G_EXTRACT_VECTOR_ELT ? 0 : 1;
  unsigned IdxTypeIdx = 2;

  getActionDefinitionsBuilder(Op)
    .customIf([=](const LegalityQuery &Query) {
        const LLT EltTy = Query.Types[EltTypeIdx];
        const LLT VecTy = Query.Types[VecTypeIdx];
        const LLT IdxTy = Query.Types[IdxTypeIdx];
        return (EltTy.getSizeInBits() == 16 ||
                EltTy.getSizeInBits() % 32 == 0) &&
               VecTy.getSizeInBits() % 32 == 0 &&
               VecTy.getSizeInBits() <= 1024 &&
               IdxTy.getSizeInBits() == 32;
      })
    .clampScalar(EltTypeIdx, S32, S64)
    .clampScalar(VecTypeIdx, S32, S64)
    .clampScalar(IdxTypeIdx, S32, S32);
}

getActionDefinitionsBuilder(G_EXTRACT_VECTOR_ELT)
  .unsupportedIf([=](const LegalityQuery &Query) {
      const LLT &EltTy = Query.Types[1].getElementType();
      return Query.Types[0] != EltTy;
    });

for (unsigned Op : {G_EXTRACT, G_INSERT}) {
  unsigned BigTyIdx = Op == G_EXTRACT ? 1 : 0;
  unsigned LitTyIdx = Op == G_EXTRACT ? 0 : 1;

  // FIXME: Doesn't handle extract of illegal sizes.
  getActionDefinitionsBuilder(Op)
    .lowerIf(all(typeIs(LitTyIdx, S16), sizeIs(BigTyIdx, 32)))
    // FIXME: Multiples of 16 should not be legal.
    .legalIf([=](const LegalityQuery &Query) {
        const LLT BigTy = Query.Types[BigTyIdx];
        const LLT LitTy = Query.Types[LitTyIdx];
        return (BigTy.getSizeInBits() % 32 == 0) &&
               (LitTy.getSizeInBits() % 16 == 0);
      })
    .widenScalarIf(
      [=](const LegalityQuery &Query) {
        const LLT BigTy = Query.Types[BigTyIdx];
        return (BigTy.getScalarSizeInBits() < 16);
      },
      LegalizeMutations::widenScalarOrEltToNextPow2(BigTyIdx, 16))
    .widenScalarIf(
      [=](const LegalityQuery &Query) {
        const LLT LitTy = Query.Types[LitTyIdx];
        return (LitTy.getScalarSizeInBits() < 16);
      },
      LegalizeMutations::widenScalarOrEltToNextPow2(LitTyIdx, 16))
    .moreElementsIf(isSmallOddVector(BigTyIdx), oneMoreElement(BigTyIdx))
    .widenScalarToNextPow2(BigTyIdx, 32);

}

auto &BuildVector = getActionDefinitionsBuilder(G_BUILD_VECTOR)
  .legalForCartesianProduct(AllS32Vectors, {S32})
  .legalForCartesianProduct(AllS64Vectors, {S64})
  .clampNumElements(0, V16S32, V32S32)
  .clampNumElements(0, V2S64, V16S64)
  .fewerElementsIf(isWideVec16(0), changeTo(0, V2S16));

if (ST.hasScalarPackInsts())
  BuildVector.legalFor({V2S16, S32});

BuildVector
  .minScalarSameAs(1, 0)
  .legalIf(isRegisterType(0))
  .minScalarOrElt(0, S32);

if (ST.hasScalarPackInsts()) {
  getActionDefinitionsBuilder(G_BUILD_VECTOR_TRUNC)
    .legalFor({V2S16, S32})
    .lower();
} else {
  getActionDefinitionsBuilder(G_BUILD_VECTOR_TRUNC)
    .lower();
}

getActionDefinitionsBuilder(G_CONCAT_VECTORS)
  .legalIf(isRegisterType(0));

// TODO: Don't fully scalarize v2s16 pieces
getActionDefinitionsBuilder(G_SHUFFLE_VECTOR).lower();

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

  auto &Builder = getActionDefinitionsBuilder(Op)
    .widenScalarToNextPow2(LitTyIdx, /*Min*/ 16)
    // 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, S16, S256)
    .widenScalarToNextPow2(LitTyIdx, /*Min*/ 32)
    .moreElementsIf(isSmallOddVector(BigTyIdx), oneMoreElement(BigTyIdx))
    .fewerElementsIf(all(typeIs(0, S16), vectorWiderThan(1, 32),
                         elementTypeIs(1, S16)),
                     changeTo(1, V2S16))
    // 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))
    .clampScalar(BigTyIdx, S32, S1024)
    .lowerFor({{S16, V2S16}});

  if (Op == G_MERGE_VALUES) {
    Builder.widenScalarIf(
      // TODO: Use 16-bit shifts if legal for 8-bit values?
      [=](const LegalityQuery &Query) {
        const LLT Ty = Query.Types[LitTyIdx];
        return Ty.getSizeInBits() < 32;
      },
      changeTo(LitTyIdx, S32));
  }

  Builder.widenScalarIf(
    [=](const LegalityQuery &Query) {
      const LLT Ty = Query.Types[BigTyIdx];
      return !isPowerOf2_32(Ty.getSizeInBits()) &&
        Ty.getSizeInBits() % 16 != 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));
    })
    .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() % 16 == 0 &&
               LitTy.getSizeInBits() % 16 == 0 &&
               BigTy.getSizeInBits() <= 1024;
      })
    // Any vectors left are the wrong size. Scalarize them.
    .scalarize(0)
    .scalarize(1);
}

getActionDefinitionsBuilder(G_SEXT_INREG).lower();

computeTables();
verify(*ST.getInstrInfo());
1088}

1090bool AMDGPULegalizerInfo::legalizeCustom(MachineInstr &MI,
                                       MachineRegisterInfo &MRI,
                                       MachineIRBuilder &B,
                                       GISelChangeObserver &Observer) const {
switch (MI.getOpcode()) {
case TargetOpcode::G_ADDRSPACE_CAST:
  return legalizeAddrSpaceCast(MI, MRI, B);
case TargetOpcode::G_FRINT:
  return legalizeFrint(MI, MRI, B);
case TargetOpcode::G_FCEIL:
  return legalizeFceil(MI, MRI, B);
case TargetOpcode::G_INTRINSIC_TRUNC:
  return legalizeIntrinsicTrunc(MI, MRI, B);
case TargetOpcode::G_SITOFP:
  return legalizeITOFP(MI, MRI, B, true);
case TargetOpcode::G_UITOFP:
  return legalizeITOFP(MI, MRI, B, false);
case TargetOpcode::G_FMINNUM:
case TargetOpcode::G_FMAXNUM:
case TargetOpcode::G_FMINNUM_IEEE:
case TargetOpcode::G_FMAXNUM_IEEE:
  return legalizeMinNumMaxNum(MI, MRI, B);
case TargetOpcode::G_EXTRACT_VECTOR_ELT:
  return legalizeExtractVectorElt(MI, MRI, B);
case TargetOpcode::G_INSERT_VECTOR_ELT:
  return legalizeInsertVectorElt(MI, MRI, B);
case TargetOpcode::G_FSIN:
case TargetOpcode::G_FCOS:
  return legalizeSinCos(MI, MRI, B);
case TargetOpcode::G_GLOBAL_VALUE:
  return legalizeGlobalValue(MI, MRI, B);
case TargetOpcode::G_LOAD:
  return legalizeLoad(MI, MRI, B, Observer);
case TargetOpcode::G_FMAD:
  return legalizeFMad(MI, MRI, B);
case TargetOpcode::G_FDIV:
  return legalizeFDIV(MI, MRI, B);
case TargetOpcode::G_ATOMIC_CMPXCHG:
  return legalizeAtomicCmpXChg(MI, MRI, B);
default:
  return false;
}

llvm_unreachable("expected switch to return")::llvm::llvm_unreachable_internal("expected switch to return"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1133);
1134}

1136Register AMDGPULegalizerInfo::getSegmentAperture(
unsigned AS,
MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
MachineFunction &MF = B.getMF();
const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
const LLT S32 = LLT::scalar(32);

assert(AS == AMDGPUAS::LOCAL_ADDRESS || AS == AMDGPUAS::PRIVATE_ADDRESS)((AS == AMDGPUAS::LOCAL_ADDRESS || AS == AMDGPUAS::PRIVATE_ADDRESS
) ? static_cast<void> (0) : __assert_fail ("AS == AMDGPUAS::LOCAL_ADDRESS || AS == AMDGPUAS::PRIVATE_ADDRESS"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1144, __PRETTY_FUNCTION__));

if (ST.hasApertureRegs()) {
  // FIXME: Use inline constants (src_{shared, private}_base) instead of
  // getreg.
  unsigned Offset = AS == AMDGPUAS::LOCAL_ADDRESS ?
      AMDGPU::Hwreg::OFFSET_SRC_SHARED_BASE :
      AMDGPU::Hwreg::OFFSET_SRC_PRIVATE_BASE;
  unsigned WidthM1 = AS == AMDGPUAS::LOCAL_ADDRESS ?
      AMDGPU::Hwreg::WIDTH_M1_SRC_SHARED_BASE :
      AMDGPU::Hwreg::WIDTH_M1_SRC_PRIVATE_BASE;
  unsigned Encoding =
      AMDGPU::Hwreg::ID_MEM_BASES << AMDGPU::Hwreg::ID_SHIFT_ |
      Offset << AMDGPU::Hwreg::OFFSET_SHIFT_ |
      WidthM1 << AMDGPU::Hwreg::WIDTH_M1_SHIFT_;

  Register ApertureReg = MRI.createGenericVirtualRegister(S32);
  Register GetReg = MRI.createVirtualRegister(&AMDGPU::SReg_32RegClass);

  B.buildInstr(AMDGPU::S_GETREG_B32)
    .addDef(GetReg)
    .addImm(Encoding);
  MRI.setType(GetReg, S32);

  auto ShiftAmt = B.buildConstant(S32, WidthM1 + 1);
  B.buildInstr(TargetOpcode::G_SHL)
    .addDef(ApertureReg)
    .addUse(GetReg)
    .addUse(ShiftAmt.getReg(0));

  return ApertureReg;
}

Register QueuePtr = MRI.createGenericVirtualRegister(
  LLT::pointer(AMDGPUAS::CONSTANT_ADDRESS, 64));

const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
if (!loadInputValue(QueuePtr, B, &MFI->getArgInfo().QueuePtr))
  return Register();

// Offset into amd_queue_t for group_segment_aperture_base_hi /
// private_segment_aperture_base_hi.
uint32_t StructOffset = (AS == AMDGPUAS::LOCAL_ADDRESS) ? 0x40 : 0x44;

// FIXME: Don't use undef
Value *V = UndefValue::get(PointerType::get(
                             Type::getInt8Ty(MF.getFunction().getContext()),
                             AMDGPUAS::CONSTANT_ADDRESS));

MachinePointerInfo PtrInfo(V, StructOffset);
MachineMemOperand *MMO = MF.getMachineMemOperand(
  PtrInfo,
  MachineMemOperand::MOLoad |
  MachineMemOperand::MODereferenceable |
  MachineMemOperand::MOInvariant,
  4,
  MinAlign(64, StructOffset));

Register LoadResult = MRI.createGenericVirtualRegister(S32);
Register LoadAddr;

B.materializePtrAdd(LoadAddr, QueuePtr, LLT::scalar(64), StructOffset);
B.buildLoad(LoadResult, LoadAddr, *MMO);
return LoadResult;
1208}

1210bool AMDGPULegalizerInfo::legalizeAddrSpaceCast(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
MachineFunction &MF = B.getMF();

B.setInstr(MI);

const LLT S32 = LLT::scalar(32);
Register Dst = MI.getOperand(0).getReg();
Register Src = MI.getOperand(1).getReg();

LLT DstTy = MRI.getType(Dst);
LLT SrcTy = MRI.getType(Src);
unsigned DestAS = DstTy.getAddressSpace();
unsigned SrcAS = SrcTy.getAddressSpace();

// TODO: Avoid reloading from the queue ptr for each cast, or at least each
// vector element.
assert(!DstTy.isVector())((!DstTy.isVector()) ? static_cast<void> (0) : __assert_fail
 ("!DstTy.isVector()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1228, __PRETTY_FUNCTION__));

const AMDGPUTargetMachine &TM
  = static_cast<const AMDGPUTargetMachine &>(MF.getTarget());

const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
if (ST.getTargetLowering()->isNoopAddrSpaceCast(SrcAS, DestAS)) {
  MI.setDesc(B.getTII().get(TargetOpcode::G_BITCAST));
  return true;
}

if (DestAS == AMDGPUAS::CONSTANT_ADDRESS_32BIT) {
  // Truncate.
  B.buildExtract(Dst, Src, 0);
  MI.eraseFromParent();
  return true;
}

if (SrcAS == AMDGPUAS::CONSTANT_ADDRESS_32BIT) {
  const SIMachineFunctionInfo *Info = MF.getInfo<SIMachineFunctionInfo>();
  uint32_t AddrHiVal = Info->get32BitAddressHighBits();

  // FIXME: This is a bit ugly due to creating a merge of 2 pointers to
  // another. Merge operands are required to be the same type, but creating an
  // extra ptrtoint would be kind of pointless.
  auto HighAddr = B.buildConstant(
    LLT::pointer(AMDGPUAS::CONSTANT_ADDRESS_32BIT, 32), AddrHiVal);
  B.buildMerge(Dst, {Src, HighAddr.getReg(0)});
  MI.eraseFromParent();
  return true;
}

if (SrcAS == AMDGPUAS::FLAT_ADDRESS) {
  assert(DestAS == AMDGPUAS::LOCAL_ADDRESS ||((DestAS == AMDGPUAS::LOCAL_ADDRESS || DestAS == AMDGPUAS::PRIVATE_ADDRESS
) ? static_cast<void> (0) : __assert_fail ("DestAS == AMDGPUAS::LOCAL_ADDRESS || DestAS == AMDGPUAS::PRIVATE_ADDRESS"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1262, __PRETTY_FUNCTION__))
         DestAS == AMDGPUAS::PRIVATE_ADDRESS)((DestAS == AMDGPUAS::LOCAL_ADDRESS || DestAS == AMDGPUAS::PRIVATE_ADDRESS
) ? static_cast<void> (0) : __assert_fail ("DestAS == AMDGPUAS::LOCAL_ADDRESS || DestAS == AMDGPUAS::PRIVATE_ADDRESS"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1262, __PRETTY_FUNCTION__));
  unsigned NullVal = TM.getNullPointerValue(DestAS);

  auto SegmentNull = B.buildConstant(DstTy, NullVal);
  auto FlatNull = B.buildConstant(SrcTy, 0);

  Register PtrLo32 = MRI.createGenericVirtualRegister(DstTy);

  // Extract low 32-bits of the pointer.
  B.buildExtract(PtrLo32, Src, 0);

  Register CmpRes = MRI.createGenericVirtualRegister(LLT::scalar(1));
  B.buildICmp(CmpInst::ICMP_NE, CmpRes, Src, FlatNull.getReg(0));
  B.buildSelect(Dst, CmpRes, PtrLo32, SegmentNull.getReg(0));

  MI.eraseFromParent();
  return true;
}

if (SrcAS != AMDGPUAS::LOCAL_ADDRESS && SrcAS != AMDGPUAS::PRIVATE_ADDRESS)
  return false;

if (!ST.hasFlatAddressSpace())
  return false;

auto SegmentNull =
    B.buildConstant(SrcTy, TM.getNullPointerValue(SrcAS));
auto FlatNull =
    B.buildConstant(DstTy, TM.getNullPointerValue(DestAS));

Register ApertureReg = getSegmentAperture(SrcAS, MRI, B);
if (!ApertureReg.isValid())
  return false;

Register CmpRes = MRI.createGenericVirtualRegister(LLT::scalar(1));
B.buildICmp(CmpInst::ICMP_NE, CmpRes, Src, SegmentNull.getReg(0));

Register BuildPtr = MRI.createGenericVirtualRegister(DstTy);

// Coerce the type of the low half of the result so we can use merge_values.
Register SrcAsInt = MRI.createGenericVirtualRegister(S32);
B.buildInstr(TargetOpcode::G_PTRTOINT)
  .addDef(SrcAsInt)
  .addUse(Src);

// TODO: Should we allow mismatched types but matching sizes in merges to
// avoid the ptrtoint?
B.buildMerge(BuildPtr, {SrcAsInt, ApertureReg});
B.buildSelect(Dst, CmpRes, BuildPtr, FlatNull.getReg(0));

MI.eraseFromParent();
return true;
1314}

1316bool AMDGPULegalizerInfo::legalizeFrint(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
B.setInstr(MI);

Register Src = MI.getOperand(1).getReg();
LLT Ty = MRI.getType(Src);
assert(Ty.isScalar() && Ty.getSizeInBits() == 64)((Ty.isScalar() && Ty.getSizeInBits() == 64) ? static_cast
<void> (0) : __assert_fail ("Ty.isScalar() && Ty.getSizeInBits() == 64"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1323, __PRETTY_FUNCTION__));

APFloat C1Val(APFloat::IEEEdouble(), "0x1.0p+52");
APFloat C2Val(APFloat::IEEEdouble(), "0x1.fffffffffffffp+51");

auto C1 = B.buildFConstant(Ty, C1Val);
auto CopySign = B.buildFCopysign(Ty, C1, Src);

// TODO: Should this propagate fast-math-flags?
auto Tmp1 = B.buildFAdd(Ty, Src, CopySign);
auto Tmp2 = B.buildFSub(Ty, Tmp1, CopySign);

auto C2 = B.buildFConstant(Ty, C2Val);
auto Fabs = B.buildFAbs(Ty, Src);

auto Cond = B.buildFCmp(CmpInst::FCMP_OGT, LLT::scalar(1), Fabs, C2);
B.buildSelect(MI.getOperand(0).getReg(), Cond, Src, Tmp2);
return true;
1341}

1343bool AMDGPULegalizerInfo::legalizeFceil(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
B.setInstr(MI);

const LLT S1 = LLT::scalar(1);
const LLT S64 = LLT::scalar(64);

Register Src = MI.getOperand(1).getReg();
assert(MRI.getType(Src) == S64)((MRI.getType(Src) == S64) ? static_cast<void> (0) : __assert_fail
 ("MRI.getType(Src) == S64", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1352, __PRETTY_FUNCTION__));

// result = trunc(src)
// if (src > 0.0 && src != result)
//   result += 1.0

auto Trunc = B.buildInstr(TargetOpcode::G_INTRINSIC_TRUNC, {S64}, {Src});

const auto Zero = B.buildFConstant(S64, 0.0);
const auto One = B.buildFConstant(S64, 1.0);
auto Lt0 = B.buildFCmp(CmpInst::FCMP_OGT, S1, Src, Zero);
auto NeTrunc = B.buildFCmp(CmpInst::FCMP_ONE, S1, Src, Trunc);
auto And = B.buildAnd(S1, Lt0, NeTrunc);
auto Add = B.buildSelect(S64, And, One, Zero);

// TODO: Should this propagate fast-math-flags?
B.buildFAdd(MI.getOperand(0).getReg(), Trunc, Add);
return true;
1370}

1372static MachineInstrBuilder extractF64Exponent(unsigned Hi,
                                            MachineIRBuilder &B) {
const unsigned FractBits = 52;
const unsigned ExpBits = 11;
LLT S32 = LLT::scalar(32);

auto Const0 = B.buildConstant(S32, FractBits - 32);
auto Const1 = B.buildConstant(S32, ExpBits);

auto ExpPart = B.buildIntrinsic(Intrinsic::amdgcn_ubfe, {S32}, false)
  .addUse(Const0.getReg(0))
  .addUse(Const1.getReg(0));

return B.buildSub(S32, ExpPart, B.buildConstant(S32, 1023));
1386}

1388bool AMDGPULegalizerInfo::legalizeIntrinsicTrunc(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
B.setInstr(MI);

const LLT S1 = LLT::scalar(1);
const LLT S32 = LLT::scalar(32);
const LLT S64 = LLT::scalar(64);

Register Src = MI.getOperand(1).getReg();
assert(MRI.getType(Src) == S64)((MRI.getType(Src) == S64) ? static_cast<void> (0) : __assert_fail
 ("MRI.getType(Src) == S64", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1398, __PRETTY_FUNCTION__));

// TODO: Should this use extract since the low half is unused?
auto Unmerge = B.buildUnmerge({S32, S32}, Src);
Register Hi = Unmerge.getReg(1);

// Extract the upper half, since this is where we will find the sign and
// exponent.
auto Exp = extractF64Exponent(Hi, B);

const unsigned FractBits = 52;

// Extract the sign bit.
const auto SignBitMask = B.buildConstant(S32, UINT32_C(1)1U << 31);
auto SignBit = B.buildAnd(S32, Hi, SignBitMask);

const auto FractMask = B.buildConstant(S64, (UINT64_C(1)1UL << FractBits) - 1);

const auto Zero32 = B.buildConstant(S32, 0);

// Extend back to 64-bits.
auto SignBit64 = B.buildMerge(S64, {Zero32.getReg(0), SignBit.getReg(0)});

auto Shr = B.buildAShr(S64, FractMask, Exp);
auto Not = B.buildNot(S64, Shr);
auto Tmp0 = B.buildAnd(S64, Src, Not);
auto FiftyOne = B.buildConstant(S32, FractBits - 1);

auto ExpLt0 = B.buildICmp(CmpInst::ICMP_SLT, S1, Exp, Zero32);
auto ExpGt51 = B.buildICmp(CmpInst::ICMP_SGT, S1, Exp, FiftyOne);

auto Tmp1 = B.buildSelect(S64, ExpLt0, SignBit64, Tmp0);
B.buildSelect(MI.getOperand(0).getReg(), ExpGt51, Src, Tmp1);
return true;
1432}

1434bool AMDGPULegalizerInfo::legalizeITOFP(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B, bool Signed) const {
B.setInstr(MI);

Register Dst = MI.getOperand(0).getReg();
Register Src = MI.getOperand(1).getReg();

const LLT S64 = LLT::scalar(64);
const LLT S32 = LLT::scalar(32);

assert(MRI.getType(Src) == S64 && MRI.getType(Dst) == S64)((MRI.getType(Src) == S64 && MRI.getType(Dst) == S64)
 ? static_cast<void> (0) : __assert_fail ("MRI.getType(Src) == S64 && MRI.getType(Dst) == S64"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1445, __PRETTY_FUNCTION__));

auto Unmerge = B.buildUnmerge({S32, S32}, Src);

auto CvtHi = Signed ?
  B.buildSITOFP(S64, Unmerge.getReg(1)) :
  B.buildUITOFP(S64, Unmerge.getReg(1));

auto CvtLo = B.buildUITOFP(S64, Unmerge.getReg(0));

auto ThirtyTwo = B.buildConstant(S32, 32);
auto LdExp = B.buildIntrinsic(Intrinsic::amdgcn_ldexp, {S64}, false)
  .addUse(CvtHi.getReg(0))
  .addUse(ThirtyTwo.getReg(0));

// TODO: Should this propagate fast-math-flags?
B.buildFAdd(Dst, LdExp, CvtLo);
MI.eraseFromParent();
return true;
1464}

1466bool AMDGPULegalizerInfo::legalizeMinNumMaxNum(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
MachineFunction &MF = B.getMF();
const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();

const bool IsIEEEOp = MI.getOpcode() == AMDGPU::G_FMINNUM_IEEE ||
                      MI.getOpcode() == AMDGPU::G_FMAXNUM_IEEE;

// With ieee_mode disabled, the instructions have the correct behavior
// already for G_FMINNUM/G_FMAXNUM
if (!MFI->getMode().IEEE)
  return !IsIEEEOp;

if (IsIEEEOp)
  return true;

MachineIRBuilder HelperBuilder(MI);
GISelObserverWrapper DummyObserver;
LegalizerHelper Helper(MF, DummyObserver, HelperBuilder);
HelperBuilder.setInstr(MI);
return Helper.lowerFMinNumMaxNum(MI) == LegalizerHelper::Legalized;
1488}

1490bool AMDGPULegalizerInfo::legalizeExtractVectorElt(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
// TODO: Should move some of this into LegalizerHelper.

// TODO: Promote dynamic indexing of s16 to s32
// TODO: Dynamic s64 indexing is only legal for SGPR.
Optional<int64_t> IdxVal = getConstantVRegVal(MI.getOperand(2).getReg(), MRI);
if (!IdxVal) // Dynamic case will be selected to register indexing.
  return true;

Register Dst = MI.getOperand(0).getReg();
Register Vec = MI.getOperand(1).getReg();

LLT VecTy = MRI.getType(Vec);
LLT EltTy = VecTy.getElementType();
assert(EltTy == MRI.getType(Dst))((EltTy == MRI.getType(Dst)) ? static_cast<void> (0) : __assert_fail
 ("EltTy == MRI.getType(Dst)", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1506, __PRETTY_FUNCTION__));

B.setInstr(MI);

if (IdxVal.getValue() < VecTy.getNumElements())
  B.buildExtract(Dst, Vec, IdxVal.getValue() * EltTy.getSizeInBits());
else
  B.buildUndef(Dst);

MI.eraseFromParent();
return true;
1517}

1519bool AMDGPULegalizerInfo::legalizeInsertVectorElt(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
// TODO: Should move some of this into LegalizerHelper.

// TODO: Promote dynamic indexing of s16 to s32
// TODO: Dynamic s64 indexing is only legal for SGPR.
Optional<int64_t> IdxVal = getConstantVRegVal(MI.getOperand(3).getReg(), MRI);
if (!IdxVal) // Dynamic case will be selected to register indexing.
  return true;

Register Dst = MI.getOperand(0).getReg();
Register Vec = MI.getOperand(1).getReg();
Register Ins = MI.getOperand(2).getReg();

LLT VecTy = MRI.getType(Vec);
LLT EltTy = VecTy.getElementType();
assert(EltTy == MRI.getType(Ins))((EltTy == MRI.getType(Ins)) ? static_cast<void> (0) : __assert_fail
 ("EltTy == MRI.getType(Ins)", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1536, __PRETTY_FUNCTION__));

B.setInstr(MI);

if (IdxVal.getValue() < VecTy.getNumElements())
  B.buildInsert(Dst, Vec, Ins, IdxVal.getValue() * EltTy.getSizeInBits());
else
  B.buildUndef(Dst);

MI.eraseFromParent();
return true;
1547}

1549bool AMDGPULegalizerInfo::legalizeSinCos(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
B.setInstr(MI);

Register DstReg = MI.getOperand(0).getReg();
Register SrcReg = MI.getOperand(1).getReg();
LLT Ty = MRI.getType(DstReg);
unsigned Flags = MI.getFlags();

Register TrigVal;
auto OneOver2Pi = B.buildFConstant(Ty, 0.5 / M_PI3.14159265358979323846);
if (ST.hasTrigReducedRange()) {
  auto MulVal = B.buildFMul(Ty, SrcReg, OneOver2Pi, Flags);
  TrigVal = B.buildIntrinsic(Intrinsic::amdgcn_fract, {Ty}, false)
    .addUse(MulVal.getReg(0))
    .setMIFlags(Flags).getReg(0);
} else
  TrigVal = B.buildFMul(Ty, SrcReg, OneOver2Pi, Flags).getReg(0);

Intrinsic::ID TrigIntrin = MI.getOpcode() == AMDGPU::G_FSIN ?
  Intrinsic::amdgcn_sin : Intrinsic::amdgcn_cos;
B.buildIntrinsic(TrigIntrin, makeArrayRef<Register>(DstReg), false)
  .addUse(TrigVal)
  .setMIFlags(Flags);
MI.eraseFromParent();
return true;
1576}

1578bool AMDGPULegalizerInfo::buildPCRelGlobalAddress(
Register DstReg, LLT PtrTy,
MachineIRBuilder &B, const GlobalValue *GV,
unsigned Offset, unsigned GAFlags) const {
// In order to support pc-relative addressing, SI_PC_ADD_REL_OFFSET is lowered
// to the following code sequence:
//
// For constant address space:
//   s_getpc_b64 s[0:1]
//   s_add_u32 s0, s0, $symbol
//   s_addc_u32 s1, s1, 0
//
//   s_getpc_b64 returns the address of the s_add_u32 instruction and then
//   a fixup or relocation is emitted to replace $symbol with a literal
//   constant, which is a pc-relative offset from the encoding of the $symbol
//   operand to the global variable.
//
// For global address space:
//   s_getpc_b64 s[0:1]
//   s_add_u32 s0, s0, $symbol@{gotpc}rel32@lo
//   s_addc_u32 s1, s1, $symbol@{gotpc}rel32@hi
//
//   s_getpc_b64 returns the address of the s_add_u32 instruction and then
//   fixups or relocations are emitted to replace $symbol@*@lo and
//   $symbol@*@hi with lower 32 bits and higher 32 bits of a literal constant,
//   which is a 64-bit pc-relative offset from the encoding of the $symbol
//   operand to the global variable.
//
// What we want here is an offset from the value returned by s_getpc
// (which is the address of the s_add_u32 instruction) to the global
// variable, but since the encoding of $symbol starts 4 bytes after the start
// of the s_add_u32 instruction, we end up with an offset that is 4 bytes too
// small. This requires us to add 4 to the global variable offset in order to
// compute the correct address.

LLT ConstPtrTy = LLT::pointer(AMDGPUAS::CONSTANT_ADDRESS, 64);

Register PCReg = PtrTy.getSizeInBits() != 32 ? DstReg :
  B.getMRI()->createGenericVirtualRegister(ConstPtrTy);

MachineInstrBuilder MIB = B.buildInstr(AMDGPU::SI_PC_ADD_REL_OFFSET)
  .addDef(PCReg);

MIB.addGlobalAddress(GV, Offset + 4, GAFlags);
if (GAFlags == SIInstrInfo::MO_NONE)
  MIB.addImm(0);
else
  MIB.addGlobalAddress(GV, Offset + 4, GAFlags + 1);

B.getMRI()->setRegClass(PCReg, &AMDGPU::SReg_64RegClass);

if (PtrTy.getSizeInBits() == 32)
  B.buildExtract(DstReg, PCReg, 0);
return true;
}

1634bool AMDGPULegalizerInfo::legalizeGlobalValue(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
Register DstReg = MI.getOperand(0).getReg();
LLT Ty = MRI.getType(DstReg);
unsigned AS = Ty.getAddressSpace();

const GlobalValue *GV = MI.getOperand(1).getGlobal();
MachineFunction &MF = B.getMF();
SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
B.setInstr(MI);

if (AS == AMDGPUAS::LOCAL_ADDRESS || AS == AMDGPUAS::REGION_ADDRESS) {
  if (!MFI->isEntryFunction()) {
    const Function &Fn = MF.getFunction();
    DiagnosticInfoUnsupported BadLDSDecl(
      Fn, "local memory global used by non-kernel function", MI.getDebugLoc());
    Fn.getContext().diagnose(BadLDSDecl);
  }

  // TODO: We could emit code to handle the initialization somewhere.
  if (!AMDGPUTargetLowering::hasDefinedInitializer(GV)) {
    B.buildConstant(DstReg, MFI->allocateLDSGlobal(B.getDataLayout(), *GV));
    MI.eraseFromParent();
    return true;
  }

  const Function &Fn = MF.getFunction();
  DiagnosticInfoUnsupported BadInit(
    Fn, "unsupported initializer for address space", MI.getDebugLoc());
  Fn.getContext().diagnose(BadInit);
  return true;
}

const SITargetLowering *TLI = ST.getTargetLowering();

if (TLI->shouldEmitFixup(GV)) {
  buildPCRelGlobalAddress(DstReg, Ty, B, GV, 0);
  MI.eraseFromParent();
  return true;
}

if (TLI->shouldEmitPCReloc(GV)) {
  buildPCRelGlobalAddress(DstReg, Ty, B, GV, 0, SIInstrInfo::MO_REL32);
  MI.eraseFromParent();
  return true;
}

LLT PtrTy = LLT::pointer(AMDGPUAS::CONSTANT_ADDRESS, 64);
Register GOTAddr = MRI.createGenericVirtualRegister(PtrTy);

MachineMemOperand *GOTMMO = MF.getMachineMemOperand(
  MachinePointerInfo::getGOT(MF),
  MachineMemOperand::MOLoad | MachineMemOperand::MODereferenceable |
  MachineMemOperand::MOInvariant,
  8 /*Size*/, 8 /*Align*/);

buildPCRelGlobalAddress(GOTAddr, PtrTy, B, GV, 0, SIInstrInfo::MO_GOTPCREL32);

if (Ty.getSizeInBits() == 32) {
  // Truncate if this is a 32-bit constant adrdess.
  auto Load = B.buildLoad(PtrTy, GOTAddr, *GOTMMO);
  B.buildExtract(DstReg, Load, 0);
} else
  B.buildLoad(DstReg, GOTAddr, *GOTMMO);

MI.eraseFromParent();
return true;
1702}

1704bool AMDGPULegalizerInfo::legalizeLoad(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B, GISelChangeObserver &Observer) const {
B.setInstr(MI);
LLT ConstPtr = LLT::pointer(AMDGPUAS::CONSTANT_ADDRESS, 64);
auto Cast = B.buildAddrSpaceCast(ConstPtr, MI.getOperand(1).getReg());
Observer.changingInstr(MI);
MI.getOperand(1).setReg(Cast.getReg(0));
Observer.changedInstr(MI);
return true;
1714}

1716bool AMDGPULegalizerInfo::legalizeFMad(
MachineInstr &MI, MachineRegisterInfo &MRI,
MachineIRBuilder &B) const {
LLT Ty = MRI.getType(MI.getOperand(0).getReg());
assert(Ty.isScalar())((Ty.isScalar()) ? static_cast<void> (0) : __assert_fail
 ("Ty.isScalar()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1720, __PRETTY_FUNCTION__));

// TODO: Always legal with future ftz flag.
if (Ty == LLT::scalar(32) && !ST.hasFP32Denormals())
  return true;
if (Ty == LLT::scalar(16) && !ST.hasFP16Denormals())
  return true;

MachineFunction &MF = B.getMF();

MachineIRBuilder HelperBuilder(MI);
GISelObserverWrapper DummyObserver;
LegalizerHelper Helper(MF, DummyObserver, HelperBuilder);
HelperBuilder.setMBB(*MI.getParent());
return Helper.lowerFMad(MI) == LegalizerHelper::Legalized;
1735}

1737bool AMDGPULegalizerInfo::legalizeAtomicCmpXChg(
MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &B) const {
Register DstReg = MI.getOperand(0).getReg();
Register PtrReg = MI.getOperand(1).getReg();
Register CmpVal = MI.getOperand(2).getReg();
Register NewVal = MI.getOperand(3).getReg();

assert(SITargetLowering::isFlatGlobalAddrSpace(((SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg
).getAddressSpace()) && "this should not have been custom lowered"
) ? static_cast<void> (0) : __assert_fail ("SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg).getAddressSpace()) && \"this should not have been custom lowered\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1746, __PRETTY_FUNCTION__))
         MRI.getType(PtrReg).getAddressSpace()) &&((SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg
).getAddressSpace()) && "this should not have been custom lowered"
) ? static_cast<void> (0) : __assert_fail ("SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg).getAddressSpace()) && \"this should not have been custom lowered\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1746, __PRETTY_FUNCTION__))
       "this should not have been custom lowered")((SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg
).getAddressSpace()) && "this should not have been custom lowered"
) ? static_cast<void> (0) : __assert_fail ("SITargetLowering::isFlatGlobalAddrSpace( MRI.getType(PtrReg).getAddressSpace()) && \"this should not have been custom lowered\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1746, __PRETTY_FUNCTION__));

LLT ValTy = MRI.getType(CmpVal);
LLT VecTy = LLT::vector(2, ValTy);

B.setInstr(MI);
Register PackedVal = B.buildBuildVector(VecTy, { NewVal, CmpVal }).getReg(0);

B.buildInstr(AMDGPU::G_AMDGPU_ATOMIC_CMPXCHG)
  .addDef(DstReg)
  .addUse(PtrReg)
  .addUse(PackedVal)
  .setMemRefs(MI.memoperands());

MI.eraseFromParent();
return true;
1762}

1764// Return the use branch instruction, otherwise null if the usage is invalid.
1765static MachineInstr *verifyCFIntrinsic(MachineInstr &MI,
                                     MachineRegisterInfo &MRI) {
Register CondDef = MI.getOperand(0).getReg();
if (!MRI.hasOneNonDBGUse(CondDef))
  return nullptr;

MachineInstr &UseMI = *MRI.use_instr_nodbg_begin(CondDef);
return UseMI.getParent() == MI.getParent() &&
  UseMI.getOpcode() == AMDGPU::G_BRCOND ? &UseMI : nullptr;
1774}

1776Register AMDGPULegalizerInfo::getLiveInRegister(MachineRegisterInfo &MRI,
                                              Register Reg, LLT Ty) const {
Register LiveIn = MRI.getLiveInVirtReg(Reg);
if (LiveIn)
  return LiveIn;

Register NewReg = MRI.createGenericVirtualRegister(Ty);
MRI.addLiveIn(Reg, NewReg);
return NewReg;
1785}

1787bool AMDGPULegalizerInfo::loadInputValue(Register DstReg, MachineIRBuilder &B,
                                       const ArgDescriptor *Arg) const {
if (!Arg->isRegister() || !Arg->getRegister().isValid())
9
←
Taking false branch→
  return false; // TODO: Handle these

assert(Arg->getRegister().isPhysical())((Arg->getRegister().isPhysical()) ? static_cast<void>
 (0) : __assert_fail ("Arg->getRegister().isPhysical()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 1792, __PRETTY_FUNCTION__));
10
←
'?' condition is true→

MachineRegisterInfo &MRI = *B.getMRI();

LLT Ty = MRI.getType(DstReg);
Register LiveIn = getLiveInRegister(MRI, Arg->getRegister(), Ty);

if (Arg->isMasked()) {
11
←
Calling 'ArgDescriptor::isMasked'→
14
←
Returning from 'ArgDescriptor::isMasked'→
15
←
Taking true branch→
  // TODO: Should we try to emit this once in the entry block?
  const LLT S32 = LLT::scalar(32);
  const unsigned Mask = Arg->getMask();
  const unsigned Shift = countTrailingZeros<unsigned>(Mask);
16
←
Calling 'countTrailingZeros<unsigned int>'→
23
←
Returning from 'countTrailingZeros<unsigned int>'→
24
←
'Shift' initialized to 32→

  Register AndMaskSrc = LiveIn;

  if (Shift24.1
'Shift' is not equal to 0
1
'Shift' is not equal to 0
1
'Shift' is not equal to 0
 != 0) {
25
←
Taking true branch→
    auto ShiftAmt = B.buildConstant(S32, Shift);
    AndMaskSrc = B.buildLShr(S32, LiveIn, ShiftAmt).getReg(0);
  }

  B.buildAnd(DstReg, AndMaskSrc, B.buildConstant(S32, Mask >> Shift));
26
←
The result of the right shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'
} else
  B.buildCopy(DstReg, LiveIn);

// Insert the argument copy if it doens't already exist.
// FIXME: It seems EmitLiveInCopies isn't called anywhere?
if (!MRI.getVRegDef(LiveIn)) {
  // FIXME: Should have scoped insert pt
  MachineBasicBlock &OrigInsBB = B.getMBB();
  auto OrigInsPt = B.getInsertPt();

  MachineBasicBlock &EntryMBB = B.getMF().front();
  EntryMBB.addLiveIn(Arg->getRegister());
  B.setInsertPt(EntryMBB, EntryMBB.begin());
  B.buildCopy(LiveIn, Arg->getRegister());

  B.setInsertPt(OrigInsBB, OrigInsPt);
}

return true;
1832}

1834bool AMDGPULegalizerInfo::legalizePreloadedArgIntrin(
MachineInstr &MI,
MachineRegisterInfo &MRI,
MachineIRBuilder &B,
AMDGPUFunctionArgInfo::PreloadedValue ArgType) const {
B.setInstr(MI);

const SIMachineFunctionInfo *MFI = B.getMF().getInfo<SIMachineFunctionInfo>();

const ArgDescriptor *Arg;
const TargetRegisterClass *RC;
std::tie(Arg, RC) = MFI->getPreloadedValue(ArgType);
if (!Arg) {
6
←
Assuming 'Arg' is non-null→
7
←
Taking false branch→
  LLVM_DEBUG(dbgs() << "Required arg register missing\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpu-legalinfo")) { dbgs() << "Required arg register missing\n"
; } } while (false);
  return false;
}

if (loadInputValue(MI.getOperand(0).getReg(), B, Arg)) {
8
←
Calling 'AMDGPULegalizerInfo::loadInputValue'→
  MI.eraseFromParent();
  return true;
}

return false;
1857}

1859bool AMDGPULegalizerInfo::legalizeFDIV(MachineInstr &MI,
                                     MachineRegisterInfo &MRI,
                                     MachineIRBuilder &B) const {
B.setInstr(MI);
Register Dst = MI.getOperand(0).getReg();
LLT DstTy = MRI.getType(Dst);
LLT S16 = LLT::scalar(16);
LLT S32 = LLT::scalar(32);

if (legalizeFastUnsafeFDIV(MI, MRI, B))
  return true;

if (DstTy == S16)
  return legalizeFDIV16(MI, MRI, B);
if (DstTy == S32)
  return legalizeFDIV32(MI, MRI, B);

return false;
1877}

1879bool AMDGPULegalizerInfo::legalizeFastUnsafeFDIV(MachineInstr &MI,
                                               MachineRegisterInfo &MRI,
                                               MachineIRBuilder &B) const {
Register Res = MI.getOperand(0).getReg();
Register LHS = MI.getOperand(1).getReg();
Register RHS = MI.getOperand(2).getReg();

uint16_t Flags = MI.getFlags();

LLT ResTy = MRI.getType(Res);
LLT S32 = LLT::scalar(32);
LLT S64 = LLT::scalar(64);

const MachineFunction &MF = B.getMF();
bool Unsafe =
  MF.getTarget().Options.UnsafeFPMath || MI.getFlag(MachineInstr::FmArcp);

if (!MF.getTarget().Options.UnsafeFPMath && ResTy == S64)
  return false;

if (!Unsafe && ResTy == S32 && ST.hasFP32Denormals())
  return false;

if (auto CLHS = getConstantFPVRegVal(LHS, MRI)) {
  // 1 / x -> RCP(x)
  if (CLHS->isExactlyValue(1.0)) {
    B.buildIntrinsic(Intrinsic::amdgcn_rcp, Res, false)
      .addUse(RHS)
      .setMIFlags(Flags);

    MI.eraseFromParent();
    return true;
  }

  // -1 / x -> RCP( FNEG(x) )
  if (CLHS->isExactlyValue(-1.0)) {
    auto FNeg = B.buildFNeg(ResTy, RHS, Flags);
    B.buildIntrinsic(Intrinsic::amdgcn_rcp, Res, false)
      .addUse(FNeg.getReg(0))
      .setMIFlags(Flags);

    MI.eraseFromParent();
    return true;
  }
}

// x / y -> x * (1.0 / y)
if (Unsafe) {
  auto RCP = B.buildIntrinsic(Intrinsic::amdgcn_rcp, {ResTy}, false)
    .addUse(RHS)
    .setMIFlags(Flags);
  B.buildFMul(Res, LHS, RCP, Flags);

  MI.eraseFromParent();
  return true;
}

return false;
1937}

1939bool AMDGPULegalizerInfo::legalizeFDIV16(MachineInstr &MI,
                                       MachineRegisterInfo &MRI,
                                       MachineIRBuilder &B) const {
B.setInstr(MI);
Register Res = MI.getOperand(0).getReg();
Register LHS = MI.getOperand(1).getReg();
Register RHS = MI.getOperand(2).getReg();

uint16_t Flags = MI.getFlags();

LLT S16 = LLT::scalar(16);
LLT S32 = LLT::scalar(32);

auto LHSExt = B.buildFPExt(S32, LHS, Flags);
auto RHSExt = B.buildFPExt(S32, RHS, Flags);

auto RCP = B.buildIntrinsic(Intrinsic::amdgcn_rcp, {S32}, false)
  .addUse(RHSExt.getReg(0))
  .setMIFlags(Flags);

auto QUOT = B.buildFMul(S32, LHSExt, RCP, Flags);
auto RDst = B.buildFPTrunc(S16, QUOT, Flags);

B.buildIntrinsic(Intrinsic::amdgcn_div_fixup, Res, false)
  .addUse(RDst.getReg(0))
  .addUse(RHS)
  .addUse(LHS)
  .setMIFlags(Flags);

MI.eraseFromParent();
return true;
1970}

1972// Enable or disable FP32 denorm mode. When 'Enable' is true, emit instructions
1973// to enable denorm mode. When 'Enable' is false, disable denorm mode.
1974static void toggleSPDenormMode(bool Enable,
                             const GCNSubtarget &ST,
                             MachineIRBuilder &B) {
// Set SP denorm mode to this value.
unsigned SPDenormMode =
  Enable ? FP_DENORM_FLUSH_NONE3 : FP_DENORM_FLUSH_IN_FLUSH_OUT0;

if (ST.hasDenormModeInst()) {
  // Preserve default FP64FP16 denorm mode while updating FP32 mode.
  unsigned DPDenormModeDefault = ST.hasFP64Denormals()
                                 ? FP_DENORM_FLUSH_NONE3
                                 : FP_DENORM_FLUSH_IN_FLUSH_OUT0;

  unsigned NewDenormModeValue = SPDenormMode | (DPDenormModeDefault << 2);
  B.buildInstr(AMDGPU::S_DENORM_MODE)
    .addImm(NewDenormModeValue);

} else {
  // Select FP32 bit field in mode register.
  unsigned SPDenormModeBitField = AMDGPU::Hwreg::ID_MODE |
                                  (4 << AMDGPU::Hwreg::OFFSET_SHIFT_) |
                                  (1 << AMDGPU::Hwreg::WIDTH_M1_SHIFT_);

  B.buildInstr(AMDGPU::S_SETREG_IMM32_B32)
    .addImm(SPDenormMode)
    .addImm(SPDenormModeBitField);
}
2001}

2003bool AMDGPULegalizerInfo::legalizeFDIV32(MachineInstr &MI,
                                       MachineRegisterInfo &MRI,
                                       MachineIRBuilder &B) const {
B.setInstr(MI);
Register Res = MI.getOperand(0).getReg();
Register LHS = MI.getOperand(1).getReg();
Register RHS = MI.getOperand(2).getReg();

uint16_t Flags = MI.getFlags();

LLT S32 = LLT::scalar(32);
LLT S1 = LLT::scalar(1);

auto One = B.buildFConstant(S32, 1.0f);

auto DenominatorScaled =
  B.buildIntrinsic(Intrinsic::amdgcn_div_scale, {S32, S1}, false)
    .addUse(RHS)
    .addUse(RHS)
    .addUse(LHS)
    .setMIFlags(Flags);
auto NumeratorScaled =
  B.buildIntrinsic(Intrinsic::amdgcn_div_scale, {S32, S1}, false)
    .addUse(LHS)
    .addUse(RHS)
    .addUse(LHS)
    .setMIFlags(Flags);

auto ApproxRcp = B.buildIntrinsic(Intrinsic::amdgcn_rcp, {S32}, false)
  .addUse(DenominatorScaled.getReg(0))
  .setMIFlags(Flags);
auto NegDivScale0 = B.buildFNeg(S32, DenominatorScaled, Flags);

// FIXME: Doesn't correctly model the FP mode switch, and the FP operations
// aren't modeled as reading it.
if (!ST.hasFP32Denormals())
  toggleSPDenormMode(true, ST, B);

auto Fma0 = B.buildFMA(S32, NegDivScale0, ApproxRcp, One, Flags);
auto Fma1 = B.buildFMA(S32, Fma0, ApproxRcp, ApproxRcp, Flags);
auto Mul = B.buildFMul(S32, NumeratorScaled, Fma1, Flags);
auto Fma2 = B.buildFMA(S32, NegDivScale0, Mul, NumeratorScaled, Flags);
auto Fma3 = B.buildFMA(S32, Fma2, Fma1, Mul, Flags);
auto Fma4 = B.buildFMA(S32, NegDivScale0, Fma3, NumeratorScaled, Flags);

if (!ST.hasFP32Denormals())
  toggleSPDenormMode(false, ST, B);

auto Fmas = B.buildIntrinsic(Intrinsic::amdgcn_div_fmas, {S32}, false)
  .addUse(Fma4.getReg(0))
  .addUse(Fma1.getReg(0))
  .addUse(Fma3.getReg(0))
  .addUse(NumeratorScaled.getReg(1))
  .setMIFlags(Flags);

B.buildIntrinsic(Intrinsic::amdgcn_div_fixup, Res, false)
  .addUse(Fmas.getReg(0))
  .addUse(RHS)
  .addUse(LHS)
  .setMIFlags(Flags);

MI.eraseFromParent();
return true;
2066}

2068bool AMDGPULegalizerInfo::legalizeFDIVFastIntrin(MachineInstr &MI,
                                               MachineRegisterInfo &MRI,
                                               MachineIRBuilder &B) const {
B.setInstr(MI);
Register Res = MI.getOperand(0).getReg();
Register LHS = MI.getOperand(2).getReg();
Register RHS = MI.getOperand(3).getReg();
uint16_t Flags = MI.getFlags();

LLT S32 = LLT::scalar(32);
LLT S1 = LLT::scalar(1);

auto Abs = B.buildFAbs(S32, RHS, Flags);
const APFloat C0Val(1.0f);

auto C0 = B.buildConstant(S32, 0x6f800000);
auto C1 = B.buildConstant(S32, 0x2f800000);
auto C2 = B.buildConstant(S32, FloatToBits(1.0f));

auto CmpRes = B.buildFCmp(CmpInst::FCMP_OGT, S1, Abs, C0, Flags);
auto Sel = B.buildSelect(S32, CmpRes, C1, C2, Flags);

auto Mul0 = B.buildFMul(S32, RHS, Sel, Flags);

auto RCP = B.buildIntrinsic(Intrinsic::amdgcn_rcp, {S32}, false)
  .addUse(Mul0.getReg(0))
  .setMIFlags(Flags);

auto Mul1 = B.buildFMul(S32, LHS, RCP, Flags);

B.buildFMul(Res, Sel, Mul1, Flags);

MI.eraseFromParent();
return true;
2102}

2104bool AMDGPULegalizerInfo::legalizeImplicitArgPtr(MachineInstr &MI,
                                               MachineRegisterInfo &MRI,
                                               MachineIRBuilder &B) const {
const SIMachineFunctionInfo *MFI = B.getMF().getInfo<SIMachineFunctionInfo>();
if (!MFI->isEntryFunction()) {
3
←
Assuming the condition is true→
4
←
Taking true branch→
  return legalizePreloadedArgIntrin(MI, MRI, B,
5
←
Calling 'AMDGPULegalizerInfo::legalizePreloadedArgIntrin'→
                                    AMDGPUFunctionArgInfo::IMPLICIT_ARG_PTR);
}

B.setInstr(MI);

uint64_t Offset =
  ST.getTargetLowering()->getImplicitParameterOffset(
    B.getMF(), AMDGPUTargetLowering::FIRST_IMPLICIT);
Register DstReg = MI.getOperand(0).getReg();
LLT DstTy = MRI.getType(DstReg);
LLT IdxTy = LLT::scalar(DstTy.getSizeInBits());

const ArgDescriptor *Arg;
const TargetRegisterClass *RC;
std::tie(Arg, RC)
  = MFI->getPreloadedValue(AMDGPUFunctionArgInfo::KERNARG_SEGMENT_PTR);
if (!Arg)
  return false;

Register KernargPtrReg = MRI.createGenericVirtualRegister(DstTy);
if (!loadInputValue(KernargPtrReg, B, Arg))
  return false;

B.buildPtrAdd(DstReg, KernargPtrReg, B.buildConstant(IdxTy, Offset).getReg(0));
MI.eraseFromParent();
return true;
2136}

2138bool AMDGPULegalizerInfo::legalizeIsAddrSpace(MachineInstr &MI,
                                            MachineRegisterInfo &MRI,
                                            MachineIRBuilder &B,
                                            unsigned AddrSpace) const {
B.setInstr(MI);
Register ApertureReg = getSegmentAperture(AddrSpace, MRI, B);
auto Hi32 = B.buildExtract(LLT::scalar(32), MI.getOperand(2).getReg(), 32);
B.buildICmp(ICmpInst::ICMP_EQ, MI.getOperand(0), Hi32, ApertureReg);
MI.eraseFromParent();
return true;
2148}

2150/// Handle register layout difference for f16 images for some subtargets.
2151Register AMDGPULegalizerInfo::handleD16VData(MachineIRBuilder &B,
                                           MachineRegisterInfo &MRI,
                                           Register Reg) const {
if (!ST.hasUnpackedD16VMem())
  return Reg;

const LLT S16 = LLT::scalar(16);
const LLT S32 = LLT::scalar(32);
LLT StoreVT = MRI.getType(Reg);
assert(StoreVT.isVector() && StoreVT.getElementType() == S16)((StoreVT.isVector() && StoreVT.getElementType() == S16
) ? static_cast<void> (0) : __assert_fail ("StoreVT.isVector() && StoreVT.getElementType() == S16"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp"
, 2160, __PRETTY_FUNCTION__));

auto Unmerge = B.buildUnmerge(S16, Reg);

SmallVector<Register, 4> WideRegs;
for (int I = 0, E = Unmerge->getNumOperands() - 1; I != E; ++I)
  WideRegs.push_back(B.buildAnyExt(S32, Unmerge.getReg(I)).getReg(0));

int NumElts = StoreVT.getNumElements();

return B.buildBuildVector(LLT::vector(NumElts, S32), WideRegs).getReg(0);
2171}

2173bool AMDGPULegalizerInfo::legalizeRawBufferStore(MachineInstr &MI,
                                               MachineRegisterInfo &MRI,
                                               MachineIRBuilder &B,
                                               bool IsFormat) const {
// TODO: Reject f16 format on targets where unsupported.
Register VData = MI.getOperand(1).getReg();
LLT Ty = MRI.getType(VData);

B.setInstr(MI);

const LLT S32 = LLT::scalar(32);
const LLT S16 = LLT::scalar(16);

// Fixup illegal register types for i8 stores.
if (Ty == LLT::scalar(8) || Ty == S16) {
  Register AnyExt = B.buildAnyExt(LLT::scalar(32), VData).getReg(0);
  MI.getOperand(1).setReg(AnyExt);
  return true;
}

if (Ty.isVector()) {
  if (Ty.getElementType() == S16 && Ty.getNumElements() <= 4) {
    if (IsFormat)
      MI.getOperand(1).setReg(handleD16VData(B, MRI, VData));
    return true;
  }

  return Ty.getElementType() == S32 && Ty.getNumElements() <= 4;
}

return Ty == S32;
2204}

2206bool AMDGPULegalizerInfo::legalizeIntrinsic(MachineInstr &MI,
                                          MachineRegisterInfo &MRI,
                                          MachineIRBuilder &B) const {
// Replace the use G_BRCOND with the exec manipulate and branch pseudos.
switch (MI.getIntrinsicID()) {
1
Control jumps to 'case amdgcn_implicitarg_ptr:'  at line 2254→
case Intrinsic::amdgcn_if: {
  if (MachineInstr *BrCond = verifyCFIntrinsic(MI, MRI)) {
    const SIRegisterInfo *TRI
      = static_cast<const SIRegisterInfo *>(MRI.getTargetRegisterInfo());

    B.setInstr(*BrCond);
    Register Def = MI.getOperand(1).getReg();
    Register Use = MI.getOperand(3).getReg();
    B.buildInstr(AMDGPU::SI_IF)
      .addDef(Def)
      .addUse(Use)
      .addMBB(BrCond->getOperand(1).getMBB());

    MRI.setRegClass(Def, TRI->getWaveMaskRegClass());
    MRI.setRegClass(Use, TRI->getWaveMaskRegClass());
    MI.eraseFromParent();
    BrCond->eraseFromParent();
    return true;
  }

  return false;
}
case Intrinsic::amdgcn_loop: {
  if (MachineInstr *BrCond = verifyCFIntrinsic(MI, MRI)) {
    const SIRegisterInfo *TRI
      = static_cast<const SIRegisterInfo *>(MRI.getTargetRegisterInfo());

    B.setInstr(*BrCond);
    Register Reg = MI.getOperand(2).getReg();
    B.buildInstr(AMDGPU::SI_LOOP)
      .addUse(Reg)
      .addMBB(BrCond->getOperand(1).getMBB());
    MI.eraseFromParent();
    BrCond->eraseFromParent();
    MRI.setRegClass(Reg, TRI->getWaveMaskRegClass());
    return true;
  }

  return false;
}
case Intrinsic::amdgcn_kernarg_segment_ptr:
  return legalizePreloadedArgIntrin(
    MI, MRI, B, AMDGPUFunctionArgInfo::KERNARG_SEGMENT_PTR);
case Intrinsic::amdgcn_implicitarg_ptr:
  return legalizeImplicitArgPtr(MI, MRI, B);
2
←
Calling 'AMDGPULegalizerInfo::legalizeImplicitArgPtr'→
case Intrinsic::amdgcn_workitem_id_x:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKITEM_ID_X);
case Intrinsic::amdgcn_workitem_id_y:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKITEM_ID_Y);
case Intrinsic::amdgcn_workitem_id_z:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKITEM_ID_Z);
case Intrinsic::amdgcn_workgroup_id_x:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKGROUP_ID_X);
case Intrinsic::amdgcn_workgroup_id_y:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKGROUP_ID_Y);
case Intrinsic::amdgcn_workgroup_id_z:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::WORKGROUP_ID_Z);
case Intrinsic::amdgcn_dispatch_ptr:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::DISPATCH_PTR);
case Intrinsic::amdgcn_queue_ptr:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::QUEUE_PTR);
case Intrinsic::amdgcn_implicit_buffer_ptr:
  return legalizePreloadedArgIntrin(
    MI, MRI, B, AMDGPUFunctionArgInfo::IMPLICIT_BUFFER_PTR);
case Intrinsic::amdgcn_dispatch_id:
  return legalizePreloadedArgIntrin(MI, MRI, B,
                                    AMDGPUFunctionArgInfo::DISPATCH_ID);
case Intrinsic::amdgcn_fdiv_fast:
  return legalizeFDIVFastIntrin(MI, MRI, B);
case Intrinsic::amdgcn_is_shared:
  return legalizeIsAddrSpace(MI, MRI, B, AMDGPUAS::LOCAL_ADDRESS);
case Intrinsic::amdgcn_is_private:
  return legalizeIsAddrSpace(MI, MRI, B, AMDGPUAS::PRIVATE_ADDRESS);
case Intrinsic::amdgcn_wavefrontsize: {
  B.setInstr(MI);
  B.buildConstant(MI.getOperand(0), ST.getWavefrontSize());
  MI.eraseFromParent();
  return true;
}
case Intrinsic::amdgcn_raw_buffer_store:
  return legalizeRawBufferStore(MI, MRI, B, false);
case Intrinsic::amdgcn_raw_buffer_store_format:
  return legalizeRawBufferStore(MI, MRI, B, true);
default:
  return true;
}

return true;
2307}

←

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPUArgumentUsageInfo.h

→

1//==- AMDGPUArgumentrUsageInfo.h - Function Arg Usage Info -------*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//

9#ifndef LLVM_LIB_TARGET_AMDGPU_AMDGPUARGUMENTUSAGEINFO_H
10#define LLVM_LIB_TARGET_AMDGPU_AMDGPUARGUMENTUSAGEINFO_H

12#include "llvm/ADT/DenseMap.h"
13#include "llvm/CodeGen/Register.h"
14#include "llvm/IR/Function.h"
15#include "llvm/Pass.h"

17namespace llvm {

19class Function;
20class raw_ostream;
21class GCNSubtarget;
22class TargetMachine;
23class TargetRegisterClass;
24class TargetRegisterInfo;

26struct ArgDescriptor {
27private:
friend struct AMDGPUFunctionArgInfo;
friend class AMDGPUArgumentUsageInfo;

union {
  Register Reg;
  unsigned StackOffset;
};

// Bitmask to locate argument within the register.
unsigned Mask;

bool IsStack : 1;
bool IsSet : 1;

42public:
ArgDescriptor(unsigned Val = 0, unsigned Mask = ~0u,
              bool IsStack = false, bool IsSet = false)
  : Reg(Val), Mask(Mask), IsStack(IsStack), IsSet(IsSet) {}

static ArgDescriptor createRegister(Register Reg, unsigned Mask = ~0u) {
  return ArgDescriptor(Reg, Mask, false, true);
}

static ArgDescriptor createStack(unsigned Offset, unsigned Mask = ~0u) {
  return ArgDescriptor(Offset, Mask, true, true);
}

static ArgDescriptor createArg(const ArgDescriptor &Arg, unsigned Mask) {
  return ArgDescriptor(Arg.Reg, Mask, Arg.IsStack, Arg.IsSet);
}

bool isSet() const {
  return IsSet;
}

explicit operator bool() const {
  return isSet();
}

bool isRegister() const {
  return !IsStack;
}

Register getRegister() const {
  assert(!IsStack)((!IsStack) ? static_cast<void> (0) : __assert_fail ("!IsStack"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPUArgumentUsageInfo.h"
, 72, __PRETTY_FUNCTION__));
  return Reg;
}

unsigned getStackOffset() const {
  assert(IsStack)((IsStack) ? static_cast<void> (0) : __assert_fail ("IsStack"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPUArgumentUsageInfo.h"
, 77, __PRETTY_FUNCTION__));
  return StackOffset;
}

unsigned getMask() const {
  return Mask;
}

bool isMasked() const {
  return Mask != ~0u;
12
←
Assuming the condition is true→
13
←
Returning the value 1, which participates in a condition later→
}

void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const;
90};

92inline raw_ostream &operator<<(raw_ostream &OS, const ArgDescriptor &Arg) {
Arg.print(OS);
return OS;
95}

97struct AMDGPUFunctionArgInfo {
enum PreloadedValue {
  // SGPRS:
  PRIVATE_SEGMENT_BUFFER = 0,
  DISPATCH_PTR        =  1,
  QUEUE_PTR           =  2,
  KERNARG_SEGMENT_PTR =  3,
  DISPATCH_ID         =  4,
  FLAT_SCRATCH_INIT   =  5,
  WORKGROUP_ID_X      = 10,
  WORKGROUP_ID_Y      = 11,
  WORKGROUP_ID_Z      = 12,
  PRIVATE_SEGMENT_WAVE_BYTE_OFFSET = 14,
  IMPLICIT_BUFFER_PTR = 15,
  IMPLICIT_ARG_PTR = 16,

  // VGPRS:
  WORKITEM_ID_X       = 17,
  WORKITEM_ID_Y       = 18,
  WORKITEM_ID_Z       = 19,
  FIRST_VGPR_VALUE    = WORKITEM_ID_X
};

// Kernel input registers setup for the HSA ABI in allocation order.

// User SGPRs in kernels
// XXX - Can these require argument spills?
ArgDescriptor PrivateSegmentBuffer;
ArgDescriptor DispatchPtr;
ArgDescriptor QueuePtr;
ArgDescriptor KernargSegmentPtr;
ArgDescriptor DispatchID;
ArgDescriptor FlatScratchInit;
ArgDescriptor PrivateSegmentSize;

// System SGPRs in kernels.
ArgDescriptor WorkGroupIDX;
ArgDescriptor WorkGroupIDY;
ArgDescriptor WorkGroupIDZ;
ArgDescriptor WorkGroupInfo;
ArgDescriptor PrivateSegmentWaveByteOffset;

// Pointer with offset from kernargsegmentptr to where special ABI arguments
// are passed to callable functions.
ArgDescriptor ImplicitArgPtr;

// Input registers for non-HSA ABI
ArgDescriptor ImplicitBufferPtr = 0;

// VGPRs inputs. These are always v0, v1 and v2 for entry functions.
ArgDescriptor WorkItemIDX;
ArgDescriptor WorkItemIDY;
ArgDescriptor WorkItemIDZ;

std::pair<const ArgDescriptor *, const TargetRegisterClass *>
getPreloadedValue(PreloadedValue Value) const;
153};

155class AMDGPUArgumentUsageInfo : public ImmutablePass {
156private:
static const AMDGPUFunctionArgInfo ExternFunctionInfo;
DenseMap<const Function *, AMDGPUFunctionArgInfo> ArgInfoMap;

160public:
static char ID;

AMDGPUArgumentUsageInfo() : ImmutablePass(ID) { }

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesAll();
}

bool doInitialization(Module &M) override;
bool doFinalization(Module &M) override;

void print(raw_ostream &OS, const Module *M = nullptr) const override;

void setFuncArgInfo(const Function &F, const AMDGPUFunctionArgInfo &ArgInfo) {
  ArgInfoMap[&F] = ArgInfo;
}

const AMDGPUFunctionArgInfo &lookupFuncArgInfo(const Function &F) const {
  auto I = ArgInfoMap.find(&F);
  if (I == ArgInfoMap.end()) {
    assert(F.isDeclaration())((F.isDeclaration()) ? static_cast<void> (0) : __assert_fail
 ("F.isDeclaration()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Target/AMDGPU/AMDGPUArgumentUsageInfo.h"
, 181, __PRETTY_FUNCTION__));
    return ExternFunctionInfo;
  }

  return I->second;
}
187};

189} // end namespace llvm

191#endif

←

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12 
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15 
16#include "llvm/Support/Compiler.h"
17#include "llvm/Support/SwapByteOrder.h"
18#include <algorithm>
19#include <cassert>
20#include <climits>
21#include <cstring>
22#include <limits>
23#include <type_traits>
24 
25#ifdef __ANDROID_NDK__
26#include <android/api-level.h>
27#endif
28 
29#ifdef _MSC_VER
30// Declare these intrinsics manually rather including intrin.h. It's very
31// expensive, and MathExtras.h is popular.
32// #include <intrin.h>
33extern "C" {
34unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
35unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
36unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
37unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
38}
39#endif
40 
41namespace llvm {
42 
43/// The behavior an operation has on an input of 0.
44enum ZeroBehavior {
45  /// The returned value is undefined.
46  ZB_Undefined,
47  /// The returned value is numeric_limits<T>::max()
48  ZB_Max,
49  /// The returned value is numeric_limits<T>::digits
50  ZB_Width
51};
52 
53/// Mathematical constants.
54namespace numbers {
55// TODO: Track C++20 std::numbers.
56// TODO: Favor using the hexadecimal FP constants (requires C++17).
57constexpr double e          = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
58                 egamma     = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
59                 ln2        = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
60                 ln10       = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
61                 log2e      = 1.4426950408889634074, // (0x1.71547652b82feP+0)
62                 log10e     = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
63                 pi         = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
64                 inv_pi     = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
65                 sqrtpi     = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
66                 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
67                 sqrt2      = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
68                 inv_sqrt2  = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
69                 sqrt3      = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
70                 inv_sqrt3  = .57735026918962576451, // (0x1.279a74590331cP-1)
71                 phi        = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
72constexpr float ef          = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
73                egammaf     = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
74                ln2f        = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
75                ln10f       = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
76                log2ef      = 1.44269504F, // (0x1.715476P+0)
77                log10ef     = .434294482F, // (0x1.bcb7b2P-2)
78                pif         = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
79                inv_pif     = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
80                sqrtpif     = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
81                inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
82                sqrt2f      = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
83                inv_sqrt2f  = .707106781F, // (0x1.6a09e6P-1)
84                sqrt3f      = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
85                inv_sqrt3f  = .577350269F, // (0x1.279a74P-1)
86                phif        = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
87} // namespace numbers
88 
89namespace detail {
90template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
91  static unsigned count(T Val, ZeroBehavior) {
92    if (!Val)
93      return std::numeric_limits<T>::digits;
94    if (Val & 0x1)
95      return 0;
96 
97    // Bisection method.
98    unsigned ZeroBits = 0;
99    T Shift = std::numeric_limits<T>::digits >> 1;
100    T Mask = std::numeric_limits<T>::max() >> Shift;
101    while (Shift) {
102      if ((Val & Mask) == 0) {
103        Val >>= Shift;
104        ZeroBits |= Shift;
105      }
106      Shift >>= 1;
107      Mask >>= Shift;
108    }
109    return ZeroBits;
110  }
111};
112 
113#if defined(__GNUC__4) || defined(_MSC_VER)
114template <typename T> struct TrailingZerosCounter<T, 4> {
115  static unsigned count(T Val, ZeroBehavior ZB) {
116    if (ZB17.1
'ZB' is not equal to ZB_Undefined
17.1
'ZB' is not equal to ZB_Undefined
17.1
'ZB' is not equal to ZB_Undefined
 != ZB_Undefined && Val == 0)
18
←
Assuming 'Val' is equal to 0→
19
←
Taking true branch→
117      return 32;
20
←
Returning the value 32→
118 
119#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
120    return __builtin_ctz(Val);
121#elif defined(_MSC_VER)
122    unsigned long Index;
123    _BitScanForward(&Index, Val);
124    return Index;
125#endif
126  }
127};
128 
129#if !defined(_MSC_VER) || defined(_M_X64)
130template <typename T> struct TrailingZerosCounter<T, 8> {
131  static unsigned count(T Val, ZeroBehavior ZB) {
132    if (ZB != ZB_Undefined && Val == 0)
133      return 64;
134 
135#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
136    return __builtin_ctzll(Val);
137#elif defined(_MSC_VER)
138    unsigned long Index;
139    _BitScanForward64(&Index, Val);
140    return Index;
141#endif
142  }
143};
144#endif
145#endif
146} // namespace detail
147 
148/// Count number of 0's from the least significant bit to the most
149///   stopping at the first 1.
150///
151/// Only unsigned integral types are allowed.
152///
153/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
154///   valid arguments.
155template <typename T>
156unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
157  static_assert(std::numeric_limits<T>::is_integer &&
158                    !std::numeric_limits<T>::is_signed,
159                "Only unsigned integral types are allowed.");
160  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
17
←
Calling 'TrailingZerosCounter::count'→
21
←
Returning from 'TrailingZerosCounter::count'→
22
←
Returning the value 32→
161}
162 
163namespace detail {
164template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
165  static unsigned count(T Val, ZeroBehavior) {
166    if (!Val)
167      return std::numeric_limits<T>::digits;
168 
169    // Bisection method.
170    unsigned ZeroBits = 0;
171    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
172      T Tmp = Val >> Shift;
173      if (Tmp)
174        Val = Tmp;
175      else
176        ZeroBits |= Shift;
177    }
178    return ZeroBits;
179  }
180};
181 
182#if defined(__GNUC__4) || defined(_MSC_VER)
183template <typename T> struct LeadingZerosCounter<T, 4> {
184  static unsigned count(T Val, ZeroBehavior ZB) {
185    if (ZB != ZB_Undefined && Val == 0)
186      return 32;
187 
188#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
189    return __builtin_clz(Val);
190#elif defined(_MSC_VER)
191    unsigned long Index;
192    _BitScanReverse(&Index, Val);
193    return Index ^ 31;
194#endif
195  }
196};
197 
198#if !defined(_MSC_VER) || defined(_M_X64)
199template <typename T> struct LeadingZerosCounter<T, 8> {
200  static unsigned count(T Val, ZeroBehavior ZB) {
201    if (ZB != ZB_Undefined && Val == 0)
202      return 64;
203 
204#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
205    return __builtin_clzll(Val);
206#elif defined(_MSC_VER)
207    unsigned long Index;
208    _BitScanReverse64(&Index, Val);
209    return Index ^ 63;
210#endif
211  }
212};
213#endif
214#endif
215} // namespace detail
216 
217/// Count number of 0's from the most significant bit to the least
218///   stopping at the first 1.
219///
220/// Only unsigned integral types are allowed.
221///
222/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
223///   valid arguments.
224template <typename T>
225unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
226  static_assert(std::numeric_limits<T>::is_integer &&
227                    !std::numeric_limits<T>::is_signed,
228                "Only unsigned integral types are allowed.");
229  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
230}
231 
232/// Get the index of the first set bit starting from the least
233///   significant bit.
234///
235/// Only unsigned integral types are allowed.
236///
237/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
238///   valid arguments.
239template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
240  if (ZB == ZB_Max && Val == 0)
241    return std::numeric_limits<T>::max();
242 
243  return countTrailingZeros(Val, ZB_Undefined);
244}
245 
246/// Create a bitmask with the N right-most bits set to 1, and all other
247/// bits set to 0.  Only unsigned types are allowed.
248template <typename T> T maskTrailingOnes(unsigned N) {
249  static_assert(std::is_unsigned<T>::value, "Invalid type!");
250  const unsigned Bits = CHAR_BIT8 * sizeof(T);
251  assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast<
void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 251, __PRETTY_FUNCTION__));
252  return N == 0 ? 0 : (T(-1) >> (Bits - N));
253}
254 
255/// Create a bitmask with the N left-most bits set to 1, and all other
256/// bits set to 0.  Only unsigned types are allowed.
257template <typename T> T maskLeadingOnes(unsigned N) {
258  return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
259}
260 
261/// Create a bitmask with the N right-most bits set to 0, and all other
262/// bits set to 1.  Only unsigned types are allowed.
263template <typename T> T maskTrailingZeros(unsigned N) {
264  return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
265}
266 
267/// Create a bitmask with the N left-most bits set to 0, and all other
268/// bits set to 1.  Only unsigned types are allowed.
269template <typename T> T maskLeadingZeros(unsigned N) {
270  return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
271}
272 
273/// Get the index of the last set bit starting from the least
274///   significant bit.
275///
276/// Only unsigned integral types are allowed.
277///
278/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
279///   valid arguments.
280template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
281  if (ZB == ZB_Max && Val == 0)
282    return std::numeric_limits<T>::max();
283 
284  // Use ^ instead of - because both gcc and llvm can remove the associated ^
285  // in the __builtin_clz intrinsic on x86.
286  return countLeadingZeros(Val, ZB_Undefined) ^
287         (std::numeric_limits<T>::digits - 1);
288}
289 
290/// Macro compressed bit reversal table for 256 bits.
291///
292/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
293static const unsigned char BitReverseTable256[256] = {
294#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
295#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
296#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
297  R6(0), R6(2), R6(1), R6(3)
298#undef R2
299#undef R4
300#undef R6
301};
302 
303/// Reverse the bits in \p Val.
304template <typename T>
305T reverseBits(T Val) {
306  unsigned char in[sizeof(Val)];
307  unsigned char out[sizeof(Val)];
308  std::memcpy(in, &Val, sizeof(Val));
309  for (unsigned i = 0; i < sizeof(Val); ++i)
310    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
311  std::memcpy(&Val, out, sizeof(Val));
312  return Val;
313}
314 
315// NOTE: The following support functions use the _32/_64 extensions instead of
316// type overloading so that signed and unsigned integers can be used without
317// ambiguity.
318 
319/// Return the high 32 bits of a 64 bit value.
320constexpr inline uint32_t Hi_32(uint64_t Value) {
321  return static_cast<uint32_t>(Value >> 32);
322}
323 
324/// Return the low 32 bits of a 64 bit value.
325constexpr inline uint32_t Lo_32(uint64_t Value) {
326  return static_cast<uint32_t>(Value);
327}
328 
329/// Make a 64-bit integer from a high / low pair of 32-bit integers.
330constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
331  return ((uint64_t)High << 32) | (uint64_t)Low;
332}
333 
334/// Checks if an integer fits into the given bit width.
335template <unsigned N> constexpr inline bool isInt(int64_t x) {
336  return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
337}
338// Template specializations to get better code for common cases.
339template <> constexpr inline bool isInt<8>(int64_t x) {
340  return static_cast<int8_t>(x) == x;
341}
342template <> constexpr inline bool isInt<16>(int64_t x) {
343  return static_cast<int16_t>(x) == x;
344}
345template <> constexpr inline bool isInt<32>(int64_t x) {
346  return static_cast<int32_t>(x) == x;
347}
348 
349/// Checks if a signed integer is an N bit number shifted left by S.
350template <unsigned N, unsigned S>
351constexpr inline bool isShiftedInt(int64_t x) {
352  static_assert(
353      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
354  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
355  return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
356}
357 
358/// Checks if an unsigned integer fits into the given bit width.
359///
360/// This is written as two functions rather than as simply
361///
362///   return N >= 64 || X < (UINT64_C(1) << N);
363///
364/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
365/// left too many places.
366template <unsigned N>
367constexpr inline typename std::enable_if<(N < 64), bool>::type
368isUInt(uint64_t X) {
369  static_assert(N > 0, "isUInt<0> doesn't make sense");
370  return X < (UINT64_C(1)1UL << (N));
371}
372template <unsigned N>
373constexpr inline typename std::enable_if<N >= 64, bool>::type
374isUInt(uint64_t X) {
375  return true;
376}
377 
378// Template specializations to get better code for common cases.
379template <> constexpr inline bool isUInt<8>(uint64_t x) {
380  return static_cast<uint8_t>(x) == x;
381}
382template <> constexpr inline bool isUInt<16>(uint64_t x) {
383  return static_cast<uint16_t>(x) == x;
384}
385template <> constexpr inline bool isUInt<32>(uint64_t x) {
386  return static_cast<uint32_t>(x) == x;
387}
388 
389/// Checks if a unsigned integer is an N bit number shifted left by S.
390template <unsigned N, unsigned S>
391constexpr inline bool isShiftedUInt(uint64_t x) {
392  static_assert(
393      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
394  static_assert(N + S <= 64,
395                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
396  // Per the two static_asserts above, S must be strictly less than 64.  So
397  // 1 << S is not undefined behavior.
398  return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
399}
400 
401/// Gets the maximum value for a N-bit unsigned integer.
402inline uint64_t maxUIntN(uint64_t N) {
403  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 403, __PRETTY_FUNCTION__));
404 
405  // uint64_t(1) << 64 is undefined behavior, so we can't do
406  //   (uint64_t(1) << N) - 1
407  // without checking first that N != 64.  But this works and doesn't have a
408  // branch.
409  return UINT64_MAX(18446744073709551615UL) >> (64 - N);
410}
411 
412/// Gets the minimum value for a N-bit signed integer.
413inline int64_t minIntN(int64_t N) {
414  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 414, __PRETTY_FUNCTION__));
415 
416  return -(UINT64_C(1)1UL<<(N-1));
417}
418 
419/// Gets the maximum value for a N-bit signed integer.
420inline int64_t maxIntN(int64_t N) {
421  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 421, __PRETTY_FUNCTION__));
422 
423  // This relies on two's complement wraparound when N == 64, so we convert to
424  // int64_t only at the very end to avoid UB.
425  return (UINT64_C(1)1UL << (N - 1)) - 1;
426}
427 
428/// Checks if an unsigned integer fits into the given (dynamic) bit width.
429inline bool isUIntN(unsigned N, uint64_t x) {
430  return N >= 64 || x <= maxUIntN(N);
431}
432 
433/// Checks if an signed integer fits into the given (dynamic) bit width.
434inline bool isIntN(unsigned N, int64_t x) {
435  return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
436}
437 
438/// Return true if the argument is a non-empty sequence of ones starting at the
439/// least significant bit with the remainder zero (32 bit version).
440/// Ex. isMask_32(0x0000FFFFU) == true.
441constexpr inline bool isMask_32(uint32_t Value) {
442  return Value && ((Value + 1) & Value) == 0;
443}
444 
445/// Return true if the argument is a non-empty sequence of ones starting at the
446/// least significant bit with the remainder zero (64 bit version).
447constexpr inline bool isMask_64(uint64_t Value) {
448  return Value && ((Value + 1) & Value) == 0;
449}
450 
451/// Return true if the argument contains a non-empty sequence of ones with the
452/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
453constexpr inline bool isShiftedMask_32(uint32_t Value) {
454  return Value && isMask_32((Value - 1) | Value);
455}
456 
457/// Return true if the argument contains a non-empty sequence of ones with the
458/// remainder zero (64 bit version.)
459constexpr inline bool isShiftedMask_64(uint64_t Value) {
460  return Value && isMask_64((Value - 1) | Value);
461}
462 
463/// Return true if the argument is a power of two > 0.
464/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
465constexpr inline bool isPowerOf2_32(uint32_t Value) {
466  return Value && !(Value & (Value - 1));
467}
468 
469/// Return true if the argument is a power of two > 0 (64 bit edition.)
470constexpr inline bool isPowerOf2_64(uint64_t Value) {
471  return Value && !(Value & (Value - 1));
472}
473 
474/// Return a byte-swapped representation of the 16-bit argument.
475inline uint16_t ByteSwap_16(uint16_t Value) {
476  return sys::SwapByteOrder_16(Value);
477}
478 
479/// Return a byte-swapped representation of the 32-bit argument.
480inline uint32_t ByteSwap_32(uint32_t Value) {
481  return sys::SwapByteOrder_32(Value);
482}
483 
484/// Return a byte-swapped representation of the 64-bit argument.
485inline uint64_t ByteSwap_64(uint64_t Value) {
486  return sys::SwapByteOrder_64(Value);
487}
488 
489/// Count the number of ones from the most significant bit to the first
490/// zero bit.
491///
492/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
493/// Only unsigned integral types are allowed.
494///
495/// \param ZB the behavior on an input of all ones. Only ZB_Width and
496/// ZB_Undefined are valid arguments.
497template <typename T>
498unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
499  static_assert(std::numeric_limits<T>::is_integer &&
500                    !std::numeric_limits<T>::is_signed,
501                "Only unsigned integral types are allowed.");
502  return countLeadingZeros<T>(~Value, ZB);
503}
504 
505/// Count the number of ones from the least significant bit to the first
506/// zero bit.
507///
508/// Ex. countTrailingOnes(0x00FF00FF) == 8.
509/// Only unsigned integral types are allowed.
510///
511/// \param ZB the behavior on an input of all ones. Only ZB_Width and
512/// ZB_Undefined are valid arguments.
513template <typename T>
514unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
515  static_assert(std::numeric_limits<T>::is_integer &&
516                    !std::numeric_limits<T>::is_signed,
517                "Only unsigned integral types are allowed.");
518  return countTrailingZeros<T>(~Value, ZB);
519}
520 
521namespace detail {
522template <typename T, std::size_t SizeOfT> struct PopulationCounter {
523  static unsigned count(T Value) {
524    // Generic version, forward to 32 bits.
525    static_assert(SizeOfT <= 4, "Not implemented!");
526#if defined(__GNUC__4)
527    return __builtin_popcount(Value);
528#else
529    uint32_t v = Value;
530    v = v - ((v >> 1) & 0x55555555);
531    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
532    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
533#endif
534  }
535};
536 
537template <typename T> struct PopulationCounter<T, 8> {
538  static unsigned count(T Value) {
539#if defined(__GNUC__4)
540    return __builtin_popcountll(Value);
541#else
542    uint64_t v = Value;
543    v = v - ((v >> 1) & 0x5555555555555555ULL);
544    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
545    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
546    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
547#endif
548  }
549};
550} // namespace detail
551 
552/// Count the number of set bits in a value.
553/// Ex. countPopulation(0xF000F000) = 8
554/// Returns 0 if the word is zero.
555template <typename T>
556inline unsigned countPopulation(T Value) {
557  static_assert(std::numeric_limits<T>::is_integer &&
558                    !std::numeric_limits<T>::is_signed,
559                "Only unsigned integral types are allowed.");
560  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
561}
562 
563/// Compile time Log2.
564/// Valid only for positive powers of two.
565template <size_t kValue> constexpr inline size_t CTLog2() {
566  static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
567                "Value is not a valid power of 2");
568  return 1 + CTLog2<kValue / 2>();
569}
570 
571template <> constexpr inline size_t CTLog2<1>() { return 0; }
572 
573/// Return the log base 2 of the specified value.
574inline double Log2(double Value) {
575#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
576  return __builtin_log(Value) / __builtin_log(2.0);
577#else
578  return log2(Value);
579#endif
580}
581 
582/// Return the floor log base 2 of the specified value, -1 if the value is zero.
583/// (32 bit edition.)
584/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
585inline unsigned Log2_32(uint32_t Value) {
586  return 31 - countLeadingZeros(Value);
587}
588 
589/// Return the floor log base 2 of the specified value, -1 if the value is zero.
590/// (64 bit edition.)
591inline unsigned Log2_64(uint64_t Value) {
592  return 63 - countLeadingZeros(Value);
593}
594 
595/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
596/// (32 bit edition).
597/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
598inline unsigned Log2_32_Ceil(uint32_t Value) {
599  return 32 - countLeadingZeros(Value - 1);
600}
601 
602/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
603/// (64 bit edition.)
604inline unsigned Log2_64_Ceil(uint64_t Value) {
605  return 64 - countLeadingZeros(Value - 1);
606}
607 
608/// Return the greatest common divisor of the values using Euclid's algorithm.
609template <typename T>
610inline T greatestCommonDivisor(T A, T B) {
611  while (B) {
612    T Tmp = B;
613    B = A % B;
614    A = Tmp;
615  }
616  return A;
617}
618 
619inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
620  return greatestCommonDivisor<uint64_t>(A, B);
621}
622 
623/// This function takes a 64-bit integer and returns the bit equivalent double.
624inline double BitsToDouble(uint64_t Bits) {
625  double D;
626  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
627  memcpy(&D, &Bits, sizeof(Bits));
628  return D;
629}
630 
631/// This function takes a 32-bit integer and returns the bit equivalent float.
632inline float BitsToFloat(uint32_t Bits) {
633  float F;
634  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
635  memcpy(&F, &Bits, sizeof(Bits));
636  return F;
637}
638 
639/// This function takes a double and returns the bit equivalent 64-bit integer.
640/// Note that copying doubles around changes the bits of NaNs on some hosts,
641/// notably x86, so this routine cannot be used if these bits are needed.
642inline uint64_t DoubleToBits(double Double) {
643  uint64_t Bits;
644  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
645  memcpy(&Bits, &Double, sizeof(Double));
646  return Bits;
647}
648 
649/// This function takes a float and returns the bit equivalent 32-bit integer.
650/// Note that copying floats around changes the bits of NaNs on some hosts,
651/// notably x86, so this routine cannot be used if these bits are needed.
652inline uint32_t FloatToBits(float Float) {
653  uint32_t Bits;
654  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
655  memcpy(&Bits, &Float, sizeof(Float));
656  return Bits;
657}
658 
659/// A and B are either alignments or offsets. Return the minimum alignment that
660/// may be assumed after adding the two together.
661constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
662  // The largest power of 2 that divides both A and B.
663  //
664  // Replace "-Value" by "1+~Value" in the following commented code to avoid
665  // MSVC warning C4146
666  //    return (A | B) & -(A | B);
667  return (A | B) & (1 + ~(A | B));
668}
669 
670/// Returns the next power of two (in 64-bits) that is strictly greater than A.
671/// Returns zero on overflow.
672inline uint64_t NextPowerOf2(uint64_t A) {
673  A |= (A >> 1);
674  A |= (A >> 2);
675  A |= (A >> 4);
676  A |= (A >> 8);
677  A |= (A >> 16);
678  A |= (A >> 32);
679  return A + 1;
680}
681 
682/// Returns the power of two which is less than or equal to the given value.
683/// Essentially, it is a floor operation across the domain of powers of two.
684inline uint64_t PowerOf2Floor(uint64_t A) {
685  if (!A) return 0;
686  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
687}
688 
689/// Returns the power of two which is greater than or equal to the given value.
690/// Essentially, it is a ceil operation across the domain of powers of two.
691inline uint64_t PowerOf2Ceil(uint64_t A) {
692  if (!A)
693    return 0;
694  return NextPowerOf2(A - 1);
695}
696 
697/// Returns the next integer (mod 2**64) that is greater than or equal to
698/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
699///
700/// If non-zero \p Skew is specified, the return value will be a minimal
701/// integer that is greater than or equal to \p Value and equal to
702/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
703/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
704///
705/// Examples:
706/// \code
707///   alignTo(5, 8) = 8
708///   alignTo(17, 8) = 24
709///   alignTo(~0LL, 8) = 0
710///   alignTo(321, 255) = 510
711///
712///   alignTo(5, 8, 7) = 7
713///   alignTo(17, 8, 1) = 17
714///   alignTo(~0LL, 8, 3) = 3
715///   alignTo(321, 255, 42) = 552
716/// \endcode
717inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
718  assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 718, __PRETTY_FUNCTION__));
719  Skew %= Align;
720  return (Value + Align - 1 - Skew) / Align * Align + Skew;
721}
722 
723/// Returns the next integer (mod 2**64) that is greater than or equal to
724/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
725template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
726  static_assert(Align != 0u, "Align must be non-zero");
727  return (Value + Align - 1) / Align * Align;
728}
729 
730/// Returns the integer ceil(Numerator / Denominator).
731inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
732  return alignTo(Numerator, Denominator) / Denominator;
733}
734 
735/// Returns the largest uint64_t less than or equal to \p Value and is
736/// \p Skew mod \p Align. \p Align must be non-zero
737inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
738  assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 738, __PRETTY_FUNCTION__));
739  Skew %= Align;
740  return (Value - Skew) / Align * Align + Skew;
741}
742 
743/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
744/// Requires 0 < B <= 32.
745template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
746  static_assert(B > 0, "Bit width can't be 0.");
747  static_assert(B <= 32, "Bit width out of range.");
748  return int32_t(X << (32 - B)) >> (32 - B);
749}
750 
751/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
752/// Requires 0 < B < 32.
753inline int32_t SignExtend32(uint32_t X, unsigned B) {
754  assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 754, __PRETTY_FUNCTION__));
755  assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 755, __PRETTY_FUNCTION__));
756  return int32_t(X << (32 - B)) >> (32 - B);
757}
758 
759/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
760/// Requires 0 < B < 64.
761template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
762  static_assert(B > 0, "Bit width can't be 0.");
763  static_assert(B <= 64, "Bit width out of range.");
764  return int64_t(x << (64 - B)) >> (64 - B);
765}
766 
767/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
768/// Requires 0 < B < 64.
769inline int64_t SignExtend64(uint64_t X, unsigned B) {
770  assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 770, __PRETTY_FUNCTION__));
771  assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/Support/MathExtras.h"
, 771, __PRETTY_FUNCTION__));
772  return int64_t(X << (64 - B)) >> (64 - B);
773}
774 
775/// Subtract two unsigned integers, X and Y, of type T and return the absolute
776/// value of the result.
777template <typename T>
778typename std::enable_if<std::is_unsigned<T>::value, T>::type
779AbsoluteDifference(T X, T Y) {
780  return std::max(X, Y) - std::min(X, Y);
781}
782 
783/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
784/// maximum representable value of T on overflow.  ResultOverflowed indicates if
785/// the result is larger than the maximum representable value of type T.
786template <typename T>
787typename std::enable_if<std::is_unsigned<T>::value, T>::type
788SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
789  bool Dummy;
790  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
791  // Hacker's Delight, p. 29
792  T Z = X + Y;
793  Overflowed = (Z < X || Z < Y);
794  if (Overflowed)
795    return std::numeric_limits<T>::max();
796  else
797    return Z;
798}
799 
800/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
801/// maximum representable value of T on overflow.  ResultOverflowed indicates if
802/// the result is larger than the maximum representable value of type T.
803template <typename T>
804typename std::enable_if<std::is_unsigned<T>::value, T>::type
805SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
806  bool Dummy;
807  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
808 
809  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
810  // because it fails for uint16_t (where multiplication can have undefined
811  // behavior due to promotion to int), and requires a division in addition
812  // to the multiplication.
813 
814  Overflowed = false;
815 
816  // Log2(Z) would be either Log2Z or Log2Z + 1.
817  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
818  // will necessarily be less than Log2Max as desired.
819  int Log2Z = Log2_64(X) + Log2_64(Y);
820  const T Max = std::numeric_limits<T>::max();
821  int Log2Max = Log2_64(Max);
822  if (Log2Z < Log2Max) {
823    return X * Y;
824  }
825  if (Log2Z > Log2Max) {
826    Overflowed = true;
827    return Max;
828  }
829 
830  // We're going to use the top bit, and maybe overflow one
831  // bit past it. Multiply all but the bottom bit then add
832  // that on at the end.
833  T Z = (X >> 1) * Y;
834  if (Z & ~(Max >> 1)) {
835    Overflowed = true;
836    return Max;
837  }
838  Z <<= 1;
839  if (X & 1)
840    return SaturatingAdd(Z, Y, ResultOverflowed);
841 
842  return Z;
843}
844 
845/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
846/// the product. Clamp the result to the maximum representable value of T on
847/// overflow. ResultOverflowed indicates if the result is larger than the
848/// maximum representable value of type T.
849template <typename T>
850typename std::enable_if<std::is_unsigned<T>::value, T>::type
851SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
852  bool Dummy;
853  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
854 
855  T Product = SaturatingMultiply(X, Y, &Overflowed);
856  if (Overflowed)
857    return Product;
858 
859  return SaturatingAdd(A, Product, &Overflowed);
860}
861 
862/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
863extern const float huge_valf;
864 
865 
866/// Add two signed integers, computing the two's complement truncated result,
867/// returning true if overflow occured.
868template <typename T>
869typename std::enable_if<std::is_signed<T>::value, T>::type
870AddOverflow(T X, T Y, T &Result) {
871#if __has_builtin(__builtin_add_overflow)1
872  return __builtin_add_overflow(X, Y, &Result);
873#else
874  // Perform the unsigned addition.
875  using U = typename std::make_unsigned<T>::type;
876  const U UX = static_cast<U>(X);
877  const U UY = static_cast<U>(Y);
878  const U UResult = UX + UY;
879 
880  // Convert to signed.
881  Result = static_cast<T>(UResult);
882 
883  // Adding two positive numbers should result in a positive number.
884  if (X > 0 && Y > 0)
885    return Result <= 0;
886  // Adding two negatives should result in a negative number.
887  if (X < 0 && Y < 0)
888    return Result >= 0;
889  return false;
890#endif
891}
892 
893/// Subtract two signed integers, computing the two's complement truncated
894/// result, returning true if an overflow ocurred.
895template <typename T>
896typename std::enable_if<std::is_signed<T>::value, T>::type
897SubOverflow(T X, T Y, T &Result) {
898#if __has_builtin(__builtin_sub_overflow)1
899  return __builtin_sub_overflow(X, Y, &Result);
900#else
901  // Perform the unsigned addition.
902  using U = typename std::make_unsigned<T>::type;
903  const U UX = static_cast<U>(X);
904  const U UY = static_cast<U>(Y);
905  const U UResult = UX - UY;
906 
907  // Convert to signed.
908  Result = static_cast<T>(UResult);
909 
910  // Subtracting a positive number from a negative results in a negative number.
911  if (X <= 0 && Y > 0)
912    return Result >= 0;
913  // Subtracting a negative number from a positive results in a positive number.
914  if (X >= 0 && Y < 0)
915    return Result <= 0;
916  return false;
917#endif
918}
919 
920 
921/// Multiply two signed integers, computing the two's complement truncated
922/// result, returning true if an overflow ocurred.
923template <typename T>
924typename std::enable_if<std::is_signed<T>::value, T>::type
925MulOverflow(T X, T Y, T &Result) {
926  // Perform the unsigned multiplication on absolute values.
927  using U = typename std::make_unsigned<T>::type;
928  const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
929  const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
930  const U UResult = UX * UY;
931 
932  // Convert to signed.
933  const bool IsNegative = (X < 0) ^ (Y < 0);
934  Result = IsNegative ? (0 - UResult) : UResult;
935 
936  // If any of the args was 0, result is 0 and no overflow occurs.
937  if (UX == 0 || UY == 0)
938    return false;
939 
940  // UX and UY are in [1, 2^n], where n is the number of digits.
941  // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
942  // positive) divided by an argument compares to the other.
943  if (IsNegative)
944    return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
945  else
946    return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
947}
948 
949} // End llvm namespace
950 
951#endif