LoweringHelpers.cpp

Go to the documentation of this file.

//====- LoweringHelpers.cpp - Lowering helper functions -------------------===//
//
// 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 contains helper functions for lowering from CIR to LLVM or MLIR.
//
//===----------------------------------------------------------------------===//
 
#include "clang/CIR/LoweringHelpers.h"
#include "mlir/Dialect/LLVMIR/LLVMDialect.h"
#include "mlir/Dialect/LLVMIR/LLVMTypes.h"
#include "mlir/IR/BuiltinTypes.h"
#include "mlir/IR/SymbolTable.h"
#include "mlir/Interfaces/DataLayoutInterfaces.h"
#include "clang/CIR/MissingFeatures.h"
 
namespace {
/// A _BitInt(N) whose padded storage integer iM has a larger alloc size than
/// its M/8 store size is laid out by clang as a byte array, not a plain
/// integer (e.g. _BitInt(129) -> i192 with alloc size 32 != store size 24).
/// That "split" storage form is not yet implemented; lowerings must detect
/// it and report errorNYI rather than emit the wrong-sized integer.
bool isSplitStorageBitInt(cir::IntType ty, const mlir::DataLayout &dataLayout) {
  if (!ty.isBitInt())
    return false;
  unsigned storageBits = ty.getStorageTypeWidth(dataLayout);
  auto storageTy = mlir::IntegerType::get(ty.getContext(), storageBits);
  uint64_t storeSize = storageBits / 8;
  uint64_t allocSize =
      llvm::alignTo(storeSize, dataLayout.getTypeABIAlignment(storageTy));
  return allocSize != storeSize;
}
 
/// Checks if `dataLayout` describes a big endian layout.
bool isBigEndian(const mlir::DataLayout &dataLayout) {
  auto endiannessStr =
      mlir::dyn_cast_or_null<mlir::StringAttr>(dataLayout.getEndianness());
  return endiannessStr && endiannessStr == "big";
}
} // namespace
 
mlir::Attribute getBitIntStorageAttr(mlir::ConversionPatternRewriter &rewriter,
                                     cir::IntAttr attr,
                                     const mlir::DataLayout &dataLayout) {
  auto intTy = mlir::cast<cir::IntType>(attr.getType());
  unsigned storageBits = intTy.getStorageTypeWidth(dataLayout);
  llvm::APInt val = attr.getValue();
  val = intTy.isSigned() ? val.sext(storageBits) : val.zext(storageBits);
 
  if (!isSplitStorageBitInt(intTy, dataLayout))
    return rewriter.getIntegerAttr(
        mlir::IntegerType::get(intTy.getContext(), storageBits), val);
 
  if (isBigEndian(dataLayout))
    val = val.byteSwap();
 
  // If we have to do split storage, we are an array of bytes.  Split this up
  // into the array that matches convertTypeForMemory.
  unsigned numBytes = storageBits / 8;
  llvm::SmallVector<mlir::APInt> bytes;
  bytes.reserve(numBytes);
  for (unsigned i = 0; i != numBytes; ++i)
    bytes.emplace_back(8, val.extractBitsAsZExtValue(8, i * 8));
 
  auto i8Ty = mlir::IntegerType::get(intTy.getContext(), 8);
  return mlir::DenseElementsAttr::get(
      mlir::RankedTensorType::get({numBytes}, i8Ty), bytes);
}
 
mlir::Type convertTypeForMemory(const mlir::TypeConverter &converter,
                                mlir::DataLayout const &dataLayout,
                                mlir::Type type, bool isForHLSL) {
  // TODO(cir): Handle other types similarly to clang's codegen
  // convertTypeForMemory
  if (mlir::isa<cir::BoolType>(type)) {
    return mlir::IntegerType::get(type.getContext(),
                                  dataLayout.getTypeSizeInBits(type));
  }
 
  if (auto matrixTy = mlir::dyn_cast<cir::MatrixType>(type)) {
    if (isForHLSL) {
      unsigned vecLen = matrixTy.getNumRows();
      unsigned arrayLen = matrixTy.getNumColumns();
      mlir::Type elementType = converter.convertType(matrixTy.getElementType());
      auto vecTy = mlir::VectorType::get(vecLen, elementType);
      return mlir::LLVM::LLVMArrayType::get(vecTy, arrayLen);
    }
 
    uint64_t size = matrixTy.getNumRows() * matrixTy.getNumColumns();
    mlir::Type elementType = converter.convertType(matrixTy.getElementType());
    return mlir::LLVM::LLVMArrayType::get(elementType, size);
  }
 
  if (auto vecTy = mlir::dyn_cast<cir::VectorType>(type)) {
    if (mlir::isa<cir::BoolType>(vecTy.getElementType())) {
      assert(!cir::MissingFeatures::hlsl());
      return mlir::IntegerType::get(type.getContext(),
                                    vecTy.getBoolStorageWidth());
    }
  }
 
  // _BitInt(N) keeps its literal width as a value but is stored in a padded
  // integer iM in memory, the same way bool is i1 as a value and i8 in
  // memory. When iM's own LLVM alloc size would overshoot the AST-exact
  // M/8 byte count (isSplitStorageBitInt), use a byte array instead so the
  // size stays exact.
  if (auto intTy = mlir::dyn_cast<cir::IntType>(type);
      intTy && intTy.isBitInt()) {
    if (isSplitStorageBitInt(intTy, dataLayout))
      return mlir::LLVM::LLVMArrayType::get(
          mlir::IntegerType::get(type.getContext(), 8),
          intTy.getStorageTypeWidth(dataLayout) / 8);
    return mlir::IntegerType::get(type.getContext(),
                                  intTy.getStorageTypeWidth(dataLayout));
  }
 
  return converter.convertType(type);
}
 
mlir::Type convertTypeForLoadStore(const mlir::TypeConverter &converter,
                                   mlir::DataLayout const &dataLayout,
                                   mlir::Type type) {
  // A split-storage _BitInt's memory type is a byte array (see
  // convertTypeForMemory), but a load/store must still access the whole
  // integer as-is.
  if (auto intTy = mlir::dyn_cast<cir::IntType>(type);
      intTy && intTy.isBitInt())
    return mlir::IntegerType::get(type.getContext(),
                                  intTy.getStorageTypeWidth(dataLayout));
 
  // Convert the Matrix type to a vector type (the value type of
  // MatrixType), if it points to a array (the memory type of MatrixType).
  if (auto matrixTy = mlir::dyn_cast<cir::MatrixType>(type)) {
    uint64_t size = matrixTy.getNumRows() * matrixTy.getNumColumns();
    mlir::Type elemTy = converter.convertType(matrixTy.getElementType());
    return mlir::VectorType::get(size, elemTy);
  }
 
  return convertTypeForMemory(converter, dataLayout, type);
}
 
static unsigned getIntOrBoolBitWidth(mlir::Type ty) {
  if (auto intTy = mlir::dyn_cast<cir::IntType>(ty))
    return intTy.getWidth();
  assert(mlir::isa<cir::BoolType>(ty) &&
         "expected CIR integer or bool element type");
  return 1;
}
 
mlir::DenseElementsAttr
convertStringAttrToDenseElementsAttr(cir::ConstArrayAttr attr,
                                     mlir::Type type) {
  const auto stringAttr = mlir::cast<mlir::StringAttr>(attr.getElts());
  const auto arrayTy = mlir::cast<cir::ArrayType>(attr.getType());
  const unsigned totalSize = arrayTy.getSize();
  const unsigned trailingZeros = attr.getTrailingZerosNum();
  assert(stringAttr.size() + trailingZeros == totalSize &&
         "string const_array size must match explicit elements plus "
         "trailing_zeros");
 
  const unsigned bitWidth = getIntOrBoolBitWidth(arrayTy.getElementType());
  llvm::SmallVector<mlir::APInt> values;
  values.reserve(totalSize);
 
  // String bytes are raw values; interpret each as an unsigned byte so a
  // high-bit char (>= 0x80) does not sign-extend to a value that overflows
  // the element bit width when constructing the APInt.
  for (const char element : stringAttr)
    values.emplace_back(bitWidth, static_cast<unsigned char>(element));
 
  values.insert(values.end(), trailingZeros, mlir::APInt::getZero(bitWidth));
 
  return mlir::DenseElementsAttr::get(
      mlir::RankedTensorType::get({totalSize}, type), llvm::ArrayRef(values));
}
 
template <> mlir::APInt getZeroInitFromType(mlir::Type ty) {
  if (mlir::isa<cir::BoolType>(ty))
    return mlir::APInt::getZero(1);
  const auto intTy = mlir::cast<cir::IntType>(ty);
  return mlir::APInt::getZero(intTy.getWidth());
}
 
template <> mlir::APFloat getZeroInitFromType(mlir::Type ty) {
  auto fpTy = mlir::cast<cir::FPTypeInterface>(ty);
  return mlir::APFloat::getZero(fpTy.getFloatSemantics());
}
 
/// \param attr the ConstArrayAttr to convert
/// \param values the output parameter, the values array to fill
/// \param currentDims the shpae of tensor we're going to convert to
/// \param dimIndex the current dimension we're processing
/// \param currentIndex the current index in the values array
template <typename AttrTy, typename StorageTy>
bool convertToDenseElementsAttrImpl(
    cir::ConstArrayAttr attr, llvm::SmallVectorImpl<StorageTy> &values,
    const llvm::SmallVectorImpl<int64_t> &currentDims, int64_t dimIndex,
    int64_t currentIndex) {
  if (auto stringAttr = mlir::dyn_cast<mlir::StringAttr>(attr.getElts())) {
    if (auto arrayType = mlir::dyn_cast<cir::ArrayType>(attr.getType())) {
      for (auto element : stringAttr) {
        auto intAttr = cir::IntAttr::get(arrayType.getElementType(), element);
        values[currentIndex++] = mlir::dyn_cast<AttrTy>(intAttr).getValue();
      }
      // Remaining slots are trailing zeros; values was zero-initialized.
      currentIndex += attr.getTrailingZerosNum();
      return true;
    }
  }
 
  dimIndex++;
  std::size_t elementsSizeInCurrentDim = 1;
  for (std::size_t i = dimIndex; i < currentDims.size(); i++)
    elementsSizeInCurrentDim *= currentDims[i];
 
  auto arrayAttr = mlir::cast<mlir::ArrayAttr>(attr.getElts());
  for (auto eltAttr : arrayAttr) {
    if constexpr (std::is_same_v<StorageTy, mlir::APInt>) {
      if (auto boolAttr = mlir::dyn_cast<cir::BoolAttr>(eltAttr)) {
        values[currentIndex++] =
            llvm::APInt(1, static_cast<uint64_t>(boolAttr.getValue()));
        continue;
      }
    }
    if (auto valueAttr = mlir::dyn_cast<AttrTy>(eltAttr)) {
      values[currentIndex++] = valueAttr.getValue();
      continue;
    }
 
    if (auto subArrayAttr = mlir::dyn_cast<cir::ConstArrayAttr>(eltAttr)) {
      convertToDenseElementsAttrImpl<AttrTy>(subArrayAttr, values, currentDims,
                                             dimIndex, currentIndex);
      currentIndex += elementsSizeInCurrentDim;
      continue;
    }
 
    if (mlir::isa<cir::ZeroAttr, cir::UndefAttr>(eltAttr)) {
      currentIndex += elementsSizeInCurrentDim;
      continue;
    }
 
    // A global view can be the result of pointer conversions, so we can't
    // represent them as an APInt/APFloat.  So give up if we see one.
    if (auto global = mlir::dyn_cast<cir::GlobalViewAttr>(eltAttr))
      return false;
 
    llvm_unreachable("unknown element in ConstArrayAttr");
  }
  return true;
}
 
template <typename AttrTy, typename StorageTy>
std::optional<mlir::DenseElementsAttr> convertToDenseElementsAttr(
    cir::ConstArrayAttr attr, const llvm::SmallVectorImpl<int64_t> &dims,
    mlir::Type elementType, mlir::Type convertedElementType) {
  unsigned vectorSize = 1;
  for (auto dim : dims)
    vectorSize *= dim;
  auto values = llvm::SmallVector<StorageTy, 8>(
      vectorSize, getZeroInitFromType<StorageTy>(elementType));
 
  if (!convertToDenseElementsAttrImpl<AttrTy>(attr, values, dims,
                                              /*currentDim=*/0,
                                              /*initialIndex=*/0))
    return std::nullopt;
 
  return mlir::DenseElementsAttr::get(
      mlir::RankedTensorType::get(dims, convertedElementType),
      llvm::ArrayRef(values));
}
 
/// Return true when \p gv can be lowered to a \c FlatSymbolRefAttr leaf without
/// addrspacecast or bitcast (mirrors \c CIRAttrToValue::visitCirAttr).
static bool
globalViewMatchesPointerLeaf(cir::GlobalViewAttr gv, mlir::ModuleOp moduleOp,
                             mlir::SymbolTableCollection &symbolTables,
                             const mlir::TypeConverter *converter) {
  if (gv.getIndices() || mlir::isa<cir::IntType, cir::VPtrType>(gv.getType()))
    return false;
 
  auto ptrTy = mlir::dyn_cast<cir::PointerType>(gv.getType());
  if (!ptrTy)
    return false;
 
  unsigned sourceAddrSpace = 0;
  mlir::Type sourceType;
  auto sourceSymbol = symbolTables.lookupSymbolIn(moduleOp, gv.getSymbol());
  if (auto llvmSymbol = mlir::dyn_cast<mlir::LLVM::GlobalOp>(sourceSymbol)) {
    sourceType = llvmSymbol.getType();
    sourceAddrSpace = llvmSymbol.getAddrSpace();
  } else if (auto cirSymbol = mlir::dyn_cast<cir::GlobalOp>(sourceSymbol)) {
    sourceType = converter->convertType(cirSymbol.getSymType());
    if (auto targetAS = mlir::dyn_cast_if_present<cir::TargetAddressSpaceAttr>(
            cirSymbol.getAddrSpaceAttr()))
      sourceAddrSpace = targetAS.getValue();
  } else {
    // cir.func and other symbols not yet lowered to globals cannot be used as
    // bulk constant leaves; those cases keep the insertvalue fallback.
    return false;
  }
 
  auto llvmDstTy = converter->convertType<mlir::LLVM::LLVMPointerType>(ptrTy);
  if (llvmDstTy.getAddressSpace() != sourceAddrSpace)
    return false;
 
  mlir::Type llvmEltTy = converter->convertType(ptrTy.getPointee());
  if (llvmEltTy == sourceType)
    return true;
  if (auto arrTy = mlir::dyn_cast<mlir::LLVM::LLVMArrayType>(sourceType))
    return llvmEltTy == arrTy.getElementType();
  return false;
}
 
/// Lower a single pointer-element of a \c cir.const_array to an LLVM-dialect
/// constant leaf suitable for a bulk \c llvm.mlir.constant.  Only handles
/// address-of-global without indices and null pointers; indexed global views
/// must use the per-element \c llvm.insertvalue fallback.
static std::optional<mlir::Attribute>
lowerPointerElementAttr(mlir::Attribute elt, mlir::MLIRContext *ctx,
                        mlir::ModuleOp moduleOp,
                        mlir::SymbolTableCollection &symbolTables,
                        const mlir::TypeConverter *converter) {
  if (auto gv = mlir::dyn_cast<cir::GlobalViewAttr>(elt)) {
    if (!moduleOp ||
        !globalViewMatchesPointerLeaf(gv, moduleOp, symbolTables, converter))
      return std::nullopt;
    return gv.getSymbol();
  }
  if (auto nullPtr = mlir::dyn_cast<cir::ConstPtrAttr>(elt)) {
    if (nullPtr.isNullValue())
      return mlir::LLVM::ZeroAttr::get(ctx);
    return std::nullopt;
  }
  return std::nullopt;
}
 
static bool containsPoison(mlir::Attribute attr) {
  if (mlir::isa<cir::PoisonAttr>(attr))
    return true;
  if (auto elts = mlir::dyn_cast<mlir::ArrayAttr>(attr))
    return llvm::any_of(elts, containsPoison);
  if (auto constArr = mlir::dyn_cast<cir::ConstArrayAttr>(attr)) {
    if (mlir::isa<mlir::StringAttr>(constArr.getElts()))
      return false;
    if (auto elts = mlir::dyn_cast<mlir::ArrayAttr>(constArr.getElts()))
      return llvm::any_of(elts, containsPoison);
  }
  return false;
}
 
/// Block-address attributes (address-of-label and label differences) are
/// lowered to relocation expressions that cannot be materialized as part of a
/// dense/aggregate constant attribute; they require the per-element
/// insertvalue region lowering. Return true if \p attr contains any such
/// element.
static bool containsBlockAddress(mlir::Attribute attr) {
  if (mlir::isa<cir::BlockAddrInfoAttr, cir::BlockAddrDiffAttr>(attr))
    return true;
  if (auto elts = mlir::dyn_cast<mlir::ArrayAttr>(attr))
    return llvm::any_of(elts, containsBlockAddress);
  if (auto constArr = mlir::dyn_cast<cir::ConstArrayAttr>(attr)) {
    if (mlir::isa<mlir::StringAttr>(constArr.getElts()))
      return false;
    if (auto elts = mlir::dyn_cast<mlir::ArrayAttr>(constArr.getElts()))
      return llvm::any_of(elts, containsBlockAddress);
  }
  return false;
}
 
/// The fewest trailing zeros that adjustGlobalArrayTypeForInit splits off an
/// array constant into a zero-initialized tail, as in classic codegen.
static constexpr int minSplitTrailingZeros = 8;
 
static bool shouldSplitTrailingZeros(cir::ConstArrayAttr attr) {
  auto elts = mlir::dyn_cast<mlir::ArrayAttr>(attr.getElts());
  return elts && !elts.empty() &&
         attr.getTrailingZerosNum() >= minSplitTrailingZeros;
}
 
static bool containsSplitTrailingZeros(mlir::Attribute attr) {
  if (auto record = mlir::dyn_cast<cir::ConstRecordAttr>(attr))
    return llvm::any_of(record.getMembers(), containsSplitTrailingZeros);
  auto array = mlir::dyn_cast<cir::ConstArrayAttr>(attr);
  if (!array)
    return false;
  if (shouldSplitTrailingZeros(array))
    return true;
  auto elts = mlir::dyn_cast<mlir::ArrayAttr>(array.getElts());
  return elts && llvm::any_of(elts, containsSplitTrailingZeros);
}
 
mlir::Attribute spellOutSplitTrailingZeros(mlir::Attribute attr) {
  if (!containsSplitTrailingZeros(attr))
    return attr;
 
  if (auto record = mlir::dyn_cast<cir::ConstRecordAttr>(attr)) {
    auto members =
        llvm::map_to_vector(record.getMembers(), spellOutSplitTrailingZeros);
    return cir::ConstRecordAttr::get(
        mlir::cast<cir::RecordType>(record.getType()),
        mlir::ArrayAttr::get(attr.getContext(), members));
  }
 
  auto array = mlir::cast<cir::ConstArrayAttr>(attr);
  auto arrayTy = mlir::cast<cir::ArrayType>(array.getType());
  auto elts = llvm::map_to_vector(mlir::cast<mlir::ArrayAttr>(array.getElts()),
                                  spellOutSplitTrailingZeros);
  if (!shouldSplitTrailingZeros(array))
    return cir::ConstArrayAttr::get(
        arrayTy, mlir::ArrayAttr::get(attr.getContext(), elts),
        array.getTrailingZerosNum());
  elts.append(array.getTrailingZerosNum(),
              cir::ZeroAttr::get(arrayTy.getElementType()));
  return cir::ConstArrayAttr::get(arrayTy,
                                  mlir::ArrayAttr::get(attr.getContext(), elts),
                                  /*trailingZerosNum=*/0);
}
 
static std::optional<mlir::Attribute> lowerConstRecordMemberAttr(
    mlir::Attribute attr, mlir::SymbolTableCollection &symbolTables,
    const mlir::TypeConverter *converter, mlir::ModuleOp moduleOp);
 
/// Lower \p constArr, which is or contains an array split by
/// adjustGlobalArrayTypeForInit, element by element into the shape of its
/// adjusted type. A dense attribute would span the split-off zeros.
static std::optional<mlir::Attribute> lowerConstArrayAttrByElement(
    cir::ConstArrayAttr constArr, mlir::SymbolTableCollection &symbolTables,
    const mlir::TypeConverter *converter, mlir::ModuleOp moduleOp) {
  mlir::MLIRContext *ctx = constArr.getContext();
  auto arrayTy = mlir::cast<cir::ArrayType>(constArr.getType());
  auto elts = mlir::cast<mlir::ArrayAttr>(constArr.getElts());
  mlir::Type adjustedTy =
      adjustGlobalTypeForInit(converter->convertType(arrayTy), constArr,
                              *converter, mlir::DataLayout(moduleOp));
 
  llvm::SmallVector<mlir::Attribute> lowered;
  // Fewer members than elements: the elements were grouped into one array.
  auto structTy = mlir::dyn_cast<mlir::LLVM::LLVMStructType>(adjustedTy);
  if (structTy && structTy.getBody().size() < elts.size()) {
    auto prefix = cir::ConstArrayAttr::get(
        cir::ArrayType::get(arrayTy.getElementType(), elts.size()), elts);
    std::optional<mlir::Attribute> loweredPrefix =
        lowerConstArrayAttr(prefix, symbolTables, converter, moduleOp);
    if (!loweredPrefix)
      return std::nullopt;
    lowered.push_back(*loweredPrefix);
  } else {
    for (mlir::Attribute elt : elts) {
      std::optional<mlir::Attribute> loweredElt =
          lowerConstRecordMemberAttr(elt, symbolTables, converter, moduleOp);
      if (!loweredElt)
        return std::nullopt;
      lowered.push_back(*loweredElt);
    }
  }
 
  // A split array ends in one zero-initialized member; otherwise its few
  // trailing zeros are spelled out.
  lowered.append(
      shouldSplitTrailingZeros(constArr) ? 1 : constArr.getTrailingZerosNum(),
      mlir::LLVM::ZeroAttr::get(ctx));
  return mlir::ArrayAttr::get(ctx, lowered);
}
 
std::optional<mlir::Attribute> lowerConstArrayAttr(
    cir::ConstArrayAttr constArr, mlir::SymbolTableCollection &symbolTables,
    const mlir::TypeConverter *converter, mlir::ModuleOp moduleOp) {
  // Ensure ConstArrayAttr has a type.
  const auto typedConstArr = mlir::cast<mlir::TypedAttr>(constArr);
 
  // Ensure ConstArrayAttr type is a ArrayType.
  const auto cirArrayType = mlir::cast<cir::ArrayType>(typedConstArr.getType());
 
  // Is a ConstArrayAttr with an cir::ArrayType: fetch element type.
  mlir::Type type = cirArrayType;
  auto dims = llvm::SmallVector<int64_t, 2>{};
  while (auto arrayType = mlir::dyn_cast<cir::ArrayType>(type)) {
    dims.push_back(arrayType.getSize());
    type = arrayType.getElementType();
  }
 
  if (containsPoison(constArr))
    return std::nullopt;
 
  // Block-address initializers cannot be represented as a dense/aggregate
  // constant attribute; fall back to the per-element insertvalue lowering.
  if (containsBlockAddress(constArr))
    return std::nullopt;
 
  if (containsSplitTrailingZeros(constArr))
    return lowerConstArrayAttrByElement(constArr, symbolTables, converter,
                                        moduleOp);
 
  if (mlir::isa<mlir::StringAttr>(constArr.getElts()))
    return convertStringAttrToDenseElementsAttr(constArr,
                                                converter->convertType(type));
  if (mlir::isa<cir::IntType>(type)) {
    // A _BitInt array element is stored in a padded integer in memory; the
    // dense-attribute path here cannot express that widening, so fall back to
    // the insertvalue region, which widens each element via emitToMemory.
    if (mlir::cast<cir::IntType>(type).isBitInt())
      return std::nullopt;
    return convertToDenseElementsAttr<cir::IntAttr, mlir::APInt>(
        constArr, dims, type, converter->convertType(type));
  }
 
  if (mlir::isa<cir::BoolType>(type))
    return convertToDenseElementsAttr<cir::IntAttr, mlir::APInt>(
        constArr, dims, type, converter->convertType(type));
 
  if (mlir::isa<cir::FPTypeInterface>(type))
    return convertToDenseElementsAttr<cir::FPAttr, mlir::APFloat>(
        constArr, dims, type, converter->convertType(type));
 
  if (mlir::isa<cir::PointerType>(type)) {
    // FIXME: Pointer arrays with trailing_zeros (null-sentinel tables) fall
    // through to the insertvalue path for now.
    if (constArr.getTrailingZerosNum() > 0)
      return std::nullopt;
    auto eltsArr = mlir::dyn_cast<mlir::ArrayAttr>(constArr.getElts());
    if (!eltsArr)
      return std::nullopt;
    llvm::SmallVector<mlir::Attribute> lowered;
    lowered.reserve(eltsArr.size());
    mlir::MLIRContext *ctx = constArr.getContext();
    for (mlir::Attribute elt : eltsArr) {
      std::optional<mlir::Attribute> llvmElt =
          lowerPointerElementAttr(elt, ctx, moduleOp, symbolTables, converter);
      if (!llvmElt)
        return std::nullopt;
      lowered.push_back(*llvmElt);
    }
    return mlir::ArrayAttr::get(ctx, lowered);
  }
 
  if (mlir::isa<cir::RecordType>(type)) {
    // A record type is just an array of the element values.
    auto eltsArr = mlir::dyn_cast<mlir::ArrayAttr>(constArr.getElts());
    if (!eltsArr)
      return std::nullopt;
 
    llvm::SmallVector<mlir::Attribute> loweredElts;
    loweredElts.reserve(cirArrayType.getSize());
 
    for (mlir::Attribute elt : eltsArr) {
      std::optional<mlir::Attribute> llvmElt =
          lowerConstRecordMemberAttr(elt, symbolTables, converter, moduleOp);
      if (!llvmElt)
        return std::nullopt;
      loweredElts.push_back(*llvmElt);
    }
 
    // Remaining elts are either going to be padding (and should be undef), or
    // trailing-zeros. We can't really tell the difference as CIR lowering
    // doesn't differentiate anyway, so just zero-fill them.
    while (loweredElts.size() < cirArrayType.getSize())
      loweredElts.push_back(mlir::LLVM::ZeroAttr::get(constArr.getContext()));
    return mlir::ArrayAttr::get(constArr.getContext(), loweredElts);
  }
 
  return std::nullopt;
}
 
/// Lower a constant attribute that initializes a single member of a record (or
/// a leaf of a nested aggregate) to an LLVM-dialect attribute that can be
/// attached directly to an \c llvm.mlir.global, avoiding an insertvalue
/// initializer region. Returns \c std::nullopt when the attribute cannot be
/// represented as a single constant attribute (e.g. an indexed
/// \c GlobalViewAttr), in which case the caller falls back to the region-based
/// lowering.
static std::optional<mlir::Attribute> lowerConstRecordMemberAttr(
    mlir::Attribute attr, mlir::SymbolTableCollection &symbolTables,
    const mlir::TypeConverter *converter, mlir::ModuleOp moduleOp) {
  mlir::MLIRContext *ctx = attr.getContext();
 
  if (auto arrayAttr = mlir::dyn_cast<cir::ConstArrayAttr>(attr))
    return lowerConstArrayAttr(arrayAttr, symbolTables, converter, moduleOp);
 
  if (auto recordAttr = mlir::dyn_cast<cir::ConstRecordAttr>(attr))
    return lowerConstRecordAttr(recordAttr, symbolTables, converter, moduleOp);
 
  if (mlir::isa<cir::ZeroAttr>(attr))
    return mlir::LLVM::ZeroAttr::get(ctx);
 
  if (mlir::isa<cir::UndefAttr>(attr))
    return mlir::LLVM::UndefAttr::get(ctx);
 
  if (auto intAttr = mlir::dyn_cast<cir::IntAttr>(attr)) {
    // A _BitInt member is stored in a padded integer in memory; defer to the
    // insertvalue region (CIRAttrToValue), which performs the extension.
    if (mlir::cast<cir::IntType>(intAttr.getType()).isBitInt())
      return std::nullopt;
    return mlir::IntegerAttr::get(converter->convertType(intAttr.getType()),
                                  intAttr.getValue());
  }
 
  if (auto boolAttr = mlir::dyn_cast<cir::BoolAttr>(attr))
    return mlir::IntegerAttr::get(converter->convertType(boolAttr.getType()),
                                  boolAttr.getValue() ? 1 : 0);
 
  if (auto fpAttr = mlir::dyn_cast<cir::FPAttr>(attr))
    return mlir::FloatAttr::get(converter->convertType(fpAttr.getType()),
                                fpAttr.getValue());
 
  // Null pointers and simple address-of-global references can be represented
  // as constant attributes; anything more complex uses the region fallback.
  return lowerPointerElementAttr(attr, ctx, moduleOp, symbolTables, converter);
}
 
// Figure out if we want mark the new struct 'packed' if it isn't already. IF
// it is already, we have to keep that behavior. We pack it with logic similar
// to classic codegen, though will end up missing cases, since we don't want to
// change the type other than the FAM.
// We can do so if:
// 1- Packing it won't change any of the field offsets.
// 2- the non-padded struct would add padding beyond the
// flexible array member.  We don't pack if the flexible array member manages
// to not cause trailing padding.
static bool shouldPackFAMStruct(const mlir::DataLayout &dataLayout,
                                llvm::ArrayRef<mlir::Type> members) {
  uint64_t maxAlign = 1;
  uint64_t totalSize = 0;
  for (mlir::Type member : members) {
    uint64_t align = dataLayout.getTypeABIAlignment(member);
    maxAlign = std::max(maxAlign, align);
    uint64_t size = dataLayout.getTypeSize(member).getFixedValue();
 
    if (llvm::alignTo(totalSize, align) != totalSize)
      return false;
 
    totalSize += size;
  }
  return llvm::alignTo(totalSize, maxAlign) != totalSize;
}
 
// CIR supports flexible-array-members in its struct types. That is, a
// zero-length array as the last element, which can be initialized with an
// arbitrary number of elements. A ConstRecordAttr can be created with one of
// these, and our verifier allows it.  However, the LLVM implementation does NOT
// permit this. So we have to replace this type in LLVM with special struct for
// this value.
//
// Additionally, the struct itself could contain a struct with a FAM or a union
// that needed adjustment, so it recurses to check those.  If no such type has
// been found/no adjustment needed, this returns the type unchanged.
//
// Additionally, a union having an active member of not-the-largest
// alignment can cause the need for a small padding array. We also capture the
// original indices of the fields that had this padding prepended, so the
// lowerConstRecordAttr can later put in a 'zero' init there.
static mlir::Type adjustGlobalStructTypeForInit(
    mlir::LLVM::LLVMStructType structTy, cir::ConstRecordAttr constRecord,
    const mlir::TypeConverter &converter, const mlir::DataLayout &dataLayout,
    llvm::SmallVectorImpl<unsigned> &paddingAddedIndexes) {
  assert(paddingAddedIndexes.empty() &&
         "Not for accumulation, just single depth");
  llvm::ArrayRef<mlir::Attribute> initMembers =
      constRecord.getMembers().getValue();
  llvm::SmallVector<mlir::Type> origBody{structTy.getBody()};
  llvm::SmallVector<mlir::Type> newBody{};
  bool packed = structTy.isPacked();
  uint64_t curOffset = 0;
  bool changed = false;
 
  // Recursively adjust each member. A member that is itself a union (or a
  // struct containing one) lowers to a type that differs from its declared
  // field type, and this struct has to adopt that adjusted type so the
  // enclosing insertvalue chain type-checks.
  for (auto [idx, member] : llvm::enumerate(initMembers)) {
    if (idx >= origBody.size())
      break;
    mlir::Type adjusted =
        adjustGlobalTypeForInit(origBody[idx], member, converter, dataLayout);
    if (!adjusted)
      return {};
    unsigned adjustedAlign = dataLayout.getTypeABIAlignment(adjusted);
 
    if (adjusted != origBody[idx]) {
      // We're always going to 'change' the layout if it has changed, but we
      // need to see if there is new 'padding' that won't happen automatically
      // here based on alignment.
      unsigned origAlign = dataLayout.getTypeABIAlignment(origBody[idx]);
 
      uint64_t origOffset =
          packed ? curOffset : llvm::alignTo(curOffset, origAlign);
      uint64_t adjustedOffset =
          packed ? curOffset : llvm::alignTo(curOffset, adjustedAlign);
 
      if (adjustedOffset != origOffset) {
        // If the offset would change, we have to insert padding to make up for
        // it. This should only happen since alignment will decrease with
        // unions, so we should be able to assume adjusted-offset < origOffset?
        assert(adjustedOffset < origOffset);
        // Rather than just pad the difference between the offsets, we have to
        // fill in since the end of the last field, else we leave room thanks to
        // alignment between this field and the padding.
        uint64_t difference = origOffset - curOffset;
        newBody.push_back(mlir::LLVM::LLVMArrayType::get(
            mlir::IntegerType::get(structTy.getContext(), 8), difference));
        paddingAddedIndexes.push_back(idx);
        curOffset = origOffset;
      }
      changed = true;
    }
    newBody.push_back(adjusted);
 
    if (!packed)
      curOffset = llvm::alignTo(curOffset, adjustedAlign);
    curOffset += dataLayout.getTypeSize(adjusted).getFixedValue();
  }
 
  // CIR supports flexible-array-members in its struct types. That is, a
  // zero-length array as the last element, which can be initialized with an
  // arbitrary number of elements. A ConstRecordAttr can be created with one of
  // these, and our verifier allows it. However, the LLVM implementation does
  // NOT permit this, so we widen that trailing member to the initializer's
  // array type (packing the struct if that changes the layout).
  bool widenedFAM = false;
  if (auto fam =
          mlir::dyn_cast<mlir::LLVM::LLVMArrayType>(structTy.getBody().back());
      fam && fam.getNumElements() == 0) {
    mlir::Type lastInitType =
        mlir::cast<mlir::TypedAttr>(initMembers.back()).getType();
    if (mlir::cast<cir::ArrayType>(lastInitType).getSize() != 0) {
      newBody.back() =
          adjustGlobalTypeForInit(converter.convertType(lastInitType),
                                  initMembers.back(), converter, dataLayout);
      if (!newBody.back())
        return {};
      packed = packed || shouldPackFAMStruct(dataLayout, newBody);
      widenedFAM = true;
      changed = true;
    }
  }
 
  if (!changed)
    return structTy;
 
  // We've likely reduced the alignment, so make sure we put padding 'behind'
  // it.  We can skip this in the FAM case, since a Flexible array member is not
  // allowed to be initialized unless it is the 'last' element.  So it doesn't
  // need to be padded out.
  if (!widenedFAM) {
    uint64_t declaredSize = dataLayout.getTypeSize(structTy).getFixedValue();
    assert(curOffset <= declaredSize && "body bigger than type?");
    if (curOffset < declaredSize)
      newBody.push_back(mlir::LLVM::LLVMArrayType::get(
          mlir::IntegerType::get(structTy.getContext(), 8),
          declaredSize - curOffset));
  }
 
  return mlir::LLVM::LLVMStructType::getLiteral(structTy.getContext(), newBody,
                                                packed);
}
 
// A union constant only initializes its active member, but a union is lowered
// to its most-aligned member (its 'storage' type), which need not be the
// initialized one -- e.g. `union { char buf[16]; long cap; }` stores as `long`
// (higher alignment) but may be initialized through `buf`. So the storage type
// (and thus structTy) generally can't hold the active member's value. Rebuild
// an anonymous struct `{ <active member>, [pad x i8] }` that holds the active
// member followed by enough byte padding to span the union's full allocated
// size, mirroring classic codegen.
static mlir::Type adjustGlobalUnionTypeForInit(
    mlir::LLVM::LLVMStructType structTy, cir::ConstRecordAttr constRecord,
    const mlir::TypeConverter &converter, const mlir::DataLayout &dataLayout) {
 
  auto unionTy = mlir::cast<cir::UnionType>(constRecord.getType());
 
  // Unions can only initialize one field, so this has to be sizeof-one.
  assert(constRecord.getMembers().size() == 1);
  mlir::Attribute member = constRecord.getMembers()[0];
  mlir::Type memberTy = convertTypeForMemory(
      converter, dataLayout, mlir::cast<mlir::TypedAttr>(member).getType());
 
  // The active member may itself need adjusting (e.g. it is a nested union, or
  // a struct containing one), so recurse before using its type below.
  memberTy = adjustGlobalTypeForInit(memberTy, member, converter, dataLayout);
  if (!memberTy)
    return {};
 
  // The converted union type is { storage, [padding] }, where storage is the
  // union's most-aligned member. When the active member IS that storage type,
  // the converted type already describes this initializer exactly (the pad we
  // would compute equals the union's declared pad), so there is nothing to do.
  if (memberTy == structTy.getBody().front())
    return structTy;
 
  uint64_t unionSize = dataLayout.getTypeSize(unionTy).getFixedValue();
  uint64_t initSize = dataLayout.getTypeSize(memberTy).getFixedValue();
  llvm::SmallVector<mlir::Type> newBody;
  newBody.push_back(memberTy);
 
  // Pad to the union size unless a flexible array initializer is larger.
  if (initSize < unionSize)
    newBody.push_back(mlir::LLVM::LLVMArrayType::get(
        mlir::IntegerType::get(structTy.getContext(), 8),
        unionSize - initSize));
 
  return mlir::LLVM::LLVMStructType::getLiteral(structTy.getContext(), newBody,
                                                unionTy.getPacked());
}
 
// Unions in an array can cause individual elements to be of different types.
// This function adjusts the array type and replaces it with a struct type if
// necessary, OR leaves it as a 'new' array type if necessary.
//
// Like classic codegen, an array ending in many zeros becomes a packed struct
// of its explicit elements and one zero-initialized array, so the zeros are
// never spelled out:
//   <{ T0, T1, [N x T] }>
// or, when 8 or more elements share a type,
//   <{ [M x T], [N x T] }>
static mlir::Type adjustGlobalArrayTypeForInit(
    mlir::LLVM::LLVMArrayType arrayTy, cir::ConstArrayAttr arrayInit,
    const mlir::TypeConverter &converter, const mlir::DataLayout &dataLayout) {
  auto elts = mlir::dyn_cast<mlir::ArrayAttr>(arrayInit.getElts());
 
  if (!elts)
    return arrayTy;
 
  mlir::Type origEltTy = arrayTy.getElementType();
  llvm::SmallVector<mlir::Type> adjustedElts;
  adjustedElts.reserve(elts.size());
  bool changed = elts.size() > arrayTy.getNumElements();
 
  for (mlir::Attribute elt : elts) {
    mlir::Type adjusted =
        adjustGlobalTypeForInit(origEltTy, elt, converter, dataLayout);
    if (!adjusted)
      return {};
    changed |= adjusted != origEltTy;
    adjustedElts.push_back(adjusted);
  }
 
  if (shouldSplitTrailingZeros(arrayInit)) {
    mlir::Type commonEltTy =
        llvm::all_equal(adjustedElts) ? adjustedElts.front() : mlir::Type{};
    llvm::SmallVector<mlir::Type> body;
    if (commonEltTy && elts.size() >= minSplitTrailingZeros)
      body.push_back(
          mlir::LLVM::LLVMArrayType::get(commonEltTy, adjustedElts.size()));
    else
      body.append(adjustedElts);
    body.push_back(
        mlir::LLVM::LLVMArrayType::get(commonEltTy ? commonEltTy : origEltTy,
                                       arrayInit.getTrailingZerosNum()));
    return mlir::LLVM::LLVMStructType::getLiteral(arrayTy.getContext(), body,
                                                  /*isPacked=*/true);
  }
 
  if (!changed)
    return arrayTy;
 
  adjustedElts.resize(
      std::max<size_t>(adjustedElts.size(), arrayTy.getNumElements()),
      origEltTy);
 
  if (llvm::all_equal(adjustedElts))
    return mlir::LLVM::LLVMArrayType::get(adjustedElts.front(),
                                          adjustedElts.size());
 
  // Packed, because arrays shouldn't be subject to padding.
  return mlir::LLVM::LLVMStructType::getLiteral(
      arrayTy.getContext(), adjustedElts, /*isPacked=*/true);
}
 
// Apply various adjustments required for struct/union types.
mlir::Type
adjustGlobalTypeForInit(mlir::Type llvmType, mlir::Attribute init,
                        const mlir::TypeConverter &converter,
                        const mlir::DataLayout &dataLayout,
                        llvm::SmallVectorImpl<unsigned> &paddingAddedIndexes) {
  if (!llvmType)
    return {};
  if (auto arrayInit = mlir::dyn_cast_if_present<cir::ConstArrayAttr>(init)) {
    auto arrayTy = mlir::dyn_cast<mlir::LLVM::LLVMArrayType>(llvmType);
    if (!arrayTy)
      return llvmType;
    return adjustGlobalArrayTypeForInit(arrayTy, arrayInit, converter,
                                        dataLayout);
  }
 
  // Conversions for both only happen if we have a record init.
  auto constRecord = mlir::dyn_cast_if_present<cir::ConstRecordAttr>(init);
  if (!constRecord)
    return llvmType;
 
  // If this isn't of struct-type, or doesn't have any members, there is nothing
  // to do.
  auto structTy = mlir::dyn_cast<mlir::LLVM::LLVMStructType>(llvmType);
  if (!structTy || structTy.getBody().empty())
    return llvmType;
 
  // Structs can have a flexible array member, adjust that.
  if (mlir::isa<cir::StructType>(constRecord.getType()))
    return adjustGlobalStructTypeForInit(structTy, constRecord, converter,
                                         dataLayout, paddingAddedIndexes);
  if (mlir::isa<cir::UnionType>(constRecord.getType()))
    return adjustGlobalUnionTypeForInit(structTy, constRecord, converter,
                                        dataLayout);
  return llvmType;
}
 
mlir::Type adjustGlobalTypeForInit(mlir::Type llvmType, mlir::Attribute init,
                                   const mlir::TypeConverter &converter,
                                   const mlir::DataLayout &dataLayout) {
  llvm::SmallVector<unsigned> ignoredAddedIndexes;
  return adjustGlobalTypeForInit(llvmType, init, converter, dataLayout,
                                 ignoredAddedIndexes);
}
 
std::optional<mlir::Attribute> lowerConstRecordAttr(
    cir::ConstRecordAttr constRecord, mlir::SymbolTableCollection &symbolTables,
    const mlir::TypeConverter *converter, mlir::ModuleOp moduleOp) {
 
  // Build one constant attribute per record member. The LLVM dialect global
  // translation accepts an ArrayAttr (one element per struct field) and emits
  // an llvm::ConstantStruct, so the whole initializer can be a single
  // attribute on the global instead of an insertvalue region.
  mlir::ArrayAttr memberAttrs = constRecord.getMembers();
  llvm::SmallVector<mlir::Attribute> loweredMembers;
  loweredMembers.reserve(memberAttrs.size());
  for (mlir::Attribute member : memberAttrs) {
    std::optional<mlir::Attribute> lowered =
        lowerConstRecordMemberAttr(member, symbolTables, converter, moduleOp);
    if (!lowered)
      return std::nullopt;
    loweredMembers.push_back(*lowered);
  }
 
  // The lowered LLVM type may have more fields than the CIR record has members
  // for a few reasons:
  // 1- a union lowers to { active-member, [pad x i8]).
  // 2- A struct that contains such a union can have its alignment changed too,
  //    so it needs tail padding to fill that in.
  // 3- A struct containing a union whose initializer doesn't use the
  // highest-aligned field will have to prepend a bit of padding, such as struct
  // { i32, union { i64, i32 } }.  Typically the union gets lowered to a struct
  // { i64 } (as i64 has the greatest alignment), but if the init causes it to
  // be the i32(or any such smaller field) we have to prepend it with padding:
  // struct { i32, [4 x i8], struct { i32 }}
  // instead of (with no init):
  // struct { i32, struct { i64 }}
  llvm::SmallVector<unsigned> paddingAddedIndexes;
  mlir::Type adjustedTy = adjustGlobalTypeForInit(
      converter->convertType(constRecord.getType()), constRecord, *converter,
      mlir::DataLayout(moduleOp), paddingAddedIndexes);
  if (!adjustedTy)
    return std::nullopt;
 
  // This handles #3 from above. adjustGlobalTypeForInit ensures the
  // indexes are in increasing order, so we can insert 'backwards' without
  // causing problems.
  for (unsigned paddedElt : llvm::reverse(paddingAddedIndexes))
    loweredMembers.insert(loweredMembers.begin() + paddedElt,
                          mlir::LLVM::ZeroAttr::get(constRecord.getContext()));
 
  // Any remaining difference will be the union/struct padding case. We don't
  // have a great handle/way to tell when to zero-vs-undef init, so always
  // zero init, as it is always safe to do so.
  if (auto structTy = mlir::dyn_cast<mlir::LLVM::LLVMStructType>(adjustedTy))
    while (loweredMembers.size() < structTy.getBody().size())
      loweredMembers.push_back(
          mlir::LLVM::ZeroAttr::get(constRecord.getContext()));
 
  return mlir::ArrayAttr::get(constRecord.getContext(), loweredMembers);
}
 
mlir::Value getConstAPInt(mlir::OpBuilder &bld, mlir::Location loc,
                          mlir::Type typ, const llvm::APInt &val) {
  return mlir::LLVM::ConstantOp::create(bld, loc, typ, val);
}
 
mlir::Value getConst(mlir::OpBuilder &bld, mlir::Location loc, mlir::Type typ,
                     unsigned val) {
  return mlir::LLVM::ConstantOp::create(bld, loc, typ, val);
}
 
mlir::Value createShL(mlir::OpBuilder &bld, mlir::Value lhs, unsigned rhs) {
  if (!rhs)
    return lhs;
  mlir::Value rhsVal = getConst(bld, lhs.getLoc(), lhs.getType(), rhs);
  return mlir::LLVM::ShlOp::create(bld, lhs.getLoc(), lhs, rhsVal);
}
 
mlir::Value createAShR(mlir::OpBuilder &bld, mlir::Value lhs, unsigned rhs) {
  if (!rhs)
    return lhs;
  mlir::Value rhsVal = getConst(bld, lhs.getLoc(), lhs.getType(), rhs);
  return mlir::LLVM::AShrOp::create(bld, lhs.getLoc(), lhs, rhsVal);
}
 
mlir::Value createAnd(mlir::OpBuilder &bld, mlir::Value lhs,
                      const llvm::APInt &rhs) {
  mlir::Value rhsVal = getConstAPInt(bld, lhs.getLoc(), lhs.getType(), rhs);
  return mlir::LLVM::AndOp::create(bld, lhs.getLoc(), lhs, rhsVal);
}
 
mlir::Value createLShR(mlir::OpBuilder &bld, mlir::Value lhs, unsigned rhs) {
  if (!rhs)
    return lhs;
  mlir::Value rhsVal = getConst(bld, lhs.getLoc(), lhs.getType(), rhs);
  return mlir::LLVM::LShrOp::create(bld, lhs.getLoc(), lhs, rhsVal);
}