//===-- DWARFExpression.cpp -----------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// The DWARF expression opcodes evaluated in this file are defined by the DWARF
// Debugging Information Format specification, available at:
//
//   https://dwarfstd.org/
//
//===----------------------------------------------------------------------===//

#include "lldb/Expression/DWARFExpression.h"

#include <cinttypes>
#include <limits>

#include <optional>
#include <vector>

#include "lldb/Core/Module.h"
#include "lldb/Core/Value.h"
#include "lldb/Utility/DataEncoder.h"
#include "lldb/Utility/LLDBLog.h"
#include "lldb/Utility/Log.h"
#include "lldb/Utility/RegisterValue.h"
#include "lldb/Utility/Scalar.h"
#include "lldb/Utility/StreamString.h"

#include "lldb/Host/Host.h"
#include "lldb/Utility/Endian.h"

#include "lldb/Symbol/Function.h"

#include "lldb/Target/ABI.h"
#include "lldb/Target/ExecutionContext.h"
#include "lldb/Target/Process.h"
#include "lldb/Target/RegisterContext.h"
#include "lldb/Target/StackFrame.h"
#include "lldb/Target/StackID.h"
#include "lldb/Target/Target.h"
#include "lldb/Target/Thread.h"
#include "llvm/DebugInfo/DWARF/DWARFExpressionPrinter.h"
#include "llvm/DebugInfo/DWARF/LowLevel/DWARFExpression.h"
#include "llvm/Support/ErrorExtras.h"

using namespace lldb;
using namespace lldb_private;
using namespace lldb_private::plugin::dwarf;
using namespace llvm::dwarf;

namespace {
/// The location description kinds described by the DWARF v5
/// specification.  Composite locations are handled out-of-band and
/// thus aren't part of the enum.
enum LocationDescriptionKind {
  Empty,
  Memory,
  Register,
  Implicit
  /* Composite*/
};

/// Aggregates the inputs, derived pointers, and mutable evaluation state for
/// a single DWARF expression evaluation. Passed by reference to every helper
/// so they don't need to re-thread these individually.
struct EvalContext {
  ExecutionContext *exe_ctx;
  RegisterContext *reg_ctx;
  lldb::ModuleSP module_sp;
  const DWARFExpression::Delegate *dwarf_cu;
  lldb::RegisterKind reg_kind;
  const Value *initial_value_ptr;
  const Value *object_address_ptr;
  Process *process = nullptr;
  Target *target = nullptr;
  StackFrame *frame = nullptr;

  /// Mutable evaluation state.
  /// @{
  std::vector<Value> stack;
  Value pieces;
  uint64_t op_piece_offset = 0;
  LocationDescriptionKind loc_desc_kind = Memory;
  /// @}

  EvalContext(ExecutionContext *exe_ctx, RegisterContext *reg_ctx,
              lldb::ModuleSP module_sp,
              const DWARFExpression::Delegate *dwarf_cu,
              lldb::RegisterKind reg_kind, const Value *initial_value_ptr,
              const Value *object_address_ptr)
      : exe_ctx(exe_ctx), reg_ctx(reg_ctx), module_sp(std::move(module_sp)),
        dwarf_cu(dwarf_cu), reg_kind(reg_kind),
        initial_value_ptr(initial_value_ptr),
        object_address_ptr(object_address_ptr) {
    if (exe_ctx) {
      process = exe_ctx->GetProcessPtr();
      frame = exe_ctx->GetFramePtr();
      target = exe_ctx->GetTargetPtr();
    }
    if (this->reg_ctx == nullptr && frame)
      this->reg_ctx = frame->GetRegisterContext().get();
  }
};
} // namespace

// DWARFExpression constructor
DWARFExpression::DWARFExpression() : m_data() {}

DWARFExpression::DWARFExpression(const DataExtractor &data) : m_data(data) {}

// Destructor
DWARFExpression::~DWARFExpression() = default;

bool DWARFExpression::IsValid() const { return m_data.GetByteSize() > 0; }

void DWARFExpression::UpdateValue(uint64_t const_value,
                                  lldb::offset_t const_value_byte_size,
                                  uint8_t addr_byte_size) {
  if (!const_value_byte_size)
    return;

  m_data.SetData(
      DataBufferSP(new DataBufferHeap(&const_value, const_value_byte_size)));
  m_data.SetByteOrder(endian::InlHostByteOrder());
  m_data.SetAddressByteSize(addr_byte_size);
}

void DWARFExpression::DumpLocation(Stream *s, lldb::DescriptionLevel level,
                                   ABI *abi,
                                   llvm::DIDumpOptions options) const {
  auto *MCRegInfo = abi ? &abi->GetMCRegisterInfo() : nullptr;
  auto GetRegName = [&MCRegInfo](uint64_t DwarfRegNum,
                                 bool IsEH) -> llvm::StringRef {
    if (!MCRegInfo)
      return {};
    if (std::optional<unsigned> LLVMRegNum =
            MCRegInfo->getLLVMRegNum(DwarfRegNum, IsEH))
      if (const char *RegName = MCRegInfo->getName(*LLVMRegNum))
        return llvm::StringRef(RegName);
    return {};
  };
  options.GetNameForDWARFReg = GetRegName;
  llvm::DWARFExpression E(m_data.GetAsLLVM(), m_data.GetAddressByteSize());
  llvm::printDwarfExpression(&E, s->AsRawOstream(), options, nullptr);
}

RegisterKind DWARFExpression::GetRegisterKind() const { return m_reg_kind; }

void DWARFExpression::SetRegisterKind(RegisterKind reg_kind) {
  m_reg_kind = reg_kind;
}

llvm::Error
DWARFExpression::ReadRegisterValueAsScalar(RegisterContext *reg_ctx,
                                           lldb::RegisterKind reg_kind,
                                           uint32_t reg_num, Value &value) {
  if (reg_ctx == nullptr)
    return llvm::createStringError("no register context in frame");

  const uint32_t native_reg =
      reg_ctx->ConvertRegisterKindToRegisterNumber(reg_kind, reg_num);
  if (native_reg == LLDB_INVALID_REGNUM)
    return llvm::createStringError(
        "unable to convert register kind=%u reg_num=%u to a native "
        "register number",
        reg_kind, reg_num);

  const RegisterInfo *reg_info = reg_ctx->GetRegisterInfoAtIndex(native_reg);
  RegisterValue reg_value;
  if (reg_ctx->ReadRegister(reg_info, reg_value)) {
    if (reg_value.GetScalarValue(value.GetScalar())) {
      value.SetValueType(Value::ValueType::Scalar);
      value.SetContext(Value::ContextType::RegisterInfo,
                       const_cast<RegisterInfo *>(reg_info));
      return llvm::Error::success();
    }

    // If we get this error, then we need to implement a value buffer in
    // the dwarf expression evaluation function...
    return llvm::createStringError(
        "register %s can't be converted to a scalar value", reg_info->name);
  }

  return llvm::createStringError("register %s is not available",
                                 reg_info->name);
}

/// Return the length in bytes of the set of operands for \p op. No guarantees
/// are made on the state of \p data after this call.
static lldb::offset_t
GetOpcodeDataSize(const DataExtractor &data, const lldb::offset_t data_offset,
                  const LocationAtom op,
                  const DWARFExpression::Delegate *dwarf_cu) {
  lldb::offset_t offset = data_offset;
  switch (op) {
  // Only used in LLVM metadata.
  case DW_OP_LLVM_fragment:
  case DW_OP_LLVM_convert:
  case DW_OP_LLVM_tag_offset:
  case DW_OP_LLVM_entry_value:
  case DW_OP_LLVM_implicit_pointer:
  case DW_OP_LLVM_arg:
  case DW_OP_LLVM_extract_bits_sext:
  case DW_OP_LLVM_extract_bits_zext:
    break;
  // Vendor extensions:
  case DW_OP_HP_is_value:
  case DW_OP_HP_fltconst4:
  case DW_OP_HP_fltconst8:
  case DW_OP_HP_mod_range:
  case DW_OP_HP_unmod_range:
  case DW_OP_HP_tls:
  case DW_OP_INTEL_bit_piece:
  case DW_OP_WASM_location:
  case DW_OP_WASM_location_int:
  case DW_OP_APPLE_uninit:
  case DW_OP_PGI_omp_thread_num:
  case DW_OP_hi_user:
  case DW_OP_GNU_implicit_pointer:
    break;

  case DW_OP_addr:
  case DW_OP_call_ref: // 0x9a 1 address sized offset of DIE (DWARF3)
    return data.GetAddressByteSize();

  // Opcodes with no arguments
  case DW_OP_deref:                // 0x06
  case DW_OP_dup:                  // 0x12
  case DW_OP_drop:                 // 0x13
  case DW_OP_over:                 // 0x14
  case DW_OP_swap:                 // 0x16
  case DW_OP_rot:                  // 0x17
  case DW_OP_xderef:               // 0x18
  case DW_OP_abs:                  // 0x19
  case DW_OP_and:                  // 0x1a
  case DW_OP_div:                  // 0x1b
  case DW_OP_minus:                // 0x1c
  case DW_OP_mod:                  // 0x1d
  case DW_OP_mul:                  // 0x1e
  case DW_OP_neg:                  // 0x1f
  case DW_OP_not:                  // 0x20
  case DW_OP_or:                   // 0x21
  case DW_OP_plus:                 // 0x22
  case DW_OP_shl:                  // 0x24
  case DW_OP_shr:                  // 0x25
  case DW_OP_shra:                 // 0x26
  case DW_OP_xor:                  // 0x27
  case DW_OP_eq:                   // 0x29
  case DW_OP_ge:                   // 0x2a
  case DW_OP_gt:                   // 0x2b
  case DW_OP_le:                   // 0x2c
  case DW_OP_lt:                   // 0x2d
  case DW_OP_ne:                   // 0x2e
  case DW_OP_lit0:                 // 0x30
  case DW_OP_lit1:                 // 0x31
  case DW_OP_lit2:                 // 0x32
  case DW_OP_lit3:                 // 0x33
  case DW_OP_lit4:                 // 0x34
  case DW_OP_lit5:                 // 0x35
  case DW_OP_lit6:                 // 0x36
  case DW_OP_lit7:                 // 0x37
  case DW_OP_lit8:                 // 0x38
  case DW_OP_lit9:                 // 0x39
  case DW_OP_lit10:                // 0x3A
  case DW_OP_lit11:                // 0x3B
  case DW_OP_lit12:                // 0x3C
  case DW_OP_lit13:                // 0x3D
  case DW_OP_lit14:                // 0x3E
  case DW_OP_lit15:                // 0x3F
  case DW_OP_lit16:                // 0x40
  case DW_OP_lit17:                // 0x41
  case DW_OP_lit18:                // 0x42
  case DW_OP_lit19:                // 0x43
  case DW_OP_lit20:                // 0x44
  case DW_OP_lit21:                // 0x45
  case DW_OP_lit22:                // 0x46
  case DW_OP_lit23:                // 0x47
  case DW_OP_lit24:                // 0x48
  case DW_OP_lit25:                // 0x49
  case DW_OP_lit26:                // 0x4A
  case DW_OP_lit27:                // 0x4B
  case DW_OP_lit28:                // 0x4C
  case DW_OP_lit29:                // 0x4D
  case DW_OP_lit30:                // 0x4E
  case DW_OP_lit31:                // 0x4f
  case DW_OP_reg0:                 // 0x50
  case DW_OP_reg1:                 // 0x51
  case DW_OP_reg2:                 // 0x52
  case DW_OP_reg3:                 // 0x53
  case DW_OP_reg4:                 // 0x54
  case DW_OP_reg5:                 // 0x55
  case DW_OP_reg6:                 // 0x56
  case DW_OP_reg7:                 // 0x57
  case DW_OP_reg8:                 // 0x58
  case DW_OP_reg9:                 // 0x59
  case DW_OP_reg10:                // 0x5A
  case DW_OP_reg11:                // 0x5B
  case DW_OP_reg12:                // 0x5C
  case DW_OP_reg13:                // 0x5D
  case DW_OP_reg14:                // 0x5E
  case DW_OP_reg15:                // 0x5F
  case DW_OP_reg16:                // 0x60
  case DW_OP_reg17:                // 0x61
  case DW_OP_reg18:                // 0x62
  case DW_OP_reg19:                // 0x63
  case DW_OP_reg20:                // 0x64
  case DW_OP_reg21:                // 0x65
  case DW_OP_reg22:                // 0x66
  case DW_OP_reg23:                // 0x67
  case DW_OP_reg24:                // 0x68
  case DW_OP_reg25:                // 0x69
  case DW_OP_reg26:                // 0x6A
  case DW_OP_reg27:                // 0x6B
  case DW_OP_reg28:                // 0x6C
  case DW_OP_reg29:                // 0x6D
  case DW_OP_reg30:                // 0x6E
  case DW_OP_reg31:                // 0x6F
  case DW_OP_nop:                  // 0x96
  case DW_OP_push_object_address:  // 0x97 DWARF3
  case DW_OP_form_tls_address:     // 0x9b DWARF3
  case DW_OP_call_frame_cfa:       // 0x9c DWARF3
  case DW_OP_stack_value:          // 0x9f DWARF4
  case DW_OP_GNU_push_tls_address: // 0xe0 GNU extension
    return 0;

  // Opcodes with a single 1 byte arguments
  case DW_OP_const1u:     // 0x08 1 1-byte constant
  case DW_OP_const1s:     // 0x09 1 1-byte constant
  case DW_OP_pick:        // 0x15 1 1-byte stack index
  case DW_OP_deref_size:  // 0x94 1 1-byte size of data retrieved
  case DW_OP_xderef_size: // 0x95 1 1-byte size of data retrieved
  case DW_OP_deref_type:  // 0xa6 1 1-byte constant
    return 1;

  // Opcodes with a single 2 byte arguments
  case DW_OP_const2u: // 0x0a 1 2-byte constant
  case DW_OP_const2s: // 0x0b 1 2-byte constant
  case DW_OP_skip:    // 0x2f 1 signed 2-byte constant
  case DW_OP_bra:     // 0x28 1 signed 2-byte constant
  case DW_OP_call2:   // 0x98 1 2-byte offset of DIE (DWARF3)
    return 2;

  // Opcodes with a single 4 byte arguments
  case DW_OP_const4u: // 0x0c 1 4-byte constant
  case DW_OP_const4s: // 0x0d 1 4-byte constant
  case DW_OP_call4:   // 0x99 1 4-byte offset of DIE (DWARF3)
    return 4;

  // Opcodes with a single 8 byte arguments
  case DW_OP_const8u: // 0x0e 1 8-byte constant
  case DW_OP_const8s: // 0x0f 1 8-byte constant
    return 8;

  // All opcodes that have a single ULEB (signed or unsigned) argument
  case DW_OP_constu:          // 0x10 1 ULEB128 constant
  case DW_OP_consts:          // 0x11 1 SLEB128 constant
  case DW_OP_plus_uconst:     // 0x23 1 ULEB128 addend
  case DW_OP_breg0:           // 0x70 1 ULEB128 register
  case DW_OP_breg1:           // 0x71 1 ULEB128 register
  case DW_OP_breg2:           // 0x72 1 ULEB128 register
  case DW_OP_breg3:           // 0x73 1 ULEB128 register
  case DW_OP_breg4:           // 0x74 1 ULEB128 register
  case DW_OP_breg5:           // 0x75 1 ULEB128 register
  case DW_OP_breg6:           // 0x76 1 ULEB128 register
  case DW_OP_breg7:           // 0x77 1 ULEB128 register
  case DW_OP_breg8:           // 0x78 1 ULEB128 register
  case DW_OP_breg9:           // 0x79 1 ULEB128 register
  case DW_OP_breg10:          // 0x7a 1 ULEB128 register
  case DW_OP_breg11:          // 0x7b 1 ULEB128 register
  case DW_OP_breg12:          // 0x7c 1 ULEB128 register
  case DW_OP_breg13:          // 0x7d 1 ULEB128 register
  case DW_OP_breg14:          // 0x7e 1 ULEB128 register
  case DW_OP_breg15:          // 0x7f 1 ULEB128 register
  case DW_OP_breg16:          // 0x80 1 ULEB128 register
  case DW_OP_breg17:          // 0x81 1 ULEB128 register
  case DW_OP_breg18:          // 0x82 1 ULEB128 register
  case DW_OP_breg19:          // 0x83 1 ULEB128 register
  case DW_OP_breg20:          // 0x84 1 ULEB128 register
  case DW_OP_breg21:          // 0x85 1 ULEB128 register
  case DW_OP_breg22:          // 0x86 1 ULEB128 register
  case DW_OP_breg23:          // 0x87 1 ULEB128 register
  case DW_OP_breg24:          // 0x88 1 ULEB128 register
  case DW_OP_breg25:          // 0x89 1 ULEB128 register
  case DW_OP_breg26:          // 0x8a 1 ULEB128 register
  case DW_OP_breg27:          // 0x8b 1 ULEB128 register
  case DW_OP_breg28:          // 0x8c 1 ULEB128 register
  case DW_OP_breg29:          // 0x8d 1 ULEB128 register
  case DW_OP_breg30:          // 0x8e 1 ULEB128 register
  case DW_OP_breg31:          // 0x8f 1 ULEB128 register
  case DW_OP_regx:            // 0x90 1 ULEB128 register
  case DW_OP_fbreg:           // 0x91 1 SLEB128 offset
  case DW_OP_piece:           // 0x93 1 ULEB128 size of piece addressed
  case DW_OP_convert:         // 0xa8 1 ULEB128 offset
  case DW_OP_reinterpret:     // 0xa9 1 ULEB128 offset
  case DW_OP_addrx:           // 0xa1 1 ULEB128 index
  case DW_OP_constx:          // 0xa2 1 ULEB128 index
  case DW_OP_xderef_type:     // 0xa7 1 ULEB128 index
  case DW_OP_GNU_addr_index:  // 0xfb 1 ULEB128 index
  case DW_OP_GNU_const_index: // 0xfc 1 ULEB128 index
    data.Skip_LEB128(&offset);
    return offset - data_offset;

  // All opcodes that have a 2 ULEB (signed or unsigned) arguments
  case DW_OP_bregx:       // 0x92 2 ULEB128 register followed by SLEB128 offset
  case DW_OP_bit_piece:   // 0x9d ULEB128 bit size, ULEB128 bit offset (DWARF3);
  case DW_OP_regval_type: // 0xa5 ULEB128 + ULEB128
    data.Skip_LEB128(&offset);
    data.Skip_LEB128(&offset);
    return offset - data_offset;

  case DW_OP_implicit_value: // 0x9e ULEB128 size followed by block of that size
                             // (DWARF4)
  {
    uint64_t block_len = data.GetULEB128(&offset);
    offset += block_len;
    return offset - data_offset;
  }

  case DW_OP_implicit_pointer: // 0xa0 4-byte (or 8-byte for DWARF 64) constant
                               // + LEB128
  {
    data.Skip_LEB128(&offset);
    return (dwarf_cu ? dwarf_cu->GetAddressByteSize() : 4) + offset -
           data_offset;
  }

  case DW_OP_GNU_entry_value:
  case DW_OP_entry_value: // 0xa3 ULEB128 size + variable-length block
  {
    uint64_t subexpr_len = data.GetULEB128(&offset);
    return (offset - data_offset) + subexpr_len;
  }

  case DW_OP_const_type: // 0xa4 ULEB128 + size + variable-length block
  {
    data.Skip_LEB128(&offset);
    uint8_t length = data.GetU8(&offset);
    return (offset - data_offset) + length;
  }

  case DW_OP_LLVM_user: // 0xe9: ULEB128 + variable length constant
  {
    uint64_t constants = data.GetULEB128(&offset);
    return (offset - data_offset) + constants;
  }
  }

  if (dwarf_cu)
    return dwarf_cu->GetVendorDWARFOpcodeSize(data, data_offset, op);

  return LLDB_INVALID_OFFSET;
}

static const char *DW_OP_value_to_name(uint32_t val) {
  static char invalid[100];
  llvm::StringRef llvmstr = llvm::dwarf::OperationEncodingString(val);
  if (llvmstr.empty()) {
    snprintf(invalid, sizeof(invalid), "Unknown DW_OP constant: 0x%x", val);
    return invalid;
  }
  return llvmstr.data();
}

llvm::Expected<lldb::addr_t> DWARFExpression::GetLocation_DW_OP_addr(
    const DWARFExpression::Delegate *dwarf_cu) const {
  lldb::offset_t offset = 0;
  while (m_data.ValidOffset(offset)) {
    const LocationAtom op = static_cast<LocationAtom>(m_data.GetU8(&offset));

    if (op == DW_OP_addr)
      return m_data.GetAddress(&offset);

    if (op == DW_OP_GNU_addr_index || op == DW_OP_addrx) {
      const uint64_t index = m_data.GetULEB128(&offset);
      if (dwarf_cu)
        return dwarf_cu->ReadAddressFromDebugAddrSection(index);
      return llvm::createStringError("cannot evaluate %s without a DWARF unit",
                                     DW_OP_value_to_name(op));
    }

    const lldb::offset_t op_arg_size =
        GetOpcodeDataSize(m_data, offset, op, dwarf_cu);
    if (op_arg_size == LLDB_INVALID_OFFSET)
      return llvm::createStringError("cannot get opcode data size for %s",
                                     DW_OP_value_to_name(op));

    offset += op_arg_size;
  }

  return LLDB_INVALID_ADDRESS;
}

bool DWARFExpression::Update_DW_OP_addr(
    const DWARFExpression::Delegate *dwarf_cu, lldb::addr_t file_addr) {
  lldb::offset_t offset = 0;
  while (m_data.ValidOffset(offset)) {
    const LocationAtom op = static_cast<LocationAtom>(m_data.GetU8(&offset));

    if (op == DW_OP_addr) {
      const uint32_t addr_byte_size = m_data.GetAddressByteSize();
      // We have to make a copy of the data as we don't know if this data is
      // from a read only memory mapped buffer, so we duplicate all of the data
      // first, then modify it, and if all goes well, we then replace the data
      // for this expression

      // Make en encoder that contains a copy of the location expression data
      // so we can write the address into the buffer using the correct byte
      // order.
      DataEncoder encoder(m_data.GetDataStart(), m_data.GetByteSize(),
                          m_data.GetByteOrder(), addr_byte_size);

      // Replace the address in the new buffer
      if (encoder.PutAddress(offset, file_addr) == UINT32_MAX)
        return false;

      // All went well, so now we can reset the data using a shared pointer to
      // the heap data so "m_data" will now correctly manage the heap data.
      m_data.SetData(encoder.GetDataBuffer());
      return true;
    }
    if (op == DW_OP_addrx) {
      // Replace DW_OP_addrx with DW_OP_addr, since we can't modify the
      // read-only debug_addr table.
      // Subtract one to account for the opcode.
      llvm::ArrayRef data_before_op = m_data.GetData().take_front(offset - 1);

      // Read the addrx index to determine how many bytes it needs.
      const lldb::offset_t old_offset = offset;
      m_data.GetULEB128(&offset);
      if (old_offset == offset)
        return false;
      llvm::ArrayRef data_after_op = m_data.GetData().drop_front(offset);

      DataEncoder encoder(m_data.GetByteOrder(), m_data.GetAddressByteSize());
      encoder.AppendData(data_before_op);
      encoder.AppendU8(DW_OP_addr);
      encoder.AppendAddress(file_addr);
      encoder.AppendData(data_after_op);
      m_data.SetData(encoder.GetDataBuffer());
      return true;
    }
    const lldb::offset_t op_arg_size =
        GetOpcodeDataSize(m_data, offset, op, dwarf_cu);
    if (op_arg_size == LLDB_INVALID_OFFSET)
      break;
    offset += op_arg_size;
  }
  return false;
}

bool DWARFExpression::ContainsThreadLocalStorage(
    const DWARFExpression::Delegate *dwarf_cu) const {
  lldb::offset_t offset = 0;
  while (m_data.ValidOffset(offset)) {
    const LocationAtom op = static_cast<LocationAtom>(m_data.GetU8(&offset));

    if (op == DW_OP_form_tls_address || op == DW_OP_GNU_push_tls_address)
      return true;
    const lldb::offset_t op_arg_size =
        GetOpcodeDataSize(m_data, offset, op, dwarf_cu);
    if (op_arg_size == LLDB_INVALID_OFFSET)
      return false;
    offset += op_arg_size;
  }
  return false;
}

bool DWARFExpression::IsImplicit(
    const DWARFExpression::Delegate *dwarf_cu) const {
  lldb::offset_t offset = 0;
  while (m_data.ValidOffset(offset)) {
    const LocationAtom op = static_cast<LocationAtom>(m_data.GetU8(&offset));

    switch (op) {
    // Implicit locations have no storage in the inferior. Composite locations
    // might, but we conservatively treat them as non-writable because LLDB
    // does not write their pieces back.
    case DW_OP_stack_value:
    case DW_OP_implicit_value:
    case DW_OP_implicit_pointer:
    case DW_OP_piece:
    case DW_OP_bit_piece:
      return true;
    default:
      break;
    }

    const lldb::offset_t op_arg_size =
        GetOpcodeDataSize(m_data, offset, op, dwarf_cu);
    if (op_arg_size == LLDB_INVALID_OFFSET)
      return false;
    offset += op_arg_size;
  }
  return false;
}

bool DWARFExpression::LinkThreadLocalStorage(
    const DWARFExpression::Delegate *dwarf_cu,
    std::function<lldb::addr_t(lldb::addr_t file_addr)> const
        &link_address_callback) {
  const uint32_t addr_byte_size = m_data.GetAddressByteSize();
  // We have to make a copy of the data as we don't know if this data is from a
  // read only memory mapped buffer, so we duplicate all of the data first,
  // then modify it, and if all goes well, we then replace the data for this
  // expression.
  // Make en encoder that contains a copy of the location expression data so we
  // can write the address into the buffer using the correct byte order.
  DataEncoder encoder(m_data.GetDataStart(), m_data.GetByteSize(),
                      m_data.GetByteOrder(), addr_byte_size);

  lldb::offset_t offset = 0;
  lldb::offset_t const_offset = 0;
  lldb::addr_t const_value = 0;
  size_t const_byte_size = 0;
  while (m_data.ValidOffset(offset)) {
    const LocationAtom op = static_cast<LocationAtom>(m_data.GetU8(&offset));

    bool decoded_data = false;
    switch (op) {
    case DW_OP_const4u:
      // Remember the const offset in case we later have a
      // DW_OP_form_tls_address or DW_OP_GNU_push_tls_address
      const_offset = offset;
      const_value = m_data.GetU32(&offset);
      decoded_data = true;
      const_byte_size = 4;
      break;

    case DW_OP_const8u:
      // Remember the const offset in case we later have a
      // DW_OP_form_tls_address or DW_OP_GNU_push_tls_address
      const_offset = offset;
      const_value = m_data.GetU64(&offset);
      decoded_data = true;
      const_byte_size = 8;
      break;

    case DW_OP_form_tls_address:
    case DW_OP_GNU_push_tls_address:
      // DW_OP_form_tls_address and DW_OP_GNU_push_tls_address must be preceded
      // by a file address on the stack. We assume that DW_OP_const4u or
      // DW_OP_const8u is used for these values, and we check that the last
      // opcode we got before either of these was DW_OP_const4u or
      // DW_OP_const8u. If so, then we can link the value accordingly. For
      // Darwin, the value in the DW_OP_const4u or DW_OP_const8u is the file
      // address of a structure that contains a function pointer, the pthread
      // key and the offset into the data pointed to by the pthread key. So we
      // must link this address and also set the module of this expression to
      // the new_module_sp so we can resolve the file address correctly
      if (const_byte_size > 0) {
        lldb::addr_t linked_file_addr = link_address_callback(const_value);
        if (linked_file_addr == LLDB_INVALID_ADDRESS)
          return false;
        // Replace the address in the new buffer
        if (encoder.PutUnsigned(const_offset, const_byte_size,
                                linked_file_addr) == UINT32_MAX)
          return false;
      }
      break;

    default:
      const_offset = 0;
      const_value = 0;
      const_byte_size = 0;
      break;
    }

    if (!decoded_data) {
      const lldb::offset_t op_arg_size =
          GetOpcodeDataSize(m_data, offset, op, dwarf_cu);
      if (op_arg_size == LLDB_INVALID_OFFSET)
        return false;
      else
        offset += op_arg_size;
    }
  }

  m_data.SetData(encoder.GetDataBuffer());
  return true;
}

static llvm::Error Evaluate_DW_OP_entry_value(EvalContext &eval_ctx,
                                              llvm::ArrayRef<uint8_t> subexpr) {
  Log *log = GetLog(LLDBLog::Expressions);
  // DW_OP_entry_value(sub-expr) describes the location a variable had upon
  // function entry: this variable location is presumed to be optimized out at
  // the current PC value.  The caller of the function may have call site
  // information that describes an alternate location for the variable (e.g. a
  // constant literal, or a spilled stack value) in the parent frame.
  //
  // Example (this is pseudo-code & pseudo-DWARF, but hopefully illustrative):
  //
  //     void child(int &sink, int x) {
  //       ...
  //       /* "x" gets optimized out. */
  //
  //       /* The location of "x" here is: DW_OP_entry_value($reg2). */
  //       ++sink;
  //     }
  //
  //     void parent() {
  //       int sink;
  //
  //       /*
  //        * The callsite information emitted here is:
  //        *
  //        * DW_TAG_call_site
  //        *   DW_AT_return_pc ... (for "child(sink, 123);")
  //        *   DW_TAG_call_site_parameter (for "sink")
  //        *     DW_AT_location   ($reg1)
  //        *     DW_AT_call_value ($SP - 8)
  //        *   DW_TAG_call_site_parameter (for "x")
  //        *     DW_AT_location   ($reg2)
  //        *     DW_AT_call_value ($literal 123)
  //        *
  //        * DW_TAG_call_site
  //        *   DW_AT_return_pc ... (for "child(sink, 456);")
  //        *   ...
  //        */
  //       child(sink, 123);
  //       child(sink, 456);
  //     }
  //
  // When the program stops at "++sink" within `child`, the debugger determines
  // the call site by analyzing the return address. Once the call site is found,
  // the debugger determines which parameter is referenced by DW_OP_entry_value
  // and evaluates the corresponding location for that parameter in `parent`.

  // 1. Find the function which pushed the current frame onto the stack.
  if ((!eval_ctx.exe_ctx || !eval_ctx.exe_ctx->HasTargetScope()) ||
      !eval_ctx.reg_ctx) {
    return llvm::createStringError("no exe/reg context");
  }

  StackFrame *current_frame = eval_ctx.exe_ctx->GetFramePtr();
  Thread *thread = eval_ctx.exe_ctx->GetThreadPtr();
  if (!current_frame || !thread)
    return llvm::createStringError("no current frame/thread");

  Target &target = eval_ctx.exe_ctx->GetTargetRef();
  StackFrameSP parent_frame = nullptr;
  addr_t return_pc = LLDB_INVALID_ADDRESS;
  uint32_t current_frame_idx = current_frame->GetFrameIndex();

  for (uint32_t parent_frame_idx = current_frame_idx + 1;; parent_frame_idx++) {
    parent_frame = thread->GetStackFrameAtIndex(parent_frame_idx);
    // If this is null, we're at the end of the stack.
    if (!parent_frame)
      break;

    // Record the first valid return address, even if this is an inlined frame,
    // in order to look up the associated call edge in the first non-inlined
    // parent frame.
    if (return_pc == LLDB_INVALID_ADDRESS) {
      return_pc = parent_frame->GetFrameCodeAddress().GetLoadAddress(&target);
      LLDB_LOG(log, "immediate ancestor with pc = {0:x}", return_pc);
    }

    // If we've found an inlined frame, skip it (these have no call site
    // parameters).
    if (parent_frame->IsInlined())
      continue;

    // We've found the first non-inlined parent frame.
    break;
  }
  if (!parent_frame || !parent_frame->GetRegisterContext()) {
    return llvm::createStringError("no parent frame with reg ctx");
  }

  Function *parent_func =
      parent_frame->GetSymbolContext(eSymbolContextFunction).function;
  if (!parent_func)
    return llvm::createStringError("no parent function");

  // 2. Find the call edge in the parent function responsible for creating the
  //    current activation.
  Function *current_func =
      current_frame->GetSymbolContext(eSymbolContextFunction).function;
  if (!current_func)
    return llvm::createStringError("no current function");

  CallEdge *call_edge = nullptr;
  ModuleList &modlist = target.GetImages();
  ExecutionContext parent_exe_ctx = *eval_ctx.exe_ctx;
  parent_exe_ctx.SetFrameSP(parent_frame);
  if (!parent_frame->IsArtificial()) {
    // If the parent frame is not artificial, the current activation may be
    // produced by an ambiguous tail call. In this case, refuse to proceed.
    call_edge = parent_func->GetCallEdgeForReturnAddress(return_pc, target);
    if (!call_edge) {
      return llvm::createStringErrorV(
          "no call edge for retn-pc = {0:x} in parent frame {1}", return_pc,
          parent_func->GetName());
    }
    Function *callee_func = call_edge->GetCallee(modlist, parent_exe_ctx);
    if (callee_func != current_func) {
      return llvm::createStringError(
          "ambiguous call sequence, can't find real parent frame");
    }
  } else {
    // The StackFrameList solver machinery has deduced that an unambiguous tail
    // call sequence that produced the current activation.  The first edge in
    // the parent that points to the current function must be valid.
    for (auto &edge : parent_func->GetTailCallingEdges()) {
      if (edge->GetCallee(modlist, parent_exe_ctx) == current_func) {
        call_edge = edge.get();
        break;
      }
    }
  }
  if (!call_edge)
    return llvm::createStringError("no unambiguous edge from parent "
                                   "to current function");

  // 3. Attempt to locate the DW_OP_entry_value expression in the set of
  //    available call site parameters. If found, evaluate the corresponding
  //    parameter in the context of the parent frame.
  const CallSiteParameter *matched_param = nullptr;
  for (const CallSiteParameter &param : call_edge->GetCallSiteParameters()) {
    DataExtractor param_subexpr_extractor;
    if (!param.LocationInCallee.GetExpressionData(param_subexpr_extractor))
      continue;
    lldb::offset_t param_subexpr_offset = 0;
    const void *param_subexpr_data =
        param_subexpr_extractor.GetData(&param_subexpr_offset, subexpr.size());
    if (!param_subexpr_data ||
        param_subexpr_extractor.BytesLeft(param_subexpr_offset) != 0)
      continue;

    // At this point, the DW_OP_entry_value sub-expression and the callee-side
    // expression in the call site parameter are known to have the same length.
    // Check whether they are equal.
    //
    // Note that an equality check is sufficient: the contents of the
    // DW_OP_entry_value subexpression are only used to identify the right call
    // site parameter in the parent, and do not require any special handling.
    if (memcmp(subexpr.data(), param_subexpr_data, subexpr.size()) == 0) {
      matched_param = &param;
      break;
    }
  }
  if (!matched_param)
    return llvm::createStringError("no matching call site param found");

  // TODO: Add support for DW_OP_push_object_address within a DW_OP_entry_value
  // subexpresion whenever llvm does.
  const DWARFExpressionList &param_expr = matched_param->LocationInCaller;

  // Recurse through the public entry point so the call-site parameter is
  // evaluated with a fresh EvalContext (separate stack and piece state).
  llvm::Expected<Value> maybe_result = param_expr.Evaluate(
      &parent_exe_ctx, parent_frame->GetRegisterContext().get(),
      LLDB_INVALID_ADDRESS,
      /*initial_value_ptr=*/nullptr,
      /*object_address_ptr=*/nullptr);
  if (!maybe_result) {
    LLDB_LOG(log,
             "Evaluate_DW_OP_entry_value: call site param evaluation failed");
    return maybe_result.takeError();
  }

  eval_ctx.stack.push_back(*maybe_result);
  return llvm::Error::success();
}

/// Adjust value's ValueType according to the kind of location description.
static void UpdateValueTypeFromLocationDescription(EvalContext &eval_ctx,
                                                   LocationDescriptionKind kind,
                                                   Value *value = nullptr) {
  // Note that this function is conflating DWARF expressions with
  // DWARF location descriptions. Perhaps it would be better to define
  // a wrapper for DWARFExpression::Eval() that deals with DWARF
  // location descriptions (which consist of one or more DWARF
  // expressions). But doing this would mean we'd also need factor the
  // handling of DW_OP_(bit_)piece out of this function.
  if (eval_ctx.dwarf_cu && eval_ctx.dwarf_cu->GetVersion() >= 4) {
    Log *log = GetLog(LLDBLog::Expressions);
    const char *log_msg = "DWARF location description kind: %s";
    switch (kind) {
    case Empty:
      LLDB_LOGF(log, log_msg, "Empty");
      break;
    case Memory:
      LLDB_LOGF(log, log_msg, "Memory");
      if (value->GetValueType() == Value::ValueType::Scalar)
        value->SetValueType(Value::ValueType::LoadAddress);
      break;
    case Register:
      LLDB_LOGF(log, log_msg, "Register");
      value->SetValueType(Value::ValueType::Scalar);
      break;
    case Implicit:
      LLDB_LOGF(log, log_msg, "Implicit");
      if (value->GetValueType() == Value::ValueType::LoadAddress)
        value->SetValueType(Value::ValueType::Scalar);
      break;
    }
  }
}

/// Helper function to move common code used to resolve a file address and turn
/// into a load address.
///
/// \param eval_ctx Evaluation context (provides exe_ctx and module_sp).
/// \param dw_op_type C-style string used to vary the error output
/// \param file_addr the file address we are trying to resolve and turn into a
///                  load address
/// \param so_addr out parameter, will be set to load address or section offset
/// \param check_sectionoffset bool which determines if having a section offset
///                            but not a load address is considerd a success
/// \returns std::optional containing the load address if resolving and getting
///          the load address succeed or an empty Optinal otherwise. If
///          check_sectionoffset is true we consider LLDB_INVALID_ADDRESS a
///          success if so_addr.IsSectionOffset() is true.
static llvm::Expected<lldb::addr_t>
ResolveLoadAddress(EvalContext &eval_ctx, const char *dw_op_type,
                   lldb::addr_t file_addr, Address &so_addr,
                   bool check_sectionoffset = false) {
  if (!eval_ctx.module_sp)
    return llvm::createStringError("need module to resolve file address for %s",
                                   dw_op_type);

  if (!eval_ctx.module_sp->ResolveFileAddress(file_addr, so_addr))
    return llvm::createStringError("failed to resolve file address in module");

  const addr_t load_addr = so_addr.GetLoadAddress(eval_ctx.target);

  if (load_addr == LLDB_INVALID_ADDRESS &&
      (check_sectionoffset && !so_addr.IsSectionOffset()))
    return llvm::createStringError("failed to resolve load address");

  return load_addr;
}

/// @brief Helper function to load sized data from a uint8_t buffer.
///
/// @param addr_bytes The buffer containing raw data.
/// @param size_addr_bytes How large is the underlying raw data.
/// @param byte_order What is the byte order of the underlying data.
/// @param size How much of the underlying data we want to use.
/// @return The underlying data converted into a Scalar.
static Scalar DerefSizeExtractDataHelper(uint8_t *addr_bytes,
                                         size_t size_addr_bytes,
                                         ByteOrder byte_order, size_t size) {
  DataExtractor addr_data(addr_bytes, size_addr_bytes, byte_order, size);

  lldb::offset_t addr_data_offset = 0;
  if (size <= 8)
    return addr_data.GetMaxU64(&addr_data_offset, size);
  return addr_data.GetAddress(&addr_data_offset);
}

static llvm::Error Evaluate_DW_OP_deref(EvalContext &eval_ctx,
                                        LocationAtom opcode, unsigned size,
                                        size_t size_addr_bytes) {
  const char *op_name = DW_OP_value_to_name(opcode);
  if (eval_ctx.stack.empty())
    return llvm::createStringError("expression stack empty for %s", op_name);

  if (size == 0 || size > 8)
    return llvm::createStringError("Invalid address size for %s: %u", op_name,
                                   size);

  if (opcode == DW_OP_deref_size && size > size_addr_bytes)
    return llvm::createStringError(
        "DW_OP_deref_size size (%u) exceeds address size (%zu)", size,
        size_addr_bytes);

  // Deref a register or implicit location and truncate the value to `size`
  // bytes. See the corresponding comment in DW_OP_deref for more details on
  // why we deref these locations this way.
  if (eval_ctx.loc_desc_kind == Register ||
      eval_ctx.loc_desc_kind == Implicit) {
    // Reset context to default values.
    eval_ctx.loc_desc_kind = Memory;
    eval_ctx.stack.back().ClearContext();

    // Truncate the value on top of the stack to *size* bytes then
    // extend to the size of an address (e.g. generic type).
    Scalar scalar = eval_ctx.stack.back().GetScalar();
    scalar.TruncOrExtendTo(size * 8, /*sign=*/false);
    scalar.TruncOrExtendTo(size_addr_bytes * 8,
                           /*sign=*/false);
    eval_ctx.stack.back().GetScalar() = scalar;
    return llvm::Error::success();
  }

  Value::ValueType value_type = eval_ctx.stack.back().GetValueType();
  switch (value_type) {
  case Value::ValueType::HostAddress: {
    void *src = (void *)eval_ctx.stack.back().GetScalar().ULongLong();
    intptr_t ptr;
    ::memcpy(&ptr, src, sizeof(void *));
    // I can't decide whether the size operand should apply to the bytes in
    // their lldb-host endianness or the target endianness.. I doubt this'll
    // ever come up but I'll opt for assuming big endian regardless.
    switch (size) {
    case 1:
      ptr = ptr & 0xff;
      break;
    case 2:
      ptr = ptr & 0xffff;
      break;
    case 3:
      ptr = ptr & 0xffffff;
      break;
    case 4:
      ptr = ptr & 0xffffffff;
      break;
    // The casts are added to work around the case where intptr_t is a 32-bit
    // quantity. Presumably we won't hit the 5..7 cases if (void*) is 32-bits in
    // this program.
    case 5:
      ptr = (intptr_t)ptr & 0xffffffffffULL;
      break;
    case 6:
      ptr = (intptr_t)ptr & 0xffffffffffffULL;
      break;
    case 7:
      ptr = (intptr_t)ptr & 0xffffffffffffffULL;
      break;
    default:
      break;
    }
    eval_ctx.stack.back().GetScalar() = ptr;
    eval_ctx.stack.back().ClearContext();
  } break;
  case Value::ValueType::FileAddress: {
    auto file_addr =
        eval_ctx.stack.back().GetScalar().ULongLong(LLDB_INVALID_ADDRESS);
    Address so_addr;
    auto maybe_load_addr =
        ResolveLoadAddress(eval_ctx, op_name, file_addr, so_addr,
                           /*check_sectionoffset=*/true);

    if (!maybe_load_addr)
      return maybe_load_addr.takeError();

    addr_t load_addr = *maybe_load_addr;

    if (load_addr == LLDB_INVALID_ADDRESS && so_addr.IsSectionOffset()) {
      uint8_t addr_bytes[8];
      Status error;

      if (!eval_ctx.target ||
          eval_ctx.target->ReadMemory(so_addr, &addr_bytes, size, error,
                                      /*force_live_memory=*/false) != size)
        return llvm::createStringError("failed to dereference pointer for %s: "
                                       "%s\n",
                                       op_name, error.AsCString());

      ObjectFile *objfile = eval_ctx.module_sp->GetObjectFile();

      eval_ctx.stack.back().GetScalar() = DerefSizeExtractDataHelper(
          addr_bytes, size, objfile->GetByteOrder(), size);
      eval_ctx.stack.back().ClearContext();
      break;
    }
    eval_ctx.stack.back().GetScalar() = load_addr;
    // Fall through to load address promotion code below.
  }

    [[fallthrough]];
  case Value::ValueType::Scalar:
    // Promote Scalar to LoadAddress and fall through.
    eval_ctx.stack.back().SetValueType(Value::ValueType::LoadAddress);
    [[fallthrough]];
  case Value::ValueType::LoadAddress: {
    if (!eval_ctx.exe_ctx)
      return llvm::createStringError("no execution context for %s", op_name);
    if (!eval_ctx.process)
      return llvm::createStringError("no process for %s", op_name);

    lldb::addr_t pointer_addr =
        eval_ctx.stack.back().GetScalar().ULongLong(LLDB_INVALID_ADDRESS);
    uint8_t addr_bytes[sizeof(lldb::addr_t)];
    Status error;

    if (eval_ctx.process->ReadMemory(pointer_addr, &addr_bytes, size, error) !=
        size)
      return llvm::createStringError(
          "failed to dereference pointer from 0x%" PRIx64 " for %s: %s\n",
          pointer_addr, op_name, error.AsCString());

    eval_ctx.stack.back().GetScalar() = DerefSizeExtractDataHelper(
        addr_bytes, sizeof(addr_bytes), eval_ctx.process->GetByteOrder(), size);
    eval_ctx.stack.back().ClearContext();
  } break;

  case Value::ValueType::Invalid:
    return llvm::createStringError("invalid value for %s", op_name);
  }

  // Both operations push a generic, address-sized result. The truncation to
  // `size` bytes is unnecessary here because the branches above already limit
  // the value to `size` bytes; it is only done for consistency with the
  // Register/Implicit path above.
  eval_ctx.stack.back().GetScalar().TruncOrExtendTo(size * 8, /*sign=*/false);
  eval_ctx.stack.back().GetScalar().TruncOrExtendTo(size_addr_bytes * 8,
                                                    /*sign=*/false);
  return llvm::Error::success();
}

static llvm::Error Evaluate_DW_OP_piece(EvalContext &eval_ctx,
                                        uint64_t piece_byte_size) {
  LocationDescriptionKind piece_locdesc = eval_ctx.loc_desc_kind;
  // Reset for the next piece.
  eval_ctx.loc_desc_kind = Memory;

  if (piece_byte_size == 0)
    return llvm::Error::success();

  Value curr_piece;

  if (eval_ctx.stack.empty()) {
    UpdateValueTypeFromLocationDescription(eval_ctx,
                                           LocationDescriptionKind::Empty);
    // In a multi-piece expression, this means that the current piece is
    // not available. Fill with zeros for now by resizing the data and
    // appending it
    curr_piece.ResizeData(piece_byte_size);
    // Note that "0" is not a correct value for the unknown bits.
    // It would be better to also return a mask of valid bits together
    // with the expression result, so the debugger can print missing
    // members as "<optimized out>" or something.
    ::memset(curr_piece.GetBuffer().GetBytes(), 0, piece_byte_size);
    eval_ctx.pieces.AppendDataToHostBuffer(curr_piece);
  } else {
    Status error;
    // Extract the current piece into "curr_piece"
    Value curr_piece_source_value(eval_ctx.stack.back());
    eval_ctx.stack.pop_back();
    UpdateValueTypeFromLocationDescription(eval_ctx, piece_locdesc,
                                           &curr_piece_source_value);

    const Value::ValueType curr_piece_source_value_type =
        curr_piece_source_value.GetValueType();
    Scalar &scalar = curr_piece_source_value.GetScalar();
    lldb::addr_t addr = scalar.ULongLong(LLDB_INVALID_ADDRESS);
    switch (curr_piece_source_value_type) {
    case Value::ValueType::Invalid:
      return llvm::createStringError("invalid value type");
    case Value::ValueType::FileAddress:
      if (eval_ctx.target) {
        curr_piece_source_value.ConvertToLoadAddress(eval_ctx.module_sp.get(),
                                                     eval_ctx.target);
        addr = scalar.ULongLong(LLDB_INVALID_ADDRESS);
      } else {
        return llvm::createStringError(
            "unable to convert file address 0x%" PRIx64 " to load address "
            "for DW_OP_piece(%" PRIu64 "): "
            "no target available",
            addr, piece_byte_size);
      }
      [[fallthrough]];
    case Value::ValueType::LoadAddress: {
      if (eval_ctx.target) {
        if (curr_piece.ResizeData(piece_byte_size) == piece_byte_size) {
          if (eval_ctx.target->ReadMemory(
                  Address(addr), curr_piece.GetBuffer().GetBytes(),
                  piece_byte_size, error,
                  /*force_live_memory=*/false) != piece_byte_size) {
            const char *addr_type =
                (curr_piece_source_value_type == Value::ValueType::LoadAddress)
                    ? "load"
                    : "file";
            return llvm::createStringError(
                "failed to read memory DW_OP_piece(%" PRIu64
                ") from %s address 0x%" PRIx64,
                piece_byte_size, addr_type, addr);
          }
        } else {
          return llvm::createStringError(
              "failed to resize the piece memory buffer for "
              "DW_OP_piece(%" PRIu64 ")",
              piece_byte_size);
        }
      }
    } break;
    case Value::ValueType::HostAddress: {
      // DW_OP_implicit_value uses a host-address Value to own its bytes. For
      // a full-width piece, the address is only an implementation detail and
      // the backing bytes are the value of the piece.
      if (piece_locdesc == Implicit &&
          curr_piece_source_value.GetBuffer().GetByteSize() ==
              piece_byte_size) {
        curr_piece = curr_piece_source_value;
        break;
      }
      return llvm::createStringError(
          "failed to read memory DW_OP_piece(%" PRIu64
          ") from host address 0x%" PRIx64,
          piece_byte_size, addr);
    } break;

    case Value::ValueType::Scalar: {
      uint32_t bit_size = piece_byte_size * 8;
      uint32_t bit_offset = 0;
      if (!scalar.ExtractBitfield(bit_size, bit_offset)) {
        return llvm::createStringError(
            "unable to extract %" PRIu64 " bytes from a %" PRIu64
            " byte scalar value.",
            piece_byte_size,
            (uint64_t)curr_piece_source_value.GetScalar().GetByteSize());
      }

      // We have seen a case where we have expression like:
      //      DW_OP_lit0, DW_OP_stack_value, DW_OP_piece 0x28
      // here we are assuming the compiler was trying to zero
      // extend the value that we should append to the buffer.
      scalar.TruncOrExtendTo(bit_size, /*sign=*/false);
      curr_piece.GetScalar() = scalar;
    } break;
    }

    // Check if this is the first piece?
    if (eval_ctx.op_piece_offset == 0) {
      // This is the first piece, we should push it back onto the stack
      // so subsequent pieces will be able to access this piece and add
      // to it.
      if (eval_ctx.pieces.AppendDataToHostBuffer(curr_piece) == 0) {
        return llvm::createStringError("failed to append piece data");
      }
    } else {
      // If this is the second or later piece there should be a value on
      // the stack.
      if (eval_ctx.pieces.GetBuffer().GetByteSize() !=
          eval_ctx.op_piece_offset) {
        return llvm::createStringError(
            "DW_OP_piece for offset %" PRIu64
            " but top of stack is of size %" PRIu64,
            eval_ctx.op_piece_offset,
            eval_ctx.pieces.GetBuffer().GetByteSize());
      }

      if (eval_ctx.pieces.AppendDataToHostBuffer(curr_piece) == 0)
        return llvm::createStringError("failed to append piece data");
    }
  }
  eval_ctx.op_piece_offset += piece_byte_size;
  return llvm::Error::success();
}

static llvm::Error Evaluate_DW_OP_convert(EvalContext &eval_ctx,
                                          uint64_t relative_die_offset) {
  uint64_t bit_size;
  llvm::dwarf::TypeKind encoding;
  if (relative_die_offset == 0) {
    // The generic type has the size of an address on the target
    // machine and an unspecified signedness. Scalar has no
    // "unspecified signedness", so we use unsigned types.
    if (!eval_ctx.module_sp)
      return llvm::createStringError("no module");
    encoding = llvm::dwarf::DW_ATE_unsigned;
    bit_size = eval_ctx.module_sp->GetArchitecture().GetAddressByteSize() * 8;
    if (!bit_size)
      return llvm::createStringError("unspecified architecture");
  } else {
    if (!eval_ctx.dwarf_cu)
      return llvm::createStringError(
          "DW_OP_convert with a DIE offset requires a DWARF unit");
    auto bit_size_encoding_or_err =
        eval_ctx.dwarf_cu->GetDIEBitSizeAndEncoding(relative_die_offset);
    if (!bit_size_encoding_or_err)
      return bit_size_encoding_or_err.takeError();
    bit_size = bit_size_encoding_or_err->first;
    encoding = bit_size_encoding_or_err->second;
  }

  Scalar &scalar = eval_ctx.stack.back().GetScalar();
  if (encoding == llvm::dwarf::DW_ATE_float) {
    const llvm::fltSemantics *semantics;
    switch (bit_size) {
    case 32:
      semantics = &llvm::APFloat::IEEEsingle();
      break;
    case 64:
      semantics = &llvm::APFloat::IEEEdouble();
      break;
    case 80:
      semantics = &llvm::APFloat::x87DoubleExtended();
      break;
    default:
      return llvm::createStringError("unsupported floating-point type size");
    }

    if (scalar.GetType() == Scalar::e_float) {
      llvm::APFloat value = scalar.GetAPFloat();
      bool loses_info;
      value.convert(*semantics, llvm::APFloat::rmNearestTiesToEven,
                    &loses_info);
      scalar = Scalar(std::move(value));
    } else if (!scalar.FloatPromote(*semantics)) {
      return llvm::createStringError("cannot convert value to floating point");
    }
    return llvm::Error::success();
  }

  const bool sign = encoding == llvm::dwarf::DW_ATE_signed ||
                    encoding == llvm::dwarf::DW_ATE_signed_char;
  if (scalar.GetType() == Scalar::e_float) {
    if (bit_size > std::numeric_limits<uint16_t>::max())
      return llvm::createStringError("unsupported integer type size: %" PRIu64,
                                     bit_size);

    llvm::APSInt value(static_cast<unsigned>(bit_size),
                       /*isUnsigned=*/!sign);
    bool is_exact;
    llvm::APFloat::opStatus status = scalar.GetAPFloat().convertToInteger(
        value, llvm::APFloat::rmTowardZero, &is_exact);
    if (status & llvm::APFloat::opInvalidOp)
      return llvm::createStringError(
          "cannot convert floating-point value to integer");
    scalar = Scalar(std::move(value));
  } else {
    scalar.TruncOrExtendTo(bit_size, sign);
  }
  return llvm::Error::success();
}

static llvm::Error Evaluate_DW_OP_form_tls_address(EvalContext &eval_ctx,
                                                   LocationAtom opcode) {
  if (eval_ctx.stack.empty())
    return llvm::createStringError("%s needs an argument",
                                   opcode == DW_OP_form_tls_address
                                       ? "DW_OP_form_tls_address"
                                       : "DW_OP_GNU_push_tls_address");

  if (!eval_ctx.exe_ctx || !eval_ctx.module_sp)
    return llvm::createStringError("no context to evaluate TLS within");

  Thread *thread = eval_ctx.exe_ctx->GetThreadPtr();
  if (!thread)
    return llvm::createStringError("no thread to evaluate TLS within");

  // Lookup the TLS block address for this thread and module.
  const addr_t tls_file_addr =
      eval_ctx.stack.back().GetScalar().ULongLong(LLDB_INVALID_ADDRESS);
  const addr_t tls_load_addr =
      thread->GetThreadLocalData(eval_ctx.module_sp, tls_file_addr);

  if (tls_load_addr == LLDB_INVALID_ADDRESS)
    return llvm::createStringError(
        "no TLS data currently exists for this thread");

  eval_ctx.stack.back().GetScalar() = tls_load_addr;
  eval_ctx.stack.back().SetValueType(Value::ValueType::LoadAddress);
  return llvm::Error::success();
}

static llvm::Error Evaluate_DW_OP_fbreg(EvalContext &eval_ctx,
                                        int64_t fbreg_offset) {
  if (!eval_ctx.exe_ctx)
    return llvm::createStringError("NULL execution context for DW_OP_fbreg");
  if (!eval_ctx.frame)
    return llvm::createStringError(
        "invalid stack frame in context for DW_OP_fbreg opcode");

  Scalar value;
  if (llvm::Error err = eval_ctx.frame->GetFrameBaseValue(value))
    return err;
  value += fbreg_offset;
  eval_ctx.stack.push_back(value);
  eval_ctx.stack.back().SetValueType(Value::ValueType::LoadAddress);
  return llvm::Error::success();
}

static llvm::Error Evaluate_DW_OP_call_frame_cfa(EvalContext &eval_ctx) {
  if (!eval_ctx.frame)
    return llvm::createStringError(
        "invalid stack frame in context for DW_OP_call_frame_cfa opcode");

  // Note that we don't have to parse FDEs because this DWARF expression
  // is commonly evaluated with a valid stack frame.
  StackID id = eval_ctx.frame->GetStackID();
  addr_t cfa = id.GetCallFrameAddressWithMetadata();
  if (cfa == LLDB_INVALID_ADDRESS)
    return llvm::createStringError("stack frame does not include a canonical "
                                   "frame address for DW_OP_call_frame_cfa "
                                   "opcode");

  eval_ctx.stack.push_back(Scalar(cfa));
  eval_ctx.stack.back().SetValueType(Value::ValueType::LoadAddress);
  return llvm::Error::success();
}

static llvm::Error CheckScalarOperandsHaveSameType(const Scalar &lhs,
                                                   const Scalar &rhs,
                                                   LocationAtom opcode,
                                                   size_t address_size) {
  auto mismatch = [&](const char *what) {
    return llvm::createStringError("%s requires operands to have the same %s",
                                   DW_OP_value_to_name(opcode), what);
  };

  // Scalar does not preserve the original DWARF DIE, but it does carry the
  // pieces of base-type information used by the evaluator: kind, size, and
  // integer signedness.
  if (lhs.GetType() != rhs.GetType())
    return mismatch("type");

  // Only integer scalars have signedness. Non-integer operands (e.g. floats)
  // have no further scalar type information to compare once kind and size
  // match.
  if (lhs.GetType() != Scalar::e_int) {
    if (lhs.GetByteSize() != rhs.GetByteSize())
      return mismatch("size");
    return llvm::Error::success();
  }

  // DWARF generic values are address-sized integers with unspecified
  // signedness. LLDB does not explicitly preserve genericness on the
  // expression stack, so treat integers at least as wide as the generic type
  // as potentially generic and compatible with one another, regardless of
  // exact width or signedness. This keeps common expressions working: e.g.
  // DW_OP_breg produces a register-sized value while DW_OP_const* produces an
  // address-sized one, yet both are meant to be generic. DW_OP_constu and
  // DW_OP_consts also do not always use to_generic due to
  // https://github.com/llvm/llvm-project/issues/47431. A precise fix would
  // require tracking genericness directly, which is a larger type-system
  // change.
  if (address_size != 0 && lhs.GetByteSize() >= address_size &&
      rhs.GetByteSize() >= address_size)
    return llvm::Error::success();

  // For non-generic integer operands, size and signedness are part of the
  // base-type information preserved by Scalar, so require them to match.
  if (lhs.GetByteSize() != rhs.GetByteSize())
    return mismatch("size");
  if (lhs.IsSigned() != rhs.IsSigned())
    return mismatch("signedness");

  return llvm::Error::success();
}

// Scalar does not preserve DWARF's generic type identifier. Since generic
// values are address-sized integers, use the scalar kind and width as an
// approximation.
static bool IsPotentiallyGenericIntegerOperand(const Scalar &operand,
                                               size_t address_size) {
  return address_size != 0 && operand.GetType() == Scalar::e_int &&
         operand.GetByteSize() == address_size;
}

llvm::Expected<Value> DWARFExpression::Evaluate(
    ExecutionContext *exe_ctx, RegisterContext *reg_ctx,
    lldb::ModuleSP module_sp, const DataExtractor &opcodes,
    const DWARFExpression::Delegate *dwarf_cu,
    const lldb::RegisterKind reg_kind, const Value *initial_value_ptr,
    const Value *object_address_ptr) {
  uint32_t address_size = opcodes.GetAddressByteSize();
  llvm::DataExtractor expr_data = opcodes.GetAsLLVM();
  llvm::DWARFExpression expr(expr_data, address_size);

  if (expr_data.size() == 0)
    return llvm::createStringError(
        "no location, value may have been optimized out");

  EvalContext eval_ctx(exe_ctx, reg_ctx, std::move(module_sp), dwarf_cu,
                       reg_kind, initial_value_ptr, object_address_ptr);

  Stack &stack = eval_ctx.stack;

  if (initial_value_ptr)
    stack.push_back(*initial_value_ptr);

  Value tmp;
  uint32_t reg_num;

  Log *log = GetLog(LLDBLog::Expressions);
  // A generic type is "an integral type that has the size of an address and an
  // unspecified signedness". For now, just use the signedness of the operand.
  // TODO: Implement a real typed stack, and store the genericness of the value
  // there.
  auto to_generic = [&](auto v) {
    // TODO: Avoid implicit trunc?
    // See https://github.com/llvm/llvm-project/issues/112510.
    bool is_signed = std::is_signed<decltype(v)>::value;
    return Scalar(llvm::APSInt(
        llvm::APInt(8 * address_size, v, is_signed, /*implicitTrunc=*/true),
        !is_signed));
  };

  llvm::DWARFExpression::iterator op = expr.begin(), op_end = expr.end();
  while (op != op_end) {
    const uint64_t op_offset = op.getOffset();
    const LocationAtom opcode = static_cast<LocationAtom>(op->getCode());

    if (log && log->GetVerbose()) {
      size_t count = stack.size();
      LLDB_LOGF(log, "Stack before operation has %" PRIu64 " values:",
                static_cast<uint64_t>(count));
      for (size_t i = 0; i < count; ++i) {
        StreamString new_value;
        new_value.Printf("[%" PRIu64 "]", static_cast<uint64_t>(i));
        stack[i].Dump(&new_value);
        LLDB_LOGF(log, "  %s", new_value.GetData());
      }
      LLDB_LOGF(log, "0x%8.8" PRIx64 ": %s", op_offset,
                DW_OP_value_to_name(opcode));
    }

    if (std::optional<unsigned> arity = OperationArity(opcode)) {
      if (stack.size() < *arity)
        return llvm::createStringError(
            "%s needs at least %d stack entries (stack has %d entries)",
            DW_OP_value_to_name(opcode), *arity, stack.size());
    }

    switch (opcode) {
    case DW_OP_addr:
      stack.push_back(to_generic(op->getRawOperand(0)));
      stack.back().SetValueType(Value::ValueType::FileAddress);
      break;

    case DW_OP_deref: {
      size_t size = address_size;
      if (llvm::Error err = Evaluate_DW_OP_deref(eval_ctx, opcode, size, size))
        return err;
    } break;

    case DW_OP_deref_size: {
      size_t size = op->getRawOperand(0);
      if (llvm::Error err =
              Evaluate_DW_OP_deref(eval_ctx, opcode, size, address_size))
        return err;
    } break;

    case DW_OP_const1u:
      stack.push_back(to_generic(op->getRawOperand(0)));
      break;
    case DW_OP_const1s:
      stack.push_back(to_generic(static_cast<int8_t>(op->getRawOperand(0))));
      break;
    case DW_OP_const2u:
      stack.push_back(to_generic(op->getRawOperand(0)));
      break;
    case DW_OP_const2s:
      stack.push_back(to_generic(static_cast<int16_t>(op->getRawOperand(0))));
      break;
    case DW_OP_const4u:
      stack.push_back(to_generic(op->getRawOperand(0)));
      break;
    case DW_OP_const4s:
      stack.push_back(to_generic(static_cast<int32_t>(op->getRawOperand(0))));
      break;
    case DW_OP_const8u:
      stack.push_back(to_generic(op->getRawOperand(0)));
      break;
    case DW_OP_const8s:
      stack.push_back(to_generic(static_cast<int64_t>(op->getRawOperand(0))));
      break;
    case DW_OP_constu:
      stack.push_back(to_generic(op->getRawOperand(0)));
      break;
    case DW_OP_consts:
      stack.push_back(to_generic(static_cast<int64_t>(op->getRawOperand(0))));
      break;

    case DW_OP_dup:
      if (stack.empty()) {
        return llvm::createStringError("expression stack empty for DW_OP_dup");
      } else
        stack.push_back(stack.back());
      break;

    case DW_OP_drop:
      if (stack.empty()) {
        return llvm::createStringError("expression stack empty for DW_OP_drop");
      } else
        stack.pop_back();
      break;

    case DW_OP_over:
      stack.push_back(stack[stack.size() - 2]);
      break;

    case DW_OP_pick: {
      uint8_t pick_idx = op->getRawOperand(0);
      if (pick_idx < stack.size())
        stack.push_back(stack[stack.size() - 1 - pick_idx]);
      else {
        return llvm::createStringError(
            "Index %u out of range for DW_OP_pick.\n", pick_idx);
      }
    } break;

    case DW_OP_swap:
      tmp = stack.back();
      stack.back() = stack[stack.size() - 2];
      stack[stack.size() - 2] = tmp;
      break;

    case DW_OP_rot: {
      size_t last_idx = stack.size() - 1;
      Value old_top = stack[last_idx];
      stack[last_idx] = stack[last_idx - 1];
      stack[last_idx - 1] = stack[last_idx - 2];
      stack[last_idx - 2] = old_top;
    } break;

    case DW_OP_abs:
      if (!stack.back().GetScalar().AbsoluteValue()) {
        return llvm::createStringError(
            "failed to take the absolute value of the first stack item");
      }
      break;

    case DW_OP_and:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() = stack.back().GetScalar() & tmp.GetScalar();
      break;

    case DW_OP_div: {
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      if (tmp.GetScalar().IsZero())
        return llvm::createStringError("divide by zero");

      stack.pop_back();
      Scalar divisor, dividend;
      divisor = tmp.GetScalar();
      dividend = stack.back().GetScalar();
      divisor.MakeSigned();
      dividend.MakeSigned();
      stack.back() = dividend / divisor;

      if (!stack.back().GetScalar().IsValid())
        return llvm::createStringError("divide failed");
    } break;

    case DW_OP_minus:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() = stack.back().GetScalar() - tmp.GetScalar();
      break;

    case DW_OP_mod:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (IsPotentiallyGenericIntegerOperand(tmp.GetScalar(), address_size) &&
          IsPotentiallyGenericIntegerOperand(stack.back().GetScalar(),
                                             address_size)) {
        tmp.GetScalar().MakeUnsigned();
        stack.back().GetScalar().MakeUnsigned();
      }
      stack.back().GetScalar() = stack.back().GetScalar() % tmp.GetScalar();
      break;

    case DW_OP_mul:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() = stack.back().GetScalar() * tmp.GetScalar();
      break;

    case DW_OP_neg:
      if (!stack.back().GetScalar().UnaryNegate())
        return llvm::createStringError("unary negate failed");
      break;

    case DW_OP_not:
      if (!stack.back().GetScalar().OnesComplement())
        return llvm::createStringError("logical NOT failed");
      break;

    case DW_OP_or:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() = stack.back().GetScalar() | tmp.GetScalar();
      break;

    case DW_OP_plus:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() += tmp.GetScalar();
      break;

    case DW_OP_plus_uconst: {
      const uint64_t uconst_value = op->getRawOperand(0);
      Scalar &operand = stack.back().GetScalar();
      Scalar addend(uconst_value);
      // The addend is interpreted as the same type as the popped operand
      // (DWARF v5, 2.5.1.4). Give it the operand's exact integer type so
      // the addition keeps the operand's width and wraparound semantics
      // instead of promoting to a 64-bit unsigned value.
      if (operand.GetType() == Scalar::e_int)
        addend.TruncOrExtendTo(operand.GetAPSInt().getBitWidth(),
                               operand.GetAPSInt().isSigned());
      operand += addend;
      if (!operand.IsValid())
        return llvm::createStringError("DW_OP_plus_uconst failed");
    } break;

    case DW_OP_shl:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() <<= tmp.GetScalar();
      break;

    case DW_OP_shr:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (!stack.back().GetScalar().ShiftRightLogical(tmp.GetScalar()))
        return llvm::createStringError("DW_OP_shr failed");
      break;

    case DW_OP_shra:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() >>= tmp.GetScalar();
      break;

    case DW_OP_xor:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() = stack.back().GetScalar() ^ tmp.GetScalar();
      break;

    case DW_OP_skip: {
      int16_t skip_offset = static_cast<int16_t>(op->getRawOperand(0));
      lldb::offset_t new_offset = op->getEndOffset() + skip_offset;
      // New offset can point at the end of the data, in this case we should
      // terminate the DWARF expression evaluation (will happen in the loop
      // condition).
      if (new_offset <= expr_data.size()) {
        op = op.skipBytes(skip_offset);
        continue;
      }
      return llvm::createStringErrorV(
          "Invalid opcode offset in DW_OP_skip: {0}+({1}) > {2}",
          op->getEndOffset(), skip_offset, expr_data.size());
    }

    case DW_OP_bra: {
      tmp = stack.back();
      stack.pop_back();
      int16_t bra_offset = static_cast<int16_t>(op->getRawOperand(0));
      Scalar zero(0);
      if (tmp.GetScalar() != zero) {
        lldb::offset_t new_offset = op->getEndOffset() + bra_offset;
        // New offset can point at the end of the data, in this case we should
        // terminate the DWARF expression evaluation (will happen in the loop
        // condition).
        if (new_offset <= expr_data.size()) {
          op = op.skipBytes(bra_offset);
          continue;
        }
        return llvm::createStringErrorV(
            "Invalid opcode offset in DW_OP_bra: {0}+({1}) > {2}",
            op->getEndOffset(), bra_offset, expr_data.size());
      }
    } break;

    case DW_OP_eq:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() == tmp.GetScalar());
      break;

    case DW_OP_ge:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (IsPotentiallyGenericIntegerOperand(tmp.GetScalar(), address_size) &&
          IsPotentiallyGenericIntegerOperand(stack.back().GetScalar(),
                                             address_size)) {
        tmp.GetScalar().MakeSigned();
        stack.back().GetScalar().MakeSigned();
      }
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() >= tmp.GetScalar());
      break;

    case DW_OP_gt:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (IsPotentiallyGenericIntegerOperand(tmp.GetScalar(), address_size) &&
          IsPotentiallyGenericIntegerOperand(stack.back().GetScalar(),
                                             address_size)) {
        tmp.GetScalar().MakeSigned();
        stack.back().GetScalar().MakeSigned();
      }
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() > tmp.GetScalar());
      break;

    case DW_OP_le:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (IsPotentiallyGenericIntegerOperand(tmp.GetScalar(), address_size) &&
          IsPotentiallyGenericIntegerOperand(stack.back().GetScalar(),
                                             address_size)) {
        tmp.GetScalar().MakeSigned();
        stack.back().GetScalar().MakeSigned();
      }
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() <= tmp.GetScalar());
      break;

    case DW_OP_lt:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      if (IsPotentiallyGenericIntegerOperand(tmp.GetScalar(), address_size) &&
          IsPotentiallyGenericIntegerOperand(stack.back().GetScalar(),
                                             address_size)) {
        tmp.GetScalar().MakeSigned();
        stack.back().GetScalar().MakeSigned();
      }
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() < tmp.GetScalar());
      break;

    case DW_OP_ne:
      if (llvm::Error err = CheckScalarOperandsHaveSameType(
              stack[stack.size() - 2].GetScalar(), stack.back().GetScalar(),
              opcode, address_size))
        return err;
      tmp = stack.back();
      stack.pop_back();
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar() != tmp.GetScalar());
      break;

    case DW_OP_lit0:
    case DW_OP_lit1:
    case DW_OP_lit2:
    case DW_OP_lit3:
    case DW_OP_lit4:
    case DW_OP_lit5:
    case DW_OP_lit6:
    case DW_OP_lit7:
    case DW_OP_lit8:
    case DW_OP_lit9:
    case DW_OP_lit10:
    case DW_OP_lit11:
    case DW_OP_lit12:
    case DW_OP_lit13:
    case DW_OP_lit14:
    case DW_OP_lit15:
    case DW_OP_lit16:
    case DW_OP_lit17:
    case DW_OP_lit18:
    case DW_OP_lit19:
    case DW_OP_lit20:
    case DW_OP_lit21:
    case DW_OP_lit22:
    case DW_OP_lit23:
    case DW_OP_lit24:
    case DW_OP_lit25:
    case DW_OP_lit26:
    case DW_OP_lit27:
    case DW_OP_lit28:
    case DW_OP_lit29:
    case DW_OP_lit30:
    case DW_OP_lit31:
      stack.push_back(to_generic(opcode - DW_OP_lit0));
      break;

    case DW_OP_reg0:
    case DW_OP_reg1:
    case DW_OP_reg2:
    case DW_OP_reg3:
    case DW_OP_reg4:
    case DW_OP_reg5:
    case DW_OP_reg6:
    case DW_OP_reg7:
    case DW_OP_reg8:
    case DW_OP_reg9:
    case DW_OP_reg10:
    case DW_OP_reg11:
    case DW_OP_reg12:
    case DW_OP_reg13:
    case DW_OP_reg14:
    case DW_OP_reg15:
    case DW_OP_reg16:
    case DW_OP_reg17:
    case DW_OP_reg18:
    case DW_OP_reg19:
    case DW_OP_reg20:
    case DW_OP_reg21:
    case DW_OP_reg22:
    case DW_OP_reg23:
    case DW_OP_reg24:
    case DW_OP_reg25:
    case DW_OP_reg26:
    case DW_OP_reg27:
    case DW_OP_reg28:
    case DW_OP_reg29:
    case DW_OP_reg30:
    case DW_OP_reg31: {
      eval_ctx.loc_desc_kind = Register;
      reg_num = opcode - DW_OP_reg0;

      if (llvm::Error err = ReadRegisterValueAsScalar(
              eval_ctx.reg_ctx, eval_ctx.reg_kind, reg_num, tmp))
        return err;
      stack.push_back(tmp);
    } break;
    case DW_OP_regx: {
      eval_ctx.loc_desc_kind = Register;
      reg_num = op->getRawOperand(0);
      Status read_err;
      if (llvm::Error err = ReadRegisterValueAsScalar(
              eval_ctx.reg_ctx, eval_ctx.reg_kind, reg_num, tmp))
        return err;
      stack.push_back(tmp);
    } break;

    case DW_OP_breg0:
    case DW_OP_breg1:
    case DW_OP_breg2:
    case DW_OP_breg3:
    case DW_OP_breg4:
    case DW_OP_breg5:
    case DW_OP_breg6:
    case DW_OP_breg7:
    case DW_OP_breg8:
    case DW_OP_breg9:
    case DW_OP_breg10:
    case DW_OP_breg11:
    case DW_OP_breg12:
    case DW_OP_breg13:
    case DW_OP_breg14:
    case DW_OP_breg15:
    case DW_OP_breg16:
    case DW_OP_breg17:
    case DW_OP_breg18:
    case DW_OP_breg19:
    case DW_OP_breg20:
    case DW_OP_breg21:
    case DW_OP_breg22:
    case DW_OP_breg23:
    case DW_OP_breg24:
    case DW_OP_breg25:
    case DW_OP_breg26:
    case DW_OP_breg27:
    case DW_OP_breg28:
    case DW_OP_breg29:
    case DW_OP_breg30:
    case DW_OP_breg31: {
      reg_num = opcode - DW_OP_breg0;
      if (llvm::Error err = ReadRegisterValueAsScalar(
              eval_ctx.reg_ctx, eval_ctx.reg_kind, reg_num, tmp))
        return err;

      int64_t breg_offset = op->getRawOperand(0);
      tmp.GetScalar() = to_generic(tmp.GetScalar().ULongLong());
      tmp.GetScalar() += to_generic(breg_offset);
      tmp.ClearContext();
      stack.push_back(tmp);
      stack.back().SetValueType(Value::ValueType::LoadAddress);
    } break;
    case DW_OP_bregx: {
      reg_num = op->getRawOperand(0);
      if (llvm::Error err = ReadRegisterValueAsScalar(
              eval_ctx.reg_ctx, eval_ctx.reg_kind, reg_num, tmp))
        return err;

      int64_t breg_offset = op->getRawOperand(1);
      tmp.GetScalar() = to_generic(tmp.GetScalar().ULongLong());
      tmp.GetScalar() += to_generic(breg_offset);
      tmp.ClearContext();
      stack.push_back(tmp);
      stack.back().SetValueType(Value::ValueType::LoadAddress);
    } break;

    case DW_OP_fbreg:
      if (llvm::Error err =
              Evaluate_DW_OP_fbreg(eval_ctx, op->getRawOperand(0)))
        return err;
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar().ULongLong());
      break;

    case DW_OP_nop:
      break;

    case DW_OP_piece: {
      if (llvm::Error err =
              Evaluate_DW_OP_piece(eval_ctx, op->getRawOperand(0)))
        return err;
    } break;

    case DW_OP_bit_piece:
      if (stack.size() < 1) {
        UpdateValueTypeFromLocationDescription(eval_ctx,
                                               LocationDescriptionKind::Empty);
        // Reset for the next piece.
        eval_ctx.loc_desc_kind = Memory;
        return llvm::createStringError(
            "expression stack needs at least 1 item for DW_OP_bit_piece");
      } else {
        const LocationDescriptionKind piece_locdesc = eval_ctx.loc_desc_kind;
        UpdateValueTypeFromLocationDescription(eval_ctx, piece_locdesc,
                                               &stack.back());
        // Reset for the next piece.
        eval_ctx.loc_desc_kind = Memory;
        const uint64_t piece_bit_size = op->getRawOperand(0);
        const uint64_t piece_bit_offset = op->getRawOperand(1);
        switch (stack.back().GetValueType()) {
        case Value::ValueType::Invalid:
          return llvm::createStringError(
              "unable to extract bit value from invalid value");
        case Value::ValueType::Scalar: {
          if (!stack.back().GetScalar().ExtractBitfield(piece_bit_size,
                                                        piece_bit_offset)) {
            return llvm::createStringError(
                "unable to extract %" PRIu64 " bit value with %" PRIu64
                " bit offset from a %" PRIu64 " bit scalar value.",
                piece_bit_size, piece_bit_offset,
                (uint64_t)(stack.back().GetScalar().GetByteSize() * 8));
          }
        } break;

        case Value::ValueType::FileAddress:
        case Value::ValueType::LoadAddress:
          return llvm::createStringError(
              "unable to extract DW_OP_bit_piece(bit_size = %" PRIu64
              ", bit_offset = %" PRIu64 ") from an address value.",
              piece_bit_size, piece_bit_offset);

        case Value::ValueType::HostAddress:
          // As above, a full-width DW_OP_implicit_value piece refers to the
          // backing bytes, not the address of that backing storage.
          if (piece_locdesc == Implicit && piece_bit_offset == 0 &&
              piece_bit_size % 8 == 0 &&
              stack.back().GetBuffer().GetByteSize() == piece_bit_size / 8)
            break;
          return llvm::createStringError(
              "unable to extract DW_OP_bit_piece(bit_size = %" PRIu64
              ", bit_offset = %" PRIu64 ") from an address value.",
              piece_bit_size, piece_bit_offset);
        }
      }
      break;

    case DW_OP_implicit_value: {
      eval_ctx.loc_desc_kind = Implicit;

      // The second operand is a sequence of bytes of the length specified by
      // the first operand. LLVM represents it as an offset to that sequence.
      const uint64_t block_size = op->getRawOperand(0);
      uint64_t block_offset = op->getRawOperand(1);

      llvm::Error error = llvm::Error::success();
      llvm::StringRef block_data =
          expr_data.getBytes(&block_offset, block_size, &error);

      if (error)
        return error;

      Value result(block_data.data(), block_data.size());
      stack.push_back(result);
      break;
    }

    case DW_OP_implicit_pointer: {
      eval_ctx.loc_desc_kind = Implicit;
      return llvm::createStringError("could not evaluate %s",
                                     DW_OP_value_to_name(opcode));
    }

    case DW_OP_push_object_address:
      if (eval_ctx.object_address_ptr)
        stack.push_back(*eval_ctx.object_address_ptr);
      else {
        return llvm::createStringError("DW_OP_push_object_address used without "
                                       "specifying an object address");
      }
      break;

    case DW_OP_stack_value:
      eval_ctx.loc_desc_kind = Implicit;
      stack.back().SetValueType(Value::ValueType::Scalar);
      break;

    case DW_OP_convert:
      if (llvm::Error err =
              Evaluate_DW_OP_convert(eval_ctx, op->getRawOperand(0)))
        return err;
      break;

    case DW_OP_call_frame_cfa:
      if (llvm::Error err = Evaluate_DW_OP_call_frame_cfa(eval_ctx))
        return err;
      stack.back().GetScalar() =
          to_generic(stack.back().GetScalar().ULongLong());
      break;

    case DW_OP_form_tls_address:
    case DW_OP_GNU_push_tls_address:
      if (llvm::Error err = Evaluate_DW_OP_form_tls_address(eval_ctx, opcode))
        return err;
      break;

    case DW_OP_addrx:
    case DW_OP_GNU_addr_index: {
      if (!eval_ctx.dwarf_cu)
        return llvm::createStringError("DW_OP_GNU_addr_index found without a "
                                       "compile unit being specified");
      uint64_t index = op->getRawOperand(0);
      lldb::addr_t value =
          eval_ctx.dwarf_cu->ReadAddressFromDebugAddrSection(index);
      stack.push_back(to_generic(value));
      stack.back().SetValueType(Value::ValueType::FileAddress);
    } break;

    case DW_OP_GNU_const_index: {
      if (!eval_ctx.dwarf_cu) {
        return llvm::createStringError("DW_OP_GNU_const_index found without a "
                                       "compile unit being specified");
      }
      uint64_t index = op->getRawOperand(0);
      lldb::addr_t value =
          eval_ctx.dwarf_cu->ReadAddressFromDebugAddrSection(index);
      stack.push_back(to_generic(value));
    } break;

    case DW_OP_GNU_entry_value:
    case DW_OP_entry_value: {
      // Technically, DW_OP_entry_value has two operands, but LLVM represents
      // it as a single-operand operation (bug?). We can deal with this: the
      // second operand immediately follows the first, but have to be careful
      // when advancing the iterator, see the comment below.
      const uint64_t block_size = op->getRawOperand(0);
      uint64_t block_offset = op->getEndOffset();

      llvm::Error error = llvm::Error::success();
      llvm::ArrayRef<uint8_t> block_data = llvm::arrayRefFromStringRef(
          expr_data.getBytes(&block_offset, block_size, &error));

      if (error)
        return error;

      if (llvm::Error err = Evaluate_DW_OP_entry_value(eval_ctx, block_data))
        return llvm::createStringError(
            "could not evaluate DW_OP_entry_value: %s",
            llvm::toString(std::move(err)).c_str());

      // We can't use `operator++` here because the iterator currently points
      // to the second operand. See the comment above.
      op = op.skipBytes(block_size);
      continue;
    }

    // These opcodes are decoded but not evaluated here.
    case DW_OP_xderef:
    case DW_OP_xderef_size:
    case DW_OP_call2:
    case DW_OP_call4:
    case DW_OP_call_ref:
    case DW_OP_constx:
    case DW_OP_const_type:
    case DW_OP_regval_type:
    case DW_OP_deref_type:
    case DW_OP_xderef_type:
    case DW_OP_reinterpret:
    case DW_OP_GNU_implicit_pointer:
      return llvm::createStringError("unimplemented opcode %s",
                                     DW_OP_value_to_name(opcode));

    case DW_OP_LLVM_user:
      if (op->getSubCode() == DW_OP_LLVM_piece_end) {
        if (op->getEndOffset() != expr_data.size())
          return llvm::createStringError(
              "DW_OP_LLVM_piece_end is only supported at the end of an "
              "expression");

        // LLDB already constructs one composite in `pieces`, so a terminal
        // DW_OP_LLVM_piece_end is a no-op. TODO: Support multiple composites
        // and DW_OP_piece_end once LLVM implements DWARF 6 locations on the
        // stack.
        // Extension:
        // https://llvm.org/docs/AMDGPUDwarfExtensionsForHeterogeneousDebugging.html
        // Standard: https://dwarfstd.org/issues/230524.1-orig.html
        break;
      }
      [[fallthrough]];

    default:
      if (eval_ctx.dwarf_cu) {
        const uint64_t operands_offset = op_offset + 1;
        uint64_t offset = operands_offset; // Updated by the callee.
        if (eval_ctx.dwarf_cu->ParseVendorDWARFOpcode(
                opcode, expr_data, offset, eval_ctx.reg_ctx, eval_ctx.reg_kind,
                stack)) {
          // This is a little tricky. If LLVM knows about this vendor-specific
          // operation, `getEndOffset()` points past its last operand. If LLVM
          // knows nothing about this operation, `getEndOffset()` points to its
          // opcode. In both cases `offset` will point to the next operation,
          // but we can't use it directly because the only available mutating
          // method of `iterator` (not counting `operator++`) is `skipBytes()`.
          // So we calculate the offset and pass it to `skipBytes()`.
          assert(offset >= op->getEndOffset());
          uint64_t offset_to_next_op = offset - op->getEndOffset();
          op = op.skipBytes(offset_to_next_op);
          continue;
        }
      }
      return llvm::createStringErrorV("unhandled opcode {0} in DWARFExpression",
                                      opcode);
    }
    ++op;
  }

  if (stack.empty()) {
    // Nothing on the stack, check if we created a piece value from DW_OP_piece
    // or DW_OP_bit_piece opcodes
    if (eval_ctx.pieces.GetBuffer().GetByteSize())
      return eval_ctx.pieces;

    return llvm::createStringError("stack empty after evaluation");
  }

  UpdateValueTypeFromLocationDescription(eval_ctx, eval_ctx.loc_desc_kind,
                                         &stack.back());

  if (log && log->GetVerbose()) {
    size_t count = stack.size();
    LLDB_LOGF(log, "Stack after operation has %" PRIu64 " values:",
              static_cast<uint64_t>(count));
    for (size_t i = 0; i < count; ++i) {
      StreamString new_value;
      new_value.Printf("[%" PRIu64 "]", static_cast<uint64_t>(i));
      stack[i].Dump(&new_value);
      LLDB_LOGF(log, "  %s", new_value.GetData());
    }
  }
  return stack.back();
}

bool DWARFExpression::MatchesOperand(
    StackFrame &frame, const Instruction::Operand &operand) const {
  using namespace OperandMatchers;

  RegisterContextSP reg_ctx_sp = frame.GetRegisterContext();
  if (!reg_ctx_sp) {
    return false;
  }

  DataExtractor opcodes(m_data);

  lldb::offset_t op_offset = 0;
  uint8_t opcode = opcodes.GetU8(&op_offset);

  if (opcode == DW_OP_fbreg) {
    int64_t offset = opcodes.GetSLEB128(&op_offset);

    DWARFExpressionList *fb_expr = frame.GetFrameBaseExpression(nullptr);
    if (!fb_expr) {
      return false;
    }

    auto recurse = [&frame, fb_expr](const Instruction::Operand &child) {
      return fb_expr->MatchesOperand(frame, child);
    };

    if (!offset &&
        MatchUnaryOp(MatchOpType(Instruction::Operand::Type::Dereference),
                     recurse)(operand)) {
      return true;
    }

    return MatchUnaryOp(
        MatchOpType(Instruction::Operand::Type::Dereference),
        MatchBinaryOp(MatchOpType(Instruction::Operand::Type::Sum),
                      MatchImmOp(offset), recurse))(operand);
  }

  bool dereference = false;
  const RegisterInfo *reg = nullptr;
  int64_t offset = 0;

  if (opcode >= DW_OP_reg0 && opcode <= DW_OP_reg31) {
    reg = reg_ctx_sp->GetRegisterInfo(m_reg_kind, opcode - DW_OP_reg0);
  } else if (opcode >= DW_OP_breg0 && opcode <= DW_OP_breg31) {
    offset = opcodes.GetSLEB128(&op_offset);
    reg = reg_ctx_sp->GetRegisterInfo(m_reg_kind, opcode - DW_OP_breg0);
  } else if (opcode == DW_OP_regx) {
    uint32_t reg_num = static_cast<uint32_t>(opcodes.GetULEB128(&op_offset));
    reg = reg_ctx_sp->GetRegisterInfo(m_reg_kind, reg_num);
  } else if (opcode == DW_OP_bregx) {
    uint32_t reg_num = static_cast<uint32_t>(opcodes.GetULEB128(&op_offset));
    offset = opcodes.GetSLEB128(&op_offset);
    reg = reg_ctx_sp->GetRegisterInfo(m_reg_kind, reg_num);
  } else {
    return false;
  }

  if (!reg) {
    return false;
  }

  if (dereference) {
    if (!offset &&
        MatchUnaryOp(MatchOpType(Instruction::Operand::Type::Dereference),
                     MatchRegOp(*reg))(operand)) {
      return true;
    }

    return MatchUnaryOp(
        MatchOpType(Instruction::Operand::Type::Dereference),
        MatchBinaryOp(MatchOpType(Instruction::Operand::Type::Sum),
                      MatchRegOp(*reg), MatchImmOp(offset)))(operand);
  } else {
    return MatchRegOp(*reg)(operand);
  }
}