1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_STACK_MAP_H_ 18 #define ART_RUNTIME_STACK_MAP_H_ 19 20 #include "base/bit_vector.h" 21 #include "base/bit_utils.h" 22 #include "memory_region.h" 23 24 namespace art { 25 26 // Size of a frame slot, in bytes. This constant is a signed value, 27 // to please the compiler in arithmetic operations involving int32_t 28 // (signed) values. 29 static constexpr ssize_t kFrameSlotSize = 4; 30 31 // Size of Dex virtual registers. 32 static constexpr size_t kVRegSize = 4; 33 34 class CodeInfo; 35 36 /** 37 * Classes in the following file are wrapper on stack map information backed 38 * by a MemoryRegion. As such they read and write to the region, they don't have 39 * their own fields. 40 */ 41 42 /** 43 * Inline information for a specific PC. The information is of the form: 44 * [inlining_depth, [method_dex reference]+] 45 */ 46 class InlineInfo { 47 public: 48 explicit InlineInfo(MemoryRegion region) : region_(region) {} 49 50 uint8_t GetDepth() const { 51 return region_.LoadUnaligned<uint8_t>(kDepthOffset); 52 } 53 54 void SetDepth(uint8_t depth) { 55 region_.StoreUnaligned<uint8_t>(kDepthOffset, depth); 56 } 57 58 uint32_t GetMethodReferenceIndexAtDepth(uint8_t depth) const { 59 return region_.LoadUnaligned<uint32_t>(kFixedSize + depth * SingleEntrySize()); 60 } 61 62 void SetMethodReferenceIndexAtDepth(uint8_t depth, uint32_t index) { 63 region_.StoreUnaligned<uint32_t>(kFixedSize + depth * SingleEntrySize(), index); 64 } 65 66 static size_t SingleEntrySize() { 67 return sizeof(uint32_t); 68 } 69 70 private: 71 // TODO: Instead of plain types such as "uint8_t", introduce 72 // typedefs (and document the memory layout of InlineInfo). 73 static constexpr int kDepthOffset = 0; 74 static constexpr int kFixedSize = kDepthOffset + sizeof(uint8_t); 75 76 MemoryRegion region_; 77 78 friend class CodeInfo; 79 friend class StackMap; 80 friend class StackMapStream; 81 }; 82 83 // Dex register location container used by DexRegisterMap and StackMapStream. 84 class DexRegisterLocation { 85 public: 86 /* 87 * The location kind used to populate the Dex register information in a 88 * StackMapStream can either be: 89 * - kNone: the register has no location yet, meaning it has not been set; 90 * - kConstant: value holds the constant; 91 * - kStack: value holds the stack offset; 92 * - kRegister: value holds the physical register number; 93 * - kFpuRegister: value holds the physical register number. 94 * 95 * In addition, DexRegisterMap also uses these values: 96 * - kInStackLargeOffset: value holds a "large" stack offset (greater than 97 * or equal to 128 bytes); 98 * - kConstantLargeValue: value holds a "large" constant (lower than 0, or 99 * or greater than or equal to 32). 100 */ 101 enum class Kind : uint8_t { 102 // Short location kinds, for entries fitting on one byte (3 bits 103 // for the kind, 5 bits for the value) in a DexRegisterMap. 104 kNone = 0, // 0b000 105 kInStack = 1, // 0b001 106 kInRegister = 2, // 0b010 107 kInFpuRegister = 3, // 0b011 108 kConstant = 4, // 0b100 109 110 // Large location kinds, requiring a 5-byte encoding (1 byte for the 111 // kind, 4 bytes for the value). 112 113 // Stack location at a large offset, meaning that the offset value 114 // divided by the stack frame slot size (4 bytes) cannot fit on a 115 // 5-bit unsigned integer (i.e., this offset value is greater than 116 // or equal to 2^5 * 4 = 128 bytes). 117 kInStackLargeOffset = 5, // 0b101 118 119 // Large constant, that cannot fit on a 5-bit signed integer (i.e., 120 // lower than 0, or greater than or equal to 2^5 = 32). 121 kConstantLargeValue = 6, // 0b110 122 123 kLastLocationKind = kConstantLargeValue 124 }; 125 126 static_assert( 127 sizeof(Kind) == 1u, 128 "art::DexRegisterLocation::Kind has a size different from one byte."); 129 130 static const char* PrettyDescriptor(Kind kind) { 131 switch (kind) { 132 case Kind::kNone: 133 return "none"; 134 case Kind::kInStack: 135 return "in stack"; 136 case Kind::kInRegister: 137 return "in register"; 138 case Kind::kInFpuRegister: 139 return "in fpu register"; 140 case Kind::kConstant: 141 return "as constant"; 142 case Kind::kInStackLargeOffset: 143 return "in stack (large offset)"; 144 case Kind::kConstantLargeValue: 145 return "as constant (large value)"; 146 default: 147 UNREACHABLE(); 148 } 149 } 150 151 static bool IsShortLocationKind(Kind kind) { 152 switch (kind) { 153 case Kind::kNone: 154 case Kind::kInStack: 155 case Kind::kInRegister: 156 case Kind::kInFpuRegister: 157 case Kind::kConstant: 158 return true; 159 160 case Kind::kInStackLargeOffset: 161 case Kind::kConstantLargeValue: 162 return false; 163 164 default: 165 UNREACHABLE(); 166 } 167 } 168 169 // Convert `kind` to a "surface" kind, i.e. one that doesn't include 170 // any value with a "large" qualifier. 171 // TODO: Introduce another enum type for the surface kind? 172 static Kind ConvertToSurfaceKind(Kind kind) { 173 switch (kind) { 174 case Kind::kNone: 175 case Kind::kInStack: 176 case Kind::kInRegister: 177 case Kind::kInFpuRegister: 178 case Kind::kConstant: 179 return kind; 180 181 case Kind::kInStackLargeOffset: 182 return Kind::kInStack; 183 184 case Kind::kConstantLargeValue: 185 return Kind::kConstant; 186 187 default: 188 UNREACHABLE(); 189 } 190 } 191 192 // Required by art::StackMapStream::LocationCatalogEntriesIndices. 193 DexRegisterLocation() : kind_(Kind::kNone), value_(0) {} 194 195 DexRegisterLocation(Kind kind, int32_t value) : kind_(kind), value_(value) {} 196 197 static DexRegisterLocation None() { 198 return DexRegisterLocation(Kind::kNone, 0); 199 } 200 201 // Get the "surface" kind of the location, i.e., the one that doesn't 202 // include any value with a "large" qualifier. 203 Kind GetKind() const { 204 return ConvertToSurfaceKind(kind_); 205 } 206 207 // Get the value of the location. 208 int32_t GetValue() const { return value_; } 209 210 // Get the actual kind of the location. 211 Kind GetInternalKind() const { return kind_; } 212 213 bool operator==(DexRegisterLocation other) const { 214 return kind_ == other.kind_ && value_ == other.value_; 215 } 216 217 bool operator!=(DexRegisterLocation other) const { 218 return !(*this == other); 219 } 220 221 private: 222 Kind kind_; 223 int32_t value_; 224 225 friend class DexRegisterLocationHashFn; 226 }; 227 228 /** 229 * Store information on unique Dex register locations used in a method. 230 * The information is of the form: 231 * [DexRegisterLocation+]. 232 * DexRegisterLocations are either 1- or 5-byte wide (see art::DexRegisterLocation::Kind). 233 */ 234 class DexRegisterLocationCatalog { 235 public: 236 explicit DexRegisterLocationCatalog(MemoryRegion region) : region_(region) {} 237 238 // Short (compressed) location, fitting on one byte. 239 typedef uint8_t ShortLocation; 240 241 void SetRegisterInfo(size_t offset, const DexRegisterLocation& dex_register_location) { 242 DexRegisterLocation::Kind kind = ComputeCompressedKind(dex_register_location); 243 int32_t value = dex_register_location.GetValue(); 244 if (DexRegisterLocation::IsShortLocationKind(kind)) { 245 // Short location. Compress the kind and the value as a single byte. 246 if (kind == DexRegisterLocation::Kind::kInStack) { 247 // Instead of storing stack offsets expressed in bytes for 248 // short stack locations, store slot offsets. A stack offset 249 // is a multiple of 4 (kFrameSlotSize). This means that by 250 // dividing it by 4, we can fit values from the [0, 128) 251 // interval in a short stack location, and not just values 252 // from the [0, 32) interval. 253 DCHECK_EQ(value % kFrameSlotSize, 0); 254 value /= kFrameSlotSize; 255 } 256 DCHECK(IsShortValue(value)) << value; 257 region_.StoreUnaligned<ShortLocation>(offset, MakeShortLocation(kind, value)); 258 } else { 259 // Large location. Write the location on one byte and the value 260 // on 4 bytes. 261 DCHECK(!IsShortValue(value)) << value; 262 if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) { 263 // Also divide large stack offsets by 4 for the sake of consistency. 264 DCHECK_EQ(value % kFrameSlotSize, 0); 265 value /= kFrameSlotSize; 266 } 267 // Data can be unaligned as the written Dex register locations can 268 // either be 1-byte or 5-byte wide. Use 269 // art::MemoryRegion::StoreUnaligned instead of 270 // art::MemoryRegion::Store to prevent unligned word accesses on ARM. 271 region_.StoreUnaligned<DexRegisterLocation::Kind>(offset, kind); 272 region_.StoreUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind), value); 273 } 274 } 275 276 // Find the offset of the location catalog entry number `location_catalog_entry_index`. 277 size_t FindLocationOffset(size_t location_catalog_entry_index) const { 278 size_t offset = kFixedSize; 279 // Skip the first `location_catalog_entry_index - 1` entries. 280 for (uint16_t i = 0; i < location_catalog_entry_index; ++i) { 281 // Read the first next byte and inspect its first 3 bits to decide 282 // whether it is a short or a large location. 283 DexRegisterLocation::Kind kind = ExtractKindAtOffset(offset); 284 if (DexRegisterLocation::IsShortLocationKind(kind)) { 285 // Short location. Skip the current byte. 286 offset += SingleShortEntrySize(); 287 } else { 288 // Large location. Skip the 5 next bytes. 289 offset += SingleLargeEntrySize(); 290 } 291 } 292 return offset; 293 } 294 295 // Get the internal kind of entry at `location_catalog_entry_index`. 296 DexRegisterLocation::Kind GetLocationInternalKind(size_t location_catalog_entry_index) const { 297 if (location_catalog_entry_index == kNoLocationEntryIndex) { 298 return DexRegisterLocation::Kind::kNone; 299 } 300 return ExtractKindAtOffset(FindLocationOffset(location_catalog_entry_index)); 301 } 302 303 // Get the (surface) kind and value of entry at `location_catalog_entry_index`. 304 DexRegisterLocation GetDexRegisterLocation(size_t location_catalog_entry_index) const { 305 if (location_catalog_entry_index == kNoLocationEntryIndex) { 306 return DexRegisterLocation::None(); 307 } 308 size_t offset = FindLocationOffset(location_catalog_entry_index); 309 // Read the first byte and inspect its first 3 bits to get the location. 310 ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset); 311 DexRegisterLocation::Kind kind = ExtractKindFromShortLocation(first_byte); 312 if (DexRegisterLocation::IsShortLocationKind(kind)) { 313 // Short location. Extract the value from the remaining 5 bits. 314 int32_t value = ExtractValueFromShortLocation(first_byte); 315 if (kind == DexRegisterLocation::Kind::kInStack) { 316 // Convert the stack slot (short) offset to a byte offset value. 317 value *= kFrameSlotSize; 318 } 319 return DexRegisterLocation(kind, value); 320 } else { 321 // Large location. Read the four next bytes to get the value. 322 int32_t value = region_.LoadUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind)); 323 if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) { 324 // Convert the stack slot (large) offset to a byte offset value. 325 value *= kFrameSlotSize; 326 } 327 return DexRegisterLocation(kind, value); 328 } 329 } 330 331 // Compute the compressed kind of `location`. 332 static DexRegisterLocation::Kind ComputeCompressedKind(const DexRegisterLocation& location) { 333 switch (location.GetInternalKind()) { 334 case DexRegisterLocation::Kind::kNone: 335 DCHECK_EQ(location.GetValue(), 0); 336 return DexRegisterLocation::Kind::kNone; 337 338 case DexRegisterLocation::Kind::kInRegister: 339 DCHECK_GE(location.GetValue(), 0); 340 DCHECK_LT(location.GetValue(), 1 << kValueBits); 341 return DexRegisterLocation::Kind::kInRegister; 342 343 case DexRegisterLocation::Kind::kInFpuRegister: 344 DCHECK_GE(location.GetValue(), 0); 345 DCHECK_LT(location.GetValue(), 1 << kValueBits); 346 return DexRegisterLocation::Kind::kInFpuRegister; 347 348 case DexRegisterLocation::Kind::kInStack: 349 return IsShortStackOffsetValue(location.GetValue()) 350 ? DexRegisterLocation::Kind::kInStack 351 : DexRegisterLocation::Kind::kInStackLargeOffset; 352 353 case DexRegisterLocation::Kind::kConstant: 354 return IsShortConstantValue(location.GetValue()) 355 ? DexRegisterLocation::Kind::kConstant 356 : DexRegisterLocation::Kind::kConstantLargeValue; 357 358 default: 359 LOG(FATAL) << "Unexpected location kind" 360 << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind()); 361 UNREACHABLE(); 362 } 363 } 364 365 // Can `location` be turned into a short location? 366 static bool CanBeEncodedAsShortLocation(const DexRegisterLocation& location) { 367 switch (location.GetInternalKind()) { 368 case DexRegisterLocation::Kind::kNone: 369 case DexRegisterLocation::Kind::kInRegister: 370 case DexRegisterLocation::Kind::kInFpuRegister: 371 return true; 372 373 case DexRegisterLocation::Kind::kInStack: 374 return IsShortStackOffsetValue(location.GetValue()); 375 376 case DexRegisterLocation::Kind::kConstant: 377 return IsShortConstantValue(location.GetValue()); 378 379 default: 380 UNREACHABLE(); 381 } 382 } 383 384 static size_t EntrySize(const DexRegisterLocation& location) { 385 return CanBeEncodedAsShortLocation(location) ? SingleShortEntrySize() : SingleLargeEntrySize(); 386 } 387 388 static size_t SingleShortEntrySize() { 389 return sizeof(ShortLocation); 390 } 391 392 static size_t SingleLargeEntrySize() { 393 return sizeof(DexRegisterLocation::Kind) + sizeof(int32_t); 394 } 395 396 size_t Size() const { 397 return region_.size(); 398 } 399 400 // Special (invalid) Dex register location catalog entry index meaning 401 // that there is no location for a given Dex register (i.e., it is 402 // mapped to a DexRegisterLocation::Kind::kNone location). 403 static constexpr size_t kNoLocationEntryIndex = -1; 404 405 private: 406 static constexpr int kFixedSize = 0; 407 408 // Width of the kind "field" in a short location, in bits. 409 static constexpr size_t kKindBits = 3; 410 // Width of the value "field" in a short location, in bits. 411 static constexpr size_t kValueBits = 5; 412 413 static constexpr uint8_t kKindMask = (1 << kKindBits) - 1; 414 static constexpr int32_t kValueMask = (1 << kValueBits) - 1; 415 static constexpr size_t kKindOffset = 0; 416 static constexpr size_t kValueOffset = kKindBits; 417 418 static bool IsShortStackOffsetValue(int32_t value) { 419 DCHECK_EQ(value % kFrameSlotSize, 0); 420 return IsShortValue(value / kFrameSlotSize); 421 } 422 423 static bool IsShortConstantValue(int32_t value) { 424 return IsShortValue(value); 425 } 426 427 static bool IsShortValue(int32_t value) { 428 return IsUint<kValueBits>(value); 429 } 430 431 static ShortLocation MakeShortLocation(DexRegisterLocation::Kind kind, int32_t value) { 432 uint8_t kind_integer_value = static_cast<uint8_t>(kind); 433 DCHECK(IsUint<kKindBits>(kind_integer_value)) << kind_integer_value; 434 DCHECK(IsShortValue(value)) << value; 435 return (kind_integer_value & kKindMask) << kKindOffset 436 | (value & kValueMask) << kValueOffset; 437 } 438 439 static DexRegisterLocation::Kind ExtractKindFromShortLocation(ShortLocation location) { 440 uint8_t kind = (location >> kKindOffset) & kKindMask; 441 DCHECK_LE(kind, static_cast<uint8_t>(DexRegisterLocation::Kind::kLastLocationKind)); 442 // We do not encode kNone locations in the stack map. 443 DCHECK_NE(kind, static_cast<uint8_t>(DexRegisterLocation::Kind::kNone)); 444 return static_cast<DexRegisterLocation::Kind>(kind); 445 } 446 447 static int32_t ExtractValueFromShortLocation(ShortLocation location) { 448 return (location >> kValueOffset) & kValueMask; 449 } 450 451 // Extract a location kind from the byte at position `offset`. 452 DexRegisterLocation::Kind ExtractKindAtOffset(size_t offset) const { 453 ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset); 454 return ExtractKindFromShortLocation(first_byte); 455 } 456 457 MemoryRegion region_; 458 459 friend class CodeInfo; 460 friend class StackMapStream; 461 }; 462 463 /* Information on Dex register locations for a specific PC, mapping a 464 * stack map's Dex register to a location entry in a DexRegisterLocationCatalog. 465 * The information is of the form: 466 * [live_bit_mask, entries*] 467 * where entries are concatenated unsigned integer values encoded on a number 468 * of bits (fixed per DexRegisterMap instances of a CodeInfo object) depending 469 * on the number of entries in the Dex register location catalog 470 * (see DexRegisterMap::SingleEntrySizeInBits). The map is 1-byte aligned. 471 */ 472 class DexRegisterMap { 473 public: 474 explicit DexRegisterMap(MemoryRegion region) : region_(region) {} 475 476 // Get the surface kind of Dex register `dex_register_number`. 477 DexRegisterLocation::Kind GetLocationKind(uint16_t dex_register_number, 478 uint16_t number_of_dex_registers, 479 const CodeInfo& code_info) const { 480 return DexRegisterLocation::ConvertToSurfaceKind( 481 GetLocationInternalKind(dex_register_number, number_of_dex_registers, code_info)); 482 } 483 484 // Get the internal kind of Dex register `dex_register_number`. 485 DexRegisterLocation::Kind GetLocationInternalKind(uint16_t dex_register_number, 486 uint16_t number_of_dex_registers, 487 const CodeInfo& code_info) const; 488 489 // Get the Dex register location `dex_register_number`. 490 DexRegisterLocation GetDexRegisterLocation(uint16_t dex_register_number, 491 uint16_t number_of_dex_registers, 492 const CodeInfo& code_info) const; 493 494 int32_t GetStackOffsetInBytes(uint16_t dex_register_number, 495 uint16_t number_of_dex_registers, 496 const CodeInfo& code_info) const { 497 DexRegisterLocation location = 498 GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info); 499 DCHECK(location.GetKind() == DexRegisterLocation::Kind::kInStack); 500 // GetDexRegisterLocation returns the offset in bytes. 501 return location.GetValue(); 502 } 503 504 int32_t GetConstant(uint16_t dex_register_number, 505 uint16_t number_of_dex_registers, 506 const CodeInfo& code_info) const { 507 DexRegisterLocation location = 508 GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info); 509 DCHECK(location.GetKind() == DexRegisterLocation::Kind::kConstant); 510 return location.GetValue(); 511 } 512 513 int32_t GetMachineRegister(uint16_t dex_register_number, 514 uint16_t number_of_dex_registers, 515 const CodeInfo& code_info) const { 516 DexRegisterLocation location = 517 GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info); 518 DCHECK(location.GetInternalKind() == DexRegisterLocation::Kind::kInRegister 519 || location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegister) 520 << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind()); 521 return location.GetValue(); 522 } 523 524 // Get the index of the entry in the Dex register location catalog 525 // corresponding to `dex_register_number`. 526 size_t GetLocationCatalogEntryIndex(uint16_t dex_register_number, 527 uint16_t number_of_dex_registers, 528 size_t number_of_location_catalog_entries) const { 529 if (!IsDexRegisterLive(dex_register_number)) { 530 return DexRegisterLocationCatalog::kNoLocationEntryIndex; 531 } 532 533 if (number_of_location_catalog_entries == 1) { 534 // We do not allocate space for location maps in the case of a 535 // single-entry location catalog, as it is useless. The only valid 536 // entry index is 0; 537 return 0; 538 } 539 540 // The bit offset of the beginning of the map locations. 541 size_t map_locations_offset_in_bits = 542 GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte; 543 size_t index_in_dex_register_map = GetIndexInDexRegisterMap(dex_register_number); 544 DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers)); 545 // The bit size of an entry. 546 size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries); 547 // The bit offset where `index_in_dex_register_map` is located. 548 size_t entry_offset_in_bits = 549 map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits; 550 size_t location_catalog_entry_index = 551 region_.LoadBits(entry_offset_in_bits, map_entry_size_in_bits); 552 DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries); 553 return location_catalog_entry_index; 554 } 555 556 // Map entry at `index_in_dex_register_map` to `location_catalog_entry_index`. 557 void SetLocationCatalogEntryIndex(size_t index_in_dex_register_map, 558 size_t location_catalog_entry_index, 559 uint16_t number_of_dex_registers, 560 size_t number_of_location_catalog_entries) { 561 DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers)); 562 DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries); 563 564 if (number_of_location_catalog_entries == 1) { 565 // We do not allocate space for location maps in the case of a 566 // single-entry location catalog, as it is useless. 567 return; 568 } 569 570 // The bit offset of the beginning of the map locations. 571 size_t map_locations_offset_in_bits = 572 GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte; 573 // The bit size of an entry. 574 size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries); 575 // The bit offset where `index_in_dex_register_map` is located. 576 size_t entry_offset_in_bits = 577 map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits; 578 region_.StoreBits(entry_offset_in_bits, location_catalog_entry_index, map_entry_size_in_bits); 579 } 580 581 void SetLiveBitMask(uint16_t number_of_dex_registers, 582 const BitVector& live_dex_registers_mask) { 583 size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte; 584 for (uint16_t i = 0; i < number_of_dex_registers; ++i) { 585 region_.StoreBit(live_bit_mask_offset_in_bits + i, live_dex_registers_mask.IsBitSet(i)); 586 } 587 } 588 589 bool IsDexRegisterLive(uint16_t dex_register_number) const { 590 size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte; 591 return region_.LoadBit(live_bit_mask_offset_in_bits + dex_register_number); 592 } 593 594 size_t GetNumberOfLiveDexRegisters(uint16_t number_of_dex_registers) const { 595 size_t number_of_live_dex_registers = 0; 596 for (size_t i = 0; i < number_of_dex_registers; ++i) { 597 if (IsDexRegisterLive(i)) { 598 ++number_of_live_dex_registers; 599 } 600 } 601 return number_of_live_dex_registers; 602 } 603 604 static size_t GetLiveBitMaskOffset() { 605 return kFixedSize; 606 } 607 608 // Compute the size of the live register bit mask (in bytes), for a 609 // method having `number_of_dex_registers` Dex registers. 610 static size_t GetLiveBitMaskSize(uint16_t number_of_dex_registers) { 611 return RoundUp(number_of_dex_registers, kBitsPerByte) / kBitsPerByte; 612 } 613 614 static size_t GetLocationMappingDataOffset(uint16_t number_of_dex_registers) { 615 return GetLiveBitMaskOffset() + GetLiveBitMaskSize(number_of_dex_registers); 616 } 617 618 size_t GetLocationMappingDataSize(uint16_t number_of_dex_registers, 619 size_t number_of_location_catalog_entries) const { 620 size_t location_mapping_data_size_in_bits = 621 GetNumberOfLiveDexRegisters(number_of_dex_registers) 622 * SingleEntrySizeInBits(number_of_location_catalog_entries); 623 return RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte; 624 } 625 626 // Return the size of a map entry in bits. Note that if 627 // `number_of_location_catalog_entries` equals 1, this function returns 0, 628 // which is fine, as there is no need to allocate a map for a 629 // single-entry location catalog; the only valid location catalog entry index 630 // for a live register in this case is 0 and there is no need to 631 // store it. 632 static size_t SingleEntrySizeInBits(size_t number_of_location_catalog_entries) { 633 // Handle the case of 0, as we cannot pass 0 to art::WhichPowerOf2. 634 return number_of_location_catalog_entries == 0 635 ? 0u 636 : WhichPowerOf2(RoundUpToPowerOfTwo(number_of_location_catalog_entries)); 637 } 638 639 // Return the size of the DexRegisterMap object, in bytes. 640 size_t Size() const { 641 return region_.size(); 642 } 643 644 private: 645 // Return the index in the Dex register map corresponding to the Dex 646 // register number `dex_register_number`. 647 size_t GetIndexInDexRegisterMap(uint16_t dex_register_number) const { 648 if (!IsDexRegisterLive(dex_register_number)) { 649 return kInvalidIndexInDexRegisterMap; 650 } 651 return GetNumberOfLiveDexRegisters(dex_register_number); 652 } 653 654 // Special (invalid) Dex register map entry index meaning that there 655 // is no index in the map for a given Dex register (i.e., it must 656 // have been mapped to a DexRegisterLocation::Kind::kNone location). 657 static constexpr size_t kInvalidIndexInDexRegisterMap = -1; 658 659 static constexpr int kFixedSize = 0; 660 661 MemoryRegion region_; 662 663 friend class CodeInfo; 664 friend class StackMapStream; 665 }; 666 667 /** 668 * A Stack Map holds compilation information for a specific PC necessary for: 669 * - Mapping it to a dex PC, 670 * - Knowing which stack entries are objects, 671 * - Knowing which registers hold objects, 672 * - Knowing the inlining information, 673 * - Knowing the values of dex registers. 674 * 675 * The information is of the form: 676 * [dex_pc, native_pc_offset, dex_register_map_offset, inlining_info_offset, register_mask, 677 * stack_mask]. 678 * 679 * Note that register_mask is fixed size, but stack_mask is variable size, depending on the 680 * stack size of a method. 681 */ 682 class StackMap { 683 public: 684 StackMap() {} 685 686 explicit StackMap(MemoryRegion region) : region_(region) {} 687 688 bool IsValid() const { return region_.pointer() != nullptr; } 689 690 uint32_t GetDexPc(const CodeInfo& info) const; 691 692 void SetDexPc(const CodeInfo& info, uint32_t dex_pc); 693 694 uint32_t GetNativePcOffset(const CodeInfo& info) const; 695 696 void SetNativePcOffset(const CodeInfo& info, uint32_t native_pc_offset); 697 698 uint32_t GetDexRegisterMapOffset(const CodeInfo& info) const; 699 700 void SetDexRegisterMapOffset(const CodeInfo& info, uint32_t offset); 701 702 uint32_t GetInlineDescriptorOffset(const CodeInfo& info) const; 703 704 void SetInlineDescriptorOffset(const CodeInfo& info, uint32_t offset); 705 706 uint32_t GetRegisterMask(const CodeInfo& info) const; 707 708 void SetRegisterMask(const CodeInfo& info, uint32_t mask); 709 710 MemoryRegion GetStackMask(const CodeInfo& info) const; 711 712 void SetStackMask(const CodeInfo& info, const BitVector& sp_map) { 713 MemoryRegion region = GetStackMask(info); 714 for (size_t i = 0; i < region.size_in_bits(); i++) { 715 region.StoreBit(i, sp_map.IsBitSet(i)); 716 } 717 } 718 719 bool HasDexRegisterMap(const CodeInfo& info) const { 720 return GetDexRegisterMapOffset(info) != kNoDexRegisterMap; 721 } 722 723 bool HasInlineInfo(const CodeInfo& info) const { 724 return GetInlineDescriptorOffset(info) != kNoInlineInfo; 725 } 726 727 bool Equals(const StackMap& other) const { 728 return region_.pointer() == other.region_.pointer() 729 && region_.size() == other.region_.size(); 730 } 731 732 static size_t ComputeStackMapSize(size_t stack_mask_size, 733 size_t inline_info_size, 734 size_t dex_register_map_size, 735 size_t dex_pc_max, 736 size_t native_pc_max, 737 size_t register_mask_max); 738 739 // Special (invalid) offset for the DexRegisterMapOffset field meaning 740 // that there is no Dex register map for this stack map. 741 static constexpr uint32_t kNoDexRegisterMap = -1; 742 743 // Special (invalid) offset for the InlineDescriptorOffset field meaning 744 // that there is no inline info for this stack map. 745 static constexpr uint32_t kNoInlineInfo = -1; 746 747 private: 748 static size_t ComputeStackMapSizeInternal(size_t stack_mask_size, 749 size_t number_of_bytes_for_inline_info, 750 size_t number_of_bytes_for_dex_map, 751 size_t number_of_bytes_for_dex_pc, 752 size_t number_of_bytes_for_native_pc, 753 size_t number_of_bytes_for_register_mask); 754 755 // TODO: Instead of plain types such as "uint32_t", introduce 756 // typedefs (and document the memory layout of StackMap). 757 static constexpr int kRegisterMaskOffset = 0; 758 static constexpr int kFixedSize = 0; 759 760 MemoryRegion region_; 761 762 friend class CodeInfo; 763 friend class StackMapStream; 764 }; 765 766 767 /** 768 * Wrapper around all compiler information collected for a method. 769 * The information is of the form: 770 * [overall_size, number_of_location_catalog_entries, number_of_stack_maps, stack_mask_size, 771 * DexRegisterLocationCatalog+, StackMap+, DexRegisterMap+, InlineInfo*]. 772 */ 773 class CodeInfo { 774 public: 775 explicit CodeInfo(MemoryRegion region) : region_(region) {} 776 777 explicit CodeInfo(const void* data) { 778 uint32_t size = reinterpret_cast<const uint32_t*>(data)[0]; 779 region_ = MemoryRegion(const_cast<void*>(data), size); 780 } 781 782 static size_t EncodingSizeInBytes(size_t max_element) { 783 DCHECK(IsUint<32>(max_element)); 784 return (max_element == 0) ? 0 785 : IsUint<8>(max_element) ? 1 786 : IsUint<16>(max_element) ? 2 787 : IsUint<24>(max_element) ? 3 788 : 4; 789 } 790 791 void SetEncoding(size_t inline_info_size, 792 size_t dex_register_map_size, 793 size_t dex_pc_max, 794 size_t native_pc_max, 795 size_t register_mask_max) { 796 if (inline_info_size != 0) { 797 region_.StoreBit(kHasInlineInfoBitOffset, 1); 798 // + 1 to also encode kNoInlineInfo: if an inline info offset 799 // is at 0xFF, we want to overflow to a larger encoding, because it will 800 // conflict with kNoInlineInfo. 801 // The offset is relative to the dex register map. TODO: Change this. 802 SetEncodingAt(kInlineInfoBitOffset, 803 EncodingSizeInBytes(dex_register_map_size + inline_info_size + 1)); 804 } else { 805 region_.StoreBit(kHasInlineInfoBitOffset, 0); 806 SetEncodingAt(kInlineInfoBitOffset, 0); 807 } 808 // + 1 to also encode kNoDexRegisterMap: if a dex register map offset 809 // is at 0xFF, we want to overflow to a larger encoding, because it will 810 // conflict with kNoDexRegisterMap. 811 SetEncodingAt(kDexRegisterMapBitOffset, EncodingSizeInBytes(dex_register_map_size + 1)); 812 SetEncodingAt(kDexPcBitOffset, EncodingSizeInBytes(dex_pc_max)); 813 SetEncodingAt(kNativePcBitOffset, EncodingSizeInBytes(native_pc_max)); 814 SetEncodingAt(kRegisterMaskBitOffset, EncodingSizeInBytes(register_mask_max)); 815 } 816 817 void SetEncodingAt(size_t bit_offset, size_t number_of_bytes) { 818 // We encode the number of bytes needed for writing a value on 3 bits, 819 // for values that we know are maximum 32bits. 820 region_.StoreBit(bit_offset, (number_of_bytes & 1)); 821 region_.StoreBit(bit_offset + 1, (number_of_bytes & 2)); 822 region_.StoreBit(bit_offset + 2, (number_of_bytes & 4)); 823 } 824 825 size_t GetNumberOfBytesForEncoding(size_t bit_offset) const { 826 return region_.LoadBit(bit_offset) 827 + (region_.LoadBit(bit_offset + 1) << 1) 828 + (region_.LoadBit(bit_offset + 2) << 2); 829 } 830 831 bool HasInlineInfo() const { 832 return region_.LoadBit(kHasInlineInfoBitOffset); 833 } 834 835 size_t NumberOfBytesForInlineInfo() const { 836 return GetNumberOfBytesForEncoding(kInlineInfoBitOffset); 837 } 838 839 size_t NumberOfBytesForDexRegisterMap() const { 840 return GetNumberOfBytesForEncoding(kDexRegisterMapBitOffset); 841 } 842 843 size_t NumberOfBytesForRegisterMask() const { 844 return GetNumberOfBytesForEncoding(kRegisterMaskBitOffset); 845 } 846 847 size_t NumberOfBytesForNativePc() const { 848 return GetNumberOfBytesForEncoding(kNativePcBitOffset); 849 } 850 851 size_t NumberOfBytesForDexPc() const { 852 return GetNumberOfBytesForEncoding(kDexPcBitOffset); 853 } 854 855 size_t ComputeStackMapRegisterMaskOffset() const { 856 return StackMap::kRegisterMaskOffset; 857 } 858 859 size_t ComputeStackMapStackMaskOffset() const { 860 return ComputeStackMapRegisterMaskOffset() 861 + (NumberOfBytesForRegisterMask() * sizeof(uint8_t)); 862 } 863 864 size_t ComputeStackMapDexPcOffset() const { 865 return ComputeStackMapStackMaskOffset() + GetStackMaskSize(); 866 } 867 868 size_t ComputeStackMapNativePcOffset() const { 869 return ComputeStackMapDexPcOffset() 870 + (NumberOfBytesForDexPc() * sizeof(uint8_t)); 871 } 872 873 size_t ComputeStackMapDexRegisterMapOffset() const { 874 return ComputeStackMapNativePcOffset() 875 + (NumberOfBytesForNativePc() * sizeof(uint8_t)); 876 } 877 878 size_t ComputeStackMapInlineInfoOffset() const { 879 CHECK(HasInlineInfo()); 880 return ComputeStackMapDexRegisterMapOffset() 881 + (NumberOfBytesForDexRegisterMap() * sizeof(uint8_t)); 882 } 883 884 uint32_t GetDexRegisterLocationCatalogOffset() const { 885 return kFixedSize; 886 } 887 888 DexRegisterLocationCatalog GetDexRegisterLocationCatalog() const { 889 return DexRegisterLocationCatalog(region_.Subregion( 890 GetDexRegisterLocationCatalogOffset(), 891 GetDexRegisterLocationCatalogSize())); 892 } 893 894 StackMap GetStackMapAt(size_t i) const { 895 size_t size = StackMapSize(); 896 return StackMap(GetStackMaps().Subregion(i * size, size)); 897 } 898 899 uint32_t GetOverallSize() const { 900 return region_.LoadUnaligned<uint32_t>(kOverallSizeOffset); 901 } 902 903 void SetOverallSize(uint32_t size) { 904 region_.StoreUnaligned<uint32_t>(kOverallSizeOffset, size); 905 } 906 907 uint32_t GetNumberOfDexRegisterLocationCatalogEntries() const { 908 return region_.LoadUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset); 909 } 910 911 void SetNumberOfDexRegisterLocationCatalogEntries(uint32_t num_entries) { 912 region_.StoreUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset, num_entries); 913 } 914 915 uint32_t GetDexRegisterLocationCatalogSize() const { 916 return ComputeDexRegisterLocationCatalogSize(GetDexRegisterLocationCatalogOffset(), 917 GetNumberOfDexRegisterLocationCatalogEntries()); 918 } 919 920 uint32_t GetStackMaskSize() const { 921 return region_.LoadUnaligned<uint32_t>(kStackMaskSizeOffset); 922 } 923 924 void SetStackMaskSize(uint32_t size) { 925 region_.StoreUnaligned<uint32_t>(kStackMaskSizeOffset, size); 926 } 927 928 size_t GetNumberOfStackMaps() const { 929 return region_.LoadUnaligned<uint32_t>(kNumberOfStackMapsOffset); 930 } 931 932 void SetNumberOfStackMaps(uint32_t number_of_stack_maps) { 933 region_.StoreUnaligned<uint32_t>(kNumberOfStackMapsOffset, number_of_stack_maps); 934 } 935 936 // Get the size of one stack map of this CodeInfo object, in bytes. 937 // All stack maps of a CodeInfo have the same size. 938 size_t StackMapSize() const { 939 return StackMap::ComputeStackMapSizeInternal(GetStackMaskSize(), 940 NumberOfBytesForInlineInfo(), 941 NumberOfBytesForDexRegisterMap(), 942 NumberOfBytesForDexPc(), 943 NumberOfBytesForNativePc(), 944 NumberOfBytesForRegisterMask()); 945 } 946 947 // Get the size all the stack maps of this CodeInfo object, in bytes. 948 size_t GetStackMapsSize() const { 949 return StackMapSize() * GetNumberOfStackMaps(); 950 } 951 952 size_t GetDexRegisterMapsOffset() const { 953 return GetStackMapsOffset() + GetStackMapsSize(); 954 } 955 956 uint32_t GetStackMapsOffset() const { 957 return GetDexRegisterLocationCatalogOffset() + GetDexRegisterLocationCatalogSize(); 958 } 959 960 DexRegisterMap GetDexRegisterMapOf(StackMap stack_map, uint32_t number_of_dex_registers) const { 961 DCHECK(stack_map.HasDexRegisterMap(*this)); 962 uint32_t offset = GetDexRegisterMapsOffset() + stack_map.GetDexRegisterMapOffset(*this); 963 size_t size = ComputeDexRegisterMapSizeOf(offset, number_of_dex_registers); 964 return DexRegisterMap(region_.Subregion(offset, size)); 965 } 966 967 InlineInfo GetInlineInfoOf(StackMap stack_map) const { 968 DCHECK(stack_map.HasInlineInfo(*this)); 969 uint32_t offset = stack_map.GetInlineDescriptorOffset(*this) + GetDexRegisterMapsOffset(); 970 uint8_t depth = region_.LoadUnaligned<uint8_t>(offset); 971 return InlineInfo(region_.Subregion(offset, 972 InlineInfo::kFixedSize + depth * InlineInfo::SingleEntrySize())); 973 } 974 975 StackMap GetStackMapForDexPc(uint32_t dex_pc) const { 976 for (size_t i = 0, e = GetNumberOfStackMaps(); i < e; ++i) { 977 StackMap stack_map = GetStackMapAt(i); 978 if (stack_map.GetDexPc(*this) == dex_pc) { 979 return stack_map; 980 } 981 } 982 return StackMap(); 983 } 984 985 StackMap GetStackMapForNativePcOffset(uint32_t native_pc_offset) const { 986 // TODO: stack maps are sorted by native pc, we can do a binary search. 987 for (size_t i = 0, e = GetNumberOfStackMaps(); i < e; ++i) { 988 StackMap stack_map = GetStackMapAt(i); 989 if (stack_map.GetNativePcOffset(*this) == native_pc_offset) { 990 return stack_map; 991 } 992 } 993 return StackMap(); 994 } 995 996 void Dump(std::ostream& os, uint16_t number_of_dex_registers) const; 997 void DumpStackMapHeader(std::ostream& os, size_t stack_map_num) const; 998 999 private: 1000 // TODO: Instead of plain types such as "uint32_t", introduce 1001 // typedefs (and document the memory layout of CodeInfo). 1002 static constexpr int kOverallSizeOffset = 0; 1003 static constexpr int kEncodingInfoOffset = kOverallSizeOffset + sizeof(uint32_t); 1004 static constexpr int kNumberOfDexRegisterLocationCatalogEntriesOffset = 1005 kEncodingInfoOffset + sizeof(uint16_t); 1006 static constexpr int kNumberOfStackMapsOffset = 1007 kNumberOfDexRegisterLocationCatalogEntriesOffset + sizeof(uint32_t); 1008 static constexpr int kStackMaskSizeOffset = kNumberOfStackMapsOffset + sizeof(uint32_t); 1009 static constexpr int kFixedSize = kStackMaskSizeOffset + sizeof(uint32_t); 1010 1011 static constexpr int kHasInlineInfoBitOffset = (kEncodingInfoOffset * kBitsPerByte); 1012 static constexpr int kInlineInfoBitOffset = kHasInlineInfoBitOffset + 1; 1013 static constexpr int kDexRegisterMapBitOffset = kInlineInfoBitOffset + 3; 1014 static constexpr int kDexPcBitOffset = kDexRegisterMapBitOffset + 3; 1015 static constexpr int kNativePcBitOffset = kDexPcBitOffset + 3; 1016 static constexpr int kRegisterMaskBitOffset = kNativePcBitOffset + 3; 1017 1018 MemoryRegion GetStackMaps() const { 1019 return region_.size() == 0 1020 ? MemoryRegion() 1021 : region_.Subregion(GetStackMapsOffset(), GetStackMapsSize()); 1022 } 1023 1024 // Compute the size of the Dex register map associated to the stack map at 1025 // `dex_register_map_offset_in_code_info`. 1026 size_t ComputeDexRegisterMapSizeOf(uint32_t dex_register_map_offset_in_code_info, 1027 uint16_t number_of_dex_registers) const { 1028 // Offset where the actual mapping data starts within art::DexRegisterMap. 1029 size_t location_mapping_data_offset_in_dex_register_map = 1030 DexRegisterMap::GetLocationMappingDataOffset(number_of_dex_registers); 1031 // Create a temporary art::DexRegisterMap to be able to call 1032 // art::DexRegisterMap::GetNumberOfLiveDexRegisters and 1033 DexRegisterMap dex_register_map_without_locations( 1034 MemoryRegion(region_.Subregion(dex_register_map_offset_in_code_info, 1035 location_mapping_data_offset_in_dex_register_map))); 1036 size_t number_of_live_dex_registers = 1037 dex_register_map_without_locations.GetNumberOfLiveDexRegisters(number_of_dex_registers); 1038 size_t location_mapping_data_size_in_bits = 1039 DexRegisterMap::SingleEntrySizeInBits(GetNumberOfDexRegisterLocationCatalogEntries()) 1040 * number_of_live_dex_registers; 1041 size_t location_mapping_data_size_in_bytes = 1042 RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte; 1043 size_t dex_register_map_size = 1044 location_mapping_data_offset_in_dex_register_map + location_mapping_data_size_in_bytes; 1045 return dex_register_map_size; 1046 } 1047 1048 // Compute the size of a Dex register location catalog starting at offset `origin` 1049 // in `region_` and containing `number_of_dex_locations` entries. 1050 size_t ComputeDexRegisterLocationCatalogSize(uint32_t origin, 1051 uint32_t number_of_dex_locations) const { 1052 // TODO: Ideally, we would like to use art::DexRegisterLocationCatalog::Size or 1053 // art::DexRegisterLocationCatalog::FindLocationOffset, but the 1054 // DexRegisterLocationCatalog is not yet built. Try to factor common code. 1055 size_t offset = origin + DexRegisterLocationCatalog::kFixedSize; 1056 1057 // Skip the first `number_of_dex_locations - 1` entries. 1058 for (uint16_t i = 0; i < number_of_dex_locations; ++i) { 1059 // Read the first next byte and inspect its first 3 bits to decide 1060 // whether it is a short or a large location. 1061 DexRegisterLocationCatalog::ShortLocation first_byte = 1062 region_.LoadUnaligned<DexRegisterLocationCatalog::ShortLocation>(offset); 1063 DexRegisterLocation::Kind kind = 1064 DexRegisterLocationCatalog::ExtractKindFromShortLocation(first_byte); 1065 if (DexRegisterLocation::IsShortLocationKind(kind)) { 1066 // Short location. Skip the current byte. 1067 offset += DexRegisterLocationCatalog::SingleShortEntrySize(); 1068 } else { 1069 // Large location. Skip the 5 next bytes. 1070 offset += DexRegisterLocationCatalog::SingleLargeEntrySize(); 1071 } 1072 } 1073 size_t size = offset - origin; 1074 return size; 1075 } 1076 1077 MemoryRegion region_; 1078 friend class StackMapStream; 1079 }; 1080 1081 } // namespace art 1082 1083 #endif // ART_RUNTIME_STACK_MAP_H_ 1084
