[lldb/Dwarf] Change DW_OP_piece to use an llvm::BitVector (WIP)

[mib]

Summary

This patch changes the implementation of DW_OP_piece to use
llvm::BitVector instead of the lldb_private::Value.

This allow to have more granularity which would be useful to implement
DW_OP_bit_piece but also when combined with a second BitVector for
masking the unknown bits/bytes, improves the DWARF Expression
evaluation Since it will show a future patch, the unknown bits/bytes as
optimised rather than showing - misleading - zeroes.

Additionally, this patch fixes a overloading resolution on the Scalar
constructor when using fixed-size interger types instead of fundamentale types.
It also fixes a bug when requesting a Scalar size when the value is less
than a byte.

Signed-off-by: Med Ismail Bennani <[e-mail]>

[aprantl]

lldb/source/Expression/DWARFExpression.cpp

936

Is this only going to be used for DW_OP_bit_piece? Otherwise I would have expected a name like top(_of_stack) or result.

937

This should perhaps be called undef_mask? And should have a comment what it is used for.

1267

This is not portable. The size of int could be anything depending on the host. Why not always use APIInt?

2164

how do you know the unsigned int is large enough for this operation?

lldb/source/Utility/Scalar.cpp

200

?

[vsk]

Excited to see this take shape :)

lldb/source/Expression/DWARFExpression.cpp

935

Stale comment here, would be nice to describe the purpose of the two bitvectors.

1261

I don't really understand a bunch of these changes. Is the idea to prevent implicit conversion to a type with the wrong size/signedness? I think that should really be tackled separately. We can make Scalar's constructors safe like this: https://godbolt.org/z/APUMA6

(basically stick template<typename T, std::enable_if_t<std::is_same<T, $whateverType>::value, int> = 0> in front of each overload)

2505

Can we assert that this doesn't drop any bits (bit_pieces.size() % 8 == 0)?

lldb/source/Utility/Scalar.cpp

200

This is worth a comment, I'm not sure what this is for.

[mib]

lldb/source/Expression/DWARFExpression.cpp

936

Yes, the same BitVector is used for both but I separated the DW_OP_piece changes for this diff, I forgot to change the name —‘

2505

Actually, I think this should be changed to std::ceil(bit_pieces.size() / 8.0) instead of putting an assert

lldb/source/Utility/Scalar.cpp

200

When the bitWidth is < 8, the division result is 0, but it should be 1 byte instead.

[mib]

Note that this diff is more a quick draft than a “finished” patch, I’m not expecting to submit this until the DW_OP_bit_piece support is done.

[mib]

lldb/source/Expression/DWARFExpression.cpp

2164

TBH, I just chose the same return type as GetScalar::UInt.
I’ll change it to GetScalar::UInt128 with an llvm::APInt

[labath]

looking forward to seeing the final form of this

In D76449#1932293, @mib wrote:

Note that this diff is more a quick draft than a “finished” patch, I’m not expecting to submit this until the DW_OP_bit_piece support is done.

Smaller patches are generally better. It would be great if you could split this into an "NFC" patch which just changes the underlying representation to BitVector and another patch which adds the validity mask. (It's fine if you wait with the first patch if you determine whether the validity mask approach is feasible, though honestly, I don't see any other way of achieving this.)

lldb/source/Expression/DWARFExpression.cpp

1261

+1 for doing this separately

1267

+1 for using APInt across the board. I'd be tempted to just delete the relevant Scalar constructors.

lldb/source/Utility/Scalar.cpp

200

Normally that would be done via something like (x+7)/8 and not by going floating point. However, that should be done as a separate patch (and a test).

lldb/source/Expression/DWARFExpression.cpp

bool DWARFExpression::Evaluate(
 
   if (initial_value_ptr)
     stack.push_back(*initial_value_ptr);
 
   lldb::offset_t offset = 0;
   Value tmp;
   uint32_t reg_num;
 
   /// Insertion point for evaluating multi-piece expression.
-  uint64_t op_piece_offset = 0;
-  Value pieces; // Used for DW_OP_piece
+  llvm::BitVector bit_pieces;
+  llvm::BitVector bit_mask;
 
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS));
 
   while (opcodes.ValidOffset(offset)) {
     const lldb::offset_t op_offset = offset;
     const uint8_t op = opcodes.GetU8(&offset);
 
     if (log && log->GetVerbose()) {
while (opcodes.ValidOffset(offset)) {
     // DW_OP_const1u    1-byte unsigned integer constant DW_OP_const1s
     // 1-byte signed integer constant DW_OP_const2u    2-byte unsigned integer
     // constant DW_OP_const2s    2-byte signed integer constant DW_OP_const4u
     // 4-byte unsigned integer constant DW_OP_const4s    4-byte signed integer
     // constant DW_OP_const8u    8-byte unsigned integer constant DW_OP_const8s
     // 8-byte signed integer constant DW_OP_constu     unsigned LEB128 integer
     // constant DW_OP_consts     signed LEB128 integer constant
     case DW_OP_const1u:
-      stack.push_back(Scalar((uint8_t)opcodes.GetU8(&offset)));
+      stack.push_back(Scalar((unsigned int)opcodes.GetU8(&offset)));
       break;
     case DW_OP_const1s:
-      stack.push_back(Scalar((int8_t)opcodes.GetU8(&offset)));
+      stack.push_back(Scalar((int)opcodes.GetU8(&offset)));
       break;
     case DW_OP_const2u:
-      stack.push_back(Scalar((uint16_t)opcodes.GetU16(&offset)));
+      stack.push_back(Scalar((unsigned int)opcodes.GetU16(&offset)));
       break;
     case DW_OP_const2s:
-      stack.push_back(Scalar((int16_t)opcodes.GetU16(&offset)));
+      stack.push_back(Scalar((int)opcodes.GetU16(&offset)));
       break;
     case DW_OP_const4u:
-      stack.push_back(Scalar((uint32_t)opcodes.GetU32(&offset)));
+      stack.push_back(Scalar((unsigned int)opcodes.GetU32(&offset)));
       break;
     case DW_OP_const4s:
-      stack.push_back(Scalar((int32_t)opcodes.GetU32(&offset)));
+      stack.push_back(Scalar((int)opcodes.GetU32(&offset)));
       break;
     case DW_OP_const8u:
-      stack.push_back(Scalar((uint64_t)opcodes.GetU64(&offset)));
+      stack.push_back(Scalar((unsigned long)opcodes.GetU64(&offset)));
       break;
     case DW_OP_const8s:
-      stack.push_back(Scalar((int64_t)opcodes.GetU64(&offset)));
+      stack.push_back(Scalar((long)opcodes.GetU64(&offset)));
       break;
     case DW_OP_constu:
-      stack.push_back(Scalar(opcodes.GetULEB128(&offset)));
+      stack.push_back(Scalar((unsigned long)opcodes.GetULEB128(&offset)));
       break;
     case DW_OP_consts:
-      stack.push_back(Scalar(opcodes.GetSLEB128(&offset)));
+      stack.push_back(Scalar((long)opcodes.GetSLEB128(&offset)));
       break;
 
     // OPCODE: DW_OP_dup
     // OPERANDS: none
     // DESCRIPTION: duplicates the value at the top of the stack
     case DW_OP_dup:
       if (stack.empty()) {
         if (error_ptr)

     // variable partially in memory and partially in registers. DW_OP_piece
     // provides a way of describing how large a part of a variable a particular
     // DWARF expression refers to.
     case DW_OP_piece: {
       const uint64_t piece_byte_size = opcodes.GetULEB128(&offset);
 
       if (piece_byte_size > 0) {
         Value curr_piece;
         
+        const uint64_t curr_width = std::max(bit_mask.size(), bit_pieces.size());
+
         if (stack.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);
-          pieces.AppendDataToHostBuffer(curr_piece);
+          bit_mask.resize(curr_width + piece_byte_size * 8);
+          bit_mask.set(curr_width, curr_width + piece_byte_size * 8);
         } else {
           Status error;
           // Extract the current piece into "curr_piece"
           Value curr_piece_source_value(stack.back());
           stack.pop_back();
 
-          const Value::ValueType curr_piece_source_value_type =
-              curr_piece_source_value.GetValueType();
-          switch (curr_piece_source_value_type) {
+          switch (curr_piece_source_value.GetValueType()) {
           case Value::eValueTypeLoadAddress:
             if (process) {
               if (curr_piece.ResizeData(piece_byte_size) == piece_byte_size) {
                 lldb::addr_t load_addr =
                     curr_piece_source_value.GetScalar().ULongLong(
                         LLDB_INVALID_ADDRESS);
                 if (process->ReadMemory(
                         load_addr, curr_piece.GetBuffer().GetBytes(),
case DW_OP_piece: {
                     " byte vector value.",
                     piece_byte_size,
                     (uint64_t)curr_piece_source_value.GetVector().length);
               return false;
             }
           } break;
           }
 
-          // Check if this is the first piece?
-          if (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 (pieces.AppendDataToHostBuffer(curr_piece) == 0) {
-              if (error_ptr)
-                error_ptr->SetErrorString("failed to append piece data");
-              return false;
-            }
-          } else {
-            // If this is the second or later piece there should be a value on
-            // the stack.
-            if (pieces.GetBuffer().GetByteSize() != op_piece_offset) {
-              if (error_ptr)
-                error_ptr->SetErrorStringWithFormat(
-                    "DW_OP_piece for offset %" PRIu64
-                    " but top of stack is of size %" PRIu64,
-                    op_piece_offset, pieces.GetBuffer().GetByteSize());
-              return false;
-            }
-
-            if (pieces.AppendDataToHostBuffer(curr_piece) == 0) {
-              if (error_ptr)
-                error_ptr->SetErrorString("failed to append piece data");
-              return false;
-            }
-          }
+          unsigned int curr_scalar = curr_piece.GetScalar().UInt();
+          curr_scalar = curr_scalar << curr_width;
+          bit_pieces.resize(curr_width + piece_byte_size * 8);
+          bit_pieces.setBitsInMask(&curr_scalar);
         }
-        op_piece_offset += piece_byte_size;
       }
     } break;
 
     case DW_OP_bit_piece: // 0x9d ULEB128 bit size, ULEB128 bit offset (DWARF3);
       if (stack.size() < 1) {
         if (error_ptr)
           error_ptr->SetErrorString(
               "Expression stack needs at least 1 item for DW_OP_bit_piece.");
default:
                 DW_OP_value_to_name(op));
       break;
     }
   }
 
   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 (pieces.GetBuffer().GetByteSize()) {
+    if (bit_pieces.size()) {
+      Value pieces;
+      pieces.AppendBytes(bit_pieces.getData().data(), bit_pieces.size() / 8);
       result = pieces;
     } else {
       if (error_ptr)
         error_ptr->SetErrorString("Stack empty after evaluation.");
       return false;
     }
   } else {
     if (log && log->GetVerbose()) {

lldb/source/Utility/Scalar.cpp

size_t Scalar::GetByteSize() const {
   case e_slonglong:
   case e_ulonglong:
   case e_sint128:
   case e_uint128:
   case e_sint256:
   case e_uint256:
   case e_sint512:
   case e_uint512:
-    return (m_integer.getBitWidth() / 8);
+    return ceil(m_integer.getBitWidth() / 8.0);
   case e_float:
     return sizeof(float_t);
   case e_double:
     return sizeof(double_t);
   case e_long_double:
     return sizeof(long_double_t);
   }
   return 0;