/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp

Bug Summary

File:	llvm/lib/Target/Mips/MipsLegalizerInfo.cpp
Warning:	line 359, column 25 The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'int'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MipsLegalizerInfo.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 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/build-llvm/lib/Target/Mips -I /build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips -I /build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/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-12/lib/clang/12.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-12~++20210124100612+2afaf072f5c1/build-llvm/lib/Target/Mips -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1=. -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2021-01-24-223304-31662-1 -x c++ /build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp

/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp

→

1//===- MipsLegalizerInfo.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 Mips.
10/// \todo This should be generated by TableGen.
11//===----------------------------------------------------------------------===//

13#include "MipsLegalizerInfo.h"
14#include "MipsTargetMachine.h"
15#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
16#include "llvm/IR/IntrinsicsMips.h"

18using namespace llvm;

20struct TypesAndMemOps {
LLT ValTy;
LLT PtrTy;
unsigned MemSize;
bool SystemSupportsUnalignedAccess;
25};

27// Assumes power of 2 memory size. Subtargets that have only naturally-aligned
28// memory access need to perform additional legalization here.
29static bool isUnalignedMemmoryAccess(uint64_t MemSize, uint64_t AlignInBits) {
assert(isPowerOf2_64(MemSize) && "Expected power of 2 memory size")((isPowerOf2_64(MemSize) && "Expected power of 2 memory size"
) ? static_cast<void> (0) : __assert_fail ("isPowerOf2_64(MemSize) && \"Expected power of 2 memory size\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 30, __PRETTY_FUNCTION__));
assert(isPowerOf2_64(AlignInBits) && "Expected power of 2 align")((isPowerOf2_64(AlignInBits) && "Expected power of 2 align"
) ? static_cast<void> (0) : __assert_fail ("isPowerOf2_64(AlignInBits) && \"Expected power of 2 align\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 31, __PRETTY_FUNCTION__));
if (MemSize > AlignInBits)
  return true;
return false;
35}

37static bool
38CheckTy0Ty1MemSizeAlign(const LegalityQuery &Query,
                      std::initializer_list<TypesAndMemOps> SupportedValues) {
unsigned QueryMemSize = Query.MMODescrs[0].SizeInBits;

// Non power of two memory access is never legal.
if (!isPowerOf2_64(QueryMemSize))
  return false;

for (auto &Val : SupportedValues) {
  if (Val.ValTy != Query.Types[0])
    continue;
  if (Val.PtrTy != Query.Types[1])
    continue;
  if (Val.MemSize != QueryMemSize)
    continue;
  if (!Val.SystemSupportsUnalignedAccess &&
      isUnalignedMemmoryAccess(QueryMemSize, Query.MMODescrs[0].AlignInBits))
    return false;
  return true;
}
return false;
59}

61static bool CheckTyN(unsigned N, const LegalityQuery &Query,
                   std::initializer_list<LLT> SupportedValues) {
for (auto &Val : SupportedValues)
  if (Val == Query.Types[N])
    return true;
return false;
67}

69MipsLegalizerInfo::MipsLegalizerInfo(const MipsSubtarget &ST) {
using namespace TargetOpcode;

const LLT s1 = LLT::scalar(1);
const LLT s32 = LLT::scalar(32);
const LLT s64 = LLT::scalar(64);
const LLT v16s8 = LLT::vector(16, 8);
const LLT v8s16 = LLT::vector(8, 16);
const LLT v4s32 = LLT::vector(4, 32);
const LLT v2s64 = LLT::vector(2, 64);
const LLT p0 = LLT::pointer(0, 32);

getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL})
    .legalIf([=, &ST](const LegalityQuery &Query) {
      if (CheckTyN(0, Query, {s32}))
        return true;
      if (ST.hasMSA() && CheckTyN(0, Query, {v16s8, v8s16, v4s32, v2s64}))
        return true;
      return false;
    })
    .clampScalar(0, s32, s32);

getActionDefinitionsBuilder({G_UADDO, G_UADDE, G_USUBO, G_USUBE, G_UMULO})
    .lowerFor({{s32, s1}});

getActionDefinitionsBuilder(G_UMULH)
    .legalFor({s32})
    .maxScalar(0, s32);

// MIPS32r6 does not have alignment restrictions for memory access.
// For MIPS32r5 and older memory access must be naturally-aligned i.e. aligned
// to at least a multiple of its own size. There is however a two instruction
// combination that performs 4 byte unaligned access (lwr/lwl and swl/swr)
// therefore 4 byte load and store are legal and will use NoAlignRequirements.
bool NoAlignRequirements = true;

getActionDefinitionsBuilder({G_LOAD, G_STORE})
    .legalIf([=, &ST](const LegalityQuery &Query) {
      if (CheckTy0Ty1MemSizeAlign(
              Query, {{s32, p0, 8, NoAlignRequirements},
                      {s32, p0, 16, ST.systemSupportsUnalignedAccess()},
                      {s32, p0, 32, NoAlignRequirements},
                      {p0, p0, 32, NoAlignRequirements},
                      {s64, p0, 64, ST.systemSupportsUnalignedAccess()}}))
        return true;
      if (ST.hasMSA() && CheckTy0Ty1MemSizeAlign(
                             Query, {{v16s8, p0, 128, NoAlignRequirements},
                                     {v8s16, p0, 128, NoAlignRequirements},
                                     {v4s32, p0, 128, NoAlignRequirements},
                                     {v2s64, p0, 128, NoAlignRequirements}}))
        return true;
      return false;
    })
    // Custom lower scalar memory access, up to 8 bytes, for:
    // - non-power-of-2 MemSizes
    // - unaligned 2 or 8 byte MemSizes for MIPS32r5 and older
    .customIf([=, &ST](const LegalityQuery &Query) {
      if (!Query.Types[0].isScalar() || Query.Types[1] != p0 ||
          Query.Types[0] == s1)
        return false;

      unsigned Size = Query.Types[0].getSizeInBits();
      unsigned QueryMemSize = Query.MMODescrs[0].SizeInBits;
      assert(QueryMemSize <= Size && "Scalar can't hold MemSize")((QueryMemSize <= Size && "Scalar can't hold MemSize"
) ? static_cast<void> (0) : __assert_fail ("QueryMemSize <= Size && \"Scalar can't hold MemSize\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 132, __PRETTY_FUNCTION__));

      if (Size > 64 || QueryMemSize > 64)
        return false;

      if (!isPowerOf2_64(Query.MMODescrs[0].SizeInBits))
        return true;

      if (!ST.systemSupportsUnalignedAccess() &&
          isUnalignedMemmoryAccess(QueryMemSize,
                                   Query.MMODescrs[0].AlignInBits)) {
        assert(QueryMemSize != 32 && "4 byte load and store are legal")((QueryMemSize != 32 && "4 byte load and store are legal"
) ? static_cast<void> (0) : __assert_fail ("QueryMemSize != 32 && \"4 byte load and store are legal\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 143, __PRETTY_FUNCTION__));
        return true;
      }

      return false;
    })
    .minScalar(0, s32);

getActionDefinitionsBuilder(G_IMPLICIT_DEF)
    .legalFor({s32, s64});

getActionDefinitionsBuilder(G_UNMERGE_VALUES)
   .legalFor({{s32, s64}});

getActionDefinitionsBuilder(G_MERGE_VALUES)
   .legalFor({{s64, s32}});

getActionDefinitionsBuilder({G_ZEXTLOAD, G_SEXTLOAD})
    .legalForTypesWithMemDesc({{s32, p0, 8, 8},
                               {s32, p0, 16, 8}})
    .clampScalar(0, s32, s32);

getActionDefinitionsBuilder({G_ZEXT, G_SEXT, G_ANYEXT})
    .legalIf([](const LegalityQuery &Query) { return false; })
    .maxScalar(0, s32);

getActionDefinitionsBuilder(G_TRUNC)
    .legalIf([](const LegalityQuery &Query) { return false; })
    .maxScalar(1, s32);

getActionDefinitionsBuilder(G_SELECT)
    .legalForCartesianProduct({p0, s32, s64}, {s32})
    .minScalar(0, s32)
    .minScalar(1, s32);

getActionDefinitionsBuilder(G_BRCOND)
    .legalFor({s32})
    .minScalar(0, s32);

getActionDefinitionsBuilder(G_BRJT)
    .legalFor({{p0, s32}});

getActionDefinitionsBuilder(G_BRINDIRECT)
    .legalFor({p0});

getActionDefinitionsBuilder(G_PHI)
    .legalFor({p0, s32, s64})
    .minScalar(0, s32);

getActionDefinitionsBuilder({G_AND, G_OR, G_XOR})
    .legalFor({s32})
    .clampScalar(0, s32, s32);

getActionDefinitionsBuilder({G_SDIV, G_SREM, G_UDIV, G_UREM})
    .legalIf([=, &ST](const LegalityQuery &Query) {
      if (CheckTyN(0, Query, {s32}))
        return true;
      if (ST.hasMSA() && CheckTyN(0, Query, {v16s8, v8s16, v4s32, v2s64}))
        return true;
      return false;
    })
    .minScalar(0, s32)
    .libcallFor({s64});

getActionDefinitionsBuilder({G_SHL, G_ASHR, G_LSHR})
    .legalFor({{s32, s32}})
    .clampScalar(1, s32, s32)
    .clampScalar(0, s32, s32);

getActionDefinitionsBuilder(G_ICMP)
    .legalForCartesianProduct({s32}, {s32, p0})
    .clampScalar(1, s32, s32)
    .minScalar(0, s32);

getActionDefinitionsBuilder(G_CONSTANT)
    .legalFor({s32})
    .clampScalar(0, s32, s32);

getActionDefinitionsBuilder({G_PTR_ADD, G_INTTOPTR})
    .legalFor({{p0, s32}});

getActionDefinitionsBuilder(G_PTRTOINT)
    .legalFor({{s32, p0}});

getActionDefinitionsBuilder(G_FRAME_INDEX)
    .legalFor({p0});

getActionDefinitionsBuilder({G_GLOBAL_VALUE, G_JUMP_TABLE})
    .legalFor({p0});

getActionDefinitionsBuilder(G_DYN_STACKALLOC)
    .lowerFor({{p0, s32}});

getActionDefinitionsBuilder(G_VASTART)
   .legalFor({p0});

getActionDefinitionsBuilder(G_BSWAP)
    .legalIf([=, &ST](const LegalityQuery &Query) {
      if (ST.hasMips32r2() && CheckTyN(0, Query, {s32}))
        return true;
      return false;
    })
    .lowerIf([=, &ST](const LegalityQuery &Query) {
      if (!ST.hasMips32r2() && CheckTyN(0, Query, {s32}))
        return true;
      return false;
    })
    .maxScalar(0, s32);

getActionDefinitionsBuilder(G_BITREVERSE)
    .lowerFor({s32})
    .maxScalar(0, s32);

getActionDefinitionsBuilder(G_CTLZ)
    .legalFor({{s32, s32}})
    .maxScalar(0, s32)
    .maxScalar(1, s32);
getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF)
    .lowerFor({{s32, s32}});

getActionDefinitionsBuilder(G_CTTZ)
    .lowerFor({{s32, s32}})
    .maxScalar(0, s32)
    .maxScalar(1, s32);
getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF)
    .lowerFor({{s32, s32}, {s64, s64}});

getActionDefinitionsBuilder(G_CTPOP)
    .lowerFor({{s32, s32}})
    .clampScalar(0, s32, s32)
    .clampScalar(1, s32, s32);

// FP instructions
getActionDefinitionsBuilder(G_FCONSTANT)
    .legalFor({s32, s64});

getActionDefinitionsBuilder({G_FADD, G_FSUB, G_FMUL, G_FDIV, G_FABS, G_FSQRT})
    .legalIf([=, &ST](const LegalityQuery &Query) {
      if (CheckTyN(0, Query, {s32, s64}))
        return true;
      if (ST.hasMSA() && CheckTyN(0, Query, {v16s8, v8s16, v4s32, v2s64}))
        return true;
      return false;
    });

getActionDefinitionsBuilder(G_FCMP)
    .legalFor({{s32, s32}, {s32, s64}})
    .minScalar(0, s32);

getActionDefinitionsBuilder({G_FCEIL, G_FFLOOR})
    .libcallFor({s32, s64});

getActionDefinitionsBuilder(G_FPEXT)
    .legalFor({{s64, s32}});

getActionDefinitionsBuilder(G_FPTRUNC)
    .legalFor({{s32, s64}});

// FP to int conversion instructions
getActionDefinitionsBuilder(G_FPTOSI)
    .legalForCartesianProduct({s32}, {s64, s32})
    .libcallForCartesianProduct({s64}, {s64, s32})
    .minScalar(0, s32);

getActionDefinitionsBuilder(G_FPTOUI)
    .libcallForCartesianProduct({s64}, {s64, s32})
    .lowerForCartesianProduct({s32}, {s64, s32})
    .minScalar(0, s32);

// Int to FP conversion instructions
getActionDefinitionsBuilder(G_SITOFP)
    .legalForCartesianProduct({s64, s32}, {s32})
    .libcallForCartesianProduct({s64, s32}, {s64})
    .minScalar(1, s32);

getActionDefinitionsBuilder(G_UITOFP)
    .libcallForCartesianProduct({s64, s32}, {s64})
    .customForCartesianProduct({s64, s32}, {s32})
    .minScalar(1, s32);

getActionDefinitionsBuilder(G_SEXT_INREG).lower();

getActionDefinitionsBuilder({G_MEMCPY, G_MEMMOVE, G_MEMSET}).libcall();

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

331bool MipsLegalizerInfo::legalizeCustom(LegalizerHelper &Helper,
                                     MachineInstr &MI) const {
using namespace TargetOpcode;

MachineIRBuilder &MIRBuilder = Helper.MIRBuilder;
MachineRegisterInfo &MRI = *MIRBuilder.getMRI();

const LLT s32 = LLT::scalar(32);
const LLT s64 = LLT::scalar(64);

switch (MI.getOpcode()) {
1
Control jumps to 'case G_LOAD:'  at line 342→
case G_LOAD:
case G_STORE: {
  unsigned MemSize = (**MI.memoperands_begin()).getSize();
  Register Val = MI.getOperand(0).getReg();
  unsigned Size = MRI.getType(Val).getSizeInBits();

  MachineMemOperand *MMOBase = *MI.memoperands_begin();

  assert(MemSize <= 8 && "MemSize is too large")((MemSize <= 8 && "MemSize is too large") ? static_cast
<void> (0) : __assert_fail ("MemSize <= 8 && \"MemSize is too large\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 350, __PRETTY_FUNCTION__));
2
←
Assuming 'MemSize' is <= 8→
3
←
'?' condition is true→
  assert(Size <= 64 && "Scalar size is too large")((Size <= 64 && "Scalar size is too large") ? static_cast
<void> (0) : __assert_fail ("Size <= 64 && \"Scalar size is too large\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 351, __PRETTY_FUNCTION__));
4
←
Assuming 'Size' is <= 64→
5
←
'?' condition is true→

  // Split MemSize into two, P2HalfMemSize is largest power of two smaller
  // then MemSize. e.g. 8 = 4 + 4 , 6 = 4 + 2, 3 = 2 + 1.
  unsigned P2HalfMemSize, RemMemSize;
  if (isPowerOf2_64(MemSize)) {
6
←
Calling 'isPowerOf2_64'→
9
←
Returning from 'isPowerOf2_64'→
10
←
Taking false branch→
    P2HalfMemSize = RemMemSize = MemSize / 2;
  } else {
    P2HalfMemSize = 1 << Log2_32(MemSize);
11
←
Calling 'Log2_32'→
13
←
Returning from 'Log2_32'→
14
←
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'int'
    RemMemSize = MemSize - P2HalfMemSize;
  }

  Register BaseAddr = MI.getOperand(1).getReg();
  LLT PtrTy = MRI.getType(BaseAddr);
  MachineFunction &MF = MIRBuilder.getMF();

  auto P2HalfMemOp = MF.getMachineMemOperand(MMOBase, 0, P2HalfMemSize);
  auto RemMemOp = MF.getMachineMemOperand(MMOBase, P2HalfMemSize, RemMemSize);

  if (MI.getOpcode() == G_STORE) {
    // Widen Val to s32 or s64 in order to create legal G_LSHR or G_UNMERGE.
    if (Size < 32)
      Val = MIRBuilder.buildAnyExt(s32, Val).getReg(0);
    if (Size > 32 && Size < 64)
      Val = MIRBuilder.buildAnyExt(s64, Val).getReg(0);

    auto C_P2HalfMemSize = MIRBuilder.buildConstant(s32, P2HalfMemSize);
    auto Addr = MIRBuilder.buildPtrAdd(PtrTy, BaseAddr, C_P2HalfMemSize);

    if (MI.getOpcode() == G_STORE && MemSize <= 4) {
      MIRBuilder.buildStore(Val, BaseAddr, *P2HalfMemOp);
      auto C_P2Half_InBits = MIRBuilder.buildConstant(s32, P2HalfMemSize * 8);
      auto Shift = MIRBuilder.buildLShr(s32, Val, C_P2Half_InBits);
      MIRBuilder.buildStore(Shift, Addr, *RemMemOp);
    } else {
      auto Unmerge = MIRBuilder.buildUnmerge(s32, Val);
      MIRBuilder.buildStore(Unmerge.getReg(0), BaseAddr, *P2HalfMemOp);
      MIRBuilder.buildStore(Unmerge.getReg(1), Addr, *RemMemOp);
    }
  }

  if (MI.getOpcode() == G_LOAD) {

    if (MemSize <= 4) {
      // This is anyextending load, use 4 byte lwr/lwl.
      auto *Load4MMO = MF.getMachineMemOperand(MMOBase, 0, 4);

      if (Size == 32)
        MIRBuilder.buildLoad(Val, BaseAddr, *Load4MMO);
      else {
        auto Load = MIRBuilder.buildLoad(s32, BaseAddr, *Load4MMO);
        MIRBuilder.buildTrunc(Val, Load.getReg(0));
      }

    } else {
      auto C_P2HalfMemSize = MIRBuilder.buildConstant(s32, P2HalfMemSize);
      auto Addr = MIRBuilder.buildPtrAdd(PtrTy, BaseAddr, C_P2HalfMemSize);

      auto Load_P2Half = MIRBuilder.buildLoad(s32, BaseAddr, *P2HalfMemOp);
      auto Load_Rem = MIRBuilder.buildLoad(s32, Addr, *RemMemOp);

      if (Size == 64)
        MIRBuilder.buildMerge(Val, {Load_P2Half, Load_Rem});
      else {
        auto Merge = MIRBuilder.buildMerge(s64, {Load_P2Half, Load_Rem});
        MIRBuilder.buildTrunc(Val, Merge);
      }
    }
  }
  MI.eraseFromParent();
  break;
}
case G_UITOFP: {
  Register Dst = MI.getOperand(0).getReg();
  Register Src = MI.getOperand(1).getReg();
  LLT DstTy = MRI.getType(Dst);
  LLT SrcTy = MRI.getType(Src);

  if (SrcTy != s32)
    return false;
  if (DstTy != s32 && DstTy != s64)
    return false;

  // Let 0xABCDEFGH be given unsigned in MI.getOperand(1). First let's convert
  // unsigned to double. Mantissa has 52 bits so we use following trick:
  // First make floating point bit mask 0x43300000ABCDEFGH.
  // Mask represents 2^52 * 0x1.00000ABCDEFGH i.e. 0x100000ABCDEFGH.0 .
  // Next, subtract  2^52 * 0x1.0000000000000 i.e. 0x10000000000000.0 from it.
  // Done. Trunc double to float if needed.

  auto C_HiMask = MIRBuilder.buildConstant(s32, UINT32_C(0x43300000)0x43300000U);
  auto Bitcast = MIRBuilder.buildMerge(s64, {Src, C_HiMask.getReg(0)});

  MachineInstrBuilder TwoP52FP = MIRBuilder.buildFConstant(
      s64, BitsToDouble(UINT64_C(0x4330000000000000)0x4330000000000000UL));

  if (DstTy == s64)
    MIRBuilder.buildFSub(Dst, Bitcast, TwoP52FP);
  else {
    MachineInstrBuilder ResF64 = MIRBuilder.buildFSub(s64, Bitcast, TwoP52FP);
    MIRBuilder.buildFPTrunc(Dst, ResF64);
  }

  MI.eraseFromParent();
  break;
}
default:
  return false;
}

return true;
462}

464static bool SelectMSA3OpIntrinsic(MachineInstr &MI, unsigned Opcode,
                                MachineIRBuilder &MIRBuilder,
                                const MipsSubtarget &ST) {
assert(ST.hasMSA() && "MSA intrinsic not supported on target without MSA.")((ST.hasMSA() && "MSA intrinsic not supported on target without MSA."
) ? static_cast<void> (0) : __assert_fail ("ST.hasMSA() && \"MSA intrinsic not supported on target without MSA.\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 467, __PRETTY_FUNCTION__));
if (!MIRBuilder.buildInstr(Opcode)
         .add(MI.getOperand(0))
         .add(MI.getOperand(2))
         .add(MI.getOperand(3))
         .constrainAllUses(MIRBuilder.getTII(), *ST.getRegisterInfo(),
                           *ST.getRegBankInfo()))
  return false;
MI.eraseFromParent();
return true;
477}

479static bool MSA3OpIntrinsicToGeneric(MachineInstr &MI, unsigned Opcode,
                                   MachineIRBuilder &MIRBuilder,
                                   const MipsSubtarget &ST) {
assert(ST.hasMSA() && "MSA intrinsic not supported on target without MSA.")((ST.hasMSA() && "MSA intrinsic not supported on target without MSA."
) ? static_cast<void> (0) : __assert_fail ("ST.hasMSA() && \"MSA intrinsic not supported on target without MSA.\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 482, __PRETTY_FUNCTION__));
MIRBuilder.buildInstr(Opcode)
    .add(MI.getOperand(0))
    .add(MI.getOperand(2))
    .add(MI.getOperand(3));
MI.eraseFromParent();
return true;
489}

491static bool MSA2OpIntrinsicToGeneric(MachineInstr &MI, unsigned Opcode,
                                   MachineIRBuilder &MIRBuilder,
                                   const MipsSubtarget &ST) {
assert(ST.hasMSA() && "MSA intrinsic not supported on target without MSA.")((ST.hasMSA() && "MSA intrinsic not supported on target without MSA."
) ? static_cast<void> (0) : __assert_fail ("ST.hasMSA() && \"MSA intrinsic not supported on target without MSA.\""
, "/build/llvm-toolchain-snapshot-12~++20210124100612+2afaf072f5c1/llvm/lib/Target/Mips/MipsLegalizerInfo.cpp"
, 494, __PRETTY_FUNCTION__));
MIRBuilder.buildInstr(Opcode)
    .add(MI.getOperand(0))
    .add(MI.getOperand(2));
MI.eraseFromParent();
return true;
500}

502bool MipsLegalizerInfo::legalizeIntrinsic(LegalizerHelper &Helper,
                                        MachineInstr &MI) const {
MachineIRBuilder &MIRBuilder = Helper.MIRBuilder;
const MipsSubtarget &ST =
    static_cast<const MipsSubtarget &>(MI.getMF()->getSubtarget());
const MipsInstrInfo &TII = *ST.getInstrInfo();
const MipsRegisterInfo &TRI = *ST.getRegisterInfo();
const RegisterBankInfo &RBI = *ST.getRegBankInfo();

switch (MI.getIntrinsicID()) {
case Intrinsic::trap: {
  MachineInstr *Trap = MIRBuilder.buildInstr(Mips::TRAP);
  MI.eraseFromParent();
  return constrainSelectedInstRegOperands(*Trap, TII, TRI, RBI);
}
case Intrinsic::vacopy: {
  MachinePointerInfo MPO;
  auto Tmp =
      MIRBuilder.buildLoad(LLT::pointer(0, 32), MI.getOperand(2),
                           *MI.getMF()->getMachineMemOperand(
                               MPO, MachineMemOperand::MOLoad, 4, Align(4)));
  MIRBuilder.buildStore(Tmp, MI.getOperand(1),
                        *MI.getMF()->getMachineMemOperand(
                            MPO, MachineMemOperand::MOStore, 4, Align(4)));
  MI.eraseFromParent();
  return true;
}
case Intrinsic::mips_addv_b:
case Intrinsic::mips_addv_h:
case Intrinsic::mips_addv_w:
case Intrinsic::mips_addv_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_ADD, MIRBuilder, ST);
case Intrinsic::mips_addvi_b:
  return SelectMSA3OpIntrinsic(MI, Mips::ADDVI_B, MIRBuilder, ST);
case Intrinsic::mips_addvi_h:
  return SelectMSA3OpIntrinsic(MI, Mips::ADDVI_H, MIRBuilder, ST);
case Intrinsic::mips_addvi_w:
  return SelectMSA3OpIntrinsic(MI, Mips::ADDVI_W, MIRBuilder, ST);
case Intrinsic::mips_addvi_d:
  return SelectMSA3OpIntrinsic(MI, Mips::ADDVI_D, MIRBuilder, ST);
case Intrinsic::mips_subv_b:
case Intrinsic::mips_subv_h:
case Intrinsic::mips_subv_w:
case Intrinsic::mips_subv_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_SUB, MIRBuilder, ST);
case Intrinsic::mips_subvi_b:
  return SelectMSA3OpIntrinsic(MI, Mips::SUBVI_B, MIRBuilder, ST);
case Intrinsic::mips_subvi_h:
  return SelectMSA3OpIntrinsic(MI, Mips::SUBVI_H, MIRBuilder, ST);
case Intrinsic::mips_subvi_w:
  return SelectMSA3OpIntrinsic(MI, Mips::SUBVI_W, MIRBuilder, ST);
case Intrinsic::mips_subvi_d:
  return SelectMSA3OpIntrinsic(MI, Mips::SUBVI_D, MIRBuilder, ST);
case Intrinsic::mips_mulv_b:
case Intrinsic::mips_mulv_h:
case Intrinsic::mips_mulv_w:
case Intrinsic::mips_mulv_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_MUL, MIRBuilder, ST);
case Intrinsic::mips_div_s_b:
case Intrinsic::mips_div_s_h:
case Intrinsic::mips_div_s_w:
case Intrinsic::mips_div_s_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_SDIV, MIRBuilder, ST);
case Intrinsic::mips_mod_s_b:
case Intrinsic::mips_mod_s_h:
case Intrinsic::mips_mod_s_w:
case Intrinsic::mips_mod_s_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_SREM, MIRBuilder, ST);
case Intrinsic::mips_div_u_b:
case Intrinsic::mips_div_u_h:
case Intrinsic::mips_div_u_w:
case Intrinsic::mips_div_u_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_UDIV, MIRBuilder, ST);
case Intrinsic::mips_mod_u_b:
case Intrinsic::mips_mod_u_h:
case Intrinsic::mips_mod_u_w:
case Intrinsic::mips_mod_u_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_UREM, MIRBuilder, ST);
case Intrinsic::mips_fadd_w:
case Intrinsic::mips_fadd_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_FADD, MIRBuilder, ST);
case Intrinsic::mips_fsub_w:
case Intrinsic::mips_fsub_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_FSUB, MIRBuilder, ST);
case Intrinsic::mips_fmul_w:
case Intrinsic::mips_fmul_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_FMUL, MIRBuilder, ST);
case Intrinsic::mips_fdiv_w:
case Intrinsic::mips_fdiv_d:
  return MSA3OpIntrinsicToGeneric(MI, TargetOpcode::G_FDIV, MIRBuilder, ST);
case Intrinsic::mips_fmax_a_w:
  return SelectMSA3OpIntrinsic(MI, Mips::FMAX_A_W, MIRBuilder, ST);
case Intrinsic::mips_fmax_a_d:
  return SelectMSA3OpIntrinsic(MI, Mips::FMAX_A_D, MIRBuilder, ST);
case Intrinsic::mips_fsqrt_w:
  return MSA2OpIntrinsicToGeneric(MI, TargetOpcode::G_FSQRT, MIRBuilder, ST);
case Intrinsic::mips_fsqrt_d:
  return MSA2OpIntrinsicToGeneric(MI, TargetOpcode::G_FSQRT, MIRBuilder, ST);
default:
  break;
}
return true;
604}

←

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