Compress the Dex register maps built by the optimizing compiler.
- Replace the current list-based (fixed-size) Dex register
encoding in stack maps emitted by the optimizing compiler
with another list-based variable-size Dex register
encoding compressing short locations on 1 byte (3 bits for
the location kind, 5 bits for the value); other (large)
values remain encoded on 5 bytes.
- In addition, use slot offsets instead of byte offsets to
encode the location of Dex registers placed in stack
slots at small offsets, as it enables more values to use
the short (1-byte wide) encoding instead of the large
(5-byte wide) one.
- Rename art::DexRegisterMap::LocationKind as
art::DexRegisterLocation::Kind, turn it into a
strongly-typed enum based on a uint8_t, and extend it to
support new kinds (kInStackLargeOffset and
kConstantLargeValue).
- Move art::DexRegisterEntry from
compiler/optimizing/stack_map_stream.h to
runtime/stack_map.h and rename it as
art::DexRegisterLocation.
- Adjust art::StackMapStream,
art::CodeGenerator::RecordPcInfo,
art::CheckReferenceMapVisitor::CheckOptimizedMethod,
art::StackVisitor::GetVRegFromOptimizedCode, and
art::StackVisitor::SetVRegFromOptimizedCode.
- Implement unaligned memory accesses in art::MemoryRegion.
- Use them to manipulate data in Dex register maps.
- Adjust oatdump to support the new Dex register encoding.
- Update compiler/optimizing/stack_map_test.cc.
Change-Id: Icefaa2e2b36b3c80bb1b882fe7ea2f77ba85c505
diff --git a/runtime/stack_map.h b/runtime/stack_map.h
index 6d99672..c981623 100644
--- a/runtime/stack_map.h
+++ b/runtime/stack_map.h
@@ -23,6 +23,11 @@
namespace art {
+// Size of a frame slot, in bytes. This constant is a signed value,
+// to please the compiler in arithmetic operations involving int32_t
+// (signed) values.
+static ssize_t constexpr kFrameSlotSize = 4;
+
/**
* Classes in the following file are wrapper on stack map information backed
* by a MemoryRegion. As such they read and write to the region, they don't have
@@ -58,6 +63,8 @@
}
private:
+ // TODO: Instead of plain types such as "uint8_t", introduce
+ // typedefs (and document the memory layout of InlineInfo).
static constexpr int kDepthOffset = 0;
static constexpr int kFixedSize = kDepthOffset + sizeof(uint8_t);
@@ -68,82 +75,327 @@
friend class StackMapStream;
};
+// Dex register location container used by DexRegisterMap and StackMapStream.
+class DexRegisterLocation {
+ public:
+ /*
+ * The location kind used to populate the Dex register information in a
+ * StackMapStream can either be:
+ * - kNone: the register has no location yet, meaning it has not been set;
+ * - kConstant: value holds the constant;
+ * - kStack: value holds the stack offset;
+ * - kRegister: value holds the physical register number;
+ * - kFpuRegister: value holds the physical register number.
+ *
+ * In addition, DexRegisterMap also uses these values:
+ * - kInStackLargeOffset: value holds a "large" stack offset (greater than
+ * 128 bytes);
+ * - kConstantLargeValue: value holds a "large" constant (lower than or
+ * equal to -16, or greater than 16).
+ */
+ enum class Kind : uint8_t {
+ // Short location kinds, for entries fitting on one byte (3 bits
+ // for the kind, 5 bits for the value) in a DexRegisterMap.
+ kNone = 0, // 0b000
+ kInStack = 1, // 0b001
+ kInRegister = 2, // 0b010
+ kInFpuRegister = 3, // 0b011
+ kConstant = 4, // 0b100
+
+ // Large location kinds, requiring a 5-byte encoding (1 byte for the
+ // kind, 4 bytes for the value).
+
+ // Stack location at a large offset, meaning that the offset value
+ // divided by the stack frame slot size (4 bytes) cannot fit on a
+ // 5-bit unsigned integer (i.e., this offset value is greater than
+ // or equal to 2^5 * 4 = 128 bytes).
+ kInStackLargeOffset = 5, // 0b101
+
+ // Large constant, that cannot fit on a 5-bit signed integer (i.e.,
+ // lower than -2^(5-1) = -16, or greater than or equal to
+ // 2^(5-1) - 1 = 15).
+ kConstantLargeValue = 6, // 0b110
+
+ kLastLocationKind = kConstantLargeValue
+ };
+
+ static_assert(
+ sizeof(Kind) == 1u,
+ "art::DexRegisterLocation::Kind has a size different from one byte.");
+
+ static const char* PrettyDescriptor(Kind kind) {
+ switch (kind) {
+ case Kind::kNone:
+ return "none";
+ case Kind::kInStack:
+ return "in stack";
+ case Kind::kInRegister:
+ return "in register";
+ case Kind::kInFpuRegister:
+ return "in fpu register";
+ case Kind::kConstant:
+ return "as constant";
+ case Kind::kInStackLargeOffset:
+ return "in stack (large offset)";
+ case Kind::kConstantLargeValue:
+ return "as constant (large value)";
+ default:
+ UNREACHABLE();
+ }
+ }
+
+ static bool IsShortLocationKind(Kind kind) {
+ switch (kind) {
+ case Kind::kNone:
+ case Kind::kInStack:
+ case Kind::kInRegister:
+ case Kind::kInFpuRegister:
+ case Kind::kConstant:
+ return true;
+
+ case Kind::kInStackLargeOffset:
+ case Kind::kConstantLargeValue:
+ return false;
+
+ default:
+ UNREACHABLE();
+ }
+ }
+
+ // Convert `kind` to a "surface" kind, i.e. one that doesn't include
+ // any value with a "large" qualifier.
+ // TODO: Introduce another enum type for the surface kind?
+ static Kind ConvertToSurfaceKind(Kind kind) {
+ switch (kind) {
+ case Kind::kNone:
+ case Kind::kInStack:
+ case Kind::kInRegister:
+ case Kind::kInFpuRegister:
+ case Kind::kConstant:
+ return kind;
+
+ case Kind::kInStackLargeOffset:
+ return Kind::kInStack;
+
+ case Kind::kConstantLargeValue:
+ return Kind::kConstant;
+
+ default:
+ UNREACHABLE();
+ }
+ }
+
+ DexRegisterLocation(Kind kind, int32_t value)
+ : kind_(kind), value_(value) {}
+
+ // Get the "surface" kind of the location, i.e., the one that doesn't
+ // include any value with a "large" qualifier.
+ Kind GetKind() const {
+ return ConvertToSurfaceKind(kind_);
+ }
+
+ // Get the value of the location.
+ int32_t GetValue() const { return value_; }
+
+ // Get the actual kind of the location.
+ Kind GetInternalKind() const { return kind_; }
+
+ private:
+ Kind kind_;
+ int32_t value_;
+};
+
/**
* Information on dex register values for a specific PC. The information is
* of the form:
* [location_kind, register_value]+.
- *
- * The location_kind for a Dex register can either be:
- * - kConstant: register_value holds the constant,
- * - kStack: register_value holds the stack offset,
- * - kRegister: register_value holds the physical register number.
- * - kFpuRegister: register_value holds the physical register number.
- * - kNone: the register has no location yet, meaning it has not been set.
+ * either on 1 or 5 bytes (see art::DexRegisterLocation::Kind).
*/
class DexRegisterMap {
public:
explicit DexRegisterMap(MemoryRegion region) : region_(region) {}
- enum LocationKind {
- kNone,
- kInStack,
- kInRegister,
- kInFpuRegister,
- kConstant
- };
+ // Short (compressed) location, fitting on one byte.
+ typedef uint8_t ShortLocation;
- static const char* PrettyDescriptor(LocationKind kind) {
- switch (kind) {
- case kNone:
- return "none";
- case kInStack:
- return "in stack";
- case kInRegister:
- return "in register";
- case kInFpuRegister:
- return "in fpu register";
- case kConstant:
- return "as constant";
+ void SetRegisterInfo(size_t offset, const DexRegisterLocation& dex_register_location) {
+ DexRegisterLocation::Kind kind = ComputeCompressedKind(dex_register_location);
+ int32_t value = dex_register_location.GetValue();
+ if (DexRegisterLocation::IsShortLocationKind(kind)) {
+ // Short location. Compress the kind and the value as a single byte.
+ if (kind == DexRegisterLocation::Kind::kInStack) {
+ // Instead of storing stack offsets expressed in bytes for
+ // short stack locations, store slot offsets. A stack offset
+ // is a multiple of 4 (kFrameSlotSize). This means that by
+ // dividing it by 4, we can fit values from the [0, 128)
+ // interval in a short stack location, and not just values
+ // from the [0, 32) interval.
+ DCHECK_EQ(value % kFrameSlotSize, 0);
+ value /= kFrameSlotSize;
+ }
+ DCHECK(IsUint<kValueBits>(value)) << value;
+ region_.StoreUnaligned<ShortLocation>(offset, MakeShortLocation(kind, value));
+ } else {
+ // Large location. Write the location on one byte and the value
+ // on 4 bytes.
+ DCHECK(!IsUint<kValueBits>(value)) << value;
+ if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) {
+ // Also divide large stack offsets by 4 for the sake of consistency.
+ DCHECK_EQ(value % kFrameSlotSize, 0);
+ value /= kFrameSlotSize;
+ }
+ // Data can be unaligned as the written Dex register locations can
+ // either be 1-byte or 5-byte wide. Use
+ // art::MemoryRegion::StoreUnaligned instead of
+ // art::MemoryRegion::Store to prevent unligned word accesses on ARM.
+ region_.StoreUnaligned<DexRegisterLocation::Kind>(offset, kind);
+ region_.StoreUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind), value);
}
- UNREACHABLE();
- return nullptr;
}
- LocationKind GetLocationKind(uint16_t register_index) const {
- return region_.Load<LocationKind>(
- kFixedSize + register_index * SingleEntrySize());
+ // Find the offset of the Dex register location number `dex_register_index`.
+ size_t FindLocationOffset(uint16_t dex_register_index) const {
+ size_t offset = kFixedSize;
+ // Skip the first `dex_register_index - 1` entries.
+ for (uint16_t i = 0; i < dex_register_index; ++i) {
+ // Read the first next byte and inspect its first 3 bits to decide
+ // whether it is a short or a large location.
+ DexRegisterLocation::Kind kind = ExtractKindAtOffset(offset);
+ if (DexRegisterLocation::IsShortLocationKind(kind)) {
+ // Short location. Skip the current byte.
+ offset += SingleShortEntrySize();
+ } else {
+ // Large location. Skip the 5 next bytes.
+ offset += SingleLargeEntrySize();
+ }
+ }
+ return offset;
}
- void SetRegisterInfo(uint16_t register_index, LocationKind kind, int32_t value) {
- size_t entry = kFixedSize + register_index * SingleEntrySize();
- region_.Store<LocationKind>(entry, kind);
- region_.Store<int32_t>(entry + sizeof(LocationKind), value);
+ // Get the surface kind.
+ DexRegisterLocation::Kind GetLocationKind(uint16_t dex_register_index) const {
+ return DexRegisterLocation::ConvertToSurfaceKind(GetLocationInternalKind(dex_register_index));
}
- int32_t GetValue(uint16_t register_index) const {
- return region_.Load<int32_t>(
- kFixedSize + sizeof(LocationKind) + register_index * SingleEntrySize());
+ // Get the internal kind.
+ DexRegisterLocation::Kind GetLocationInternalKind(uint16_t dex_register_index) const {
+ size_t offset = FindLocationOffset(dex_register_index);
+ return ExtractKindAtOffset(offset);
}
- int32_t GetStackOffsetInBytes(uint16_t register_index) const {
- DCHECK(GetLocationKind(register_index) == kInStack);
- // We currently encode the offset in bytes.
- return GetValue(register_index);
+ // TODO: Rename as GetDexRegisterLocation?
+ DexRegisterLocation GetLocationKindAndValue(uint16_t dex_register_index) const {
+ size_t offset = FindLocationOffset(dex_register_index);
+ // Read the first byte and inspect its first 3 bits to get the location.
+ ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset);
+ DexRegisterLocation::Kind kind = ExtractKindFromShortLocation(first_byte);
+ if (DexRegisterLocation::IsShortLocationKind(kind)) {
+ // Short location. Extract the value from the remaining 5 bits.
+ int32_t value = ExtractValueFromShortLocation(first_byte);
+ if (kind == DexRegisterLocation::Kind::kInStack) {
+ // Convert the stack slot (short) offset to a byte offset value.
+ value *= kFrameSlotSize;
+ }
+ return DexRegisterLocation(kind, value);
+ } else {
+ // Large location. Read the four next bytes to get the value.
+ int32_t value = region_.LoadUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind));
+ if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) {
+ // Convert the stack slot (large) offset to a byte offset value.
+ value *= kFrameSlotSize;
+ }
+ return DexRegisterLocation(kind, value);
+ }
}
- int32_t GetConstant(uint16_t register_index) const {
- DCHECK(GetLocationKind(register_index) == kConstant);
- return GetValue(register_index);
+ int32_t GetStackOffsetInBytes(uint16_t dex_register_index) const {
+ DexRegisterLocation location = GetLocationKindAndValue(dex_register_index);
+ DCHECK(location.GetKind() == DexRegisterLocation::Kind::kInStack);
+ // GetLocationKindAndValue returns the offset in bytes.
+ return location.GetValue();
}
- int32_t GetMachineRegister(uint16_t register_index) const {
- DCHECK(GetLocationKind(register_index) == kInRegister
- || GetLocationKind(register_index) == kInFpuRegister);
- return GetValue(register_index);
+ int32_t GetConstant(uint16_t dex_register_index) const {
+ DexRegisterLocation location = GetLocationKindAndValue(dex_register_index);
+ DCHECK(location.GetKind() == DexRegisterLocation::Kind::kConstant);
+ return location.GetValue();
}
- static size_t SingleEntrySize() {
- return sizeof(LocationKind) + sizeof(int32_t);
+ int32_t GetMachineRegister(uint16_t dex_register_index) const {
+ DexRegisterLocation location = GetLocationKindAndValue(dex_register_index);
+ DCHECK(location.GetInternalKind() == DexRegisterLocation::Kind::kInRegister
+ || location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegister)
+ << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind());
+ return location.GetValue();
+ }
+
+ // Compute the compressed kind of `location`.
+ static DexRegisterLocation::Kind ComputeCompressedKind(const DexRegisterLocation& location) {
+ switch (location.GetInternalKind()) {
+ case DexRegisterLocation::Kind::kNone:
+ DCHECK_EQ(location.GetValue(), 0);
+ return DexRegisterLocation::Kind::kNone;
+
+ case DexRegisterLocation::Kind::kInRegister:
+ DCHECK_GE(location.GetValue(), 0);
+ DCHECK_LT(location.GetValue(), 1 << DexRegisterMap::kValueBits);
+ return DexRegisterLocation::Kind::kInRegister;
+
+ case DexRegisterLocation::Kind::kInFpuRegister:
+ DCHECK_GE(location.GetValue(), 0);
+ DCHECK_LT(location.GetValue(), 1 << DexRegisterMap::kValueBits);
+ return DexRegisterLocation::Kind::kInFpuRegister;
+
+ case DexRegisterLocation::Kind::kInStack:
+ DCHECK_EQ(location.GetValue() % kFrameSlotSize, 0);
+ return IsUint<DexRegisterMap::kValueBits>(location.GetValue() / kFrameSlotSize)
+ ? DexRegisterLocation::Kind::kInStack
+ : DexRegisterLocation::Kind::kInStackLargeOffset;
+
+ case DexRegisterLocation::Kind::kConstant:
+ return IsUint<DexRegisterMap::kValueBits>(location.GetValue())
+ ? DexRegisterLocation::Kind::kConstant
+ : DexRegisterLocation::Kind::kConstantLargeValue;
+
+ default:
+ LOG(FATAL) << "Unexpected location kind"
+ << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind());
+ UNREACHABLE();
+ }
+ }
+
+ // Can `location` be turned into a short location?
+ static bool CanBeEncodedAsShortLocation(const DexRegisterLocation& location) {
+ switch (location.GetInternalKind()) {
+ case DexRegisterLocation::Kind::kNone:
+ case DexRegisterLocation::Kind::kInRegister:
+ case DexRegisterLocation::Kind::kInFpuRegister:
+ return true;
+
+ case DexRegisterLocation::Kind::kInStack:
+ DCHECK_EQ(location.GetValue() % kFrameSlotSize, 0);
+ return IsUint<kValueBits>(location.GetValue() / kFrameSlotSize);
+
+ case DexRegisterLocation::Kind::kConstant:
+ return IsUint<kValueBits>(location.GetValue());
+
+ default:
+ UNREACHABLE();
+ }
+ }
+
+ static size_t EntrySize(const DexRegisterLocation& location) {
+ return CanBeEncodedAsShortLocation(location)
+ ? DexRegisterMap::SingleShortEntrySize()
+ : DexRegisterMap::SingleLargeEntrySize();
+ }
+
+ static size_t SingleShortEntrySize() {
+ return sizeof(ShortLocation);
+ }
+
+ static size_t SingleLargeEntrySize() {
+ return sizeof(DexRegisterLocation::Kind) + sizeof(int32_t);
}
size_t Size() const {
@@ -153,7 +405,43 @@
static constexpr int kFixedSize = 0;
private:
+ // Width of the kind "field" in a short location, in bits.
+ static constexpr size_t kKindBits = 3;
+ // Width of the value "field" in a short location, in bits.
+ static constexpr size_t kValueBits = 5;
+
+ static constexpr uint8_t kKindMask = (1 << kKindBits) - 1;
+ static constexpr int32_t kValueMask = (1 << kValueBits) - 1;
+ static constexpr size_t kKindOffset = 0;
+ static constexpr size_t kValueOffset = kKindBits;
+
+ static ShortLocation MakeShortLocation(DexRegisterLocation::Kind kind, int32_t value) {
+ DCHECK(IsUint<kKindBits>(static_cast<uint8_t>(kind))) << static_cast<uint8_t>(kind);
+ DCHECK(IsUint<kValueBits>(value)) << value;
+ return (static_cast<uint8_t>(kind) & kKindMask) << kKindOffset
+ | (value & kValueMask) << kValueOffset;
+ }
+
+ static DexRegisterLocation::Kind ExtractKindFromShortLocation(ShortLocation location) {
+ uint8_t kind = (location >> kKindOffset) & kKindMask;
+ DCHECK_LE(kind, static_cast<uint8_t>(DexRegisterLocation::Kind::kLastLocationKind));
+ return static_cast<DexRegisterLocation::Kind>(kind);
+ }
+
+ static int32_t ExtractValueFromShortLocation(ShortLocation location) {
+ return (location >> kValueOffset) & kValueMask;
+ }
+
+ // Extract a location kind from the byte at position `offset`.
+ DexRegisterLocation::Kind ExtractKindAtOffset(size_t offset) const {
+ ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset);
+ return ExtractKindFromShortLocation(first_byte);
+ }
+
MemoryRegion region_;
+
+ friend class CodeInfo;
+ friend class StackMapStream;
};
/**
@@ -187,7 +475,7 @@
}
void SetNativePcOffset(uint32_t native_pc_offset) {
- return region_.Store<uint32_t>(kNativePcOffsetOffset, native_pc_offset);
+ region_.Store<uint32_t>(kNativePcOffsetOffset, native_pc_offset);
}
uint32_t GetDexRegisterMapOffset() const {
@@ -195,7 +483,7 @@
}
void SetDexRegisterMapOffset(uint32_t offset) {
- return region_.Store<uint32_t>(kDexRegisterMapOffsetOffset, offset);
+ region_.Store<uint32_t>(kDexRegisterMapOffsetOffset, offset);
}
uint32_t GetInlineDescriptorOffset() const {
@@ -203,7 +491,7 @@
}
void SetInlineDescriptorOffset(uint32_t offset) {
- return region_.Store<uint32_t>(kInlineDescriptorOffsetOffset, offset);
+ region_.Store<uint32_t>(kInlineDescriptorOffsetOffset, offset);
}
uint32_t GetRegisterMask() const {
@@ -238,9 +526,9 @@
&& region_.size() == other.region_.size();
}
- static size_t ComputeAlignedStackMapSize(size_t stack_mask_size) {
+ static size_t ComputeAlignedStackMapSize(size_t stack_map_size) {
// On ARM, the stack maps must be 4-byte aligned.
- return RoundUp(StackMap::kFixedSize + stack_mask_size, 4);
+ return RoundUp(StackMap::kFixedSize + stack_map_size, 4);
}
// Special (invalid) offset for the DexRegisterMapOffset field meaning
@@ -252,6 +540,8 @@
static constexpr uint32_t kNoInlineInfo = -1;
private:
+ // TODO: Instead of plain types such as "uint32_t", introduce
+ // typedefs (and document the memory layout of StackMap).
static constexpr int kDexPcOffset = 0;
static constexpr int kNativePcOffsetOffset = kDexPcOffset + sizeof(uint32_t);
static constexpr int kDexRegisterMapOffsetOffset = kNativePcOffsetOffset + sizeof(uint32_t);
@@ -317,11 +607,15 @@
return StackMap::ComputeAlignedStackMapSize(GetStackMaskSize());
}
+ uint32_t GetStackMapsOffset() const {
+ return kFixedSize;
+ }
+
DexRegisterMap GetDexRegisterMapOf(StackMap stack_map, uint32_t number_of_dex_registers) const {
DCHECK(stack_map.HasDexRegisterMap());
uint32_t offset = stack_map.GetDexRegisterMapOffset();
- return DexRegisterMap(region_.Subregion(offset,
- DexRegisterMap::kFixedSize + number_of_dex_registers * DexRegisterMap::SingleEntrySize()));
+ size_t size = ComputeDexRegisterMapSize(offset, number_of_dex_registers);
+ return DexRegisterMap(region_.Subregion(offset, size));
}
InlineInfo GetInlineInfoOf(StackMap stack_map) const {
@@ -356,6 +650,8 @@
}
private:
+ // TODO: Instead of plain types such as "uint32_t", introduce
+ // typedefs (and document the memory layout of CodeInfo).
static constexpr int kOverallSizeOffset = 0;
static constexpr int kNumberOfStackMapsOffset = kOverallSizeOffset + sizeof(uint32_t);
static constexpr int kStackMaskSizeOffset = kNumberOfStackMapsOffset + sizeof(uint32_t);
@@ -367,6 +663,33 @@
: region_.Subregion(kFixedSize, StackMapSize() * GetNumberOfStackMaps());
}
+ // Compute the size of a Dex register map starting at offset `origin` in
+ // `region_` and containing `number_of_dex_registers` locations.
+ size_t ComputeDexRegisterMapSize(uint32_t origin, uint32_t number_of_dex_registers) const {
+ // TODO: Ideally, we would like to use art::DexRegisterMap::Size or
+ // art::DexRegisterMap::FindLocationOffset, but the DexRegisterMap is not
+ // yet built. Try to factor common code.
+ size_t offset = origin + DexRegisterMap::kFixedSize;
+ // Skip the first `number_of_dex_registers - 1` entries.
+ for (uint16_t i = 0; i < number_of_dex_registers; ++i) {
+ // Read the first next byte and inspect its first 3 bits to decide
+ // whether it is a short or a large location.
+ DexRegisterMap::ShortLocation first_byte =
+ region_.LoadUnaligned<DexRegisterMap::ShortLocation>(offset);
+ DexRegisterLocation::Kind kind =
+ DexRegisterMap::ExtractKindFromShortLocation(first_byte);
+ if (DexRegisterLocation::IsShortLocationKind(kind)) {
+ // Short location. Skip the current byte.
+ offset += DexRegisterMap::SingleShortEntrySize();
+ } else {
+ // Large location. Skip the 5 next bytes.
+ offset += DexRegisterMap::SingleLargeEntrySize();
+ }
+ }
+ size_t size = offset - origin;
+ return size;
+ }
+
MemoryRegion region_;
friend class StackMapStream;
};