//===-- ConstantFolding.cpp - Fold instructions into constants ------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file defines routines for folding instructions into constants.

//

// Also, to supplement the basic IR ConstantExpr simplifications,

// this file defines some additional folding routines that can make use of

// DataLayout information. These functions cannot go in IR due to library

// dependency issues.

//

//===----------------------------------------------------------------------===//

#include "llvm/Analysis/ConstantFolding.h"

#include "llvm/ADT/APFloat.h"

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/APSInt.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/Analysis/TargetFolder.h"

#include "llvm/Analysis/TargetLibraryInfo.h"

#include "llvm/Analysis/ValueTracking.h"

#include "llvm/Analysis/VectorUtils.h"

#include "llvm/Config/config.h"

#include "llvm/IR/Constant.h"

#include "llvm/IR/ConstantFold.h"

#include "llvm/IR/Constants.h"

#include "llvm/IR/DataLayout.h"

#include "llvm/IR/DerivedTypes.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/GlobalValue.h"

#include "llvm/IR/GlobalVariable.h"

#include "llvm/IR/InstrTypes.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/IntrinsicInst.h"

#include "llvm/IR/Intrinsics.h"

#include "llvm/IR/IntrinsicsAArch64.h"

#include "llvm/IR/IntrinsicsAMDGPU.h"

#include "llvm/IR/IntrinsicsARM.h"

#include "llvm/IR/IntrinsicsWebAssembly.h"

#include "llvm/IR/IntrinsicsX86.h"

#include "llvm/IR/Operator.h"

#include "llvm/IR/Type.h"

#include "llvm/IR/Value.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/KnownBits.h"

#include "llvm/Support/MathExtras.h"

#include <cassert>

#include <cerrno>

#include <cfenv>

#include <cmath>

#include <cstdint>

using namespace llvm;

namespace {

//===----------------------------------------------------------------------===//

// Constant Folding internal helper functions

//===----------------------------------------------------------------------===//

static Constant *foldConstVectorToAPInt(APInt &Result, Type *DestTy,

                                        Constant *C, Type *SrcEltTy,

                                        unsigned NumSrcElts,

                                        const DataLayout &DL) {

  // Now that we know that the input value is a vector of integers, just shift

  // and insert them into our result.

  unsigned BitShift = DL.getTypeSizeInBits(SrcEltTy);

  for (unsigned i = 0; i != NumSrcElts; ++i) {

    Constant *Element;

    if (DL.isLittleEndian())

      Element = C->getAggregateElement(NumSrcElts - i - 1);

    else

      Element = C->getAggregateElement(i);

    if (Element && isa<UndefValue>(Element)) {

      Result <<= BitShift;

      continue;

    }

    auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);

    if (!ElementCI)

      return ConstantExpr::getBitCast(C, DestTy);

    Result <<= BitShift;

    Result |= ElementCI->getValue().zext(Result.getBitWidth());

  }

  return nullptr;

}

/// Constant fold bitcast, symbolically evaluating it with DataLayout.

/// This always returns a non-null constant, but it may be a

/// ConstantExpr if unfoldable.

Constant *FoldBitCast(Constant *C, Type *DestTy, const DataLayout &DL) {

  assert(CastInst::castIsValid(Instruction::BitCast, C, DestTy) &&

         "Invalid constantexpr bitcast!");

  // Catch the obvious splat cases.

  if (Constant *Res = ConstantFoldLoadFromUniformValue(C, DestTy))

    return Res;

  if (auto *VTy = dyn_cast<VectorType>(C->getType())) {

    // Handle a vector->scalar integer/fp cast.

    if (isa<IntegerType>(DestTy) || DestTy->isFloatingPointTy()) {

      unsigned NumSrcElts = cast<FixedVectorType>(VTy)->getNumElements();

      Type *SrcEltTy = VTy->getElementType();

      // If the vector is a vector of floating point, convert it to vector of int

      // to simplify things.

      if (SrcEltTy->isFloatingPointTy()) {

        unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits();

        auto *SrcIVTy = FixedVectorType::get(

            IntegerType::get(C->getContext(), FPWidth), NumSrcElts);

        // Ask IR to do the conversion now that #elts line up.

        C = ConstantExpr::getBitCast(C, SrcIVTy);

      }

      APInt Result(DL.getTypeSizeInBits(DestTy), 0);

      if (Constant *CE = foldConstVectorToAPInt(Result, DestTy, C,

                                                SrcEltTy, NumSrcElts, DL))

        return CE;

      if (isa<IntegerType>(DestTy))

        return ConstantInt::get(DestTy, Result);

      APFloat FP(DestTy->getFltSemantics(), Result);

      return ConstantFP::get(DestTy->getContext(), FP);

    }

  }

  // The code below only handles casts to vectors currently.

  auto *DestVTy = dyn_cast<VectorType>(DestTy);

  if (!DestVTy)

    return ConstantExpr::getBitCast(C, DestTy);

  // If this is a scalar -> vector cast, convert the input into a <1 x scalar>

  // vector so the code below can handle it uniformly.

  if (isa<ConstantFP>(C) || isa<ConstantInt>(C)) {

    Constant *Ops = C; // don't take the address of C!

    return FoldBitCast(ConstantVector::get(Ops), DestTy, DL);

  }

  // If this is a bitcast from constant vector -> vector, fold it.

  if (!isa<ConstantDataVector>(C) && !isa<ConstantVector>(C))

    return ConstantExpr::getBitCast(C, DestTy);

  // If the element types match, IR can fold it.

  unsigned NumDstElt = cast<FixedVectorType>(DestVTy)->getNumElements();

  unsigned NumSrcElt = cast<FixedVectorType>(C->getType())->getNumElements();

  if (NumDstElt == NumSrcElt)

    return ConstantExpr::getBitCast(C, DestTy);

  Type *SrcEltTy = cast<VectorType>(C->getType())->getElementType();

  Type *DstEltTy = DestVTy->getElementType();

  // Otherwise, we're changing the number of elements in a vector, which

  // requires endianness information to do the right thing.  For example,

  //    bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)

  // folds to (little endian):

  //    <4 x i32> <i32 0, i32 0, i32 1, i32 0>

  // and to (big endian):

  //    <4 x i32> <i32 0, i32 0, i32 0, i32 1>

  // First thing is first.  We only want to think about integer here, so if

  // we have something in FP form, recast it as integer.

  if (DstEltTy->isFloatingPointTy()) {

    // Fold to an vector of integers with same size as our FP type.

    unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits();

    auto *DestIVTy = FixedVectorType::get(

        IntegerType::get(C->getContext(), FPWidth), NumDstElt);

    // Recursively handle this integer conversion, if possible.

    C = FoldBitCast(C, DestIVTy, DL);

    // Finally, IR can handle this now that #elts line up.

    return ConstantExpr::getBitCast(C, DestTy);

  }

  // Okay, we know the destination is integer, if the input is FP, convert

  // it to integer first.

  if (SrcEltTy->isFloatingPointTy()) {

    unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits();

    auto *SrcIVTy = FixedVectorType::get(

        IntegerType::get(C->getContext(), FPWidth), NumSrcElt);

    // Ask IR to do the conversion now that #elts line up.

    C = ConstantExpr::getBitCast(C, SrcIVTy);

    // If IR wasn't able to fold it, bail out.

    if (!isa<ConstantVector>(C) &&  // FIXME: Remove ConstantVector.

        !isa<ConstantDataVector>(C))

      return C;

  }

  // Now we know that the input and output vectors are both integer vectors

  // of the same size, and that their #elements is not the same.  Do the

  // conversion here, which depends on whether the input or output has

  // more elements.

  bool isLittleEndian = DL.isLittleEndian();

  SmallVector<Constant*, 32> Result;

  if (NumDstElt < NumSrcElt) {

    // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>)

    Constant *Zero = Constant::getNullValue(DstEltTy);

    unsigned Ratio = NumSrcElt/NumDstElt;

    unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits();

    unsigned SrcElt = 0;

    for (unsigned i = 0; i != NumDstElt; ++i) {

      // Build each element of the result.

      Constant *Elt = Zero;

      unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1);

      for (unsigned j = 0; j != Ratio; ++j) {

        Constant *Src = C->getAggregateElement(SrcElt++);

        if (Src && isa<UndefValue>(Src))

          Src = Constant::getNullValue(

              cast<VectorType>(C->getType())->getElementType());

        else

          Src = dyn_cast_or_null<ConstantInt>(Src);

        if (!Src)  // Reject constantexpr elements.

          return ConstantExpr::getBitCast(C, DestTy);

        // Zero extend the element to the right size.

        Src = ConstantFoldCastOperand(Instruction::ZExt, Src, Elt->getType(),

                                      DL);

        assert(Src && "Constant folding cannot fail on plain integers");

        // Shift it to the right place, depending on endianness.

        Src = ConstantFoldBinaryOpOperands(

            Instruction::Shl, Src, ConstantInt::get(Src->getType(), ShiftAmt),

            DL);

        assert(Src && "Constant folding cannot fail on plain integers");

        ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize;

        // Mix it in.

        Elt = ConstantFoldBinaryOpOperands(Instruction::Or, Elt, Src, DL);

        assert(Elt && "Constant folding cannot fail on plain integers");

      }

      Result.push_back(Elt);

    }

    return ConstantVector::get(Result);

  }

  // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)

  unsigned Ratio = NumDstElt/NumSrcElt;

  unsigned DstBitSize = DL.getTypeSizeInBits(DstEltTy);

  // Loop over each source value, expanding into multiple results.

  for (unsigned i = 0; i != NumSrcElt; ++i) {

    auto *Element = C->getAggregateElement(i);

    if (!Element) // Reject constantexpr elements.

      return ConstantExpr::getBitCast(C, DestTy);

    if (isa<UndefValue>(Element)) {

      // Correctly Propagate undef values.

      Result.append(Ratio, UndefValue::get(DstEltTy));

      continue;

    }

    auto *Src = dyn_cast<ConstantInt>(Element);

    if (!Src)

      return ConstantExpr::getBitCast(C, DestTy);

    unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1);

    for (unsigned j = 0; j != Ratio; ++j) {

      // Shift the piece of the value into the right place, depending on

      // endianness.

      APInt Elt = Src->getValue().lshr(ShiftAmt);

      ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize;

      // Truncate and remember this piece.

      Result.push_back(ConstantInt::get(DstEltTy, Elt.trunc(DstBitSize)));

    }

  }

  return ConstantVector::get(Result);

}

} // end anonymous namespace

/// If this constant is a constant offset from a global, return the global and

/// the constant. Because of constantexprs, this function is recursive.

bool llvm::IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,

                                      APInt &Offset, const DataLayout &DL,

                                      DSOLocalEquivalent **DSOEquiv) {

  if (DSOEquiv)

    *DSOEquiv = nullptr;

  // Trivial case, constant is the global.

  if ((GV = dyn_cast<GlobalValue>(C))) {

    unsigned BitWidth = DL.getIndexTypeSizeInBits(GV->getType());

    Offset = APInt(BitWidth, 0);

    return true;

  }

  if (auto *FoundDSOEquiv = dyn_cast<DSOLocalEquivalent>(C)) {

    if (DSOEquiv)

      *DSOEquiv = FoundDSOEquiv;

    GV = FoundDSOEquiv->getGlobalValue();

    unsigned BitWidth = DL.getIndexTypeSizeInBits(GV->getType());

    Offset = APInt(BitWidth, 0);

    return true;

  }

  // Otherwise, if this isn't a constant expr, bail out.

  auto *CE = dyn_cast<ConstantExpr>(C);

  if (!CE) return false;

  // Look through ptr->int and ptr->ptr casts.

  if (CE->getOpcode() == Instruction::PtrToInt ||

      CE->getOpcode() == Instruction::BitCast)

    return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, DL,

                                      DSOEquiv);

  // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5)

  auto *GEP = dyn_cast<GEPOperator>(CE);

  if (!GEP)

    return false;

  unsigned BitWidth = DL.getIndexTypeSizeInBits(GEP->getType());

  APInt TmpOffset(BitWidth, 0);

  // If the base isn't a global+constant, we aren't either.

  if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, TmpOffset, DL,

                                  DSOEquiv))

    return false;

  // Otherwise, add any offset that our operands provide.

  if (!GEP->accumulateConstantOffset(DL, TmpOffset))

    return false;

  Offset = TmpOffset;

  return true;

}

Constant *llvm::ConstantFoldLoadThroughBitcast(Constant *C, Type *DestTy,

                                         const DataLayout &DL) {

  do {

    Type *SrcTy = C->getType();

    if (SrcTy == DestTy)

      return C;

    TypeSize DestSize = DL.getTypeSizeInBits(DestTy);

    TypeSize SrcSize = DL.getTypeSizeInBits(SrcTy);

    if (!TypeSize::isKnownGE(SrcSize, DestSize))

      return nullptr;

    // Catch the obvious splat cases (since all-zeros can coerce non-integral

    // pointers legally).

    if (Constant *Res = ConstantFoldLoadFromUniformValue(C, DestTy))

      return Res;

    // If the type sizes are the same and a cast is legal, just directly

    // cast the constant.

    // But be careful not to coerce non-integral pointers illegally.

    if (SrcSize == DestSize &&

        DL.isNonIntegralPointerType(SrcTy->getScalarType()) ==

            DL.isNonIntegralPointerType(DestTy->getScalarType())) {

      Instruction::CastOps Cast = Instruction::BitCast;

      // If we are going from a pointer to int or vice versa, we spell the cast

      // differently.

      if (SrcTy->isIntegerTy() && DestTy->isPointerTy())

        Cast = Instruction::IntToPtr;

      else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())

        Cast = Instruction::PtrToInt;

      if (CastInst::castIsValid(Cast, C, DestTy))

        return ConstantFoldCastOperand(Cast, C, DestTy, DL);

    }

    // If this isn't an aggregate type, there is nothing we can do to drill down

    // and find a bitcastable constant.

    if (!SrcTy->isAggregateType() && !SrcTy->isVectorTy())

      return nullptr;

    // We're simulating a load through a pointer that was bitcast to point to

    // a different type, so we can try to walk down through the initial

    // elements of an aggregate to see if some part of the aggregate is

    // castable to implement the "load" semantic model.

    if (SrcTy->isStructTy()) {

      // Struct types might have leading zero-length elements like [0 x i32],

      // which are certainly not what we are looking for, so skip them.

      unsigned Elem = 0;

      Constant *ElemC;

      do {

        ElemC = C->getAggregateElement(Elem++);

      } while (ElemC && DL.getTypeSizeInBits(ElemC->getType()).isZero());

      C = ElemC;

    } else {

      // For non-byte-sized vector elements, the first element is not

      // necessarily located at the vector base address.

      if (auto *VT = dyn_cast<VectorType>(SrcTy))

        if (!DL.typeSizeEqualsStoreSize(VT->getElementType()))

          return nullptr;

      C = C->getAggregateElement(0u);

    }

  } while (C);

  return nullptr;

}

namespace {

/// Recursive helper to read bits out of global. C is the constant being copied

/// out of. ByteOffset is an offset into C. CurPtr is the pointer to copy

/// results into and BytesLeft is the number of bytes left in

/// the CurPtr buffer. DL is the DataLayout.

bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset, unsigned char *CurPtr,

                        unsigned BytesLeft, const DataLayout &DL) {

  assert(ByteOffset <= DL.getTypeAllocSize(C->getType()) &&

         "Out of range access");

  // If this element is zero or undefined, we can just return since *CurPtr is

  // zero initialized.

  if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C))

    return true;

  if (auto *CI = dyn_cast<ConstantInt>(C)) {

    if ((CI->getBitWidth() & 7) != 0)

      return false;

    const APInt &Val = CI->getValue();

    unsigned IntBytes = unsigned(CI->getBitWidth()/8);

    for (unsigned i = 0; i != BytesLeft && ByteOffset != IntBytes; ++i) {

      unsigned n = ByteOffset;

      if (!DL.isLittleEndian())

        n = IntBytes - n - 1;

      CurPtr[i] = Val.extractBits(8, n * 8).getZExtValue();

      ++ByteOffset;

    }

    return true;

  }

  if (auto *CFP = dyn_cast<ConstantFP>(C)) {

    if (CFP->getType()->isDoubleTy()) {

      C = FoldBitCast(C, Type::getInt64Ty(C->getContext()), DL);

      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, DL);

    }

    if (CFP->getType()->isFloatTy()){

      C = FoldBitCast(C, Type::getInt32Ty(C->getContext()), DL);

      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, DL);

    }

    if (CFP->getType()->isHalfTy()){

      C = FoldBitCast(C, Type::getInt16Ty(C->getContext()), DL);

      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, DL);

    }

    return false;

  }

  if (auto *CS = dyn_cast<ConstantStruct>(C)) {

    const StructLayout *SL = DL.getStructLayout(CS->getType());

    unsigned Index = SL->getElementContainingOffset(ByteOffset);

    uint64_t CurEltOffset = SL->getElementOffset(Index);

    ByteOffset -= CurEltOffset;

    while (true) {

      // If the element access is to the element itself and not to tail padding,

      // read the bytes from the element.

      uint64_t EltSize = DL.getTypeAllocSize(CS->getOperand(Index)->getType());

      if (ByteOffset < EltSize &&

          !ReadDataFromGlobal(CS->getOperand(Index), ByteOffset, CurPtr,

                              BytesLeft, DL))

        return false;

      ++Index;

      // Check to see if we read from the last struct element, if so we're done.

      if (Index == CS->getType()->getNumElements())

        return true;

      // If we read all of the bytes we needed from this element we're done.

      uint64_t NextEltOffset = SL->getElementOffset(Index);

      if (BytesLeft <= NextEltOffset - CurEltOffset - ByteOffset)

        return true;

      // Move to the next element of the struct.

      CurPtr += NextEltOffset - CurEltOffset - ByteOffset;

      BytesLeft -= NextEltOffset - CurEltOffset - ByteOffset;

      ByteOffset = 0;

      CurEltOffset = NextEltOffset;

    }

    // not reached.

  }

  if (isa<ConstantArray>(C) || isa<ConstantVector>(C) ||

      isa<ConstantDataSequential>(C)) {

    uint64_t NumElts, EltSize;

    Type *EltTy;

    if (auto *AT = dyn_cast<ArrayType>(C->getType())) {

      NumElts = AT->getNumElements();

      EltTy = AT->getElementType();

      EltSize = DL.getTypeAllocSize(EltTy);

    } else {

      NumElts = cast<FixedVectorType>(C->getType())->getNumElements();

      EltTy = cast<FixedVectorType>(C->getType())->getElementType();

      // TODO: For non-byte-sized vectors, current implementation assumes there is

      // padding to the next byte boundary between elements.

      if (!DL.typeSizeEqualsStoreSize(EltTy))

        return false;

      EltSize = DL.getTypeStoreSize(EltTy);

    }

    uint64_t Index = ByteOffset / EltSize;

    uint64_t Offset = ByteOffset - Index * EltSize;

    for (; Index != NumElts; ++Index) {

      if (!ReadDataFromGlobal(C->getAggregateElement(Index), Offset, CurPtr,

                              BytesLeft, DL))

        return false;

      uint64_t BytesWritten = EltSize - Offset;

      assert(BytesWritten <= EltSize && "Not indexing into this element?");

      if (BytesWritten >= BytesLeft)

        return true;

      Offset = 0;

      BytesLeft -= BytesWritten;

      CurPtr += BytesWritten;

    }

    return true;

  }

  if (auto *CE = dyn_cast<ConstantExpr>(C)) {

    if (CE->getOpcode() == Instruction::IntToPtr &&

        CE->getOperand(0)->getType() == DL.getIntPtrType(CE->getType())) {

      return ReadDataFromGlobal(CE->getOperand(0), ByteOffset, CurPtr,

                                BytesLeft, DL);

    }

  }

  // Otherwise, unknown initializer type.

  return false;

}

Constant *FoldReinterpretLoadFromConst(Constant *C, Type *LoadTy,

                                       int64_t Offset, const DataLayout &DL) {

  // Bail out early. Not expect to load from scalable global variable.

  if (isa<ScalableVectorType>(LoadTy))

    return nullptr;

  auto *IntType = dyn_cast<IntegerType>(LoadTy);

  // If this isn't an integer load we can't fold it directly.

  if (!IntType) {

    // If this is a non-integer load, we can try folding it as an int load and

    // then bitcast the result.  This can be useful for union cases.  Note

    // that address spaces don't matter here since we're not going to result in

    // an actual new load.

    if (!LoadTy->isFloatingPointTy() && !LoadTy->isPointerTy() &&

        !LoadTy->isVectorTy())

      return nullptr;

    Type *MapTy = Type::getIntNTy(C->getContext(),

                                  DL.getTypeSizeInBits(LoadTy).getFixedValue());

    if (Constant *Res = FoldReinterpretLoadFromConst(C, MapTy, Offset, DL)) {

      if (Res->isNullValue() && !LoadTy->isX86_MMXTy() &&

          !LoadTy->isX86_AMXTy())

        // Materializing a zero can be done trivially without a bitcast

        return Constant::getNullValue(LoadTy);

      Type *CastTy = LoadTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(LoadTy) : LoadTy;

      Res = FoldBitCast(Res, CastTy, DL);

      if (LoadTy->isPtrOrPtrVectorTy()) {

        // For vector of pointer, we needed to first convert to a vector of integer, then do vector inttoptr

        if (Res->isNullValue() && !LoadTy->isX86_MMXTy() &&

            !LoadTy->isX86_AMXTy())

          return Constant::getNullValue(LoadTy);

        if (DL.isNonIntegralPointerType(LoadTy->getScalarType()))

          // Be careful not to replace a load of an addrspace value with an inttoptr here

          return nullptr;

        Res = ConstantExpr::getIntToPtr(Res, LoadTy);

      }

      return Res;

    }

    return nullptr;

  }

  unsigned BytesLoaded = (IntType->getBitWidth() + 7) / 8;

  if (BytesLoaded > 32 || BytesLoaded == 0)

    return nullptr;

  // If we're not accessing anything in this constant, the result is undefined.

  if (Offset <= -1 * static_cast<int64_t>(BytesLoaded))

    return PoisonValue::get(IntType);

  // TODO: We should be able to support scalable types.

  TypeSize InitializerSize = DL.getTypeAllocSize(C->getType());

  if (InitializerSize.isScalable())

    return nullptr;

  // If we're not accessing anything in this constant, the result is undefined.

  if (Offset >= (int64_t)InitializerSize.getFixedValue())

    return PoisonValue::get(IntType);

  unsigned char RawBytes[32] = {0};

  unsigned char *CurPtr = RawBytes;

  unsigned BytesLeft = BytesLoaded;

  // If we're loading off the beginning of the global, some bytes may be valid.

  if (Offset < 0) {

    CurPtr += -Offset;

    BytesLeft += Offset;

    Offset = 0;

  }

  if (!ReadDataFromGlobal(C, Offset, CurPtr, BytesLeft, DL))

    return nullptr;

  APInt ResultVal = APInt(IntType->getBitWidth(), 0);

  if (DL.isLittleEndian()) {

    ResultVal = RawBytes[BytesLoaded - 1];

    for (unsigned i = 1; i != BytesLoaded; ++i) {

      ResultVal <<= 8;

      ResultVal |= RawBytes[BytesLoaded - 1 - i];

    }

  } else {

    ResultVal = RawBytes[0];

    for (unsigned i = 1; i != BytesLoaded; ++i) {

      ResultVal <<= 8;

      ResultVal |= RawBytes[i];

    }

  }

  return ConstantInt::get(IntType->getContext(), ResultVal);

}

} // anonymous namespace

// If GV is a constant with an initializer read its representation starting

// at Offset and return it as a constant array of unsigned char.  Otherwise

// return null.

Constant *llvm::ReadByteArrayFromGlobal(const GlobalVariable *GV,

                                        uint64_t Offset) {

  if (!GV->isConstant() || !GV->hasDefinitiveInitializer())

    return nullptr;

  const DataLayout &DL = GV->getParent()->getDataLayout();

  Constant *Init = const_cast<Constant *>(GV->getInitializer());

  TypeSize InitSize = DL.getTypeAllocSize(Init->getType());

  if (InitSize < Offset)

    return nullptr;

  uint64_t NBytes = InitSize - Offset;

  if (NBytes > UINT16_MAX)

    // Bail for large initializers in excess of 64K to avoid allocating

    // too much memory.

    // Offset is assumed to be less than or equal than InitSize (this

    // is enforced in ReadDataFromGlobal).

    return nullptr;

  SmallVector<unsigned char, 256> RawBytes(static_cast<size_t>(NBytes));

  unsigned char *CurPtr = RawBytes.data();

  if (!ReadDataFromGlobal(Init, Offset, CurPtr, NBytes, DL))

    return nullptr;

  return ConstantDataArray::get(GV->getContext(), RawBytes);

}

/// If this Offset points exactly to the start of an aggregate element, return

/// that element, otherwise return nullptr.

Constant *getConstantAtOffset(Constant *Base, APInt Offset,

                              const DataLayout &DL) {

  if (Offset.isZero())

    return Base;

  if (!isa<ConstantAggregate>(Base) && !isa<ConstantDataSequential>(Base))

    return nullptr;

  Type *ElemTy = Base->getType();

  SmallVector<APInt> Indices = DL.getGEPIndicesForOffset(ElemTy, Offset);

  if (!Offset.isZero() || !Indices[0].isZero())

    return nullptr;

  Constant *C = Base;

  for (const APInt &Index : drop_begin(Indices)) {

    if (Index.isNegative() || Index.getActiveBits() >= 32)

      return nullptr;

    C = C->getAggregateElement(Index.getZExtValue());

    if (!C)

      return nullptr;

  }

  return C;

}

Constant *llvm::ConstantFoldLoadFromConst(Constant *C, Type *Ty,

                                          const APInt &Offset,

                                          const DataLayout &DL) {

  if (Constant *AtOffset = getConstantAtOffset(C, Offset, DL))

    if (Constant *Result = ConstantFoldLoadThroughBitcast(AtOffset, Ty, DL))

      return Result;

  // Explicitly check for out-of-bounds access, so we return poison even if the

  // constant is a uniform value.

  TypeSize Size = DL.getTypeAllocSize(C->getType());

  if (!Size.isScalable() && Offset.sge(Size.getFixedValue()))

    return PoisonValue::get(Ty);

  // Try an offset-independent fold of a uniform value.

  if (Constant *Result = ConstantFoldLoadFromUniformValue(C, Ty))

    return Result;

  // Try hard to fold loads from bitcasted strange and non-type-safe things.

  if (Offset.getSignificantBits() <= 64)

    if (Constant *Result =

            FoldReinterpretLoadFromConst(C, Ty, Offset.getSExtValue(), DL))

      return Result;

  return nullptr;

}

Constant *llvm::ConstantFoldLoadFromConst(Constant *C, Type *Ty,

                                          const DataLayout &DL) {

  return ConstantFoldLoadFromConst(C, Ty, APInt(64, 0), DL);

}

Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,

                                             APInt Offset,

                                             const DataLayout &DL) {

  // We can only fold loads from constant globals with a definitive initializer.

  // Check this upfront, to skip expensive offset calculations.

  auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(C));

  if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())

    return nullptr;

  C = cast<Constant>(C->stripAndAccumulateConstantOffsets(

          DL, Offset, /* AllowNonInbounds */ true));

  if (C == GV)

    if (Constant *Result = ConstantFoldLoadFromConst(GV->getInitializer(), Ty,

                                                     Offset, DL))

      return Result;

  // If this load comes from anywhere in a uniform constant global, the value

  // is always the same, regardless of the loaded offset.

  return ConstantFoldLoadFromUniformValue(GV->getInitializer(), Ty);

}

Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,

                                             const DataLayout &DL) {

  APInt Offset(DL.getIndexTypeSizeInBits(C->getType()), 0);

  return ConstantFoldLoadFromConstPtr(C, Ty, Offset, DL);

}

Constant *llvm::ConstantFoldLoadFromUniformValue(Constant *C, Type *Ty) {

  if (isa<PoisonValue>(C))

    return PoisonValue::get(Ty);

  if (isa<UndefValue>(C))

    return UndefValue::get(Ty);

  if (C->isNullValue() && !Ty->isX86_MMXTy() && !Ty->isX86_AMXTy())

    return Constant::getNullValue(Ty);

  if (C->isAllOnesValue() &&

      (Ty->isIntOrIntVectorTy() || Ty->isFPOrFPVectorTy()))

    return Constant::getAllOnesValue(Ty);

  return nullptr;

}

namespace {

/// One of Op0/Op1 is a constant expression.

/// Attempt to symbolically evaluate the result of a binary operator merging

/// these together.  If target data info is available, it is provided as DL,

/// otherwise DL is null.

Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, Constant *Op1,

                                    const DataLayout &DL) {

  // SROA

  // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl.

  // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute

  // bits.

  if (Opc == Instruction::And) {

    KnownBits Known0 = computeKnownBits(Op0, DL);

    KnownBits Known1 = computeKnownBits(Op1, DL);

    if ((Known1.One | Known0.Zero).isAllOnes()) {

      // All the bits of Op0 that the 'and' could be masking are already zero.

      return Op0;

    }

    if ((Known0.One | Known1.Zero).isAllOnes()) {

      // All the bits of Op1 that the 'and' could be masking are already zero.

      return Op1;

    }

    Known0 &= Known1;

    if (Known0.isConstant())

      return ConstantInt::get(Op0->getType(), Known0.getConstant());

  }

  // If the constant expr is something like &A[123] - &A[4].f, fold this into a

  // constant.  This happens frequently when iterating over a global array.

  if (Opc == Instruction::Sub) {

    GlobalValue *GV1, *GV2;

    APInt Offs1, Offs2;

    if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, DL))

      if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, DL) && GV1 == GV2) {

        unsigned OpSize = DL.getTypeSizeInBits(Op0->getType());

        // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow.

        // PtrToInt may change the bitwidth so we have convert to the right size

        // first.

        return ConstantInt::get(Op0->getType(), Offs1.zextOrTrunc(OpSize) -

                                                Offs2.zextOrTrunc(OpSize));

      }

  }

  return nullptr;

}

/// If array indices are not pointer-sized integers, explicitly cast them so

/// that they aren't implicitly casted by the getelementptr.

Constant *CastGEPIndices(Type *SrcElemTy, ArrayRef<Constant *> Ops,

                         Type *ResultTy, bool InBounds,

                         std::optional<unsigned> InRangeIndex,

                         const DataLayout &DL, const TargetLibraryInfo *TLI) {

  Type *IntIdxTy = DL.getIndexType(ResultTy);

  Type *IntIdxScalarTy = IntIdxTy->getScalarType();

  bool Any = false;

  SmallVector<Constant*, 32> NewIdxs;

  for (unsigned i = 1, e = Ops.size(); i != e; ++i) {

    if ((i == 1 ||

         !isa<StructType>(GetElementPtrInst::getIndexedType(

             SrcElemTy, Ops.slice(1, i - 1)))) &&

        Ops[i]->getType()->getScalarType() != IntIdxScalarTy) {

      Any = true;

      Type *NewType =

          Ops[i]->getType()->isVectorTy() ? IntIdxTy : IntIdxScalarTy;

      Constant *NewIdx = ConstantFoldCastOperand(

          CastInst::getCastOpcode(Ops[i], true, NewType, true), Ops[i], NewType,

          DL);

      if (!NewIdx)

        return nullptr;

      NewIdxs.push_back(NewIdx);

    } else

      NewIdxs.push_back(Ops[i]);

  }

  if (!Any)

    return nullptr;

  Constant *C = ConstantExpr::getGetElementPtr(

      SrcElemTy, Ops[0], NewIdxs, InBounds, InRangeIndex);

  return ConstantFoldConstant(C, DL, TLI);

}

/// If we can symbolically evaluate the GEP constant expression, do so.

Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,

                                  ArrayRef<Constant *> Ops,

                                  const DataLayout &DL,

                                  const TargetLibraryInfo *TLI) {

  const GEPOperator *InnermostGEP = GEP;

  bool InBounds = GEP->isInBounds();

  Type *SrcElemTy = GEP->getSourceElementType();

  Type *ResElemTy = GEP->getResultElementType();

  Type *ResTy = GEP->getType();

  if (!SrcElemTy->isSized() || isa<ScalableVectorType>(SrcElemTy))

    return nullptr;

  if (Constant *C = CastGEPIndices(SrcElemTy, Ops, ResTy,

                                   GEP->isInBounds(), GEP->getInRangeIndex(),

                                   DL, TLI))

    return C;

  Constant *Ptr = Ops[0];

  if (!Ptr->getType()->isPointerTy())

    return nullptr;

  Type *IntIdxTy = DL.getIndexType(Ptr->getType());

  for (unsigned i = 1, e = Ops.size(); i != e; ++i)

    if (!isa<ConstantInt>(Ops[i]))

      return nullptr;

  unsigned BitWidth = DL.getTypeSizeInBits(IntIdxTy);

  APInt Offset = APInt(

      BitWidth,

      DL.getIndexedOffsetInType(

          SrcElemTy, ArrayRef((Value *const *)Ops.data() + 1, Ops.size() - 1)));

  // If this is a GEP of a GEP, fold it all into a single GEP.

  while (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {

    InnermostGEP = GEP;

    InBounds &= GEP->isInBounds();

    SmallVector<Value *, 4> NestedOps(llvm::drop_begin(GEP->operands()));

    // Do not try the incorporate the sub-GEP if some index is not a number.

    bool AllConstantInt = true;

    for (Value *NestedOp : NestedOps)

      if (!isa<ConstantInt>(NestedOp)) {

        AllConstantInt = false;

        break;

      }

    if (!AllConstantInt)

      break;

    Ptr = cast<Constant>(GEP->getOperand(0));

    SrcElemTy = GEP->getSourceElementType();

    Offset += APInt(BitWidth, DL.getIndexedOffsetInType(SrcElemTy, NestedOps));

  }

  // If the base value for this address is a literal integer value, fold the

  // getelementptr to the resulting integer value casted to the pointer type.

  APInt BasePtr(BitWidth, 0);

  if (auto *CE = dyn_cast<ConstantExpr>(Ptr)) {

    if (CE->getOpcode() == Instruction::IntToPtr) {

      if (auto *Base = dyn_cast<ConstantInt>(CE->getOperand(0)))

        BasePtr = Base->getValue().zextOrTrunc(BitWidth);

    }

  }

  auto *PTy = cast<PointerType>(Ptr->getType());

  if ((Ptr->isNullValue() || BasePtr != 0) &&

      !DL.isNonIntegralPointerType(PTy)) {

    Constant *C = ConstantInt::get(Ptr->getContext(), Offset + BasePtr);

    return ConstantExpr::getIntToPtr(C, ResTy);

  }

  // Otherwise form a regular getelementptr. Recompute the indices so that

  // we eliminate over-indexing of the notional static type array bounds.

  // This makes it easy to determine if the getelementptr is "inbounds".

  // For GEPs of GlobalValues, use the value type, otherwise use an i8 GEP.

  if (auto *GV = dyn_cast<GlobalValue>(Ptr))

    SrcElemTy = GV->getValueType();

  else

    SrcElemTy = Type::getInt8Ty(Ptr->getContext());

  if (!SrcElemTy->isSized())

    return nullptr;

  Type *ElemTy = SrcElemTy;

  SmallVector<APInt> Indices = DL.getGEPIndicesForOffset(ElemTy, Offset);

  if (Offset != 0)

    return nullptr;

  // Try to add additional zero indices to reach the desired result element

  // type.

  // TODO: Should we avoid extra zero indices if ResElemTy can't be reached and

  // we'll have to insert a bitcast anyway?

  while (ElemTy != ResElemTy) {

    Type *NextTy = GetElementPtrInst::getTypeAtIndex(ElemTy, (uint64_t)0);

    if (!NextTy)

      break;

    Indices.push_back(APInt::getZero(isa<StructType>(ElemTy) ? 32 : BitWidth));

    ElemTy = NextTy;

  }

  SmallVector<Constant *, 32> NewIdxs;

  for (const APInt &Index : Indices)

    NewIdxs.push_back(ConstantInt::get(

        Type::getIntNTy(Ptr->getContext(), Index.getBitWidth()), Index));

  // Preserve the inrange index from the innermost GEP if possible. We must

  // have calculated the same indices up to and including the inrange index.

  std::optional<unsigned> InRangeIndex;

  if (std::optional<unsigned> LastIRIndex = InnermostGEP->getInRangeIndex())

    if (SrcElemTy == InnermostGEP->getSourceElementType() &&

        NewIdxs.size() > *LastIRIndex) {

      InRangeIndex = LastIRIndex;

      for (unsigned I = 0; I <= *LastIRIndex; ++I)

        if (NewIdxs[I] != InnermostGEP->getOperand(I + 1))

          return nullptr;

    }

  // Create a GEP.

  return ConstantExpr::getGetElementPtr(SrcElemTy, Ptr, NewIdxs, InBounds,

                                        InRangeIndex);

}

/// Attempt to constant fold an instruction with the

/// specified opcode and operands.  If successful, the constant result is

/// returned, if not, null is returned.  Note that this function can fail when

/// attempting to fold instructions like loads and stores, which have no

/// constant expression form.

Constant *ConstantFoldInstOperandsImpl(const Value *InstOrCE, unsigned Opcode,

                                       ArrayRef<Constant *> Ops,

                                       const DataLayout &DL,

                                       const TargetLibraryInfo *TLI) {

  Type *DestTy = InstOrCE->getType();

  if (Instruction::isUnaryOp(Opcode))

    return ConstantFoldUnaryOpOperand(Opcode, Ops[0], DL);

  if (Instruction::isBinaryOp(Opcode)) {

    switch (Opcode) {

    default:

      break;

    case Instruction::FAdd:

    case Instruction::FSub:

    case Instruction::FMul:

    case Instruction::FDiv:

    case Instruction::FRem:

      // Handle floating point instructions separately to account for denormals

      // TODO: If a constant expression is being folded rather than an

      // instruction, denormals will not be flushed/treated as zero

      if (const auto *I = dyn_cast<Instruction>(InstOrCE)) {

        return ConstantFoldFPInstOperands(Opcode, Ops[0], Ops[1], DL, I);

      }

    }

    return ConstantFoldBinaryOpOperands(Opcode, Ops[0], Ops[1], DL);

  }

  if (Instruction::isCast(Opcode))

    return ConstantFoldCastOperand(Opcode, Ops[0], DestTy, DL);

  if (auto *GEP = dyn_cast<GEPOperator>(InstOrCE)) {

    Type *SrcElemTy = GEP->getSourceElementType();

    if (!ConstantExpr::isSupportedGetElementPtr(SrcElemTy))

      return nullptr;

    if (Constant *C = SymbolicallyEvaluateGEP(GEP, Ops, DL, TLI))

      return C;

    return ConstantExpr::getGetElementPtr(SrcElemTy, Ops[0], Ops.slice(1),

                                          GEP->isInBounds(),

                                          GEP->getInRangeIndex());

  }

  if (auto *CE = dyn_cast<ConstantExpr>(InstOrCE)) {

    if (CE->isCompare())

      return ConstantFoldCompareInstOperands(CE->getPredicate(), Ops[0], Ops[1],

                                             DL, TLI);

    return CE->getWithOperands(Ops);

  }

  switch (Opcode) {