/build/source/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp

Bug Summary

File:	build/source/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp
Warning:	line 1174, column 42 The result of the right shift is undefined due to shifting by '32', which is greater or equal to the width of type 'uint32_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name HexagonISelDAGToDAG.cpp -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 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16 -I lib/Target/Hexagon -I /build/source/llvm/lib/Target/Hexagon -I include -I /build/source/llvm/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1674602410 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility=hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-01-25-024556-16494-1 -x c++ /build/source/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp

/build/source/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp

→

1//===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//
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 defines an instruction selector for the Hexagon target.
10//
11//===----------------------------------------------------------------------===//

13#include "HexagonISelDAGToDAG.h"
14#include "Hexagon.h"
15#include "HexagonISelLowering.h"
16#include "HexagonMachineFunctionInfo.h"
17#include "HexagonTargetMachine.h"
18#include "llvm/CodeGen/FunctionLoweringInfo.h"
19#include "llvm/CodeGen/MachineInstrBuilder.h"
20#include "llvm/CodeGen/SelectionDAGISel.h"
21#include "llvm/IR/Intrinsics.h"
22#include "llvm/IR/IntrinsicsHexagon.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Debug.h"
25using namespace llvm;

27#define DEBUG_TYPE"hexagon-isel" "hexagon-isel"
28#define PASS_NAME"Hexagon DAG->DAG Pattern Instruction Selection" "Hexagon DAG->DAG Pattern Instruction Selection"

30static
31cl::opt<bool>
32EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(true),
cl::desc("Rebalance address calculation trees to improve "
        "instruction selection"));

36// Rebalance only if this allows e.g. combining a GA with an offset or
37// factoring out a shift.
38static
39cl::opt<bool>
40RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(false),
cl::desc("Rebalance address tree only if this allows optimizations"));

43static
44cl::opt<bool>
45RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,
cl::init(false), cl::desc("Rebalance address tree only if it is imbalanced"));

48static cl::opt<bool> CheckSingleUse("hexagon-isel-su", cl::Hidden,
cl::init(true), cl::desc("Enable checking of SDNode's single-use status"));

51//===----------------------------------------------------------------------===//
52// Instruction Selector Implementation
53//===----------------------------------------------------------------------===//

55#define GET_DAGISEL_BODY HexagonDAGToDAGISel
56#include "HexagonGenDAGISel.inc"

58namespace llvm {
59/// createHexagonISelDag - This pass converts a legalized DAG into a
60/// Hexagon-specific DAG, ready for instruction scheduling.
61FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
                                 CodeGenOpt::Level OptLevel) {
return new HexagonDAGToDAGISel(TM, OptLevel);
64}
65}

67char HexagonDAGToDAGISel::ID = 0;

69INITIALIZE_PASS(HexagonDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)static void *initializeHexagonDAGToDAGISelPassOnce(PassRegistry
 &Registry) { PassInfo *PI = new PassInfo( "Hexagon DAG->DAG Pattern Instruction Selection"
, "hexagon-isel", &HexagonDAGToDAGISel::ID, PassInfo::NormalCtor_t
(callDefaultCtor<HexagonDAGToDAGISel>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
 InitializeHexagonDAGToDAGISelPassFlag; void llvm::initializeHexagonDAGToDAGISelPass
(PassRegistry &Registry) { llvm::call_once(InitializeHexagonDAGToDAGISelPassFlag
, initializeHexagonDAGToDAGISelPassOnce, std::ref(Registry));
 }

71void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
SDValue Chain = LD->getChain();
SDValue Base = LD->getBasePtr();
SDValue Offset = LD->getOffset();
int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
EVT LoadedVT = LD->getMemoryVT();
unsigned Opcode = 0;

// Check for zero extended loads. Treat any-extend loads as zero extended
// loads.
ISD::LoadExtType ExtType = LD->getExtensionType();
bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);
bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);

assert(LoadedVT.isSimple())(static_cast <bool> (LoadedVT.isSimple()) ? void (0) : __assert_fail
 ("LoadedVT.isSimple()", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 85, __extension__ __PRETTY_FUNCTION__));
switch (LoadedVT.getSimpleVT().SimpleTy) {
case MVT::i8:
  if (IsZeroExt)
    Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
  else
    Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
  break;
case MVT::i16:
  if (IsZeroExt)
    Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
  else
    Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
  break;
case MVT::i32:
case MVT::f32:
case MVT::v2i16:
case MVT::v4i8:
  Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
  break;
case MVT::i64:
case MVT::f64:
case MVT::v2i32:
case MVT::v4i16:
case MVT::v8i8:
  Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
  break;
case MVT::v64i8:
case MVT::v32i16:
case MVT::v16i32:
case MVT::v8i64:
case MVT::v128i8:
case MVT::v64i16:
case MVT::v32i32:
case MVT::v16i64:
  if (isAlignedMemNode(LD)) {
    if (LD->isNonTemporal())
      Opcode = IsValidInc ? Hexagon::V6_vL32b_nt_pi : Hexagon::V6_vL32b_nt_ai;
    else
      Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
  } else {
    Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
  }
  break;
default:
  llvm_unreachable("Unexpected memory type in indexed load")::llvm::llvm_unreachable_internal("Unexpected memory type in indexed load"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 130);
}

SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
MachineMemOperand *MemOp = LD->getMemOperand();

auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
      -> MachineSDNode* {
  if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
    SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
    return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,
                                  Zero, SDValue(N, 0));
  }
  if (ExtType == ISD::SEXTLOAD)
    return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,
                                  SDValue(N, 0));
  return N;
};

//                  Loaded value   Next address   Chain
SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
SDValue To[3];

EVT ValueVT = LD->getValueType(0);
if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {
  // A load extending to i64 will actually produce i32, which will then
  // need to be extended to i64.
  assert(LoadedVT.getSizeInBits() <= 32)(static_cast <bool> (LoadedVT.getSizeInBits() <= 32)
 ? void (0) : __assert_fail ("LoadedVT.getSizeInBits() <= 32"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 157, __extension__
 __PRETTY_FUNCTION__));
  ValueVT = MVT::i32;
}

if (IsValidInc) {
  MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,
                                            MVT::i32, MVT::Other, Base,
                                            IncV, Chain);
  CurDAG->setNodeMemRefs(L, {MemOp});
  To[1] = SDValue(L, 1); // Next address.
  To[2] = SDValue(L, 2); // Chain.
  // Handle special case for extension to i64.
  if (LD->getValueType(0) == MVT::i64)
    L = getExt64(L, dl);
  To[0] = SDValue(L, 0); // Loaded (extended) value.
} else {
  SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
  MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,
                                            Base, Zero, Chain);
  CurDAG->setNodeMemRefs(L, {MemOp});
  To[2] = SDValue(L, 1); // Chain.
  MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
                                            Base, IncV);
  To[1] = SDValue(A, 0); // Next address.
  // Handle special case for extension to i64.
  if (LD->getValueType(0) == MVT::i64)
    L = getExt64(L, dl);
  To[0] = SDValue(L, 0); // Loaded (extended) value.
}
ReplaceUses(From, To, 3);
CurDAG->RemoveDeadNode(LD);
188}

190MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
  return nullptr;

SDLoc dl(IntN);
unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();

static std::map<unsigned,unsigned> LoadPciMap = {
  { Intrinsic::hexagon_circ_ldb,  Hexagon::L2_loadrb_pci  },
  { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
  { Intrinsic::hexagon_circ_ldh,  Hexagon::L2_loadrh_pci  },
  { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
  { Intrinsic::hexagon_circ_ldw,  Hexagon::L2_loadri_pci  },
  { Intrinsic::hexagon_circ_ldd,  Hexagon::L2_loadrd_pci  },
};
auto FLC = LoadPciMap.find(IntNo);
if (FLC != LoadPciMap.end()) {
  EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;
  EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
  // Operands: { Base, Increment, Modifier, Chain }
  auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));
  SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), dl, MVT::i32);
  MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,
        { IntN->getOperand(2), I, IntN->getOperand(4),
          IntN->getOperand(0) });
  return Res;
}

return nullptr;
219}

221SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
    SDNode *IntN) {
// The "LoadN" is just a machine load instruction. The intrinsic also
// involves storing it. Generate an appropriate store to the location
// given in the intrinsic's operand(3).
uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;
unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
                    HexagonII::MemAccesSizeMask;
unsigned Size = 1U << (SizeBits-1);

SDLoc dl(IntN);
MachinePointerInfo PI;
SDValue TS;
SDValue Loc = IntN->getOperand(3);

if (Size >= 4)
  TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,
                        Align(Size));
else
  TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,
                             PI, MVT::getIntegerVT(Size * 8), Align(Size));

SDNode *StoreN;
{
  HandleSDNode Handle(TS);
  SelectStore(TS.getNode());
  StoreN = Handle.getValue().getNode();
}

// Load's results are { Loaded value, Updated pointer, Chain }
ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));
ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));
return StoreN;
254}

256bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
// The intrinsics for load circ/brev perform two operations:
// 1. Load a value V from the specified location, using the addressing
//    mode corresponding to the intrinsic.
// 2. Store V into a specified location. This location is typically a
//    local, temporary object.
// In many cases, the program using these intrinsics will immediately
// load V again from the local object. In those cases, when certain
// conditions are met, the last load can be removed.
// This function identifies and optimizes this pattern. If the pattern
// cannot be optimized, it returns nullptr, which will cause the load
// to be selected separately from the intrinsic (which will be handled
// in SelectIntrinsicWChain).

SDValue Ch = N->getOperand(0);
SDValue Loc = N->getOperand(1);

// Assume that the load and the intrinsic are connected directly with a
// chain:
//   t1: i32,ch = int.load ..., ..., ..., Loc, ...    // <-- C
//   t2: i32,ch = load t1:1, Loc, ...
SDNode *C = Ch.getNode();

if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
  return false;

// The second load can only be eliminated if its extension type matches
// that of the load instruction corresponding to the intrinsic. The user
// can provide an address of an unsigned variable to store the result of
// a sign-extending intrinsic into (or the other way around).
ISD::LoadExtType IntExt;
switch (cast<ConstantSDNode>(C->getOperand(1))->getZExtValue()) {
  case Intrinsic::hexagon_circ_ldub:
  case Intrinsic::hexagon_circ_lduh:
    IntExt = ISD::ZEXTLOAD;
    break;
  case Intrinsic::hexagon_circ_ldw:
  case Intrinsic::hexagon_circ_ldd:
    IntExt = ISD::NON_EXTLOAD;
    break;
  default:
    IntExt = ISD::SEXTLOAD;
    break;
}
if (N->getExtensionType() != IntExt)
  return false;

// Make sure the target location for the loaded value in the load intrinsic
// is the location from which LD (or N) is loading.
if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())
  return false;

if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {
  SDNode *S = StoreInstrForLoadIntrinsic(L, C);
  SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
  SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
  ReplaceUses(F, T, std::size(T));
  // This transformation will leave the intrinsic dead. If it remains in
  // the DAG, the selection code will see it again, but without the load,
  // and it will generate a store that is normally required for it.
  CurDAG->RemoveDeadNode(C);
  return true;
}
return false;
320}

322// Convert the bit-reverse load intrinsic to appropriate target instruction.
323bool HexagonDAGToDAGISel::SelectBrevLdIntrinsic(SDNode *IntN) {
if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
  return false;

const SDLoc &dl(IntN);
unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();

static const std::map<unsigned, unsigned> LoadBrevMap = {
  { Intrinsic::hexagon_L2_loadrb_pbr, Hexagon::L2_loadrb_pbr },
  { Intrinsic::hexagon_L2_loadrub_pbr, Hexagon::L2_loadrub_pbr },
  { Intrinsic::hexagon_L2_loadrh_pbr, Hexagon::L2_loadrh_pbr },
  { Intrinsic::hexagon_L2_loadruh_pbr, Hexagon::L2_loadruh_pbr },
  { Intrinsic::hexagon_L2_loadri_pbr, Hexagon::L2_loadri_pbr },
  { Intrinsic::hexagon_L2_loadrd_pbr, Hexagon::L2_loadrd_pbr }
};
auto FLI = LoadBrevMap.find(IntNo);
if (FLI != LoadBrevMap.end()) {
  EVT ValTy =
      (IntNo == Intrinsic::hexagon_L2_loadrd_pbr) ? MVT::i64 : MVT::i32;
  EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
  // Operands of Intrinsic: {chain, enum ID of intrinsic, baseptr,
  // modifier}.
  // Operands of target instruction: { Base, Modifier, Chain }.
  MachineSDNode *Res = CurDAG->getMachineNode(
      FLI->second, dl, RTys,
      {IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(0)});

  MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(IntN)->getMemOperand();
  CurDAG->setNodeMemRefs(Res, {MemOp});

  ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
  ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
  ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));
  CurDAG->RemoveDeadNode(IntN);
  return true;
}
return false;
360}

362/// Generate a machine instruction node for the new circular buffer intrinsics.
363/// The new versions use a CSx register instead of the K field.
364bool HexagonDAGToDAGISel::SelectNewCircIntrinsic(SDNode *IntN) {
if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
  return false;

SDLoc DL(IntN);
unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
SmallVector<SDValue, 7> Ops;

static std::map<unsigned,unsigned> LoadNPcMap = {
  { Intrinsic::hexagon_L2_loadrub_pci, Hexagon::PS_loadrub_pci },
  { Intrinsic::hexagon_L2_loadrb_pci, Hexagon::PS_loadrb_pci },
  { Intrinsic::hexagon_L2_loadruh_pci, Hexagon::PS_loadruh_pci },
  { Intrinsic::hexagon_L2_loadrh_pci, Hexagon::PS_loadrh_pci },
  { Intrinsic::hexagon_L2_loadri_pci, Hexagon::PS_loadri_pci },
  { Intrinsic::hexagon_L2_loadrd_pci, Hexagon::PS_loadrd_pci },
  { Intrinsic::hexagon_L2_loadrub_pcr, Hexagon::PS_loadrub_pcr },
  { Intrinsic::hexagon_L2_loadrb_pcr, Hexagon::PS_loadrb_pcr },
  { Intrinsic::hexagon_L2_loadruh_pcr, Hexagon::PS_loadruh_pcr },
  { Intrinsic::hexagon_L2_loadrh_pcr, Hexagon::PS_loadrh_pcr },
  { Intrinsic::hexagon_L2_loadri_pcr, Hexagon::PS_loadri_pcr },
  { Intrinsic::hexagon_L2_loadrd_pcr, Hexagon::PS_loadrd_pcr }
};
auto FLI = LoadNPcMap.find (IntNo);
if (FLI != LoadNPcMap.end()) {
  EVT ValTy = MVT::i32;
  if (IntNo == Intrinsic::hexagon_L2_loadrd_pci ||
      IntNo == Intrinsic::hexagon_L2_loadrd_pcr)
    ValTy = MVT::i64;
  EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
  // Handle load.*_pci case which has 6 operands.
  if (IntN->getNumOperands() == 6) {
    auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));
    SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);
    // Operands: { Base, Increment, Modifier, Start, Chain }.
    Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),
            IntN->getOperand(0) };
  } else
    // Handle load.*_pcr case which has 5 operands.
    // Operands: { Base, Modifier, Start, Chain }.
    Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),
            IntN->getOperand(0) };
  MachineSDNode *Res = CurDAG->getMachineNode(FLI->second, DL, RTys, Ops);
  ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
  ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
  ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));
  CurDAG->RemoveDeadNode(IntN);
  return true;
}

static std::map<unsigned,unsigned> StoreNPcMap = {
  { Intrinsic::hexagon_S2_storerb_pci, Hexagon::PS_storerb_pci },
  { Intrinsic::hexagon_S2_storerh_pci, Hexagon::PS_storerh_pci },
  { Intrinsic::hexagon_S2_storerf_pci, Hexagon::PS_storerf_pci },
  { Intrinsic::hexagon_S2_storeri_pci, Hexagon::PS_storeri_pci },
  { Intrinsic::hexagon_S2_storerd_pci, Hexagon::PS_storerd_pci },
  { Intrinsic::hexagon_S2_storerb_pcr, Hexagon::PS_storerb_pcr },
  { Intrinsic::hexagon_S2_storerh_pcr, Hexagon::PS_storerh_pcr },
  { Intrinsic::hexagon_S2_storerf_pcr, Hexagon::PS_storerf_pcr },
  { Intrinsic::hexagon_S2_storeri_pcr, Hexagon::PS_storeri_pcr },
  { Intrinsic::hexagon_S2_storerd_pcr, Hexagon::PS_storerd_pcr }
};
auto FSI = StoreNPcMap.find (IntNo);
if (FSI != StoreNPcMap.end()) {
  EVT RTys[] = { MVT::i32, MVT::Other };
  // Handle store.*_pci case which has 7 operands.
  if (IntN->getNumOperands() == 7) {
    auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));
    SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);
    // Operands: { Base, Increment, Modifier, Value, Start, Chain }.
    Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),
            IntN->getOperand(6), IntN->getOperand(0) };
  } else
    // Handle store.*_pcr case which has 6 operands.
    // Operands: { Base, Modifier, Value, Start, Chain }.
    Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),
            IntN->getOperand(5), IntN->getOperand(0) };
  MachineSDNode *Res = CurDAG->getMachineNode(FSI->second, DL, RTys, Ops);
  ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));
  ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));
  CurDAG->RemoveDeadNode(IntN);
  return true;
}

return false;
448}

450void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
SDLoc dl(N);
LoadSDNode *LD = cast<LoadSDNode>(N);

// Handle indexed loads.
ISD::MemIndexedMode AM = LD->getAddressingMode();
if (AM != ISD::UNINDEXED) {
  SelectIndexedLoad(LD, dl);
  return;
}

// Handle patterns using circ/brev load intrinsics.
if (tryLoadOfLoadIntrinsic(LD))
  return;

SelectCode(LD);
466}

468void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
SDValue Chain = ST->getChain();
SDValue Base = ST->getBasePtr();
SDValue Offset = ST->getOffset();
SDValue Value = ST->getValue();
// Get the constant value.
int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
EVT StoredVT = ST->getMemoryVT();
EVT ValueVT = Value.getValueType();

bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);
unsigned Opcode = 0;

assert(StoredVT.isSimple())(static_cast <bool> (StoredVT.isSimple()) ? void (0) : __assert_fail
 ("StoredVT.isSimple()", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 481, __extension__ __PRETTY_FUNCTION__));
switch (StoredVT.getSimpleVT().SimpleTy) {
case MVT::i8:
  Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
  break;
case MVT::i16:
  Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
  break;
case MVT::i32:
case MVT::f32:
case MVT::v2i16:
case MVT::v4i8:
  Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
  break;
case MVT::i64:
case MVT::f64:
case MVT::v2i32:
case MVT::v4i16:
case MVT::v8i8:
  Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
  break;
case MVT::v64i8:
case MVT::v32i16:
case MVT::v16i32:
case MVT::v8i64:
case MVT::v128i8:
case MVT::v64i16:
case MVT::v32i32:
case MVT::v16i64:
  if (isAlignedMemNode(ST)) {
    if (ST->isNonTemporal())
      Opcode = IsValidInc ? Hexagon::V6_vS32b_nt_pi : Hexagon::V6_vS32b_nt_ai;
    else
      Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
  } else {
    Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
  }
  break;
default:
  llvm_unreachable("Unexpected memory type in indexed store")::llvm::llvm_unreachable_internal("Unexpected memory type in indexed store"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 520);
}

if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {
  assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store")(static_cast <bool> (StoredVT.getSizeInBits() < 64 &&
 "Not a truncating store") ? void (0) : __assert_fail ("StoredVT.getSizeInBits() < 64 && \"Not a truncating store\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 524, __extension__
 __PRETTY_FUNCTION__));
  Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,
                                         dl, MVT::i32, Value);
}

SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
MachineMemOperand *MemOp = ST->getMemOperand();

//                  Next address   Chain
SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
SDValue To[2];

if (IsValidInc) {
  // Build post increment store.
  SDValue Ops[] = { Base, IncV, Value, Chain };
  MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,
                                            Ops);
  CurDAG->setNodeMemRefs(S, {MemOp});
  To[0] = SDValue(S, 0);
  To[1] = SDValue(S, 1);
} else {
  SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
  SDValue Ops[] = { Base, Zero, Value, Chain };
  MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);
  CurDAG->setNodeMemRefs(S, {MemOp});
  To[1] = SDValue(S, 0);
  MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
                                            Base, IncV);
  To[0] = SDValue(A, 0);
}

ReplaceUses(From, To, 2);
CurDAG->RemoveDeadNode(ST);
557}

559void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
SDLoc dl(N);
StoreSDNode *ST = cast<StoreSDNode>(N);

// Handle indexed stores.
ISD::MemIndexedMode AM = ST->getAddressingMode();
if (AM != ISD::UNINDEXED) {
  SelectIndexedStore(ST, dl);
  return;
}

SelectCode(ST);
571}

573void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
SDLoc dl(N);
SDValue Shl_0 = N->getOperand(0);
SDValue Shl_1 = N->getOperand(1);

auto Default = [this,N] () -> void { SelectCode(N); };

if (N->getValueType(0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)
  return Default();

// RHS is const.
int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();

if (Shl_0.getOpcode() == ISD::MUL) {
  SDValue Mul_0 = Shl_0.getOperand(0); // Val
  SDValue Mul_1 = Shl_0.getOperand(1); // Const
  // RHS of mul is const.
  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {
    int32_t ValConst = C->getSExtValue() << ShlConst;
    if (isInt<9>(ValConst)) {
      SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);
      SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
                                              MVT::i32, Mul_0, Val);
      ReplaceNode(N, Result);
      return;
    }
  }
  return Default();
}

if (Shl_0.getOpcode() == ISD::SUB) {
  SDValue Sub_0 = Shl_0.getOperand(0); // Const 0
  SDValue Sub_1 = Shl_0.getOperand(1); // Val
  if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {
    if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
      return Default();
    SDValue Shl2_0 = Sub_1.getOperand(0); // Val
    SDValue Shl2_1 = Sub_1.getOperand(1); // Const
    if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {
      int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
      if (isInt<9>(-ValConst)) {
        SDValue Val = CurDAG->getTargetConstant(-ValConst, dl, MVT::i32);
        SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
                                                MVT::i32, Shl2_0, Val);
        ReplaceNode(N, Result);
        return;
      }
    }
  }
}

return Default();
625}

627//
628// Handling intrinsics for circular load and bitreverse load.
629//
630void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {
  StoreInstrForLoadIntrinsic(L, N);
  CurDAG->RemoveDeadNode(N);
  return;
}

// Handle bit-reverse load intrinsics.
if (SelectBrevLdIntrinsic(N))
  return;

if (SelectNewCircIntrinsic(N))
  return;

unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
if (IntNo == Intrinsic::hexagon_V6_vgathermw ||
    IntNo == Intrinsic::hexagon_V6_vgathermw_128B ||
    IntNo == Intrinsic::hexagon_V6_vgathermh ||
    IntNo == Intrinsic::hexagon_V6_vgathermh_128B ||
    IntNo == Intrinsic::hexagon_V6_vgathermhw ||
    IntNo == Intrinsic::hexagon_V6_vgathermhw_128B) {
  SelectV65Gather(N);
  return;
}
if (IntNo == Intrinsic::hexagon_V6_vgathermwq ||
    IntNo == Intrinsic::hexagon_V6_vgathermwq_128B ||
    IntNo == Intrinsic::hexagon_V6_vgathermhq ||
    IntNo == Intrinsic::hexagon_V6_vgathermhq_128B ||
    IntNo == Intrinsic::hexagon_V6_vgathermhwq ||
    IntNo == Intrinsic::hexagon_V6_vgathermhwq_128B) {
  SelectV65GatherPred(N);
  return;
}

SelectCode(N);
665}

667void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
unsigned Bits;
switch (IID) {
case Intrinsic::hexagon_S2_vsplatrb:
  Bits = 8;
  break;
case Intrinsic::hexagon_S2_vsplatrh:
  Bits = 16;
  break;
case Intrinsic::hexagon_V6_vaddcarry:
case Intrinsic::hexagon_V6_vaddcarry_128B:
case Intrinsic::hexagon_V6_vsubcarry:
case Intrinsic::hexagon_V6_vsubcarry_128B:
  SelectHVXDualOutput(N);
  return;
default:
  SelectCode(N);
  return;
}

SDValue V = N->getOperand(1);
SDValue U;
// Splat intrinsics.
if (keepsLowBits(V, Bits, U)) {
  SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
                              N->getOperand(0), U);
  ReplaceNode(N, R.getNode());
  SelectCode(R.getNode());
  return;
}
SelectCode(N);
699}

701void HexagonDAGToDAGISel::SelectExtractSubvector(SDNode *N) {
SDValue Inp = N->getOperand(0);
MVT ResTy = N->getValueType(0).getSimpleVT();
auto IdxN = cast<ConstantSDNode>(N->getOperand(1));
unsigned Idx = IdxN->getZExtValue();

[[maybe_unused]] MVT InpTy = Inp.getValueType().getSimpleVT();
[[maybe_unused]] unsigned ResLen = ResTy.getVectorNumElements();
assert(InpTy.getVectorElementType() == ResTy.getVectorElementType())(static_cast <bool> (InpTy.getVectorElementType() == ResTy
.getVectorElementType()) ? void (0) : __assert_fail ("InpTy.getVectorElementType() == ResTy.getVectorElementType()"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 709, __extension__
 __PRETTY_FUNCTION__));
assert(2 * ResLen == InpTy.getVectorNumElements())(static_cast <bool> (2 * ResLen == InpTy.getVectorNumElements
()) ? void (0) : __assert_fail ("2 * ResLen == InpTy.getVectorNumElements()"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 710, __extension__
 __PRETTY_FUNCTION__));
assert(ResTy.getSizeInBits() == 32)(static_cast <bool> (ResTy.getSizeInBits() == 32) ? void
 (0) : __assert_fail ("ResTy.getSizeInBits() == 32", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 711, __extension__ __PRETTY_FUNCTION__));
assert(Idx == 0 || Idx == ResLen)(static_cast <bool> (Idx == 0 || Idx == ResLen) ? void (
0) : __assert_fail ("Idx == 0 || Idx == ResLen", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 712, __extension__ __PRETTY_FUNCTION__));

unsigned SubReg = Idx == 0 ? Hexagon::isub_lo : Hexagon::isub_hi;
SDValue Ext = CurDAG->getTargetExtractSubreg(SubReg, SDLoc(N), ResTy, Inp);

ReplaceNode(N, Ext.getNode());
718}

720//
721// Map floating point constant values.
722//
723void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
SDLoc dl(N);
auto *CN = cast<ConstantFPSDNode>(N);
APInt A = CN->getValueAPF().bitcastToAPInt();
if (N->getValueType(0) == MVT::f32) {
  SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
  ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
  return;
}
if (N->getValueType(0) == MVT::f64) {
  SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
  ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
  return;
}

SelectCode(N);
739}

741//
742// Map boolean values.
743//
744void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
if (N->getValueType(0) == MVT::i1) {
  assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1))(static_cast <bool> (!(cast<ConstantSDNode>(N)->
getZExtValue() >> 1)) ? void (0) : __assert_fail ("!(cast<ConstantSDNode>(N)->getZExtValue() >> 1)"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 746, __extension__
 __PRETTY_FUNCTION__));
  unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
                    ? Hexagon::PS_true
                    : Hexagon::PS_false;
  ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));
  return;
}

SelectCode(N);
755}

757void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
MachineFrameInfo &MFI = MF->getFrameInfo();
const HexagonFrameLowering *HFI = HST->getFrameLowering();
int FX = cast<FrameIndexSDNode>(N)->getIndex();
Align StkA = HFI->getStackAlign();
Align MaxA = MFI.getMaxAlign();
SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);
SDLoc DL(N);
SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
SDNode *R = nullptr;

// Use PS_fi when:
// - the object is fixed, or
// - there are no objects with higher-than-default alignment, or
// - there are no dynamically allocated objects.
// Otherwise, use PS_fia.
if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
  R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
} else {
  auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
  Register AR = HMFI.getStackAlignBaseReg();
  SDValue CH = CurDAG->getEntryNode();
  SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
  R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
}

ReplaceNode(N, R);
784}

786void HexagonDAGToDAGISel::SelectAddSubCarry(SDNode *N) {
unsigned OpcCarry = N->getOpcode() == HexagonISD::ADDC ? Hexagon::A4_addp_c
                                                       : Hexagon::A4_subp_c;
SDNode *C = CurDAG->getMachineNode(OpcCarry, SDLoc(N), N->getVTList(),
                                   { N->getOperand(0), N->getOperand(1),
                                     N->getOperand(2) });
ReplaceNode(N, C);
793}

795void HexagonDAGToDAGISel::SelectVAlign(SDNode *N) {
MVT ResTy = N->getValueType(0).getSimpleVT();
if (HST->isHVXVectorType(ResTy, true))
  return SelectHvxVAlign(N);

const SDLoc &dl(N);
unsigned VecLen = ResTy.getSizeInBits();
if (VecLen == 32) {
  SDValue Ops[] = {
    CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
    N->getOperand(0),
    CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
    N->getOperand(1),
    CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
  };
  SDNode *R = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
                                     MVT::i64, Ops);

  // Shift right by "(Addr & 0x3) * 8" bytes.
  SDNode *C;
  SDValue M0 = CurDAG->getTargetConstant(0x18, dl, MVT::i32);
  SDValue M1 = CurDAG->getTargetConstant(0x03, dl, MVT::i32);
  if (HST->useCompound()) {
    C = CurDAG->getMachineNode(Hexagon::S4_andi_asl_ri, dl, MVT::i32,
                               M0, N->getOperand(2), M1);
  } else {
    SDNode *T = CurDAG->getMachineNode(Hexagon::S2_asl_i_r, dl, MVT::i32,
                                       N->getOperand(2), M1);
    C = CurDAG->getMachineNode(Hexagon::A2_andir, dl, MVT::i32,
                               SDValue(T, 0), M0);
  }
  SDNode *S = CurDAG->getMachineNode(Hexagon::S2_lsr_r_p, dl, MVT::i64,
                                     SDValue(R, 0), SDValue(C, 0));
  SDValue E = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo, dl, ResTy,
                                             SDValue(S, 0));
  ReplaceNode(N, E.getNode());
} else {
  assert(VecLen == 64)(static_cast <bool> (VecLen == 64) ? void (0) : __assert_fail
 ("VecLen == 64", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 832, __extension__ __PRETTY_FUNCTION__));
  SDNode *Pu = CurDAG->getMachineNode(Hexagon::C2_tfrrp, dl, MVT::v8i1,
                                      N->getOperand(2));
  SDNode *VA = CurDAG->getMachineNode(Hexagon::S2_valignrb, dl, ResTy,
                                      N->getOperand(0), N->getOperand(1),
                                      SDValue(Pu,0));
  ReplaceNode(N, VA);
}
840}

842void HexagonDAGToDAGISel::SelectVAlignAddr(SDNode *N) {
const SDLoc &dl(N);
SDValue A = N->getOperand(1);
int Mask = -cast<ConstantSDNode>(A.getNode())->getSExtValue();
assert(isPowerOf2_32(-Mask))(static_cast <bool> (isPowerOf2_32(-Mask)) ? void (0) :
 __assert_fail ("isPowerOf2_32(-Mask)", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 846, __extension__ __PRETTY_FUNCTION__));

SDValue M = CurDAG->getTargetConstant(Mask, dl, MVT::i32);
SDNode *AA = CurDAG->getMachineNode(Hexagon::A2_andir, dl, MVT::i32,
                                    N->getOperand(0), M);
ReplaceNode(N, AA);
852}

854// Handle these nodes here to avoid having to write patterns for all
855// combinations of input/output types. In all cases, the resulting
856// instruction is the same.
857void HexagonDAGToDAGISel::SelectTypecast(SDNode *N) {
SDValue Op = N->getOperand(0);
MVT OpTy = Op.getValueType().getSimpleVT();
SDNode *T = CurDAG->MorphNodeTo(N, N->getOpcode(),
                                CurDAG->getVTList(OpTy), {Op});
ReplaceNode(T, Op.getNode());
863}

865void HexagonDAGToDAGISel::SelectP2D(SDNode *N) {
MVT ResTy = N->getValueType(0).getSimpleVT();
SDNode *T = CurDAG->getMachineNode(Hexagon::C2_mask, SDLoc(N), ResTy,
                                   N->getOperand(0));
ReplaceNode(N, T);
870}

872void HexagonDAGToDAGISel::SelectD2P(SDNode *N) {
const SDLoc &dl(N);
MVT ResTy = N->getValueType(0).getSimpleVT();
SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
SDNode *T = CurDAG->getMachineNode(Hexagon::A4_vcmpbgtui, dl, ResTy,
                                   N->getOperand(0), Zero);
ReplaceNode(N, T);
879}

881void HexagonDAGToDAGISel::SelectV2Q(SDNode *N) {
const SDLoc &dl(N);
MVT ResTy = N->getValueType(0).getSimpleVT();
// The argument to V2Q should be a single vector.
MVT OpTy = N->getOperand(0).getValueType().getSimpleVT(); (void)OpTy;
assert(HST->getVectorLength() * 8 == OpTy.getSizeInBits())(static_cast <bool> (HST->getVectorLength() * 8 == OpTy
.getSizeInBits()) ? void (0) : __assert_fail ("HST->getVectorLength() * 8 == OpTy.getSizeInBits()"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 886, __extension__
 __PRETTY_FUNCTION__));

SDValue C = CurDAG->getTargetConstant(-1, dl, MVT::i32);
SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);
SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandvrt, dl, ResTy,
                                   N->getOperand(0), SDValue(R,0));
ReplaceNode(N, T);
893}

895void HexagonDAGToDAGISel::SelectQ2V(SDNode *N) {
const SDLoc &dl(N);
MVT ResTy = N->getValueType(0).getSimpleVT();
// The result of V2Q should be a single vector.
assert(HST->getVectorLength() * 8 == ResTy.getSizeInBits())(static_cast <bool> (HST->getVectorLength() * 8 == ResTy
.getSizeInBits()) ? void (0) : __assert_fail ("HST->getVectorLength() * 8 == ResTy.getSizeInBits()"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 899, __extension__
 __PRETTY_FUNCTION__));

SDValue C = CurDAG->getTargetConstant(-1, dl, MVT::i32);
SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);
SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandqrt, dl, ResTy,
                                   N->getOperand(0), SDValue(R,0));
ReplaceNode(N, T);
906}

908void HexagonDAGToDAGISel::Select(SDNode *N) {
if (N->isMachineOpcode())
  return N->setNodeId(-1);  // Already selected.

auto isHvxOp = [this](SDNode *N) {
  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
    if (HST->isHVXVectorType(N->getValueType(i), true))
      return true;
  }
  for (SDValue I : N->ops()) {
    if (HST->isHVXVectorType(I.getValueType(), true))
      return true;
  }
  return false;
};

if (HST->useHVXOps() && isHvxOp(N)) {
  switch (N->getOpcode()) {
  case ISD::EXTRACT_SUBVECTOR:  return SelectHvxExtractSubvector(N);
  case ISD::VECTOR_SHUFFLE:     return SelectHvxShuffle(N);

  case HexagonISD::VROR:        return SelectHvxRor(N);
  }
}

switch (N->getOpcode()) {
case ISD::Constant:             return SelectConstant(N);
case ISD::ConstantFP:           return SelectConstantFP(N);
case ISD::FrameIndex:           return SelectFrameIndex(N);
case ISD::SHL:                  return SelectSHL(N);
case ISD::LOAD:                 return SelectLoad(N);
case ISD::STORE:                return SelectStore(N);
case ISD::INTRINSIC_W_CHAIN:    return SelectIntrinsicWChain(N);
case ISD::INTRINSIC_WO_CHAIN:   return SelectIntrinsicWOChain(N);
case ISD::EXTRACT_SUBVECTOR:    return SelectExtractSubvector(N);

case HexagonISD::ADDC:
case HexagonISD::SUBC:          return SelectAddSubCarry(N);
case HexagonISD::VALIGN:        return SelectVAlign(N);
case HexagonISD::VALIGNADDR:    return SelectVAlignAddr(N);
case HexagonISD::TYPECAST:      return SelectTypecast(N);
case HexagonISD::P2D:           return SelectP2D(N);
case HexagonISD::D2P:           return SelectD2P(N);
case HexagonISD::Q2V:           return SelectQ2V(N);
case HexagonISD::V2Q:           return SelectV2Q(N);
}

SelectCode(N);
956}

958bool HexagonDAGToDAGISel::
959SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
                           std::vector<SDValue> &OutOps) {
SDValue Inp = Op, Res;

switch (ConstraintID) {
default:
  return true;
case InlineAsm::Constraint_o: // Offsetable.
case InlineAsm::Constraint_v: // Not offsetable.
case InlineAsm::Constraint_m: // Memory.
  if (SelectAddrFI(Inp, Res))
    OutOps.push_back(Res);
  else
    OutOps.push_back(Inp);
  break;
}

OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
return false;
978}


981static bool isMemOPCandidate(SDNode *I, SDNode *U) {
// I is an operand of U. Check if U is an arithmetic (binary) operation
// usable in a memop, where the other operand is a loaded value, and the
// result of U is stored in the same location.

if (!U->hasOneUse())
  return false;
unsigned Opc = U->getOpcode();
switch (Opc) {
  case ISD::ADD:
  case ISD::SUB:
  case ISD::AND:
  case ISD::OR:
    break;
  default:
    return false;
}

SDValue S0 = U->getOperand(0);
SDValue S1 = U->getOperand(1);
SDValue SY = (S0.getNode() == I) ? S1 : S0;

SDNode *UUse = *U->use_begin();
if (UUse->getNumValues() != 1)
  return false;

// Check if one of the inputs to U is a load instruction and the output
// is used by a store instruction. If so and they also have the same
// base pointer, then don't preoprocess this node sequence as it
// can be matched to a memop.
SDNode *SYNode = SY.getNode();
if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {
  SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
  SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
  if (LDBasePtr == STBasePtr)
    return true;
}
return false;
1019}


1022// Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
1023//            (or (select c 0 y) z)  ->  (select c z (or y z))
1024void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
SelectionDAG &DAG = *CurDAG;

for (auto *I : Nodes) {
  if (I->getOpcode() != ISD::OR)
    continue;

  auto IsZero = [] (const SDValue &V) -> bool {
    if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
      return SC->isZero();
    return false;
  };
  auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
    if (Op.getOpcode() != ISD::SELECT)
      return false;
    return IsZero(Op.getOperand(1)) || IsZero(Op.getOperand(2));
  };

  SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
  EVT VT = I->getValueType(0);
  bool SelN0 = IsSelect0(N0);
  SDValue SOp = SelN0 ? N0 : N1;
  SDValue VOp = SelN0 ? N1 : N0;

  if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
    SDValue SC = SOp.getOperand(0);
    SDValue SX = SOp.getOperand(1);
    SDValue SY = SOp.getOperand(2);
    SDLoc DLS = SOp;
    if (IsZero(SY)) {
      SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
      SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
      DAG.ReplaceAllUsesWith(I, NewSel.getNode());
    } else if (IsZero(SX)) {
      SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
      SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
      DAG.ReplaceAllUsesWith(I, NewSel.getNode());
    }
  }
}
1064}

1066// Transform: (store ch val (add x (add (shl y c) e)))
1067//        to: (store ch val (add x (shl (add y d) c))),
1068// where e = (shl d c) for some integer d.
1069// The purpose of this is to enable generation of loads/stores with
1070// shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1071// value c must be 0, 1 or 2.
1072void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
SelectionDAG &DAG = *CurDAG;

for (auto *I : Nodes) {
  if (I->getOpcode() != ISD::STORE)
    continue;

  // I matched: (store ch val Off)
  SDValue Off = I->getOperand(2);
  // Off needs to match: (add x (add (shl y c) (shl d c))))
  if (Off.getOpcode() != ISD::ADD)
    continue;
  // Off matched: (add x T0)
  SDValue T0 = Off.getOperand(1);
  // T0 needs to match: (add T1 T2):
  if (T0.getOpcode() != ISD::ADD)
    continue;
  // T0 matched: (add T1 T2)
  SDValue T1 = T0.getOperand(0);
  SDValue T2 = T0.getOperand(1);
  // T1 needs to match: (shl y c)
  if (T1.getOpcode() != ISD::SHL)
    continue;
  SDValue C = T1.getOperand(1);
  ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());
  if (CN == nullptr)
    continue;
  unsigned CV = CN->getZExtValue();
  if (CV > 2)
    continue;
  // T2 needs to match e, where e = (shl d c) for some d.
  ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());
  if (EN == nullptr)
    continue;
  unsigned EV = EN->getZExtValue();
  if (EV % (1 << CV) != 0)
    continue;
  unsigned DV = EV / (1 << CV);

  // Replace T0 with: (shl (add y d) c)
  SDLoc DL = SDLoc(I);
  EVT VT = T0.getValueType();
  SDValue D = DAG.getConstant(DV, DL, VT);
  // NewAdd = (add y d)
  SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
  // NewShl = (shl NewAdd c)
  SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
  ReplaceNode(T0.getNode(), NewShl.getNode());
}
1121}

1123// Transform: (load ch (add x (and (srl y c) Mask)))
1124//        to: (load ch (add x (shl (srl y d) d-c)))
1125// where
1126// Mask = 00..0 111..1 0.0
1127//          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1128//          |     +-------- 1s
1129//          +-------------- at most c 0s
1130// Motivating example:
1131// DAG combiner optimizes (add x (shl (srl y 5) 2))
1132//                     to (add x (and (srl y 3) 1FFFFFFC))
1133// which results in a constant-extended and(##...,lsr). This transformation
1134// undoes this simplification for cases where the shl can be folded into
1135// an addressing mode.
1136void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
SelectionDAG &DAG = *CurDAG;

for (SDNode *N : Nodes) {
  unsigned Opc = N->getOpcode();
  if (Opc != ISD::LOAD && Opc != ISD::STORE)
3
←
Assuming 'Opc' is equal to LOAD→
    continue;
  SDValue Addr = Opc3.1
'Opc' is equal to LOAD
1
'Opc' is equal to LOAD
1
'Opc' is equal to LOAD
 == ISD::LOAD ? N->getOperand(1) : N->getOperand(2);
4
←
'?' condition is true→
  // Addr must match: (add x T0)
  if (Addr.getOpcode() != ISD::ADD)
5
←
Assuming the condition is false→
6
←
Taking false branch→
    continue;
  SDValue T0 = Addr.getOperand(1);
  // T0 must match: (and T1 Mask)
  if (T0.getOpcode() != ISD::AND)
7
←
Assuming the condition is false→
8
←
Taking false branch→
    continue;

  // We have an AND.
  //
  // Check the first operand. It must be: (srl y c).
  SDValue S = T0.getOperand(0);
  if (S.getOpcode() != ISD::SRL)
9
←
Assuming the condition is false→
10
←
Taking false branch→
    continue;
  ConstantSDNode *SN = dyn_cast<ConstantSDNode>(S.getOperand(1).getNode());
11
←
Assuming the object is a 'CastReturnType'→
  if (SN == nullptr)
12
←
Taking false branch→
    continue;
  if (SN->getAPIntValue().getBitWidth() != 32)
13
←
Assuming the condition is false→
14
←
Taking false branch→
    continue;
  uint32_t CV = SN->getZExtValue();

  // Check the second operand: the supposed mask.
  ConstantSDNode *MN = dyn_cast<ConstantSDNode>(T0.getOperand(1).getNode());
15
←
Assuming the object is a 'CastReturnType'→
  if (MN == nullptr)
16
←
Taking false branch→
    continue;
  if (MN->getAPIntValue().getBitWidth() != 32)
17
←
Assuming the condition is false→
18
←
Taking false branch→
    continue;
  uint32_t Mask = MN->getZExtValue();
  // Examine the mask.
  uint32_t TZ = countTrailingZeros(Mask);
19
←
Calling 'countTrailingZeros<unsigned int>'→
29
←
Returning from 'countTrailingZeros<unsigned int>'→
30
←
'TZ' initialized to 32→
  uint32_t M1 = countTrailingOnes(Mask >> TZ);
31
←
The result of the right shift is undefined due to shifting by '32', which is greater or equal to the width of type 'uint32_t'
  uint32_t LZ = countLeadingZeros(Mask);
  // Trailing zeros + middle ones + leading zeros must equal the width.
  if (TZ + M1 + LZ != 32)
    continue;
  // The number of trailing zeros will be encoded in the addressing mode.
  if (TZ > 2)
    continue;
  // The number of leading zeros must be at most c.
  if (LZ > CV)
    continue;

  // All looks good.
  SDValue Y = S.getOperand(0);
  EVT VT = Addr.getValueType();
  SDLoc dl(S);
  // TZ = D-C, so D = TZ+C.
  SDValue D = DAG.getConstant(TZ+CV, dl, VT);
  SDValue DC = DAG.getConstant(TZ, dl, VT);
  SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);
  SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);
  ReplaceNode(T0.getNode(), NewShl.getNode());
}
1197}

1199// Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1200//                                                  (op ... 1 ...))
1201void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
SelectionDAG &DAG = *CurDAG;

for (SDNode *N : Nodes) {
  unsigned Opc = N->getOpcode();
  if (Opc != ISD::ZERO_EXTEND)
    continue;
  SDValue OpI1 = N->getOperand(0);
  EVT OpVT = OpI1.getValueType();
  if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
    continue;
  for (auto I = N->use_begin(), E = N->use_end(); I != E; ++I) {
    SDNode *U = *I;
    if (U->getNumValues() != 1)
      continue;
    EVT UVT = U->getValueType(0);
    if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)
      continue;
    // Do not generate select for all i1 vector type.
    if (UVT.isVector() && UVT.getVectorElementType() == MVT::i1)
      continue;
    if (isMemOPCandidate(N, U))
      continue;

    // Potentially simplifiable operation.
    unsigned I1N = I.getOperandNo();
    SmallVector<SDValue,2> Ops(U->getNumOperands());
    for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)
      Ops[i] = U->getOperand(i);
    EVT BVT = Ops[I1N].getValueType();

    const SDLoc &dl(U);
    SDValue C0 = DAG.getConstant(0, dl, BVT);
    SDValue C1 = DAG.getConstant(1, dl, BVT);
    SDValue If0, If1;

    if (isa<MachineSDNode>(U)) {
      unsigned UseOpc = U->getMachineOpcode();
      Ops[I1N] = C0;
      If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
      Ops[I1N] = C1;
      If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
    } else {
      unsigned UseOpc = U->getOpcode();
      Ops[I1N] = C0;
      If0 = DAG.getNode(UseOpc, dl, UVT, Ops);
      Ops[I1N] = C1;
      If1 = DAG.getNode(UseOpc, dl, UVT, Ops);
    }
    // We're generating a SELECT way after legalization, so keep the types
    // simple.
    unsigned UW = UVT.getSizeInBits();
    EVT SVT = (UW == 32 || UW == 64) ? MVT::getIntegerVT(UW) : UVT;
    SDValue Sel = DAG.getNode(ISD::SELECT, dl, SVT, OpI1,
                              DAG.getBitcast(SVT, If1),
                              DAG.getBitcast(SVT, If0));
    SDValue Ret = DAG.getBitcast(UVT, Sel);
    DAG.ReplaceAllUsesWith(U, Ret.getNode());
  }
}
1261}

1263void HexagonDAGToDAGISel::PreprocessISelDAG() {
// Repack all nodes before calling each preprocessing function,
// because each of them can modify the set of nodes.
auto getNodes = [this]() -> std::vector<SDNode *> {
  std::vector<SDNode *> T;
  T.reserve(CurDAG->allnodes_size());
  for (SDNode &N : CurDAG->allnodes())
    T.push_back(&N);
  return T;
};

if (HST->useHVXOps())
1
Taking false branch→
  PreprocessHvxISelDAG();

// Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
//            (or (select c 0 y) z)  ->  (select c z (or y z))
ppSimplifyOrSelect0(getNodes());

// Transform: (store ch val (add x (add (shl y c) e)))
//        to: (store ch val (add x (shl (add y d) c))),
// where e = (shl d c) for some integer d.
// The purpose of this is to enable generation of loads/stores with
// shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
// value c must be 0, 1 or 2.
ppAddrReorderAddShl(getNodes());

// Transform: (load ch (add x (and (srl y c) Mask)))
//        to: (load ch (add x (shl (srl y d) d-c)))
// where
// Mask = 00..0 111..1 0.0
//          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
//          |     +-------- 1s
//          +-------------- at most c 0s
// Motivating example:
// DAG combiner optimizes (add x (shl (srl y 5) 2))
//                     to (add x (and (srl y 3) 1FFFFFFC))
// which results in a constant-extended and(##...,lsr). This transformation
// undoes this simplification for cases where the shl can be folded into
// an addressing mode.
ppAddrRewriteAndSrl(getNodes());
2
←
Calling 'HexagonDAGToDAGISel::ppAddrRewriteAndSrl'→

// Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
//                                                  (op ... 1 ...))
ppHoistZextI1(getNodes());

DEBUG_WITH_TYPE("isel", {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Preprocessed (Hexagon) selection DAG:"
; CurDAG->dump(); }; } } while (false)
  dbgs() << "Preprocessed (Hexagon) selection DAG:";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Preprocessed (Hexagon) selection DAG:"
; CurDAG->dump(); }; } } while (false)
  CurDAG->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Preprocessed (Hexagon) selection DAG:"
; CurDAG->dump(); }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Preprocessed (Hexagon) selection DAG:"
; CurDAG->dump(); }; } } while (false);

if (EnableAddressRebalancing) {
  rebalanceAddressTrees();

  DEBUG_WITH_TYPE("isel", {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Address tree balanced selection DAG:"
; CurDAG->dump(); }; } } while (false)
    dbgs() << "Address tree balanced selection DAG:";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Address tree balanced selection DAG:"
; CurDAG->dump(); }; } } while (false)
    CurDAG->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Address tree balanced selection DAG:"
; CurDAG->dump(); }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("isel")) { { dbgs() << "Address tree balanced selection DAG:"
; CurDAG->dump(); }; } } while (false);
}
1321}

1323void HexagonDAGToDAGISel::emitFunctionEntryCode() {
auto &HST = MF->getSubtarget<HexagonSubtarget>();
auto &HFI = *HST.getFrameLowering();
if (!HFI.needsAligna(*MF))
  return;

MachineFrameInfo &MFI = MF->getFrameInfo();
MachineBasicBlock *EntryBB = &MF->front();
Align EntryMaxA = MFI.getMaxAlign();

// Reserve the first non-volatile register.
Register AP = 0;
auto &HRI = *HST.getRegisterInfo();
BitVector Reserved = HRI.getReservedRegs(*MF);
for (const MCPhysReg *R = HRI.getCalleeSavedRegs(MF); *R; ++R) {
  if (Reserved[*R])
    continue;
  AP = *R;
  break;
}
assert(AP.isValid() && "Couldn't reserve stack align register")(static_cast <bool> (AP.isValid() && "Couldn't reserve stack align register"
) ? void (0) : __assert_fail ("AP.isValid() && \"Couldn't reserve stack align register\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1343, __extension__
 __PRETTY_FUNCTION__));
BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AP)
    .addImm(EntryMaxA.value());
MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseReg(AP);
1347}

1349void HexagonDAGToDAGISel::updateAligna() {
auto &HFI = *MF->getSubtarget<HexagonSubtarget>().getFrameLowering();
if (!HFI.needsAligna(*MF))
  return;
auto *AlignaI = const_cast<MachineInstr*>(HFI.getAlignaInstr(*MF));
assert(AlignaI != nullptr)(static_cast <bool> (AlignaI != nullptr) ? void (0) : __assert_fail
 ("AlignaI != nullptr", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 1354, __extension__ __PRETTY_FUNCTION__));
unsigned MaxA = MF->getFrameInfo().getMaxAlign().value();
if (AlignaI->getOperand(1).getImm() < MaxA)
  AlignaI->getOperand(1).setImm(MaxA);
1358}

1360// Match a frame index that can be used in an addressing mode.
1361bool HexagonDAGToDAGISel::SelectAddrFI(SDValue &N, SDValue &R) {
if (N.getOpcode() != ISD::FrameIndex)
  return false;
auto &HFI = *HST->getFrameLowering();
MachineFrameInfo &MFI = MF->getFrameInfo();
int FX = cast<FrameIndexSDNode>(N)->getIndex();
if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))
  return false;
R = CurDAG->getTargetFrameIndex(FX, MVT::i32);
return true;
1371}

1373inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
return SelectGlobalAddress(N, R, false, Align(1));
1375}

1377inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
return SelectGlobalAddress(N, R, true, Align(1));
1379}

1381inline bool HexagonDAGToDAGISel::SelectAnyImm(SDValue &N, SDValue &R) {
return SelectAnyImmediate(N, R, Align(1));
1383}

1385inline bool HexagonDAGToDAGISel::SelectAnyImm0(SDValue &N, SDValue &R) {
return SelectAnyImmediate(N, R, Align(1));
1387}
1388inline bool HexagonDAGToDAGISel::SelectAnyImm1(SDValue &N, SDValue &R) {
return SelectAnyImmediate(N, R, Align(2));
1390}
1391inline bool HexagonDAGToDAGISel::SelectAnyImm2(SDValue &N, SDValue &R) {
return SelectAnyImmediate(N, R, Align(4));
1393}
1394inline bool HexagonDAGToDAGISel::SelectAnyImm3(SDValue &N, SDValue &R) {
return SelectAnyImmediate(N, R, Align(8));
1396}

1398inline bool HexagonDAGToDAGISel::SelectAnyInt(SDValue &N, SDValue &R) {
EVT T = N.getValueType();
if (!T.isInteger() || T.getSizeInBits() != 32 || !isa<ConstantSDNode>(N))
  return false;
int32_t V = cast<const ConstantSDNode>(N)->getZExtValue();
R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());
return true;
1405}

1407bool HexagonDAGToDAGISel::SelectAnyImmediate(SDValue &N, SDValue &R,
                                           Align Alignment) {
switch (N.getOpcode()) {
case ISD::Constant: {
  if (N.getValueType() != MVT::i32)
    return false;
  int32_t V = cast<const ConstantSDNode>(N)->getZExtValue();
  if (!isAligned(Alignment, V))
    return false;
  R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());
  return true;
}
case HexagonISD::JT:
case HexagonISD::CP:
  // These are assumed to always be aligned at least 8-byte boundary.
  if (Alignment > Align(8))
    return false;
  R = N.getOperand(0);
  return true;
case ISD::ExternalSymbol:
  // Symbols may be aligned at any boundary.
  if (Alignment > Align(1))
    return false;
  R = N;
  return true;
case ISD::BlockAddress:
  // Block address is always aligned at least 4-byte boundary.
  if (Alignment > Align(4) ||
      !isAligned(Alignment, cast<BlockAddressSDNode>(N)->getOffset()))
    return false;
  R = N;
  return true;
}

if (SelectGlobalAddress(N, R, false, Alignment) ||
    SelectGlobalAddress(N, R, true, Alignment))
  return true;

return false;
1446}

1448bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
                                            bool UseGP, Align Alignment) {
switch (N.getOpcode()) {
case ISD::ADD: {
  SDValue N0 = N.getOperand(0);
  SDValue N1 = N.getOperand(1);
  unsigned GAOpc = N0.getOpcode();
  if (UseGP && GAOpc != HexagonISD::CONST32_GP)
    return false;
  if (!UseGP && GAOpc != HexagonISD::CONST32)
    return false;
  if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
    if (!isAligned(Alignment, Const->getZExtValue()))
      return false;
    SDValue Addr = N0.getOperand(0);
    if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
      if (GA->getOpcode() == ISD::TargetGlobalAddress) {
        uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
        R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
                                           N.getValueType(), NewOff);
        return true;
      }
    }
  }
  break;
}
case HexagonISD::CP:
case HexagonISD::JT:
case HexagonISD::CONST32:
  // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
  // want in the instruction.
  if (!UseGP)
    R = N.getOperand(0);
  return !UseGP;
case HexagonISD::CONST32_GP:
  if (UseGP)
    R = N.getOperand(0);
  return UseGP;
default:
  return false;
}

return false;
1491}

1493bool HexagonDAGToDAGISel::DetectUseSxtw(SDValue &N, SDValue &R) {
// This (complex pattern) function is meant to detect a sign-extension
// i32->i64 on a per-operand basis. This would allow writing single
// patterns that would cover a number of combinations of different ways
// a sign-extensions could be written. For example:
//   (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)
// could match either one of these:
//   (mul (sext x) (sext_inreg y))
//   (mul (sext-load *p) (sext_inreg y))
//   (mul (sext_inreg x) (sext y))
// etc.
//
// The returned value will have type i64 and its low word will
// contain the value being extended. The high bits are not specified.
// The returned type is i64 because the original type of N was i64,
// but the users of this function should only use the low-word of the
// result, e.g.
//  (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))

if (N.getValueType() != MVT::i64)
  return false;
unsigned Opc = N.getOpcode();
switch (Opc) {
  case ISD::SIGN_EXTEND:
  case ISD::SIGN_EXTEND_INREG: {
    // sext_inreg has the source type as a separate operand.
    EVT T = Opc == ISD::SIGN_EXTEND
              ? N.getOperand(0).getValueType()
              : cast<VTSDNode>(N.getOperand(1))->getVT();
    unsigned SW = T.getSizeInBits();
    if (SW == 32)
      R = N.getOperand(0);
    else if (SW < 32)
      R = N;
    else
      return false;
    break;
  }
  case ISD::LOAD: {
    LoadSDNode *L = cast<LoadSDNode>(N);
    if (L->getExtensionType() != ISD::SEXTLOAD)
      return false;
    // All extending loads extend to i32, so even if the value in
    // memory is shorter than 32 bits, it will be i32 after the load.
    if (L->getMemoryVT().getSizeInBits() > 32)
      return false;
    R = N;
    break;
  }
  case ISD::SRA: {
    auto *S = dyn_cast<ConstantSDNode>(N.getOperand(1));
    if (!S || S->getZExtValue() != 32)
      return false;
    R = N;
    break;
  }
  default:
    return false;
}
EVT RT = R.getValueType();
if (RT == MVT::i64)
  return true;
assert(RT == MVT::i32)(static_cast <bool> (RT == MVT::i32) ? void (0) : __assert_fail
 ("RT == MVT::i32", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 1555, __extension__ __PRETTY_FUNCTION__));
// This is only to produce a value of type i64. Do not rely on the
// high bits produced by this.
const SDLoc &dl(N);
SDValue Ops[] = {
  CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
  R, CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
  R, CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
};
SDNode *T = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
                                   MVT::i64, Ops);
R = SDValue(T, 0);
return true;
1568}

1570bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,
    SDValue &Src) {
unsigned Opc = Val.getOpcode();
switch (Opc) {
case ISD::SIGN_EXTEND:
case ISD::ZERO_EXTEND:
case ISD::ANY_EXTEND: {
  const SDValue &Op0 = Val.getOperand(0);
  EVT T = Op0.getValueType();
  if (T.isInteger() && T.getSizeInBits() == NumBits) {
    Src = Op0;
    return true;
  }
  break;
}
case ISD::SIGN_EXTEND_INREG:
case ISD::AssertSext:
case ISD::AssertZext:
  if (Val.getOperand(0).getValueType().isInteger()) {
    VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
    if (T->getVT().getSizeInBits() == NumBits) {
      Src = Val.getOperand(0);
      return true;
    }
  }
  break;
case ISD::AND: {
  // Check if this is an AND with NumBits of lower bits set to 1.
  uint64_t Mask = (1ULL << NumBits) - 1;
  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
    if (C->getZExtValue() == Mask) {
      Src = Val.getOperand(1);
      return true;
    }
  }
  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
    if (C->getZExtValue() == Mask) {
      Src = Val.getOperand(0);
      return true;
    }
  }
  break;
}
case ISD::OR:
case ISD::XOR: {
  // OR/XOR with the lower NumBits bits set to 0.
  uint64_t Mask = (1ULL << NumBits) - 1;
  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
    if ((C->getZExtValue() & Mask) == 0) {
      Src = Val.getOperand(1);
      return true;
    }
  }
  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
    if ((C->getZExtValue() & Mask) == 0) {
      Src = Val.getOperand(0);
      return true;
    }
  }
  break;
}
default:
  break;
}
return false;
1635}

1637bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
return N->getAlign().value() >= N->getMemoryVT().getStoreSize();
1639}

1641bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {
unsigned StackSize = MF->getFrameInfo().estimateStackSize(*MF);
switch (N->getMemoryVT().getStoreSize()) {
  case 1:
    return StackSize <= 56;   // 1*2^6 - 8
  case 2:
    return StackSize <= 120;  // 2*2^6 - 8
  case 4:
    return StackSize <= 248;  // 4*2^6 - 8
  default:
    return false;
}
1653}

1655// Return true when the given node fits in a positive half word.
1656bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {
  int64_t V = CN->getSExtValue();
  return V > 0 && isInt<16>(V);
}
if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
  const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));
  return VN->getVT().getSizeInBits() <= 16;
}
return false;
1666}

1668bool HexagonDAGToDAGISel::hasOneUse(const SDNode *N) const {
return !CheckSingleUse || N->hasOneUse();
1670}

1672////////////////////////////////////////////////////////////////////////////////
1673// Rebalancing of address calculation trees

1675static bool isOpcodeHandled(const SDNode *N) {
switch (N->getOpcode()) {
  case ISD::ADD:
  case ISD::MUL:
    return true;
  case ISD::SHL:
    // We only handle constant shifts because these can be easily flattened
    // into multiplications by 2^Op1.
    return isa<ConstantSDNode>(N->getOperand(1).getNode());
  default:
    return false;
}
1687}

1689/// Return the weight of an SDNode
1690int HexagonDAGToDAGISel::getWeight(SDNode *N) {
if (!isOpcodeHandled(N))
  return 1;
assert(RootWeights.count(N) && "Cannot get weight of unseen root!")(static_cast <bool> (RootWeights.count(N) && "Cannot get weight of unseen root!"
) ? void (0) : __assert_fail ("RootWeights.count(N) && \"Cannot get weight of unseen root!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1693, __extension__
 __PRETTY_FUNCTION__));
assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!")(static_cast <bool> (RootWeights[N] != -1 && "Cannot get weight of unvisited root!"
) ? void (0) : __assert_fail ("RootWeights[N] != -1 && \"Cannot get weight of unvisited root!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1694, __extension__
 __PRETTY_FUNCTION__));
assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!")(static_cast <bool> (RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!"
) ? void (0) : __assert_fail ("RootWeights[N] != -2 && \"Cannot get weight of RAWU'd root!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1695, __extension__
 __PRETTY_FUNCTION__));
return RootWeights[N];
1697}

1699int HexagonDAGToDAGISel::getHeight(SDNode *N) {
if (!isOpcodeHandled(N))
  return 0;
assert(RootWeights.count(N) && RootWeights[N] >= 0 &&(static_cast <bool> (RootWeights.count(N) && RootWeights
[N] >= 0 && "Cannot query height of unvisited/RAUW'd node!"
) ? void (0) : __assert_fail ("RootWeights.count(N) && RootWeights[N] >= 0 && \"Cannot query height of unvisited/RAUW'd node!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1703, __extension__
 __PRETTY_FUNCTION__))
    "Cannot query height of unvisited/RAUW'd node!")(static_cast <bool> (RootWeights.count(N) && RootWeights
[N] >= 0 && "Cannot query height of unvisited/RAUW'd node!"
) ? void (0) : __assert_fail ("RootWeights.count(N) && RootWeights[N] >= 0 && \"Cannot query height of unvisited/RAUW'd node!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1703, __extension__
 __PRETTY_FUNCTION__));
return RootHeights[N];
1705}

1707namespace {
1708struct WeightedLeaf {
SDValue Value;
int Weight;
int InsertionOrder;

WeightedLeaf() {}

WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
  Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
  assert(Weight >= 0 && "Weight must be >= 0")(static_cast <bool> (Weight >= 0 && "Weight must be >= 0"
) ? void (0) : __assert_fail ("Weight >= 0 && \"Weight must be >= 0\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1717, __extension__
 __PRETTY_FUNCTION__));
}

static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
  assert(A.Value.getNode() && B.Value.getNode())(static_cast <bool> (A.Value.getNode() && B.Value
.getNode()) ? void (0) : __assert_fail ("A.Value.getNode() && B.Value.getNode()"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1721, __extension__
 __PRETTY_FUNCTION__));
  return A.Weight == B.Weight ?
          (A.InsertionOrder > B.InsertionOrder) :
          (A.Weight > B.Weight);
}
1726};

1728/// A specialized priority queue for WeigthedLeaves. It automatically folds
1729/// constants and allows removal of non-top elements while maintaining the
1730/// priority order.
1731class LeafPrioQueue {
SmallVector<WeightedLeaf, 8> Q;
bool HaveConst;
WeightedLeaf ConstElt;
unsigned Opcode;

1737public:
bool empty() {
  return (!HaveConst && Q.empty());
}

size_t size() {
  return Q.size() + HaveConst;
}

bool hasConst() {
  return HaveConst;
}

const WeightedLeaf &top() {
  if (HaveConst)
    return ConstElt;
  return Q.front();
}

WeightedLeaf pop() {
  if (HaveConst) {
    HaveConst = false;
    return ConstElt;
  }
  std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
  return Q.pop_back_val();
}

void push(WeightedLeaf L, bool SeparateConst=true) {
  if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {
    if (Opcode == ISD::MUL &&
        cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)
      return;
    if (Opcode == ISD::ADD &&
        cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
      return;

    HaveConst = true;
    ConstElt = L;
  } else {
    Q.push_back(L);
    std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
  }
}

/// Push L to the bottom of the queue regardless of its weight. If L is
/// constant, it will not be folded with other constants in the queue.
void pushToBottom(WeightedLeaf L) {
  L.Weight = 1000;
  push(L, false);
}

/// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
/// lowest weight and remove it from the queue.
WeightedLeaf findSHL(uint64_t MaxAmount);

WeightedLeaf findMULbyConst();

LeafPrioQueue(unsigned Opcode) :
  HaveConst(false), Opcode(Opcode) { }
1797};
1798} // end anonymous namespace

1800WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
int ResultPos;
WeightedLeaf Result;

for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
  const WeightedLeaf &L = Q[Pos];
  const SDValue &Val = L.Value;
  if (Val.getOpcode() != ISD::SHL ||
      !isa<ConstantSDNode>(Val.getOperand(1)) ||
      Val.getConstantOperandVal(1) > MaxAmount)
    continue;
  if (!Result.Value.getNode() || Result.Weight > L.Weight ||
      (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
  {
    Result = L;
    ResultPos = Pos;
  }
}

if (Result.Value.getNode()) {
  Q.erase(&Q[ResultPos]);
  std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
}

return Result;
1825}

1827WeightedLeaf LeafPrioQueue::findMULbyConst() {
int ResultPos;
WeightedLeaf Result;

for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
  const WeightedLeaf &L = Q[Pos];
  const SDValue &Val = L.Value;
  if (Val.getOpcode() != ISD::MUL ||
      !isa<ConstantSDNode>(Val.getOperand(1)) ||
      Val.getConstantOperandVal(1) > 127)
    continue;
  if (!Result.Value.getNode() || Result.Weight > L.Weight ||
      (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
  {
    Result = L;
    ResultPos = Pos;
  }
}

if (Result.Value.getNode()) {
  Q.erase(&Q[ResultPos]);
  std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
}

return Result;
1852}

1854SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);
return CurDAG->getConstant(MulFactor, SDLoc(N),
                           N->getOperand(1).getValueType());
1858}

1860/// @returns the value x for which 2^x is a factor of Val
1861static unsigned getPowerOf2Factor(SDValue Val) {
if (Val.getOpcode() == ISD::MUL) {
  unsigned MaxFactor = 0;
  for (int i = 0; i < 2; ++i) {
    ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(i));
    if (!C)
      continue;
    const APInt &CInt = C->getAPIntValue();
    if (CInt.getBoolValue())
      MaxFactor = CInt.countTrailingZeros();
  }
  return MaxFactor;
}
if (Val.getOpcode() == ISD::SHL) {
  if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))
    return 0;
  return (unsigned) Val.getConstantOperandVal(1);
}

return 0;
1881}

1883/// @returns true if V>>Amount will eliminate V's operation on its child
1884static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
if (V.getOpcode() == ISD::MUL) {
  SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
  for (int i = 0; i < 2; ++i)
    if (isa<ConstantSDNode>(Ops[i].getNode()) &&
        V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {
      uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
      return (NewConst == 1);
    }
} else if (V.getOpcode() == ISD::SHL) {
  return (Amount == V.getConstantOperandVal(1));
}

return false;
1898}

1900SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
if (V.getOpcode() == ISD::MUL) {
  for (int i=0; i < 2; ++i) {
    if (isa<ConstantSDNode>(Ops[i].getNode()) &&
        V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {
      uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
      if (NewConst == 1)
        return Ops[!i];
      Ops[i] = CurDAG->getConstant(NewConst,
                                   SDLoc(V), V.getValueType());
      break;
    }
  }
} else if (V.getOpcode() == ISD::SHL) {
  uint64_t ShiftAmount = V.getConstantOperandVal(1);
  if (ShiftAmount == Power)
    return Ops[0];
  Ops[1] = CurDAG->getConstant(ShiftAmount - Power,
                               SDLoc(V), V.getValueType());
}

return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops);
1923}

1925static bool isTargetConstant(const SDValue &V) {
return V.getOpcode() == HexagonISD::CONST32 ||
       V.getOpcode() == HexagonISD::CONST32_GP;
1928}

1930unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
if (GAUsesInFunction.count(V))
  return GAUsesInFunction[V];

unsigned Result = 0;
const Function &CurF = CurDAG->getMachineFunction().getFunction();
for (const User *U : V->users()) {
  if (isa<Instruction>(U) &&
      cast<Instruction>(U)->getParent()->getParent() == &CurF)
    ++Result;
}

GAUsesInFunction[V] = Result;

return Result;
1945}

1947/// Note - After calling this, N may be dead. It may have been replaced by a
1948/// new node, so always use the returned value in place of N.
1949///
1950/// @returns The SDValue taking the place of N (which could be N if it is
1951/// unchanged)
1952SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
assert(RootWeights.count(N) && "Cannot balance non-root node.")(static_cast <bool> (RootWeights.count(N) && "Cannot balance non-root node."
) ? void (0) : __assert_fail ("RootWeights.count(N) && \"Cannot balance non-root node.\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1953, __extension__
 __PRETTY_FUNCTION__));
assert(RootWeights[N] != -2 && "This node was RAUW'd!")(static_cast <bool> (RootWeights[N] != -2 && "This node was RAUW'd!"
) ? void (0) : __assert_fail ("RootWeights[N] != -2 && \"This node was RAUW'd!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1954, __extension__
 __PRETTY_FUNCTION__));
assert(!TopLevel || N->getOpcode() == ISD::ADD)(static_cast <bool> (!TopLevel || N->getOpcode() == ISD
::ADD) ? void (0) : __assert_fail ("!TopLevel || N->getOpcode() == ISD::ADD"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 1955, __extension__
 __PRETTY_FUNCTION__));

// Return early if this node was already visited
if (RootWeights[N] != -1)
  return SDValue(N, 0);

assert(isOpcodeHandled(N))(static_cast <bool> (isOpcodeHandled(N)) ? void (0) : __assert_fail
 ("isOpcodeHandled(N)", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 1961, __extension__ __PRETTY_FUNCTION__));

SDValue Op0 = N->getOperand(0);
SDValue Op1 = N->getOperand(1);

// Return early if the operands will remain unchanged or are all roots
if ((!isOpcodeHandled(Op0.getNode()) || RootWeights.count(Op0.getNode())) &&
    (!isOpcodeHandled(Op1.getNode()) || RootWeights.count(Op1.getNode()))) {
  SDNode *Op0N = Op0.getNode();
  int Weight;
  if (isOpcodeHandled(Op0N) && RootWeights[Op0N] == -1) {
    Weight = getWeight(balanceSubTree(Op0N).getNode());
    // Weight = calculateWeight(Op0N);
  } else
    Weight = getWeight(Op0N);

  SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd
  if (isOpcodeHandled(Op1N) && RootWeights[Op1N] == -1) {
    Weight += getWeight(balanceSubTree(Op1N).getNode());
    // Weight += calculateWeight(Op1N);
  } else
    Weight += getWeight(Op1N);

  RootWeights[N] = Weight;
  RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),
                            getHeight(N->getOperand(1).getNode())) + 1;

  LLVM_DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weightdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> No need to balance root (Weight="
 << Weight << " Height=" << RootHeights[N] <<
 "): "; } } while (false)
                    << " Height=" << RootHeights[N] << "): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> No need to balance root (Weight="
 << Weight << " Height=" << RootHeights[N] <<
 "): "; } } while (false);
  LLVM_DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { N->dump(CurDAG); } } while (false);

  return SDValue(N, 0);
}

LLVM_DEBUG(dbgs() << "** Balancing root node: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "** Balancing root node: "
; } } while (false);
LLVM_DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { N->dump(CurDAG); } } while (false);

unsigned NOpcode = N->getOpcode();

LeafPrioQueue Leaves(NOpcode);
SmallVector<SDValue, 4> Worklist;
Worklist.push_back(SDValue(N, 0));

// SHL nodes will be converted to MUL nodes
if (NOpcode == ISD::SHL)
  NOpcode = ISD::MUL;

bool CanFactorize = false;
WeightedLeaf Mul1, Mul2;
unsigned MaxPowerOf2 = 0;
WeightedLeaf GA;

// Do not try to factor out a shift if there is already a shift at the tip of
// the tree.
bool HaveTopLevelShift = false;
if (TopLevel &&
    ((isOpcodeHandled(Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&
                      Op0.getConstantOperandVal(1) < 4) ||
     (isOpcodeHandled(Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&
                      Op1.getConstantOperandVal(1) < 4)))
  HaveTopLevelShift = true;

// Flatten the subtree into an ordered list of leaves; at the same time
// determine whether the tree is already balanced.
int InsertionOrder = 0;
SmallDenseMap<SDValue, int> NodeHeights;
bool Imbalanced = false;
int CurrentWeight = 0;
while (!Worklist.empty()) {
  SDValue Child = Worklist.pop_back_val();

  if (Child.getNode() != N && RootWeights.count(Child.getNode())) {
    // CASE 1: Child is a root note

    int Weight = RootWeights[Child.getNode()];
    if (Weight == -1) {
      Child = balanceSubTree(Child.getNode());
      // calculateWeight(Child.getNode());
      Weight = getWeight(Child.getNode());
    } else if (Weight == -2) {
      // Whoops, this node was RAUWd by one of the balanceSubTree calls we
      // made. Our worklist isn't up to date anymore.
      // Restart the whole process.
      LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Subtree was RAUWd. Restarting...\n"
; } } while (false);
      return balanceSubTree(N, TopLevel);
    }

    NodeHeights[Child] = 1;
    CurrentWeight += Weight;

    unsigned PowerOf2;
    if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
        (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&
        Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Child))) {
      // Try to identify two factorizable MUL/SHL children greedily. Leave
      // them out of the priority queue for now so we can deal with them
      // after.
      if (!Mul1.Value.getNode()) {
        Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
        MaxPowerOf2 = PowerOf2;
      } else {
        Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
        MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);

        // Our addressing modes can only shift by a maximum of 3
        if (MaxPowerOf2 > 3)
          MaxPowerOf2 = 3;

        CanFactorize = true;
      }
    } else
      Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
  } else if (!isOpcodeHandled(Child.getNode())) {
    // CASE 2: Child is an unhandled kind of node (e.g. constant)
    int Weight = getWeight(Child.getNode());

    NodeHeights[Child] = getHeight(Child.getNode());
    CurrentWeight += Weight;

    if (isTargetConstant(Child) && !GA.Value.getNode())
      GA = WeightedLeaf(Child, Weight, InsertionOrder++);
    else
      Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
  } else {
    // CASE 3: Child is a subtree of same opcode
    // Visit children first, then flatten.
    unsigned ChildOpcode = Child.getOpcode();
    assert(ChildOpcode == NOpcode ||(static_cast <bool> (ChildOpcode == NOpcode || (NOpcode
 == ISD::MUL && ChildOpcode == ISD::SHL)) ? void (0) :
 __assert_fail ("ChildOpcode == NOpcode || (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL)"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2089, __extension__
 __PRETTY_FUNCTION__))
           (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL))(static_cast <bool> (ChildOpcode == NOpcode || (NOpcode
 == ISD::MUL && ChildOpcode == ISD::SHL)) ? void (0) :
 __assert_fail ("ChildOpcode == NOpcode || (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL)"
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2089, __extension__
 __PRETTY_FUNCTION__));

    // Convert SHL to MUL
    SDValue Op1;
    if (ChildOpcode == ISD::SHL)
      Op1 = getMultiplierForSHL(Child.getNode());
    else
      Op1 = Child->getOperand(1);

    if (!NodeHeights.count(Op1) || !NodeHeights.count(Child->getOperand(0))) {
      assert(!NodeHeights.count(Child) && "Parent visited before children?")(static_cast <bool> (!NodeHeights.count(Child) &&
 "Parent visited before children?") ? void (0) : __assert_fail
 ("!NodeHeights.count(Child) && \"Parent visited before children?\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2099, __extension__
 __PRETTY_FUNCTION__));
      // Visit children first, then re-visit this node
      Worklist.push_back(Child);
      Worklist.push_back(Op1);
      Worklist.push_back(Child->getOperand(0));
    } else {
      // Back at this node after visiting the children
      if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)
        Imbalanced = true;

      NodeHeights[Child] = std::max(NodeHeights[Op1],
                                    NodeHeights[Child->getOperand(0)]) + 1;
    }
  }
}

LLVM_DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Current height=" <<
 NodeHeights[SDValue(N, 0)] << " weight=" << CurrentWeight
 << " imbalanced=" << Imbalanced << "\n"; }
 } while (false)
                  << " weight=" << CurrentWeightdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Current height=" <<
 NodeHeights[SDValue(N, 0)] << " weight=" << CurrentWeight
 << " imbalanced=" << Imbalanced << "\n"; }
 } while (false)
                  << " imbalanced=" << Imbalanced << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Current height=" <<
 NodeHeights[SDValue(N, 0)] << " weight=" << CurrentWeight
 << " imbalanced=" << Imbalanced << "\n"; }
 } while (false);

// Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
//  This factors out a shift in order to match memw(a<<Y+b).
if (CanFactorize && (willShiftRightEliminate(Mul1.Value, MaxPowerOf2) ||
                     willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {
  LLVM_DEBUG(dbgs() << "--> Found common factor for two MUL children!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Found common factor for two MUL children!\n"
; } } while (false);
  int Weight = Mul1.Weight + Mul2.Weight;
  int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
  SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
  SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
  SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),
                                Mul1Factored, Mul2Factored);
  SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),
                                      Mul1.Value.getValueType());
  SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),
                                Sum, Const);
  NodeHeights[New] = Height;
  Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
} else if (Mul1.Value.getNode()) {
  // We failed to factorize two MULs, so now the Muls are left outside the
  // queue... add them back.
  Leaves.push(Mul1);
  if (Mul2.Value.getNode())
    Leaves.push(Mul2);
  CanFactorize = false;
}

// Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
// and the root node itself is not used more than twice. This reduces the
// amount of additional constant extenders introduced by this optimization.
bool CombinedGA = false;
if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
    GA.Value.hasOneUse() && N->use_size() < 3) {
  GlobalAddressSDNode *GANode =
    cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
  ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);

  if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
      getTargetLowering()->isOffsetFoldingLegal(GANode)) {
    LLVM_DEBUG(dbgs() << "--> Combining GA and offset ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Combining GA and offset ("
 << Offset->getSExtValue() << "): "; } } while
 (false)
                      << Offset->getSExtValue() << "): ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Combining GA and offset ("
 << Offset->getSExtValue() << "): "; } } while
 (false);
    LLVM_DEBUG(GANode->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { GANode->dump(CurDAG); } } while (false
);

    SDValue NewTGA =
      CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),
          GANode->getValueType(0),
          GANode->getOffset() + (uint64_t)Offset->getSExtValue());
    GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),
        GA.Value.getValueType(), NewTGA);
    GA.Weight += Leaves.top().Weight;

    NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
    CombinedGA = true;

    Leaves.pop(); // Remove the offset constant from the queue
  }
}

if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||
    (RebalanceOnlyImbalancedTrees && !Imbalanced)) {
  RootWeights[N] = CurrentWeight;
  RootHeights[N] = NodeHeights[SDValue(N, 0)];

  return SDValue(N, 0);
}

// Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
if (NOpcode == ISD::ADD && GA.Value.getNode()) {
  WeightedLeaf SHL = Leaves.findSHL(31);
  if (SHL.Value.getNode()) {
    int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;
    GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),
                               GA.Value.getValueType(),
                               GA.Value, SHL.Value);
    GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
    NodeHeights[GA.Value] = Height;
  }
}

if (GA.Value.getNode())
  Leaves.push(GA);

// If this is the top level and we haven't factored out a shift, we should try
// to move a constant to the bottom to match addressing modes like memw(rX+C)
if (TopLevel && !CanFactorize && Leaves.hasConst()) {
  LLVM_DEBUG(dbgs() << "--> Pushing constant to tip of tree.")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Pushing constant to tip of tree."
; } } while (false);
  Leaves.pushToBottom(Leaves.pop());
}

const DataLayout &DL = CurDAG->getDataLayout();
const TargetLowering &TLI = *getTargetLowering();

// Rebuild the tree using Huffman's algorithm
while (Leaves.size() > 1) {
  WeightedLeaf L0 = Leaves.pop();

  // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
  // otherwise just get the next leaf
  WeightedLeaf L1 = Leaves.findMULbyConst();
  if (!L1.Value.getNode())
    L1 = Leaves.pop();

  assert(L0.Weight <= L1.Weight && "Priority queue is broken!")(static_cast <bool> (L0.Weight <= L1.Weight &&
 "Priority queue is broken!") ? void (0) : __assert_fail ("L0.Weight <= L1.Weight && \"Priority queue is broken!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2220, __extension__
 __PRETTY_FUNCTION__));

  SDValue V0 = L0.Value;
  int V0Weight = L0.Weight;
  SDValue V1 = L1.Value;
  int V1Weight = L1.Weight;

  // Make sure that none of these nodes have been RAUW'd
  if ((RootWeights.count(V0.getNode()) && RootWeights[V0.getNode()] == -2) ||
      (RootWeights.count(V1.getNode()) && RootWeights[V1.getNode()] == -2)) {
    LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Subtree was RAUWd. Restarting...\n"
; } } while (false);
    return balanceSubTree(N, TopLevel);
  }

  ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(V0);
  ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(V1);
  EVT VT = N->getValueType(0);
  SDValue NewNode;

  if (V0C && !V1C) {
    std::swap(V0, V1);
    std::swap(V0C, V1C);
  }

  // Calculate height of this node
  assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&(static_cast <bool> (NodeHeights.count(V0) && NodeHeights
.count(V1) && "Children must have been visited before re-combining them!"
) ? void (0) : __assert_fail ("NodeHeights.count(V0) && NodeHeights.count(V1) && \"Children must have been visited before re-combining them!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2246, __extension__
 __PRETTY_FUNCTION__))
         "Children must have been visited before re-combining them!")(static_cast <bool> (NodeHeights.count(V0) && NodeHeights
.count(V1) && "Children must have been visited before re-combining them!"
) ? void (0) : __assert_fail ("NodeHeights.count(V0) && NodeHeights.count(V1) && \"Children must have been visited before re-combining them!\""
, "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp", 2246, __extension__
 __PRETTY_FUNCTION__));
  int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;

  // Rebuild this node (and restore SHL from MUL if needed)
  if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())
    NewNode = CurDAG->getNode(
        ISD::SHL, SDLoc(V0), VT, V0,
        CurDAG->getConstant(
            V1C->getAPIntValue().logBase2(), SDLoc(N),
            TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
  else
    NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);

  NodeHeights[NewNode] = Height;

  int Weight = V0Weight + V1Weight;
  Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));

  LLVM_DEBUG(dbgs() << "--> Built new node (Weight=" << Weightdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Built new node (Weight="
 << Weight << ",Height=" << Height <<
 "):\n"; } } while (false)
                    << ",Height=" << Height << "):\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Built new node (Weight="
 << Weight << ",Height=" << Height <<
 "):\n"; } } while (false);
  LLVM_DEBUG(NewNode.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { NewNode.dump(); } } while (false);
}

assert(Leaves.size() == 1)(static_cast <bool> (Leaves.size() == 1) ? void (0) : __assert_fail
 ("Leaves.size() == 1", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 2269, __extension__ __PRETTY_FUNCTION__));
SDValue NewRoot = Leaves.top().Value;

assert(NodeHeights.count(NewRoot))(static_cast <bool> (NodeHeights.count(NewRoot)) ? void
 (0) : __assert_fail ("NodeHeights.count(NewRoot)", "llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp"
, 2272, __extension__ __PRETTY_FUNCTION__));
int Height = NodeHeights[NewRoot];

// Restore SHL if we earlier converted it to a MUL
if (NewRoot.getOpcode() == ISD::MUL) {
  ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));
  if (V1C && V1C->getAPIntValue().isPowerOf2()) {
    EVT VT = NewRoot.getValueType();
    SDValue V0 = NewRoot.getOperand(0);
    NewRoot = CurDAG->getNode(
        ISD::SHL, SDLoc(NewRoot), VT, V0,
        CurDAG->getConstant(
            V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),
            TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
  }
}

if (N != NewRoot.getNode()) {
  LLVM_DEBUG(dbgs() << "--> Root is now: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Root is now: "; }
 } while (false);
  LLVM_DEBUG(NewRoot.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { NewRoot.dump(); } } while (false);

  // Replace all uses of old root by new root
  CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());
  // Mark that we have RAUW'd N
  RootWeights[N] = -2;
} else {
  LLVM_DEBUG(dbgs() << "--> Root unchanged.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Root unchanged.\n"
; } } while (false);
}

RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
RootHeights[NewRoot.getNode()] = Height;

return NewRoot;
2305}

2307void HexagonDAGToDAGISel::rebalanceAddressTrees() {
for (SDNode &Node : llvm::make_early_inc_range(CurDAG->allnodes())) {
  SDNode *N = &Node;
  if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)
    continue;

  SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();
  if (BasePtr.getOpcode() != ISD::ADD)
    continue;

  // We've already processed this node
  if (RootWeights.count(BasePtr.getNode()))
    continue;

  LLVM_DEBUG(dbgs() << "** Rebalancing address calculation in node: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "** Rebalancing address calculation in node: "
; } } while (false);
  LLVM_DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { N->dump(CurDAG); } } while (false);

  // FindRoots
  SmallVector<SDNode *, 4> Worklist;

  Worklist.push_back(BasePtr.getOperand(0).getNode());
  Worklist.push_back(BasePtr.getOperand(1).getNode());

  while (!Worklist.empty()) {
    SDNode *N = Worklist.pop_back_val();
    unsigned Opcode = N->getOpcode();

    if (!isOpcodeHandled(N))
      continue;

    Worklist.push_back(N->getOperand(0).getNode());
    Worklist.push_back(N->getOperand(1).getNode());

    // Not a root if it has only one use and same opcode as its parent
    if (N->hasOneUse() && Opcode == N->use_begin()->getOpcode())
      continue;

    // This root node has already been processed
    if (RootWeights.count(N))
      continue;

    RootWeights[N] = -1;
  }

  // Balance node itself
  RootWeights[BasePtr.getNode()] = -1;
  SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);

  if (N->getOpcode() == ISD::LOAD)
    N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),
          NewBasePtr, N->getOperand(2));
  else
    N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
          NewBasePtr, N->getOperand(3));

  LLVM_DEBUG(dbgs() << "--> Final node: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { dbgs() << "--> Final node: "; } }
 while (false);
  LLVM_DEBUG(N->dump(CurDAG))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-isel")) { N->dump(CurDAG); } } while (false);
}

CurDAG->RemoveDeadNodes();
GAUsesInFunction.clear();
RootHeights.clear();
RootWeights.clear();
2370}

←

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

←

/build/source/llvm/include/llvm/ADT/bit.h

1//===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- 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/// \file
10/// This file implements the C++20 <bit> header.
11///
12//===----------------------------------------------------------------------===//
13 
14#ifndef LLVM_ADT_BIT_H
15#define LLVM_ADT_BIT_H
16 
17#include "llvm/Support/Compiler.h"
18#include <cstdint>
19#include <limits>
20#include <type_traits>
21 
22#if !__has_builtin(__builtin_bit_cast)1
23#include <cstring>
24#endif
25 
26#if defined(_MSC_VER) && !defined(_DEBUG1)
27#include <cstdlib>  // for _byteswap_{ushort,ulong,uint64}
28#endif
29 
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and bit.h is popular via MathExtras.h.
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// This implementation of bit_cast is different from the C++20 one in two ways:
45//  - It isn't constexpr because that requires compiler support.
46//  - It requires trivially-constructible To, to avoid UB in the implementation.
47template <
48    typename To, typename From,
49    typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
50    typename = std::enable_if_t<std::is_trivially_constructible<To>::value>,
51    typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
52    typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
53[[nodiscard]] inline To bit_cast(const From &from) noexcept {
54#if __has_builtin(__builtin_bit_cast)1
55  return __builtin_bit_cast(To, from);
56#else
57  To to;
58  std::memcpy(&to, &from, sizeof(To));
59  return to;
60#endif
61}
62 
63/// Reverses the bytes in the given integer value V.
64template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
65[[nodiscard]] constexpr T byteswap(T V) noexcept {
66  if constexpr (sizeof(T) == 1) {
67    return V;
68  } else if constexpr (sizeof(T) == 2) {
69    uint16_t UV = V;
70#if defined(_MSC_VER) && !defined(_DEBUG1)
71    // The DLL version of the runtime lacks these functions (bug!?), but in a
72    // release build they're replaced with BSWAP instructions anyway.
73    return _byteswap_ushort(UV);
74#else
75    uint16_t Hi = UV << 8;
76    uint16_t Lo = UV >> 8;
77    return Hi | Lo;
78#endif
79  } else if constexpr (sizeof(T) == 4) {
80    uint32_t UV = V;
81#if __has_builtin(__builtin_bswap32)1
82    return __builtin_bswap32(UV);
83#elif defined(_MSC_VER) && !defined(_DEBUG1)
84    return _byteswap_ulong(UV);
85#else
86    uint32_t Byte0 = UV & 0x000000FF;
87    uint32_t Byte1 = UV & 0x0000FF00;
88    uint32_t Byte2 = UV & 0x00FF0000;
89    uint32_t Byte3 = UV & 0xFF000000;
90    return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
91#endif
92  } else if constexpr (sizeof(T) == 8) {
93    uint64_t UV = V;
94#if __has_builtin(__builtin_bswap64)1
95    return __builtin_bswap64(UV);
96#elif defined(_MSC_VER) && !defined(_DEBUG1)
97    return _byteswap_uint64(UV);
98#else
99    uint64_t Hi = llvm::byteswap<uint32_t>(UV);
100    uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
101    return (Hi << 32) | Lo;
102#endif
103  } else {
104    static_assert(!sizeof(T *), "Don't know how to handle the given type.");
105    return 0;
106  }
107}
108 
109template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
110[[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept {
111  return (Value != 0) && ((Value & (Value - 1)) == 0);
112}
113 
114namespace detail {
115template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
116  static unsigned count(T Val) {
117    if (!Val)
118      return std::numeric_limits<T>::digits;
119    if (Val & 0x1)
120      return 0;
121 
122    // Bisection method.
123    unsigned ZeroBits = 0;
124    T Shift = std::numeric_limits<T>::digits >> 1;
125    T Mask = std::numeric_limits<T>::max() >> Shift;
126    while (Shift) {
127      if ((Val & Mask) == 0) {
128        Val >>= Shift;
129        ZeroBits |= Shift;
130      }
131      Shift >>= 1;
132      Mask >>= Shift;
133    }
134    return ZeroBits;
135  }
136};
137 
138#if defined(__GNUC__4) || defined(_MSC_VER)
139template <typename T> struct TrailingZerosCounter<T, 4> {
140  static unsigned count(T Val) {
141    if (Val == 0)
22
←
Assuming 'Val' is equal to 0→
23
←
Taking true branch→
142      return 32;
24
←
Returning the value 32→
143 
144#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
145    return __builtin_ctz(Val);
146#elif defined(_MSC_VER)
147    unsigned long Index;
148    _BitScanForward(&Index, Val);
149    return Index;
150#endif
151  }
152};
153 
154#if !defined(_MSC_VER) || defined(_M_X64)
155template <typename T> struct TrailingZerosCounter<T, 8> {
156  static unsigned count(T Val) {
157    if (Val == 0)
158      return 64;
159 
160#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
161    return __builtin_ctzll(Val);
162#elif defined(_MSC_VER)
163    unsigned long Index;
164    _BitScanForward64(&Index, Val);
165    return Index;
166#endif
167  }
168};
169#endif
170#endif
171} // namespace detail
172 
173/// Count number of 0's from the least significant bit to the most
174///   stopping at the first 1.
175///
176/// Only unsigned integral types are allowed.
177///
178/// Returns std::numeric_limits<T>::digits on an input of 0.
179template <typename T> [[nodiscard]] int countr_zero(T Val) {
180  static_assert(std::is_unsigned_v<T>,
181                "Only unsigned integral types are allowed.");
182  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
21
←
Calling 'TrailingZerosCounter::count'→
25
←
Returning from 'TrailingZerosCounter::count'→
26
←
Returning the value 32→
183}
184 
185namespace detail {
186template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
187  static unsigned count(T Val) {
188    if (!Val)
189      return std::numeric_limits<T>::digits;
190 
191    // Bisection method.
192    unsigned ZeroBits = 0;
193    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
194      T Tmp = Val >> Shift;
195      if (Tmp)
196        Val = Tmp;
197      else
198        ZeroBits |= Shift;
199    }
200    return ZeroBits;
201  }
202};
203 
204#if defined(__GNUC__4) || defined(_MSC_VER)
205template <typename T> struct LeadingZerosCounter<T, 4> {
206  static unsigned count(T Val) {
207    if (Val == 0)
208      return 32;
209 
210#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
211    return __builtin_clz(Val);
212#elif defined(_MSC_VER)
213    unsigned long Index;
214    _BitScanReverse(&Index, Val);
215    return Index ^ 31;
216#endif
217  }
218};
219 
220#if !defined(_MSC_VER) || defined(_M_X64)
221template <typename T> struct LeadingZerosCounter<T, 8> {
222  static unsigned count(T Val) {
223    if (Val == 0)
224      return 64;
225 
226#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
227    return __builtin_clzll(Val);
228#elif defined(_MSC_VER)
229    unsigned long Index;
230    _BitScanReverse64(&Index, Val);
231    return Index ^ 63;
232#endif
233  }
234};
235#endif
236#endif
237} // namespace detail
238 
239/// Count number of 0's from the most significant bit to the least
240///   stopping at the first 1.
241///
242/// Only unsigned integral types are allowed.
243///
244/// Returns std::numeric_limits<T>::digits on an input of 0.
245template <typename T> [[nodiscard]] int countl_zero(T Val) {
246  static_assert(std::is_unsigned_v<T>,
247                "Only unsigned integral types are allowed.");
248  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
249}
250 
251/// Count the number of ones from the most significant bit to the first
252/// zero bit.
253///
254/// Ex. countl_one(0xFF0FFF00) == 8.
255/// Only unsigned integral types are allowed.
256///
257/// Returns std::numeric_limits<T>::digits on an input of all ones.
258template <typename T> [[nodiscard]] int countl_one(T Value) {
259  static_assert(std::is_unsigned_v<T>,
260                "Only unsigned integral types are allowed.");
261  return llvm::countl_zero<T>(~Value);
262}
263 
264/// Count the number of ones from the least significant bit to the first
265/// zero bit.
266///
267/// Ex. countr_one(0x00FF00FF) == 8.
268/// Only unsigned integral types are allowed.
269///
270/// Returns std::numeric_limits<T>::digits on an input of all ones.
271template <typename T> [[nodiscard]] int countr_one(T Value) {
272  static_assert(std::is_unsigned_v<T>,
273                "Only unsigned integral types are allowed.");
274  return llvm::countr_zero<T>(~Value);
275}
276 
277/// Returns the number of bits needed to represent Value if Value is nonzero.
278/// Returns 0 otherwise.
279///
280/// Ex. bit_width(5) == 3.
281template <typename T> [[nodiscard]] int bit_width(T Value) {
282  static_assert(std::is_unsigned_v<T>,
283                "Only unsigned integral types are allowed.");
284  return std::numeric_limits<T>::digits - llvm::countl_zero(Value);
285}
286 
287/// Returns the largest integral power of two no greater than Value if Value is
288/// nonzero.  Returns 0 otherwise.
289///
290/// Ex. bit_floor(5) == 4.
291template <typename T> [[nodiscard]] T bit_floor(T Value) {
292  static_assert(std::is_unsigned_v<T>,
293                "Only unsigned integral types are allowed.");
294  if (!Value)
295    return 0;
296  return T(1) << (llvm::bit_width(Value) - 1);
297}
298 
299/// Returns the smallest integral power of two no smaller than Value if Value is
300/// nonzero.  Returns 0 otherwise.
301///
302/// Ex. bit_ceil(5) == 8.
303///
304/// The return value is undefined if the input is larger than the largest power
305/// of two representable in T.
306template <typename T> [[nodiscard]] T bit_ceil(T Value) {
307  static_assert(std::is_unsigned_v<T>,
308                "Only unsigned integral types are allowed.");
309  if (Value < 2)
310    return 1;
311  return T(1) << llvm::bit_width<T>(Value - 1u);
312}
313 
314namespace detail {
315template <typename T, std::size_t SizeOfT> struct PopulationCounter {
316  static int count(T Value) {
317    // Generic version, forward to 32 bits.
318    static_assert(SizeOfT <= 4, "Not implemented!");
319#if defined(__GNUC__4)
320    return (int)__builtin_popcount(Value);
321#else
322    uint32_t v = Value;
323    v = v - ((v >> 1) & 0x55555555);
324    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
325    return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
326#endif
327  }
328};
329 
330template <typename T> struct PopulationCounter<T, 8> {
331  static int count(T Value) {
332#if defined(__GNUC__4)
333    return (int)__builtin_popcountll(Value);
334#else
335    uint64_t v = Value;
336    v = v - ((v >> 1) & 0x5555555555555555ULL);
337    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
338    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
339    return int((uint64_t)(v * 0x0101010101010101ULL) >> 56);
340#endif
341  }
342};
343} // namespace detail
344 
345/// Count the number of set bits in a value.
346/// Ex. popcount(0xF000F000) = 8
347/// Returns 0 if the word is zero.
348template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
349[[nodiscard]] inline int popcount(T Value) noexcept {
350  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
351}
352 
353} // namespace llvm
354 
355#endif