LayoutDescriptorHelper is now able to calculate the length of contiguous regions of tagged/non-tagg…

src/layout-descriptor.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <sstream>
 
 #include "src/v8.h"
 
 #include "src/layout-descriptor.h"
 
@@ skipping 125 matching lines @@
            layout_descriptor->DataSize());
     return new_layout_descriptor;
   } else {
     // Fast layout.
     uint32_t value =
         static_cast<uint32_t>(Smi::cast(*layout_descriptor)->value());
     new_layout_descriptor->set(0, value);
     return new_layout_descriptor;
   }
 }
+
+
+// Number of trailing zeros, Seal’s algorithm.
+int ntz32(uint32_t x) {

[Hannes Payer (out of office), 2014/11/25 17:20:13]

Can we move this to utils or some global place that makes sense.

[Igor Sheludko, 2014/12/10 18:22:04]

I removed it in favor of v8::base::bits::CountTrailingZeros32().

+  const char u = -1;  // Unused cell.
+  static char table[64] = {32, 0,  1,  12, 2,  6,  u,  13, 3,  u,  7,  u, u,
+                           u,  u,  14, 10, 4,  u,  u,  8,  u,  u,  25, u, u,
+                           u,  u,  u,  21, 27, 15, 31, 11, 5,  u,  u,  u, u,
+                           u,  9,  u,  u,  24, u,  u,  20, 26, 30, u,  u, u,
+                           u,  23, u,  19, 29, u,  22, 18, 28, 17, 16, u};
+  x = (x & -x) * 0x0450FBAF;
+  return table[x >> 26];
+}
+
+
+bool LayoutDescriptor::IsTagged(int field_index, int max_sequence_length,
+                                int* out_sequence_length) {
+  DCHECK(max_sequence_length > 0);
+  if (IsFastPointerLayout()) {
+    *out_sequence_length = max_sequence_length;
+    return true;
+  }
+
+  int layout_word_index;
+  int layout_bit_index;
+
+  if (!GetIndexes(field_index, &layout_word_index, &layout_bit_index)) {
+    // Out of bounds queries are considered tagged.
+    *out_sequence_length = max_sequence_length;
+    return true;
+  }
+  uint32_t layout_mask = static_cast<uint32_t>(1) << layout_bit_index;
+
+  uint32_t value = IsSlowLayout()
+                       ? get_scalar(layout_word_index)
+                       : static_cast<uint32_t>(Smi::cast(this)->value());
+
+  bool is_tagged = (value & layout_mask) == 0;
+  if (!is_tagged) value = ~value;  // Count set bits instead of cleared bits.
+  value = value & ~(layout_mask - 1);  // Clear bits we are not interested in.
+  int sequence_length = ntz32(value) - layout_bit_index;
+
+  if (layout_bit_index + sequence_length == kNumberOfBits) {
+    // This is a contiguous sequence till the end of current word, proceed
+    // counting in the subsequent words.
+    if (IsSlowLayout()) {
+      int len = length();
+      ++layout_word_index;
+      for (; layout_word_index < len; layout_word_index++) {
+        value = get_scalar(layout_word_index);
+        bool cur_is_tagged = (value & 1) == 0;
+        if (cur_is_tagged != is_tagged) break;
+        if (!is_tagged) value = ~value;  // Count set bits instead.
+        int cur_sequence_length = ntz32(value);
+        sequence_length += cur_sequence_length;
+        if (sequence_length >= max_sequence_length) break;
+        if (cur_sequence_length != kNumberOfBits) break;
+      }
+    }
+    if (is_tagged && (field_index + sequence_length == capacity())) {
+      // The contiguous sequence of tagged fields lasts till the end of the
+      // layout descriptor which means that all the fields starting from
+      // field_index are tagged.
+      sequence_length = std::numeric_limits<int>::max();
+    }
+  }
+  *out_sequence_length = Min(sequence_length, max_sequence_length);
+  return is_tagged;
+}
+
+
+Handle<LayoutDescriptor> LayoutDescriptor::NewForTesting(Isolate* isolate,
+                                                         int length) {
+  return New(isolate, length);
+}
+
+
+LayoutDescriptor* LayoutDescriptor::SetTaggedForTesting(int field_index,
+                                                        bool tagged) {
+  return SetTagged(field_index, tagged);
+}
+
+
+bool LayoutDescriptorHelper::IsTagged(
+    int offset_in_bytes, int end_offset,
+    int* out_end_of_contiguous_region_offset) {
+  DCHECK(IsAligned(offset_in_bytes, kPointerSize));
+  DCHECK(IsAligned(end_offset, kPointerSize));
+  DCHECK(offset_in_bytes < end_offset);
+  if (all_fields_tagged_) {
+    *out_end_of_contiguous_region_offset = end_offset;
+    return true;
+  }
+  int max_sequence_length = (end_offset - offset_in_bytes) / kPointerSize;
+  int field_index = Max(0, (offset_in_bytes - header_size_) / kPointerSize);
+  int sequence_length;
+  bool tagged = layout_descriptor_->IsTagged(field_index, max_sequence_length,
+                                             &sequence_length);
+  DCHECK(sequence_length > 0);
+  if (offset_in_bytes < header_size_) {
+    // Object headers do not contain non-tagged fields. Check if the contiguous
+    // region continues after the header.
+    if (tagged) {
+      // First field is tagged, calculate end offset from there.
+      *out_end_of_contiguous_region_offset =
+          header_size_ + sequence_length * kPointerSize;
+
+    } else {
+      *out_end_of_contiguous_region_offset = header_size_;
+    }
+    return true;
+  }
+  *out_end_of_contiguous_region_offset =
+      offset_in_bytes + sequence_length * kPointerSize;
+  return tagged;
+}
 }
 }  // namespace v8::internal