runtime: Bitstring implementation for subtype checking (1/4).
Implement a BitString abstraction for storing nbit-sized characters in a
single machine word (uint32).
This is used to enable an O(1) subtype check in subsequent CLs.
Test: art/test.py -b -j32 --host --target
Bug: 64692057
Change-Id: I792405e0c34242cc1206cedeb18e3e6fb687d94b
diff --git a/runtime/Android.bp b/runtime/Android.bp
index cfdac1c..3059533 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -534,6 +534,7 @@
"barrier_test.cc",
"base/arena_allocator_test.cc",
"base/bit_field_test.cc",
+ "base/bit_string_test.cc",
"base/bit_struct_test.cc",
"base/bit_utils_test.cc",
"base/bit_vector_test.cc",
diff --git a/runtime/base/bit_string.h b/runtime/base/bit_string.h
new file mode 100644
index 0000000..d4197e3
--- /dev/null
+++ b/runtime/base/bit_string.h
@@ -0,0 +1,303 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_BIT_STRING_H_
+#define ART_RUNTIME_BASE_BIT_STRING_H_
+
+#include "base/bit_struct.h"
+#include "base/bit_utils.h"
+
+#include <ostream>
+
+namespace art {
+
+struct BitStringChar;
+inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc);
+
+/**
+ * A BitStringChar is a light-weight wrapper to read/write a single character
+ * into a BitString, while restricting the bitlength.
+ *
+ * This is only intended for reading/writing into temporaries, as the representation is
+ * inefficient for memory (it uses a word for the character and another word for the bitlength).
+ *
+ * See also BitString below.
+ */
+struct BitStringChar {
+ using StorageType = uint32_t;
+ static_assert(std::is_unsigned<StorageType>::value, "BitStringChar::StorageType must be unsigned");
+
+ // BitStringChars are always zero-initialized by default. Equivalent to BitStringChar(0,0).
+ BitStringChar() : data_(0u), bitlength_(0u) { }
+
+ // Create a new BitStringChar whose data bits can be at most bitlength.
+ BitStringChar(StorageType data, size_t bitlength)
+ : data_(data), bitlength_(bitlength) {
+ // All bits higher than bitlength must be set to 0.
+ DCHECK_EQ(0u, data & ~MaskLeastSignificant(bitlength_))
+ << "BitStringChar data out of range, data: " << data << ", bitlength: " << bitlength;
+ }
+
+ // What is the bitlength constraint for this character?
+ // (Data could use less bits, but this is the maximum bit capacity at that BitString position).
+ size_t GetBitLength() const {
+ return bitlength_;
+ }
+
+ // Is there any capacity in this BitStringChar to store any data?
+ bool IsEmpty() const {
+ return bitlength_ == 0;
+ }
+
+ explicit operator StorageType() const {
+ return data_;
+ }
+
+ bool operator==(StorageType storage) const {
+ return data_ == storage;
+ }
+
+ bool operator!=(StorageType storage) const {
+ return !(*this == storage);
+ }
+
+ // Compare equality against another BitStringChar. Note: bitlength is ignored.
+ bool operator==(const BitStringChar& other) const {
+ return data_ == other.data_;
+ }
+
+ // Compare non-equality against another BitStringChar. Note: bitlength is ignored.
+ bool operator!=(const BitStringChar& other) const {
+ return !(*this == other);
+ }
+
+ // Add a BitStringChar with an integer. The resulting BitStringChar's data must still fit within
+ // this BitStringChar's bit length.
+ BitStringChar operator+(StorageType storage) const {
+ DCHECK_LE(storage, MaximumValue().data_ - data_) << "Addition would overflow " << *this;
+ return BitStringChar(data_ + storage, bitlength_);
+ }
+
+ // Get the maximum representible value with the same bitlength.
+ // (Useful to figure out the maximum value for this BitString position.)
+ BitStringChar MaximumValue() const {
+ StorageType maximimum_data = MaxInt<StorageType>(bitlength_);
+ return BitStringChar(maximimum_data, bitlength_);
+ }
+
+ private:
+ StorageType data_; // Unused bits (outside of bitlength) are 0.
+ size_t bitlength_;
+ // Logically const. Physically non-const so operator= still works.
+};
+
+// Print e.g. "BitStringChar<10>(123)" where 10=bitlength, 123=data.
+inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc) {
+ os << "BitStringChar<" << bc.GetBitLength() << ">("
+ << static_cast<BitStringChar::StorageType>(bc) << ")";
+ return os;
+}
+
+/**
+ * BitString
+ *
+ * MSB LSB
+ * +------------+------------+------------+-----+------------+
+ * | | | | | |
+ * | Char0 | Char1 | Char2 | ... | CharN |
+ * | | | | | |
+ * +------------+------------+------------+-----+------------+
+ * <- len[0] -> <- len[1] -> <- len[2] -> ... <- len[N] ->
+ *
+ * Stores up to "N+1" characters in a subset of a machine word. Each character has a different
+ * bitlength, as defined by len[pos]. This BitString can be nested inside of a BitStruct
+ * (see e.g. SubtypeCheckBitsAndStatus).
+ *
+ * Definitions:
+ *
+ * "ABCDE...K" := [A,B,C,D,E, ... K] + [0]*(N-idx(K)) s.t. N >= K.
+ * // Padded with trailing 0s to fit (N+1) bitstring chars.
+ * MaxBitstringLen := N+1
+ * StrLen(Bitstring) := MaxBitStringLen - | forall char in CharI..CharN : char == 0 AND Char(I-1) != 0 |
+ * // Maximum length - the # of consecutive trailing zeroes.
+ * Bitstring[N] := CharN
+ * Bitstring[I..N) := [CharI, CharI+1, ... CharN-1]
+ *
+ * (These are used by the SubtypeCheckInfo definitions and invariants, see subtype_check_info.h)
+ */
+struct BitString {
+ using StorageType = BitStringChar::StorageType;
+
+ // As this is meant to be used only with "SubtypeCheckInfo",
+ // the bitlengths and the maximum string length is tuned by maximizing the coverage of "Assigned"
+ // bitstrings for instance-of and check-cast targets during Optimizing compilation.
+ static constexpr size_t kBitSizeAtPosition[] = {12, 3, 8}; // len[] from header docs.
+ static constexpr size_t kCapacity = arraysize(kBitSizeAtPosition); // MaxBitstringLen above.
+
+ // How many bits are needed to represent BitString[0..position)?
+ static constexpr size_t GetBitLengthTotalAtPosition(size_t position) {
+ size_t idx = 0;
+ size_t sum = 0;
+ while (idx < position && idx < kCapacity) {
+ sum += kBitSizeAtPosition[idx];
+ ++idx;
+ }
+ // TODO: precompute with CreateArray helper.
+
+ return sum;
+ }
+
+ // What is the least-significant-bit for a position?
+ // (e.g. to use with BitField{Insert,Extract,Clear}.)
+ static constexpr size_t GetLsbForPosition(size_t position) {
+ DCHECK_GE(kCapacity, position);
+ constexpr size_t kMaximumBitLength = GetBitLengthTotalAtPosition(kCapacity);
+ return kMaximumBitLength - GetBitLengthTotalAtPosition(position + 1u);
+ }
+
+ // How many bits are needed for a BitStringChar at the position?
+ // Returns 0 if the position is out of range.
+ static constexpr size_t MaybeGetBitLengthAtPosition(size_t position) {
+ if (position >= kCapacity) {
+ return 0;
+ }
+ return kBitSizeAtPosition[position];
+ }
+
+ // Read a bitchar at some index within the capacity.
+ // See also "BitString[N]" in the doc header.
+ BitStringChar operator[](size_t idx) const {
+ DCHECK_LT(idx, kCapacity);
+
+ StorageType data =
+ BitFieldExtract(storage_,
+ GetLsbForPosition(idx), kBitSizeAtPosition[idx]);
+
+ return BitStringChar(data, kBitSizeAtPosition[idx]);
+ }
+
+ // Overwrite a bitchar at a position with a new one.
+ //
+ // The `bitchar` bitlength must be no more than the maximum bitlength for that position.
+ void SetAt(size_t idx, BitStringChar bitchar) {
+ DCHECK_LT(idx, kCapacity);
+ DCHECK_LE(bitchar.GetBitLength(), kBitSizeAtPosition[idx]);
+
+ // Read the bitchar: Bits > bitlength in bitchar are defined to be 0.
+ storage_ = BitFieldInsert(storage_,
+ static_cast<StorageType>(bitchar),
+ GetLsbForPosition(idx),
+ kBitSizeAtPosition[idx]);
+ }
+
+ // How many characters are there in this bitstring?
+ // Trailing 0s are ignored, but 0s in-between are counted.
+ // See also "StrLen(BitString)" in the doc header.
+ size_t Length() const {
+ size_t num_trailing_zeros = 0;
+ size_t i;
+ for (i = kCapacity - 1u; ; --i) {
+ BitStringChar bc = (*this)[i];
+ if (bc != 0u) {
+ break; // Found first trailing non-zero.
+ }
+
+ ++num_trailing_zeros;
+ if (i == 0u) {
+ break; // No more bitchars remaining: don't underflow.
+ }
+ }
+
+ return kCapacity - num_trailing_zeros;
+ }
+
+ // Cast to the underlying integral storage type.
+ explicit operator StorageType() const {
+ return storage_;
+ }
+
+ // Get the # of bits this would use if it was nested inside of a BitStruct.
+ static constexpr size_t BitStructSizeOf() {
+ return GetBitLengthTotalAtPosition(kCapacity);
+ }
+
+ BitString() = default;
+
+ // Efficient O(1) comparison: Equal if both bitstring words are the same.
+ bool operator==(const BitString& other) const {
+ return storage_ == other.storage_;
+ }
+
+ // Efficient O(1) negative comparison: Not-equal if both bitstring words are different.
+ bool operator!=(const BitString& other) const {
+ return !(*this == other);
+ }
+
+ // Remove all BitStringChars starting at end.
+ // Returns the BitString[0..end) substring as a copy.
+ // See also "BitString[I..N)" in the doc header.
+ BitString Truncate(size_t end) {
+ DCHECK_GE(kCapacity, end);
+ BitString copy = *this;
+
+ size_t bit_size = 0;
+ for (size_t idx = end; idx < kCapacity; ++idx) {
+ bit_size += kBitSizeAtPosition[idx];
+ }
+ // TODO: precompute above table.
+
+ if (bit_size > 0) {
+ StorageType data =
+ BitFieldClear(copy.storage_,
+ GetLsbForPosition(kCapacity),
+ bit_size);
+ copy.storage_ = data;
+ }
+
+ return copy;
+ }
+
+ private:
+ friend std::ostream& operator<<(std::ostream& os, const BitString& bit_string);
+
+ // Data is stored with the "highest" position in the least-significant-bit.
+ // As positions approach 0, the bits are stored with increasing significance.
+ StorageType storage_;
+};
+
+static_assert(BitSizeOf<BitString::StorageType>() >=
+ BitString::GetBitLengthTotalAtPosition(BitString::kCapacity),
+ "Storage type is too small for the # of bits requested");
+
+// Print e.g. "BitString[1,0,3]". Trailing 0s are dropped.
+inline std::ostream& operator<<(std::ostream& os, const BitString& bit_string) {
+ const size_t length = bit_string.Length();
+
+ os << "BitString[";
+ for (size_t i = 0; i < length; ++i) {
+ BitStringChar bc = bit_string[i];
+ if (i != 0) {
+ os << ",";
+ }
+ os << static_cast<BitString::StorageType>(bc);
+ }
+ os << "]";
+ return os;
+}
+
+} // namespace art
+
+#endif // ART_RUNTIME_BASE_BIT_STRING_H_
diff --git a/runtime/base/bit_string_test.cc b/runtime/base/bit_string_test.cc
new file mode 100644
index 0000000..d5610e7
--- /dev/null
+++ b/runtime/base/bit_string_test.cc
@@ -0,0 +1,170 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "base/bit_string.h"
+
+#include "gtest/gtest.h"
+#include "android-base/logging.h"
+
+namespace art {
+
+constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
+constexpr size_t BitString::kCapacity;
+
+}; // namespace art
+
+using namespace art; // NOLINT [build/namespaces] [5]
+
+// These helper functions are only used by the test,
+// so they are not in the main BitString class.
+std::string Stringify(BitString bit_string) {
+ std::stringstream ss;
+ ss << bit_string;
+ return ss.str();
+}
+
+BitStringChar MakeBitStringChar(size_t idx, size_t val) {
+ return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx));
+}
+
+BitStringChar MakeBitStringChar(size_t val) {
+ return BitStringChar(val, MinimumBitsToStore(val));
+}
+
+BitString MakeBitString(std::initializer_list<size_t> values = {}) {
+ CHECK_GE(BitString::kCapacity, values.size());
+
+ BitString bs{}; // NOLINT
+
+ size_t i = 0;
+ for (size_t val : values) {
+ bs.SetAt(i, MakeBitStringChar(i, val));
+ ++i;
+ }
+
+ return bs;
+}
+
+template <typename T>
+size_t AsUint(const T& value) {
+ size_t uint_value = 0;
+ memcpy(&uint_value, &value, sizeof(value));
+ return uint_value;
+}
+
+// Make max bitstring, e.g. BitString[4095,7,255] for {12,3,8}
+template <size_t kCount = BitString::kCapacity>
+BitString MakeBitStringMax() {
+ BitString bs{}; // NOLINT
+
+ for (size_t i = 0; i < kCount; ++i) {
+ bs.SetAt(i,
+ MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i])));
+ }
+
+ return bs;
+}
+
+BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) {
+ BitString bs = bit_string;
+ bs.SetAt(i, MakeBitStringChar(i, val));
+ return bs;
+}
+
+#define EXPECT_BITSTRING_STR(expected_str, actual_value) \
+ EXPECT_STREQ((expected_str), Stringify((actual_value)).c_str())
+
+TEST(InstanceOfBitString, GetLsbForPosition) {
+ ASSERT_LE(3u, BitString::kCapacity);
+ // Test will fail if kCapacity is not at least 3. Update it.
+ EXPECT_EQ(0u, BitString::GetLsbForPosition(BitString::kCapacity - 1u));
+ EXPECT_EQ(BitString::kBitSizeAtPosition[BitString::kCapacity - 1u],
+ BitString::GetLsbForPosition(BitString::kCapacity - 2u));
+ EXPECT_EQ(BitString::kBitSizeAtPosition[BitString::kCapacity - 1u] +
+ BitString::kBitSizeAtPosition[BitString::kCapacity - 2u],
+ BitString::GetLsbForPosition(BitString::kCapacity - 3u));
+}
+
+TEST(InstanceOfBitString, ToString) {
+ EXPECT_BITSTRING_STR("BitString[]", MakeBitString({0}));
+ EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1}));
+ EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3}));
+}
+
+TEST(InstanceOfBitString, ReadWrite) {
+ BitString bs = MakeBitString();
+
+ // Update tests if changing the capacity.
+ ASSERT_EQ(BitString::kCapacity, 3u);
+
+ EXPECT_BITSTRING_STR("BitString[]", bs);
+ bs = SetBitStringCharAt(bs, /*i*/0, /*val*/1u);
+ EXPECT_BITSTRING_STR("BitString[1]", bs);
+ bs = SetBitStringCharAt(bs, /*i*/1, /*val*/2u);
+ EXPECT_BITSTRING_STR("BitString[1,2]", bs);
+ bs = SetBitStringCharAt(bs, /*i*/2, /*val*/3u);
+ EXPECT_BITSTRING_STR("BitString[1,2,3]", bs);
+
+ // There should be at least "kCapacity" # of checks here, 1 for each unique position.
+ EXPECT_EQ(MakeBitStringChar(/*idx*/0, /*val*/1u), bs[0]);
+ EXPECT_EQ(MakeBitStringChar(/*idx*/1, /*val*/2u), bs[1]);
+ EXPECT_EQ(MakeBitStringChar(/*idx*/2, /*val*/3u), bs[2]);
+
+ // Each maximal value should be tested here for each position.
+ uint32_t max_bitstring_ints[] = {
+ MaxInt<uint32_t>(12),
+ MaxInt<uint32_t>(3),
+ MaxInt<uint32_t>(8),
+ };
+
+ // Update tests if changing the tuning values above.
+ for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) {
+ ASSERT_EQ(MinimumBitsToStore(max_bitstring_ints[i]), BitString::kBitSizeAtPosition[i]) << i;
+ }
+
+ BitString bs_max = MakeBitStringMax();
+
+ for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) {
+ ASSERT_EQ(max_bitstring_ints[i], static_cast<uint32_t>(bs_max[i])) << i;
+ }
+
+ EXPECT_EQ(MaskLeastSignificant(BitString::GetBitLengthTotalAtPosition(BitString::kCapacity)),
+ AsUint(MakeBitStringMax()));
+}
+
+template <size_t kPos>
+constexpr auto MaxForPos() {
+ return MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[kPos]);
+}
+
+TEST(InstanceOfBitString, MemoryRepresentation) {
+ // Verify that the lower positions are stored in more significant bits.
+ BitString bs = MakeBitString({MaxForPos<0>(), MaxForPos<1>()});
+ BitString::StorageType as_int = static_cast<BitString::StorageType>(bs);
+
+ // Below tests assumes the capacity is 3. Update if it this changes.
+ ASSERT_EQ(3u, BitString::kCapacity);
+ EXPECT_EQ(MaxForPos<0>() << (BitString::kBitSizeAtPosition[2] + BitString::kBitSizeAtPosition[1]) |
+ (MaxForPos<1>() << BitString::kBitSizeAtPosition[2]),
+ as_int);
+}
+
+TEST(InstanceOfBitString, Truncate) {
+ EXPECT_BITSTRING_STR("BitString[]", MakeBitString({1, 2, 3}).Truncate(0));
+ EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1, 2, 3}).Truncate(1));
+ EXPECT_BITSTRING_STR("BitString[1,2]", MakeBitString({1, 2, 3}).Truncate(2));
+ EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3}).Truncate(3));
+}