runtime/stack_map.h

   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 "arch/code_offset.h"
  21 #include "base/bit_vector.h"
  22 #include "base/bit_utils.h"
  23 #include "bit_memory_region.h"
  24 #include "dex_file.h"
  25 #include "memory_region.h"
  26 #include "method_info.h"
  27 #include "leb128.h"
  28
  29 namespace art {
  30
  31 class VariableIndentationOutputStream;
  32
  33 // Size of a frame slot, in bytes.  This constant is a signed value,
  34 // to please the compiler in arithmetic operations involving int32_t
  35 // (signed) values.
  36 static constexpr ssize_t kFrameSlotSize = 4;
  37
  38 // Size of Dex virtual registers.
  39 static constexpr size_t kVRegSize = 4;
  40
  41 class ArtMethod;
  42 class CodeInfo;
  43 class StackMapEncoding;
  44 struct CodeInfoEncoding;
  45
  46 /**
  47  * Classes in the following file are wrapper on stack map information backed
  48  * by a MemoryRegion. As such they read and write to the region, they don't have
  49  * their own fields.
  50  */
  51
  52 // Dex register location container used by DexRegisterMap and StackMapStream.
  53 class DexRegisterLocation {
  54  public:
  55   /*
  56    * The location kind used to populate the Dex register information in a
  57    * StackMapStream can either be:
  58    * - kStack: vreg stored on the stack, value holds the stack offset;
  59    * - kInRegister: vreg stored in low 32 bits of a core physical register,
  60    *                value holds the register number;
  61    * - kInRegisterHigh: vreg stored in high 32 bits of a core physical register,
  62    *                    value holds the register number;
  63    * - kInFpuRegister: vreg stored in low 32 bits of an FPU register,
  64    *                   value holds the register number;
  65    * - kInFpuRegisterHigh: vreg stored in high 32 bits of an FPU register,
  66    *                       value holds the register number;
  67    * - kConstant: value holds the constant;
  68    *
  69    * In addition, DexRegisterMap also uses these values:
  70    * - kInStackLargeOffset: value holds a "large" stack offset (greater than
  71    *   or equal to 128 bytes);
  72    * - kConstantLargeValue: value holds a "large" constant (lower than 0, or
  73    *   or greater than or equal to 32);
  74    * - kNone: the register has no location, meaning it has not been set.
  75    */
  76   enum class Kind : uint8_t {
  77     // Short location kinds, for entries fitting on one byte (3 bits
  78     // for the kind, 5 bits for the value) in a DexRegisterMap.
  79     kInStack = 0,             // 0b000
  80     kInRegister = 1,          // 0b001
  81     kInRegisterHigh = 2,      // 0b010
  82     kInFpuRegister = 3,       // 0b011
  83     kInFpuRegisterHigh = 4,   // 0b100
  84     kConstant = 5,            // 0b101
  85
  86     // Large location kinds, requiring a 5-byte encoding (1 byte for the
  87     // kind, 4 bytes for the value).
  88
  89     // Stack location at a large offset, meaning that the offset value
  90     // divided by the stack frame slot size (4 bytes) cannot fit on a
  91     // 5-bit unsigned integer (i.e., this offset value is greater than
  92     // or equal to 2^5 * 4 = 128 bytes).
  93     kInStackLargeOffset = 6,  // 0b110
  94
  95     // Large constant, that cannot fit on a 5-bit signed integer (i.e.,
  96     // lower than 0, or greater than or equal to 2^5 = 32).
  97     kConstantLargeValue = 7,  // 0b111
  98
  99     // Entries with no location are not stored and do not need own marker.
 100     kNone = static_cast<uint8_t>(-1),
 101
 102     kLastLocationKind = kConstantLargeValue
 103   };
 104
 105   static_assert(
 106       sizeof(Kind) == 1u,
 107       "art::DexRegisterLocation::Kind has a size different from one byte.");
 108
 109   static bool IsShortLocationKind(Kind kind) {
 110     switch (kind) {
 111       case Kind::kInStack:
 112       case Kind::kInRegister:
 113       case Kind::kInRegisterHigh:
 114       case Kind::kInFpuRegister:
 115       case Kind::kInFpuRegisterHigh:
 116       case Kind::kConstant:
 117         return true;
 118
 119       case Kind::kInStackLargeOffset:
 120       case Kind::kConstantLargeValue:
 121         return false;
 122
 123       case Kind::kNone:
 124         LOG(FATAL) << "Unexpected location kind";
 125     }
 126     UNREACHABLE();
 127   }
 128
 129   // Convert `kind` to a "surface" kind, i.e. one that doesn't include
 130   // any value with a "large" qualifier.
 131   // TODO: Introduce another enum type for the surface kind?
 132   static Kind ConvertToSurfaceKind(Kind kind) {
 133     switch (kind) {
 134       case Kind::kInStack:
 135       case Kind::kInRegister:
 136       case Kind::kInRegisterHigh:
 137       case Kind::kInFpuRegister:
 138       case Kind::kInFpuRegisterHigh:
 139       case Kind::kConstant:
 140         return kind;
 141
 142       case Kind::kInStackLargeOffset:
 143         return Kind::kInStack;
 144
 145       case Kind::kConstantLargeValue:
 146         return Kind::kConstant;
 147
 148       case Kind::kNone:
 149         return kind;
 150     }
 151     UNREACHABLE();
 152   }
 153
 154   // Required by art::StackMapStream::LocationCatalogEntriesIndices.
 155   DexRegisterLocation() : kind_(Kind::kNone), value_(0) {}
 156
 157   DexRegisterLocation(Kind kind, int32_t value) : kind_(kind), value_(value) {}
 158
 159   static DexRegisterLocation None() {
 160     return DexRegisterLocation(Kind::kNone, 0);
 161   }
 162
 163   // Get the "surface" kind of the location, i.e., the one that doesn't
 164   // include any value with a "large" qualifier.
 165   Kind GetKind() const {
 166     return ConvertToSurfaceKind(kind_);
 167   }
 168
 169   // Get the value of the location.
 170   int32_t GetValue() const { return value_; }
 171
 172   // Get the actual kind of the location.
 173   Kind GetInternalKind() const { return kind_; }
 174
 175   bool operator==(DexRegisterLocation other) const {
 176     return kind_ == other.kind_ && value_ == other.value_;
 177   }
 178
 179   bool operator!=(DexRegisterLocation other) const {
 180     return !(*this == other);
 181   }
 182
 183  private:
 184   Kind kind_;
 185   int32_t value_;
 186
 187   friend class DexRegisterLocationHashFn;
 188 };
 189
 190 std::ostream& operator<<(std::ostream& stream, const DexRegisterLocation::Kind& kind);
 191
 192 /**
 193  * Store information on unique Dex register locations used in a method.
 194  * The information is of the form:
 195  *
 196  *   [DexRegisterLocation+].
 197  *
 198  * DexRegisterLocations are either 1- or 5-byte wide (see art::DexRegisterLocation::Kind).
 199  */
 200 class DexRegisterLocationCatalog {
 201  public:
 202   explicit DexRegisterLocationCatalog(MemoryRegion region) : region_(region) {}
 203
 204   // Short (compressed) location, fitting on one byte.
 205   typedef uint8_t ShortLocation;
 206
 207   void SetRegisterInfo(size_t offset, const DexRegisterLocation& dex_register_location) {
 208     DexRegisterLocation::Kind kind = ComputeCompressedKind(dex_register_location);
 209     int32_t value = dex_register_location.GetValue();
 210     if (DexRegisterLocation::IsShortLocationKind(kind)) {
 211       // Short location.  Compress the kind and the value as a single byte.
 212       if (kind == DexRegisterLocation::Kind::kInStack) {
 213         // Instead of storing stack offsets expressed in bytes for
 214         // short stack locations, store slot offsets.  A stack offset
 215         // is a multiple of 4 (kFrameSlotSize).  This means that by
 216         // dividing it by 4, we can fit values from the [0, 128)
 217         // interval in a short stack location, and not just values
 218         // from the [0, 32) interval.
 219         DCHECK_EQ(value % kFrameSlotSize, 0);
 220         value /= kFrameSlotSize;
 221       }
 222       DCHECK(IsShortValue(value)) << value;
 223       region_.StoreUnaligned<ShortLocation>(offset, MakeShortLocation(kind, value));
 224     } else {
 225       // Large location.  Write the location on one byte and the value
 226       // on 4 bytes.
 227       DCHECK(!IsShortValue(value)) << value;
 228       if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) {
 229         // Also divide large stack offsets by 4 for the sake of consistency.
 230         DCHECK_EQ(value % kFrameSlotSize, 0);
 231         value /= kFrameSlotSize;
 232       }
 233       // Data can be unaligned as the written Dex register locations can
 234       // either be 1-byte or 5-byte wide.  Use
 235       // art::MemoryRegion::StoreUnaligned instead of
 236       // art::MemoryRegion::Store to prevent unligned word accesses on ARM.
 237       region_.StoreUnaligned<DexRegisterLocation::Kind>(offset, kind);
 238       region_.StoreUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind), value);
 239     }
 240   }
 241
 242   // Find the offset of the location catalog entry number `location_catalog_entry_index`.
 243   size_t FindLocationOffset(size_t location_catalog_entry_index) const {
 244     size_t offset = kFixedSize;
 245     // Skip the first `location_catalog_entry_index - 1` entries.
 246     for (uint16_t i = 0; i < location_catalog_entry_index; ++i) {
 247       // Read the first next byte and inspect its first 3 bits to decide
 248       // whether it is a short or a large location.
 249       DexRegisterLocation::Kind kind = ExtractKindAtOffset(offset);
 250       if (DexRegisterLocation::IsShortLocationKind(kind)) {
 251         // Short location.  Skip the current byte.
 252         offset += SingleShortEntrySize();
 253       } else {
 254         // Large location.  Skip the 5 next bytes.
 255         offset += SingleLargeEntrySize();
 256       }
 257     }
 258     return offset;
 259   }
 260
 261   // Get the internal kind of entry at `location_catalog_entry_index`.
 262   DexRegisterLocation::Kind GetLocationInternalKind(size_t location_catalog_entry_index) const {
 263     if (location_catalog_entry_index == kNoLocationEntryIndex) {
 264       return DexRegisterLocation::Kind::kNone;
 265     }
 266     return ExtractKindAtOffset(FindLocationOffset(location_catalog_entry_index));
 267   }
 268
 269   // Get the (surface) kind and value of entry at `location_catalog_entry_index`.
 270   DexRegisterLocation GetDexRegisterLocation(size_t location_catalog_entry_index) const {
 271     if (location_catalog_entry_index == kNoLocationEntryIndex) {
 272       return DexRegisterLocation::None();
 273     }
 274     size_t offset = FindLocationOffset(location_catalog_entry_index);
 275     // Read the first byte and inspect its first 3 bits to get the location.
 276     ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset);
 277     DexRegisterLocation::Kind kind = ExtractKindFromShortLocation(first_byte);
 278     if (DexRegisterLocation::IsShortLocationKind(kind)) {
 279       // Short location.  Extract the value from the remaining 5 bits.
 280       int32_t value = ExtractValueFromShortLocation(first_byte);
 281       if (kind == DexRegisterLocation::Kind::kInStack) {
 282         // Convert the stack slot (short) offset to a byte offset value.
 283         value *= kFrameSlotSize;
 284       }
 285       return DexRegisterLocation(kind, value);
 286     } else {
 287       // Large location.  Read the four next bytes to get the value.
 288       int32_t value = region_.LoadUnaligned<int32_t>(offset + sizeof(DexRegisterLocation::Kind));
 289       if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) {
 290         // Convert the stack slot (large) offset to a byte offset value.
 291         value *= kFrameSlotSize;
 292       }
 293       return DexRegisterLocation(kind, value);
 294     }
 295   }
 296
 297   // Compute the compressed kind of `location`.
 298   static DexRegisterLocation::Kind ComputeCompressedKind(const DexRegisterLocation& location) {
 299     DexRegisterLocation::Kind kind = location.GetInternalKind();
 300     switch (kind) {
 301       case DexRegisterLocation::Kind::kInStack:
 302         return IsShortStackOffsetValue(location.GetValue())
 303             ? DexRegisterLocation::Kind::kInStack
 304             : DexRegisterLocation::Kind::kInStackLargeOffset;
 305
 306       case DexRegisterLocation::Kind::kInRegister:
 307       case DexRegisterLocation::Kind::kInRegisterHigh:
 308         DCHECK_GE(location.GetValue(), 0);
 309         DCHECK_LT(location.GetValue(), 1 << kValueBits);
 310         return kind;
 311
 312       case DexRegisterLocation::Kind::kInFpuRegister:
 313       case DexRegisterLocation::Kind::kInFpuRegisterHigh:
 314         DCHECK_GE(location.GetValue(), 0);
 315         DCHECK_LT(location.GetValue(), 1 << kValueBits);
 316         return kind;
 317
 318       case DexRegisterLocation::Kind::kConstant:
 319         return IsShortConstantValue(location.GetValue())
 320             ? DexRegisterLocation::Kind::kConstant
 321             : DexRegisterLocation::Kind::kConstantLargeValue;
 322
 323       case DexRegisterLocation::Kind::kConstantLargeValue:
 324       case DexRegisterLocation::Kind::kInStackLargeOffset:
 325       case DexRegisterLocation::Kind::kNone:
 326         LOG(FATAL) << "Unexpected location kind " << kind;
 327     }
 328     UNREACHABLE();
 329   }
 330
 331   // Can `location` be turned into a short location?
 332   static bool CanBeEncodedAsShortLocation(const DexRegisterLocation& location) {
 333     DexRegisterLocation::Kind kind = location.GetInternalKind();
 334     switch (kind) {
 335       case DexRegisterLocation::Kind::kInStack:
 336         return IsShortStackOffsetValue(location.GetValue());
 337
 338       case DexRegisterLocation::Kind::kInRegister:
 339       case DexRegisterLocation::Kind::kInRegisterHigh:
 340       case DexRegisterLocation::Kind::kInFpuRegister:
 341       case DexRegisterLocation::Kind::kInFpuRegisterHigh:
 342         return true;
 343
 344       case DexRegisterLocation::Kind::kConstant:
 345         return IsShortConstantValue(location.GetValue());
 346
 347       case DexRegisterLocation::Kind::kConstantLargeValue:
 348       case DexRegisterLocation::Kind::kInStackLargeOffset:
 349       case DexRegisterLocation::Kind::kNone:
 350         LOG(FATAL) << "Unexpected location kind " << kind;
 351     }
 352     UNREACHABLE();
 353   }
 354
 355   static size_t EntrySize(const DexRegisterLocation& location) {
 356     return CanBeEncodedAsShortLocation(location) ? SingleShortEntrySize() : SingleLargeEntrySize();
 357   }
 358
 359   static size_t SingleShortEntrySize() {
 360     return sizeof(ShortLocation);
 361   }
 362
 363   static size_t SingleLargeEntrySize() {
 364     return sizeof(DexRegisterLocation::Kind) + sizeof(int32_t);
 365   }
 366
 367   size_t Size() const {
 368     return region_.size();
 369   }
 370
 371   void Dump(VariableIndentationOutputStream* vios,
 372             const CodeInfo& code_info);
 373
 374   // Special (invalid) Dex register location catalog entry index meaning
 375   // that there is no location for a given Dex register (i.e., it is
 376   // mapped to a DexRegisterLocation::Kind::kNone location).
 377   static constexpr size_t kNoLocationEntryIndex = -1;
 378
 379  private:
 380   static constexpr int kFixedSize = 0;
 381
 382   // Width of the kind "field" in a short location, in bits.
 383   static constexpr size_t kKindBits = 3;
 384   // Width of the value "field" in a short location, in bits.
 385   static constexpr size_t kValueBits = 5;
 386
 387   static constexpr uint8_t kKindMask = (1 << kKindBits) - 1;
 388   static constexpr int32_t kValueMask = (1 << kValueBits) - 1;
 389   static constexpr size_t kKindOffset = 0;
 390   static constexpr size_t kValueOffset = kKindBits;
 391
 392   static bool IsShortStackOffsetValue(int32_t value) {
 393     DCHECK_EQ(value % kFrameSlotSize, 0);
 394     return IsShortValue(value / kFrameSlotSize);
 395   }
 396
 397   static bool IsShortConstantValue(int32_t value) {
 398     return IsShortValue(value);
 399   }
 400
 401   static bool IsShortValue(int32_t value) {
 402     return IsUint<kValueBits>(value);
 403   }
 404
 405   static ShortLocation MakeShortLocation(DexRegisterLocation::Kind kind, int32_t value) {
 406     uint8_t kind_integer_value = static_cast<uint8_t>(kind);
 407     DCHECK(IsUint<kKindBits>(kind_integer_value)) << kind_integer_value;
 408     DCHECK(IsShortValue(value)) << value;
 409     return (kind_integer_value & kKindMask) << kKindOffset
 410         | (value & kValueMask) << kValueOffset;
 411   }
 412
 413   static DexRegisterLocation::Kind ExtractKindFromShortLocation(ShortLocation location) {
 414     uint8_t kind = (location >> kKindOffset) & kKindMask;
 415     DCHECK_LE(kind, static_cast<uint8_t>(DexRegisterLocation::Kind::kLastLocationKind));
 416     // We do not encode kNone locations in the stack map.
 417     DCHECK_NE(kind, static_cast<uint8_t>(DexRegisterLocation::Kind::kNone));
 418     return static_cast<DexRegisterLocation::Kind>(kind);
 419   }
 420
 421   static int32_t ExtractValueFromShortLocation(ShortLocation location) {
 422     return (location >> kValueOffset) & kValueMask;
 423   }
 424
 425   // Extract a location kind from the byte at position `offset`.
 426   DexRegisterLocation::Kind ExtractKindAtOffset(size_t offset) const {
 427     ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset);
 428     return ExtractKindFromShortLocation(first_byte);
 429   }
 430
 431   MemoryRegion region_;
 432
 433   friend class CodeInfo;
 434   friend class StackMapStream;
 435 };
 436
 437 /* Information on Dex register locations for a specific PC, mapping a
 438  * stack map's Dex register to a location entry in a DexRegisterLocationCatalog.
 439  * The information is of the form:
 440  *
 441  *   [live_bit_mask, entries*]
 442  *
 443  * where entries are concatenated unsigned integer values encoded on a number
 444  * of bits (fixed per DexRegisterMap instances of a CodeInfo object) depending
 445  * on the number of entries in the Dex register location catalog
 446  * (see DexRegisterMap::SingleEntrySizeInBits).  The map is 1-byte aligned.
 447  */
 448 class DexRegisterMap {
 449  public:
 450   explicit DexRegisterMap(MemoryRegion region) : region_(region) {}
 451   DexRegisterMap() {}
 452
 453   bool IsValid() const { return region_.pointer() != nullptr; }
 454
 455   // Get the surface kind of Dex register `dex_register_number`.
 456   DexRegisterLocation::Kind GetLocationKind(uint16_t dex_register_number,
 457                                             uint16_t number_of_dex_registers,
 458                                             const CodeInfo& code_info,
 459                                             const CodeInfoEncoding& enc) const {
 460     return DexRegisterLocation::ConvertToSurfaceKind(
 461         GetLocationInternalKind(dex_register_number, number_of_dex_registers, code_info, enc));
 462   }
 463
 464   // Get the internal kind of Dex register `dex_register_number`.
 465   DexRegisterLocation::Kind GetLocationInternalKind(uint16_t dex_register_number,
 466                                                     uint16_t number_of_dex_registers,
 467                                                     const CodeInfo& code_info,
 468                                                     const CodeInfoEncoding& enc) const;
 469
 470   // Get the Dex register location `dex_register_number`.
 471   DexRegisterLocation GetDexRegisterLocation(uint16_t dex_register_number,
 472                                              uint16_t number_of_dex_registers,
 473                                              const CodeInfo& code_info,
 474                                              const CodeInfoEncoding& enc) const;
 475
 476   int32_t GetStackOffsetInBytes(uint16_t dex_register_number,
 477                                 uint16_t number_of_dex_registers,
 478                                 const CodeInfo& code_info,
 479                                 const CodeInfoEncoding& enc) const {
 480     DexRegisterLocation location =
 481         GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info, enc);
 482     DCHECK(location.GetKind() == DexRegisterLocation::Kind::kInStack);
 483     // GetDexRegisterLocation returns the offset in bytes.
 484     return location.GetValue();
 485   }
 486
 487   int32_t GetConstant(uint16_t dex_register_number,
 488                       uint16_t number_of_dex_registers,
 489                       const CodeInfo& code_info,
 490                       const CodeInfoEncoding& enc) const {
 491     DexRegisterLocation location =
 492         GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info, enc);
 493     DCHECK_EQ(location.GetKind(), DexRegisterLocation::Kind::kConstant);
 494     return location.GetValue();
 495   }
 496
 497   int32_t GetMachineRegister(uint16_t dex_register_number,
 498                              uint16_t number_of_dex_registers,
 499                              const CodeInfo& code_info,
 500                              const CodeInfoEncoding& enc) const {
 501     DexRegisterLocation location =
 502         GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info, enc);
 503     DCHECK(location.GetInternalKind() == DexRegisterLocation::Kind::kInRegister ||
 504            location.GetInternalKind() == DexRegisterLocation::Kind::kInRegisterHigh ||
 505            location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegister ||
 506            location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegisterHigh)
 507         << location.GetInternalKind();
 508     return location.GetValue();
 509   }
 510
 511   // Get the index of the entry in the Dex register location catalog
 512   // corresponding to `dex_register_number`.
 513   size_t GetLocationCatalogEntryIndex(uint16_t dex_register_number,
 514                                       uint16_t number_of_dex_registers,
 515                                       size_t number_of_location_catalog_entries) const {
 516     if (!IsDexRegisterLive(dex_register_number)) {
 517       return DexRegisterLocationCatalog::kNoLocationEntryIndex;
 518     }
 519
 520     if (number_of_location_catalog_entries == 1) {
 521       // We do not allocate space for location maps in the case of a
 522       // single-entry location catalog, as it is useless.  The only valid
 523       // entry index is 0;
 524       return 0;
 525     }
 526
 527     // The bit offset of the beginning of the map locations.
 528     size_t map_locations_offset_in_bits =
 529         GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte;
 530     size_t index_in_dex_register_map = GetIndexInDexRegisterMap(dex_register_number);
 531     DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers));
 532     // The bit size of an entry.
 533     size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries);
 534     // The bit offset where `index_in_dex_register_map` is located.
 535     size_t entry_offset_in_bits =
 536         map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits;
 537     size_t location_catalog_entry_index =
 538         region_.LoadBits(entry_offset_in_bits, map_entry_size_in_bits);
 539     DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries);
 540     return location_catalog_entry_index;
 541   }
 542
 543   // Map entry at `index_in_dex_register_map` to `location_catalog_entry_index`.
 544   void SetLocationCatalogEntryIndex(size_t index_in_dex_register_map,
 545                                     size_t location_catalog_entry_index,
 546                                     uint16_t number_of_dex_registers,
 547                                     size_t number_of_location_catalog_entries) {
 548     DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers));
 549     DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries);
 550
 551     if (number_of_location_catalog_entries == 1) {
 552       // We do not allocate space for location maps in the case of a
 553       // single-entry location catalog, as it is useless.
 554       return;
 555     }
 556
 557     // The bit offset of the beginning of the map locations.
 558     size_t map_locations_offset_in_bits =
 559         GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte;
 560     // The bit size of an entry.
 561     size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries);
 562     // The bit offset where `index_in_dex_register_map` is located.
 563     size_t entry_offset_in_bits =
 564         map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits;
 565     region_.StoreBits(entry_offset_in_bits, location_catalog_entry_index, map_entry_size_in_bits);
 566   }
 567
 568   void SetLiveBitMask(uint16_t number_of_dex_registers,
 569                       const BitVector& live_dex_registers_mask) {
 570     size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte;
 571     for (uint16_t i = 0; i < number_of_dex_registers; ++i) {
 572       region_.StoreBit(live_bit_mask_offset_in_bits + i, live_dex_registers_mask.IsBitSet(i));
 573     }
 574   }
 575
 576   ALWAYS_INLINE bool IsDexRegisterLive(uint16_t dex_register_number) const {
 577     size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte;
 578     return region_.LoadBit(live_bit_mask_offset_in_bits + dex_register_number);
 579   }
 580
 581   size_t GetNumberOfLiveDexRegisters(uint16_t number_of_dex_registers) const {
 582     size_t number_of_live_dex_registers = 0;
 583     for (size_t i = 0; i < number_of_dex_registers; ++i) {
 584       if (IsDexRegisterLive(i)) {
 585         ++number_of_live_dex_registers;
 586       }
 587     }
 588     return number_of_live_dex_registers;
 589   }
 590
 591   static size_t GetLiveBitMaskOffset() {
 592     return kFixedSize;
 593   }
 594
 595   // Compute the size of the live register bit mask (in bytes), for a
 596   // method having `number_of_dex_registers` Dex registers.
 597   static size_t GetLiveBitMaskSize(uint16_t number_of_dex_registers) {
 598     return RoundUp(number_of_dex_registers, kBitsPerByte) / kBitsPerByte;
 599   }
 600
 601   static size_t GetLocationMappingDataOffset(uint16_t number_of_dex_registers) {
 602     return GetLiveBitMaskOffset() + GetLiveBitMaskSize(number_of_dex_registers);
 603   }
 604
 605   size_t GetLocationMappingDataSize(uint16_t number_of_dex_registers,
 606                                     size_t number_of_location_catalog_entries) const {
 607     size_t location_mapping_data_size_in_bits =
 608         GetNumberOfLiveDexRegisters(number_of_dex_registers)
 609         * SingleEntrySizeInBits(number_of_location_catalog_entries);
 610     return RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte;
 611   }
 612
 613   // Return the size of a map entry in bits.  Note that if
 614   // `number_of_location_catalog_entries` equals 1, this function returns 0,
 615   // which is fine, as there is no need to allocate a map for a
 616   // single-entry location catalog; the only valid location catalog entry index
 617   // for a live register in this case is 0 and there is no need to
 618   // store it.
 619   static size_t SingleEntrySizeInBits(size_t number_of_location_catalog_entries) {
 620     // Handle the case of 0, as we cannot pass 0 to art::WhichPowerOf2.
 621     return number_of_location_catalog_entries == 0
 622         ? 0u
 623         : WhichPowerOf2(RoundUpToPowerOfTwo(number_of_location_catalog_entries));
 624   }
 625
 626   // Return the size of the DexRegisterMap object, in bytes.
 627   size_t Size() const {
 628     return region_.size();
 629   }
 630
 631   void Dump(VariableIndentationOutputStream* vios,
 632             const CodeInfo& code_info, uint16_t number_of_dex_registers) const;
 633
 634  private:
 635   // Return the index in the Dex register map corresponding to the Dex
 636   // register number `dex_register_number`.
 637   size_t GetIndexInDexRegisterMap(uint16_t dex_register_number) const {
 638     if (!IsDexRegisterLive(dex_register_number)) {
 639       return kInvalidIndexInDexRegisterMap;
 640     }
 641     return GetNumberOfLiveDexRegisters(dex_register_number);
 642   }
 643
 644   // Special (invalid) Dex register map entry index meaning that there
 645   // is no index in the map for a given Dex register (i.e., it must
 646   // have been mapped to a DexRegisterLocation::Kind::kNone location).
 647   static constexpr size_t kInvalidIndexInDexRegisterMap = -1;
 648
 649   static constexpr int kFixedSize = 0;
 650
 651   MemoryRegion region_;
 652
 653   friend class CodeInfo;
 654   friend class StackMapStream;
 655 };
 656
 657 // Represents bit range of bit-packed integer field.
 658 // We reuse the idea from ULEB128p1 to support encoding of -1 (aka 0xFFFFFFFF).
 659 // If min_value is set to -1, we implicitly subtract one from any loaded value,
 660 // and add one to any stored value. This is generalized to any negative values.
 661 // In other words, min_value acts as a base and the stored value is added to it.
 662 struct FieldEncoding {
 663   FieldEncoding(size_t start_offset, size_t end_offset, int32_t min_value = 0)
 664       : start_offset_(start_offset), end_offset_(end_offset), min_value_(min_value) {
 665     DCHECK_LE(start_offset_, end_offset_);
 666     DCHECK_LE(BitSize(), 32u);
 667   }
 668
 669   ALWAYS_INLINE size_t BitSize() const { return end_offset_ - start_offset_; }
 670
 671   template <typename Region>
 672   ALWAYS_INLINE int32_t Load(const Region& region) const {
 673     DCHECK_LE(end_offset_, region.size_in_bits());
 674     return static_cast<int32_t>(region.LoadBits(start_offset_, BitSize())) + min_value_;
 675   }
 676
 677   template <typename Region>
 678   ALWAYS_INLINE void Store(Region region, int32_t value) const {
 679     region.StoreBits(start_offset_, value - min_value_, BitSize());
 680     DCHECK_EQ(Load(region), value);
 681   }
 682
 683  private:
 684   size_t start_offset_;
 685   size_t end_offset_;
 686   int32_t min_value_;
 687 };
 688
 689 class StackMapEncoding {
 690  public:
 691   StackMapEncoding()
 692       : dex_pc_bit_offset_(0),
 693         dex_register_map_bit_offset_(0),
 694         inline_info_bit_offset_(0),
 695         register_mask_index_bit_offset_(0),
 696         stack_mask_index_bit_offset_(0),
 697         total_bit_size_(0) {}
 698
 699   // Set stack map bit layout based on given sizes.
 700   // Returns the size of stack map in bits.
 701   size_t SetFromSizes(size_t native_pc_max,
 702                       size_t dex_pc_max,
 703                       size_t dex_register_map_size,
 704                       size_t number_of_inline_info,
 705                       size_t number_of_register_masks,
 706                       size_t number_of_stack_masks) {
 707     total_bit_size_ = 0;
 708     DCHECK_EQ(kNativePcBitOffset, total_bit_size_);
 709     total_bit_size_ += MinimumBitsToStore(native_pc_max);
 710
 711     dex_pc_bit_offset_ = total_bit_size_;
 712     total_bit_size_ += MinimumBitsToStore(1 /* kNoDexPc */ + dex_pc_max);
 713
 714     // We also need +1 for kNoDexRegisterMap, but since the size is strictly
 715     // greater than any offset we might try to encode, we already implicitly have it.
 716     dex_register_map_bit_offset_ = total_bit_size_;
 717     total_bit_size_ += MinimumBitsToStore(dex_register_map_size);
 718
 719     // We also need +1 for kNoInlineInfo, but since the inline_info_size is strictly
 720     // greater than the offset we might try to encode, we already implicitly have it.
 721     // If inline_info_size is zero, we can encode only kNoInlineInfo (in zero bits).
 722     inline_info_bit_offset_ = total_bit_size_;
 723     total_bit_size_ += MinimumBitsToStore(number_of_inline_info);
 724
 725     register_mask_index_bit_offset_ = total_bit_size_;
 726     total_bit_size_ += MinimumBitsToStore(number_of_register_masks);
 727
 728     stack_mask_index_bit_offset_ = total_bit_size_;
 729     total_bit_size_ += MinimumBitsToStore(number_of_stack_masks);
 730
 731     return total_bit_size_;
 732   }
 733
 734   ALWAYS_INLINE FieldEncoding GetNativePcEncoding() const {
 735     return FieldEncoding(kNativePcBitOffset, dex_pc_bit_offset_);
 736   }
 737   ALWAYS_INLINE FieldEncoding GetDexPcEncoding() const {
 738     return FieldEncoding(dex_pc_bit_offset_, dex_register_map_bit_offset_, -1 /* min_value */);
 739   }
 740   ALWAYS_INLINE FieldEncoding GetDexRegisterMapEncoding() const {
 741     return FieldEncoding(dex_register_map_bit_offset_, inline_info_bit_offset_, -1 /* min_value */);
 742   }
 743   ALWAYS_INLINE FieldEncoding GetInlineInfoEncoding() const {
 744     return FieldEncoding(inline_info_bit_offset_,
 745                          register_mask_index_bit_offset_,
 746                          -1 /* min_value */);
 747   }
 748   ALWAYS_INLINE FieldEncoding GetRegisterMaskIndexEncoding() const {
 749     return FieldEncoding(register_mask_index_bit_offset_, stack_mask_index_bit_offset_);
 750   }
 751   ALWAYS_INLINE FieldEncoding GetStackMaskIndexEncoding() const {
 752     return FieldEncoding(stack_mask_index_bit_offset_, total_bit_size_);
 753   }
 754   ALWAYS_INLINE size_t BitSize() const {
 755     return total_bit_size_;
 756   }
 757
 758   // Encode the encoding into the vector.
 759   template<typename Vector>
 760   void Encode(Vector* dest) const {
 761     static_assert(alignof(StackMapEncoding) == 1, "Should not require alignment");
 762     const uint8_t* ptr = reinterpret_cast<const uint8_t*>(this);
 763     dest->insert(dest->end(), ptr, ptr + sizeof(*this));
 764   }
 765
 766   // Decode the encoding from a pointer, updates the pointer.
 767   void Decode(const uint8_t** ptr) {
 768     *this = *reinterpret_cast<const StackMapEncoding*>(*ptr);
 769     *ptr += sizeof(*this);
 770   }
 771
 772   void Dump(VariableIndentationOutputStream* vios) const;
 773
 774  private:
 775   static constexpr size_t kNativePcBitOffset = 0;
 776   uint8_t dex_pc_bit_offset_;
 777   uint8_t dex_register_map_bit_offset_;
 778   uint8_t inline_info_bit_offset_;
 779   uint8_t register_mask_index_bit_offset_;
 780   uint8_t stack_mask_index_bit_offset_;
 781   uint8_t total_bit_size_;
 782 };
 783
 784 /**
 785  * A Stack Map holds compilation information for a specific PC necessary for:
 786  * - Mapping it to a dex PC,
 787  * - Knowing which stack entries are objects,
 788  * - Knowing which registers hold objects,
 789  * - Knowing the inlining information,
 790  * - Knowing the values of dex registers.
 791  *
 792  * The information is of the form:
 793  *
 794  *   [native_pc_offset, dex_pc, dex_register_map_offset, inlining_info_index, register_mask_index,
 795  *   stack_mask_index].
 796  */
 797 class StackMap {
 798  public:
 799   StackMap() {}
 800   explicit StackMap(BitMemoryRegion region) : region_(region) {}
 801
 802   ALWAYS_INLINE bool IsValid() const { return region_.pointer() != nullptr; }
 803
 804   ALWAYS_INLINE uint32_t GetDexPc(const StackMapEncoding& encoding) const {
 805     return encoding.GetDexPcEncoding().Load(region_);
 806   }
 807
 808   ALWAYS_INLINE void SetDexPc(const StackMapEncoding& encoding, uint32_t dex_pc) {
 809     encoding.GetDexPcEncoding().Store(region_, dex_pc);
 810   }
 811
 812   ALWAYS_INLINE uint32_t GetNativePcOffset(const StackMapEncoding& encoding,
 813                                            InstructionSet instruction_set) const {
 814     CodeOffset offset(
 815         CodeOffset::FromCompressedOffset(encoding.GetNativePcEncoding().Load(region_)));
 816     return offset.Uint32Value(instruction_set);
 817   }
 818
 819   ALWAYS_INLINE void SetNativePcCodeOffset(const StackMapEncoding& encoding,
 820                                            CodeOffset native_pc_offset) {
 821     encoding.GetNativePcEncoding().Store(region_, native_pc_offset.CompressedValue());
 822   }
 823
 824   ALWAYS_INLINE uint32_t GetDexRegisterMapOffset(const StackMapEncoding& encoding) const {
 825     return encoding.GetDexRegisterMapEncoding().Load(region_);
 826   }
 827
 828   ALWAYS_INLINE void SetDexRegisterMapOffset(const StackMapEncoding& encoding, uint32_t offset) {
 829     encoding.GetDexRegisterMapEncoding().Store(region_, offset);
 830   }
 831
 832   ALWAYS_INLINE uint32_t GetInlineInfoIndex(const StackMapEncoding& encoding) const {
 833     return encoding.GetInlineInfoEncoding().Load(region_);
 834   }
 835
 836   ALWAYS_INLINE void SetInlineInfoIndex(const StackMapEncoding& encoding, uint32_t index) {
 837     encoding.GetInlineInfoEncoding().Store(region_, index);
 838   }
 839
 840   ALWAYS_INLINE uint32_t GetRegisterMaskIndex(const StackMapEncoding& encoding) const {
 841     return encoding.GetRegisterMaskIndexEncoding().Load(region_);
 842   }
 843
 844   ALWAYS_INLINE void SetRegisterMaskIndex(const StackMapEncoding& encoding, uint32_t mask) {
 845     encoding.GetRegisterMaskIndexEncoding().Store(region_, mask);
 846   }
 847
 848   ALWAYS_INLINE uint32_t GetStackMaskIndex(const StackMapEncoding& encoding) const {
 849     return encoding.GetStackMaskIndexEncoding().Load(region_);
 850   }
 851
 852   ALWAYS_INLINE void SetStackMaskIndex(const StackMapEncoding& encoding, uint32_t mask) {
 853     encoding.GetStackMaskIndexEncoding().Store(region_, mask);
 854   }
 855
 856   ALWAYS_INLINE bool HasDexRegisterMap(const StackMapEncoding& encoding) const {
 857     return GetDexRegisterMapOffset(encoding) != kNoDexRegisterMap;
 858   }
 859
 860   ALWAYS_INLINE bool HasInlineInfo(const StackMapEncoding& encoding) const {
 861     return GetInlineInfoIndex(encoding) != kNoInlineInfo;
 862   }
 863
 864   ALWAYS_INLINE bool Equals(const StackMap& other) const {
 865     return region_.pointer() == other.region_.pointer() &&
 866            region_.size() == other.region_.size() &&
 867            region_.BitOffset() == other.region_.BitOffset();
 868   }
 869
 870   void Dump(VariableIndentationOutputStream* vios,
 871             const CodeInfo& code_info,
 872             const CodeInfoEncoding& encoding,
 873             const MethodInfo& method_info,
 874             uint32_t code_offset,
 875             uint16_t number_of_dex_registers,
 876             InstructionSet instruction_set,
 877             const std::string& header_suffix = "") const;
 878
 879   // Special (invalid) offset for the DexRegisterMapOffset field meaning
 880   // that there is no Dex register map for this stack map.
 881   static constexpr uint32_t kNoDexRegisterMap = -1;
 882
 883   // Special (invalid) offset for the InlineDescriptorOffset field meaning
 884   // that there is no inline info for this stack map.
 885   static constexpr uint32_t kNoInlineInfo = -1;
 886
 887  private:
 888   static constexpr int kFixedSize = 0;
 889
 890   BitMemoryRegion region_;
 891
 892   friend class StackMapStream;
 893 };
 894
 895 class InlineInfoEncoding {
 896  public:
 897   void SetFromSizes(size_t method_index_idx_max,
 898                     size_t dex_pc_max,
 899                     size_t extra_data_max,
 900                     size_t dex_register_map_size) {
 901     total_bit_size_ = kMethodIndexBitOffset;
 902     total_bit_size_ += MinimumBitsToStore(method_index_idx_max);
 903
 904     dex_pc_bit_offset_ = dchecked_integral_cast<uint8_t>(total_bit_size_);
 905     // Note: We're not encoding the dex pc if there is none. That's the case
 906     // for an intrinsified native method, such as String.charAt().
 907     if (dex_pc_max != DexFile::kDexNoIndex) {
 908       total_bit_size_ += MinimumBitsToStore(1 /* kNoDexPc */ + dex_pc_max);
 909     }
 910
 911     extra_data_bit_offset_ = dchecked_integral_cast<uint8_t>(total_bit_size_);
 912     total_bit_size_ += MinimumBitsToStore(extra_data_max);
 913
 914     // We also need +1 for kNoDexRegisterMap, but since the size is strictly
 915     // greater than any offset we might try to encode, we already implicitly have it.
 916     dex_register_map_bit_offset_ = dchecked_integral_cast<uint8_t>(total_bit_size_);
 917     total_bit_size_ += MinimumBitsToStore(dex_register_map_size);
 918   }
 919
 920   ALWAYS_INLINE FieldEncoding GetMethodIndexIdxEncoding() const {
 921     return FieldEncoding(kMethodIndexBitOffset, dex_pc_bit_offset_);
 922   }
 923   ALWAYS_INLINE FieldEncoding GetDexPcEncoding() const {
 924     return FieldEncoding(dex_pc_bit_offset_, extra_data_bit_offset_, -1 /* min_value */);
 925   }
 926   ALWAYS_INLINE FieldEncoding GetExtraDataEncoding() const {
 927     return FieldEncoding(extra_data_bit_offset_, dex_register_map_bit_offset_);
 928   }
 929   ALWAYS_INLINE FieldEncoding GetDexRegisterMapEncoding() const {
 930     return FieldEncoding(dex_register_map_bit_offset_, total_bit_size_, -1 /* min_value */);
 931   }
 932   ALWAYS_INLINE size_t BitSize() const {
 933     return total_bit_size_;
 934   }
 935
 936   void Dump(VariableIndentationOutputStream* vios) const;
 937
 938   // Encode the encoding into the vector.
 939   template<typename Vector>
 940   void Encode(Vector* dest) const {
 941     static_assert(alignof(InlineInfoEncoding) == 1, "Should not require alignment");
 942     const uint8_t* ptr = reinterpret_cast<const uint8_t*>(this);
 943     dest->insert(dest->end(), ptr, ptr + sizeof(*this));
 944   }
 945
 946   // Decode the encoding from a pointer, updates the pointer.
 947   void Decode(const uint8_t** ptr) {
 948     *this = *reinterpret_cast<const InlineInfoEncoding*>(*ptr);
 949     *ptr += sizeof(*this);
 950   }
 951
 952  private:
 953   static constexpr uint8_t kIsLastBitOffset = 0;
 954   static constexpr uint8_t kMethodIndexBitOffset = 1;
 955   uint8_t dex_pc_bit_offset_;
 956   uint8_t extra_data_bit_offset_;
 957   uint8_t dex_register_map_bit_offset_;
 958   uint8_t total_bit_size_;
 959 };
 960
 961 /**
 962  * Inline information for a specific PC. The information is of the form:
 963  *
 964  *   [is_last,
 965  *    method_index (or ArtMethod high bits),
 966  *    dex_pc,
 967  *    extra_data (ArtMethod low bits or 1),
 968  *    dex_register_map_offset]+.
 969  */
 970 class InlineInfo {
 971  public:
 972   explicit InlineInfo(BitMemoryRegion region) : region_(region) {}
 973
 974   ALWAYS_INLINE uint32_t GetDepth(const InlineInfoEncoding& encoding) const {
 975     size_t depth = 0;
 976     while (!GetRegionAtDepth(encoding, depth++).LoadBit(0)) { }  // Check is_last bit.
 977     return depth;
 978   }
 979
 980   ALWAYS_INLINE void SetDepth(const InlineInfoEncoding& encoding, uint32_t depth) {
 981     DCHECK_GT(depth, 0u);
 982     for (size_t d = 0; d < depth; ++d) {
 983       GetRegionAtDepth(encoding, d).StoreBit(0, d == depth - 1);  // Set is_last bit.
 984     }
 985   }
 986
 987   ALWAYS_INLINE uint32_t GetMethodIndexIdxAtDepth(const InlineInfoEncoding& encoding,
 988                                                   uint32_t depth) const {
 989     DCHECK(!EncodesArtMethodAtDepth(encoding, depth));
 990     return encoding.GetMethodIndexIdxEncoding().Load(GetRegionAtDepth(encoding, depth));
 991   }
 992
 993   ALWAYS_INLINE void SetMethodIndexIdxAtDepth(const InlineInfoEncoding& encoding,
 994                                               uint32_t depth,
 995                                               uint32_t index) {
 996     encoding.GetMethodIndexIdxEncoding().Store(GetRegionAtDepth(encoding, depth), index);
 997   }
 998
 999
1000   ALWAYS_INLINE uint32_t GetMethodIndexAtDepth(const InlineInfoEncoding& encoding,
1001                                                const MethodInfo& method_info,
1002                                                uint32_t depth) const {
1003     return method_info.GetMethodIndex(GetMethodIndexIdxAtDepth(encoding, depth));
1004   }
1005
1006   ALWAYS_INLINE uint32_t GetDexPcAtDepth(const InlineInfoEncoding& encoding,
1007                                          uint32_t depth) const {
1008     return encoding.GetDexPcEncoding().Load(GetRegionAtDepth(encoding, depth));
1009   }
1010
1011   ALWAYS_INLINE void SetDexPcAtDepth(const InlineInfoEncoding& encoding,
1012                                      uint32_t depth,
1013                                      uint32_t dex_pc) {
1014     encoding.GetDexPcEncoding().Store(GetRegionAtDepth(encoding, depth), dex_pc);
1015   }
1016
1017   ALWAYS_INLINE bool EncodesArtMethodAtDepth(const InlineInfoEncoding& encoding,
1018                                              uint32_t depth) const {
1019     return (encoding.GetExtraDataEncoding().Load(GetRegionAtDepth(encoding, depth)) & 1) == 0;
1020   }
1021
1022   ALWAYS_INLINE void SetExtraDataAtDepth(const InlineInfoEncoding& encoding,
1023                                          uint32_t depth,
1024                                          uint32_t extra_data) {
1025     encoding.GetExtraDataEncoding().Store(GetRegionAtDepth(encoding, depth), extra_data);
1026   }
1027
1028   ALWAYS_INLINE ArtMethod* GetArtMethodAtDepth(const InlineInfoEncoding& encoding,
1029                                                uint32_t depth) const {
1030     uint32_t low_bits = encoding.GetExtraDataEncoding().Load(GetRegionAtDepth(encoding, depth));
1031     uint32_t high_bits = encoding.GetMethodIndexIdxEncoding().Load(
1032         GetRegionAtDepth(encoding, depth));
1033     if (high_bits == 0) {
1034       return reinterpret_cast<ArtMethod*>(low_bits);
1035     } else {
1036       uint64_t address = high_bits;
1037       address = address << 32;
1038       return reinterpret_cast<ArtMethod*>(address | low_bits);
1039     }
1040   }
1041
1042   ALWAYS_INLINE uint32_t GetDexRegisterMapOffsetAtDepth(const InlineInfoEncoding& encoding,
1043                                                         uint32_t depth) const {
1044     return encoding.GetDexRegisterMapEncoding().Load(GetRegionAtDepth(encoding, depth));
1045   }
1046
1047   ALWAYS_INLINE void SetDexRegisterMapOffsetAtDepth(const InlineInfoEncoding& encoding,
1048                                                     uint32_t depth,
1049                                                     uint32_t offset) {
1050     encoding.GetDexRegisterMapEncoding().Store(GetRegionAtDepth(encoding, depth), offset);
1051   }
1052
1053   ALWAYS_INLINE bool HasDexRegisterMapAtDepth(const InlineInfoEncoding& encoding,
1054                                               uint32_t depth) const {
1055     return GetDexRegisterMapOffsetAtDepth(encoding, depth) != StackMap::kNoDexRegisterMap;
1056   }
1057
1058   void Dump(VariableIndentationOutputStream* vios,
1059             const CodeInfo& info,
1060             const MethodInfo& method_info,
1061             uint16_t* number_of_dex_registers) const;
1062
1063  private:
1064   ALWAYS_INLINE BitMemoryRegion GetRegionAtDepth(const InlineInfoEncoding& encoding,
1065                                                  uint32_t depth) const {
1066     size_t entry_size = encoding.BitSize();
1067     DCHECK_GT(entry_size, 0u);
1068     return region_.Subregion(depth * entry_size, entry_size);
1069   }
1070
1071   BitMemoryRegion region_;
1072 };
1073
1074 // Bit sized region encoding, may be more than 255 bits.
1075 class BitRegionEncoding {
1076  public:
1077   uint32_t num_bits = 0;
1078
1079   ALWAYS_INLINE size_t BitSize() const {
1080     return num_bits;
1081   }
1082
1083   template<typename Vector>
1084   void Encode(Vector* dest) const {
1085     EncodeUnsignedLeb128(dest, num_bits);  // Use leb in case num_bits is greater than 255.
1086   }
1087
1088   void Decode(const uint8_t** ptr) {
1089     num_bits = DecodeUnsignedLeb128(ptr);
1090   }
1091 };
1092
1093 // A table of bit sized encodings.
1094 template <typename Encoding>
1095 struct BitEncodingTable {
1096   static constexpr size_t kInvalidOffset = static_cast<size_t>(-1);
1097   // How the encoding is laid out (serialized).
1098   Encoding encoding;
1099
1100   // Number of entries in the table (serialized).
1101   size_t num_entries;
1102
1103   // Bit offset for the base of the table (computed).
1104   size_t bit_offset = kInvalidOffset;
1105
1106   template<typename Vector>
1107   void Encode(Vector* dest) const {
1108     EncodeUnsignedLeb128(dest, num_entries);
1109     encoding.Encode(dest);
1110   }
1111
1112   ALWAYS_INLINE void Decode(const uint8_t** ptr) {
1113     num_entries = DecodeUnsignedLeb128(ptr);
1114     encoding.Decode(ptr);
1115   }
1116
1117   // Set the bit offset in the table and adds the space used by the table to offset.
1118   void UpdateBitOffset(size_t* offset) {
1119     DCHECK(offset != nullptr);
1120     bit_offset = *offset;
1121     *offset += encoding.BitSize() * num_entries;
1122   }
1123
1124   // Return the bit region for the map at index i.
1125   ALWAYS_INLINE BitMemoryRegion BitRegion(MemoryRegion region, size_t index) const {
1126     DCHECK_NE(bit_offset, kInvalidOffset) << "Invalid table offset";
1127     DCHECK_LT(index, num_entries);
1128     const size_t map_size = encoding.BitSize();
1129     return BitMemoryRegion(region, bit_offset + index * map_size, map_size);
1130   }
1131 };
1132
1133 // A byte sized table of possible variable sized encodings.
1134 struct ByteSizedTable {
1135   static constexpr size_t kInvalidOffset = static_cast<size_t>(-1);
1136
1137   // Number of entries in the table (serialized).
1138   size_t num_entries = 0;
1139
1140   // Number of bytes of the table (serialized).
1141   size_t num_bytes;
1142
1143   // Bit offset for the base of the table (computed).
1144   size_t byte_offset = kInvalidOffset;
1145
1146   template<typename Vector>
1147   void Encode(Vector* dest) const {
1148     EncodeUnsignedLeb128(dest, num_entries);
1149     EncodeUnsignedLeb128(dest, num_bytes);
1150   }
1151
1152   ALWAYS_INLINE void Decode(const uint8_t** ptr) {
1153     num_entries = DecodeUnsignedLeb128(ptr);
1154     num_bytes = DecodeUnsignedLeb128(ptr);
1155   }
1156
1157   // Set the bit offset of the table. Adds the total bit size of the table to offset.
1158   void UpdateBitOffset(size_t* offset) {
1159     DCHECK(offset != nullptr);
1160     DCHECK_ALIGNED(*offset, kBitsPerByte);
1161     byte_offset = *offset / kBitsPerByte;
1162     *offset += num_bytes * kBitsPerByte;
1163   }
1164 };
1165
1166 // Format is [native pc, invoke type, method index].
1167 class InvokeInfoEncoding {
1168  public:
1169   void SetFromSizes(size_t native_pc_max,
1170                     size_t invoke_type_max,
1171                     size_t method_index_max) {
1172     total_bit_size_ = 0;
1173     DCHECK_EQ(kNativePcBitOffset, total_bit_size_);
1174     total_bit_size_ += MinimumBitsToStore(native_pc_max);
1175     invoke_type_bit_offset_ = total_bit_size_;
1176     total_bit_size_ += MinimumBitsToStore(invoke_type_max);
1177     method_index_bit_offset_ = total_bit_size_;
1178     total_bit_size_ += MinimumBitsToStore(method_index_max);
1179   }
1180
1181   ALWAYS_INLINE FieldEncoding GetNativePcEncoding() const {
1182     return FieldEncoding(kNativePcBitOffset, invoke_type_bit_offset_);
1183   }
1184
1185   ALWAYS_INLINE FieldEncoding GetInvokeTypeEncoding() const {
1186     return FieldEncoding(invoke_type_bit_offset_, method_index_bit_offset_);
1187   }
1188
1189   ALWAYS_INLINE FieldEncoding GetMethodIndexEncoding() const {
1190     return FieldEncoding(method_index_bit_offset_, total_bit_size_);
1191   }
1192
1193   ALWAYS_INLINE size_t BitSize() const {
1194     return total_bit_size_;
1195   }
1196
1197   template<typename Vector>
1198   void Encode(Vector* dest) const {
1199     static_assert(alignof(InvokeInfoEncoding) == 1, "Should not require alignment");
1200     const uint8_t* ptr = reinterpret_cast<const uint8_t*>(this);
1201     dest->insert(dest->end(), ptr, ptr + sizeof(*this));
1202   }
1203
1204   void Decode(const uint8_t** ptr) {
1205     *this = *reinterpret_cast<const InvokeInfoEncoding*>(*ptr);
1206     *ptr += sizeof(*this);
1207   }
1208
1209  private:
1210   static constexpr uint8_t kNativePcBitOffset = 0;
1211   uint8_t invoke_type_bit_offset_;
1212   uint8_t method_index_bit_offset_;
1213   uint8_t total_bit_size_;
1214 };
1215
1216 class InvokeInfo {
1217  public:
1218   explicit InvokeInfo(BitMemoryRegion region) : region_(region) {}
1219
1220   ALWAYS_INLINE uint32_t GetNativePcOffset(const InvokeInfoEncoding& encoding,
1221                                            InstructionSet instruction_set) const {
1222     CodeOffset offset(
1223         CodeOffset::FromCompressedOffset(encoding.GetNativePcEncoding().Load(region_)));
1224     return offset.Uint32Value(instruction_set);
1225   }
1226
1227   ALWAYS_INLINE void SetNativePcCodeOffset(const InvokeInfoEncoding& encoding,
1228                                            CodeOffset native_pc_offset) {
1229     encoding.GetNativePcEncoding().Store(region_, native_pc_offset.CompressedValue());
1230   }
1231
1232   ALWAYS_INLINE uint32_t GetInvokeType(const InvokeInfoEncoding& encoding) const {
1233     return encoding.GetInvokeTypeEncoding().Load(region_);
1234   }
1235
1236   ALWAYS_INLINE void SetInvokeType(const InvokeInfoEncoding& encoding, uint32_t invoke_type) {
1237     encoding.GetInvokeTypeEncoding().Store(region_, invoke_type);
1238   }
1239
1240   ALWAYS_INLINE uint32_t GetMethodIndexIdx(const InvokeInfoEncoding& encoding) const {
1241     return encoding.GetMethodIndexEncoding().Load(region_);
1242   }
1243
1244   ALWAYS_INLINE void SetMethodIndexIdx(const InvokeInfoEncoding& encoding,
1245                                        uint32_t method_index_idx) {
1246     encoding.GetMethodIndexEncoding().Store(region_, method_index_idx);
1247   }
1248
1249   ALWAYS_INLINE uint32_t GetMethodIndex(const InvokeInfoEncoding& encoding,
1250                                         MethodInfo method_info) const {
1251     return method_info.GetMethodIndex(GetMethodIndexIdx(encoding));
1252   }
1253
1254   bool IsValid() const { return region_.pointer() != nullptr; }
1255
1256  private:
1257   BitMemoryRegion region_;
1258 };
1259
1260 // Most of the fields are encoded as ULEB128 to save space.
1261 struct CodeInfoEncoding {
1262   static constexpr uint32_t kInvalidSize = static_cast<size_t>(-1);
1263   // Byte sized tables go first to avoid unnecessary alignment bits.
1264   ByteSizedTable dex_register_map;
1265   ByteSizedTable location_catalog;
1266   BitEncodingTable<StackMapEncoding> stack_map;
1267   BitEncodingTable<BitRegionEncoding> register_mask;
1268   BitEncodingTable<BitRegionEncoding> stack_mask;
1269   BitEncodingTable<InvokeInfoEncoding> invoke_info;
1270   BitEncodingTable<InlineInfoEncoding> inline_info;
1271
1272   CodeInfoEncoding() {}
1273
1274   explicit CodeInfoEncoding(const void* data) {
1275     const uint8_t* ptr = reinterpret_cast<const uint8_t*>(data);
1276     dex_register_map.Decode(&ptr);
1277     location_catalog.Decode(&ptr);
1278     stack_map.Decode(&ptr);
1279     register_mask.Decode(&ptr);
1280     stack_mask.Decode(&ptr);
1281     invoke_info.Decode(&ptr);
1282     if (stack_map.encoding.GetInlineInfoEncoding().BitSize() > 0) {
1283       inline_info.Decode(&ptr);
1284     } else {
1285       inline_info = BitEncodingTable<InlineInfoEncoding>();
1286     }
1287     cache_header_size =
1288         dchecked_integral_cast<uint32_t>(ptr - reinterpret_cast<const uint8_t*>(data));
1289     ComputeTableOffsets();
1290   }
1291
1292   // Compress is not const since it calculates cache_header_size. This is used by PrepareForFillIn.
1293   template<typename Vector>
1294   void Compress(Vector* dest) {
1295     dex_register_map.Encode(dest);
1296     location_catalog.Encode(dest);
1297     stack_map.Encode(dest);
1298     register_mask.Encode(dest);
1299     stack_mask.Encode(dest);
1300     invoke_info.Encode(dest);
1301     if (stack_map.encoding.GetInlineInfoEncoding().BitSize() > 0) {
1302       inline_info.Encode(dest);
1303     }
1304     cache_header_size = dest->size();
1305   }
1306
1307   ALWAYS_INLINE void ComputeTableOffsets() {
1308     // Skip the header.
1309     size_t bit_offset = HeaderSize() * kBitsPerByte;
1310     // The byte tables must be aligned so they must go first.
1311     dex_register_map.UpdateBitOffset(&bit_offset);
1312     location_catalog.UpdateBitOffset(&bit_offset);
1313     // Other tables don't require alignment.
1314     stack_map.UpdateBitOffset(&bit_offset);
1315     register_mask.UpdateBitOffset(&bit_offset);
1316     stack_mask.UpdateBitOffset(&bit_offset);
1317     invoke_info.UpdateBitOffset(&bit_offset);
1318     inline_info.UpdateBitOffset(&bit_offset);
1319     cache_non_header_size = RoundUp(bit_offset, kBitsPerByte) / kBitsPerByte - HeaderSize();
1320   }
1321
1322   ALWAYS_INLINE size_t HeaderSize() const {
1323     DCHECK_NE(cache_header_size, kInvalidSize) << "Uninitialized";
1324     return cache_header_size;
1325   }
1326
1327   ALWAYS_INLINE size_t NonHeaderSize() const {
1328     DCHECK_NE(cache_non_header_size, kInvalidSize) << "Uninitialized";
1329     return cache_non_header_size;
1330   }
1331
1332  private:
1333   // Computed fields (not serialized).
1334   // Header size in bytes, cached to avoid needing to re-decoding the encoding in HeaderSize.
1335   uint32_t cache_header_size = kInvalidSize;
1336   // Non header size in bytes, cached to avoid needing to re-decoding the encoding in NonHeaderSize.
1337   uint32_t cache_non_header_size = kInvalidSize;
1338 };
1339
1340 /**
1341  * Wrapper around all compiler information collected for a method.
1342  * The information is of the form:
1343  *
1344  *   [CodeInfoEncoding, DexRegisterMap+, DexLocationCatalog+, StackMap+, RegisterMask+, StackMask+,
1345  *    InlineInfo*]
1346  *
1347  * where CodeInfoEncoding is of the form:
1348  *
1349  *   [ByteSizedTable(dex_register_map), ByteSizedTable(location_catalog),
1350  *    BitEncodingTable<StackMapEncoding>, BitEncodingTable<BitRegionEncoding>,
1351  *    BitEncodingTable<BitRegionEncoding>, BitEncodingTable<InlineInfoEncoding>]
1352  */
1353 class CodeInfo {
1354  public:
1355   explicit CodeInfo(MemoryRegion region) : region_(region) {
1356   }
1357
1358   explicit CodeInfo(const void* data) {
1359     CodeInfoEncoding encoding = CodeInfoEncoding(data);
1360     region_ = MemoryRegion(const_cast<void*>(data),
1361                            encoding.HeaderSize() + encoding.NonHeaderSize());
1362   }
1363
1364   CodeInfoEncoding ExtractEncoding() const {
1365     CodeInfoEncoding encoding(region_.begin());
1366     AssertValidStackMap(encoding);
1367     return encoding;
1368   }
1369
1370   bool HasInlineInfo(const CodeInfoEncoding& encoding) const {
1371     return encoding.stack_map.encoding.GetInlineInfoEncoding().BitSize() > 0;
1372   }
1373
1374   DexRegisterLocationCatalog GetDexRegisterLocationCatalog(const CodeInfoEncoding& encoding) const {
1375     return DexRegisterLocationCatalog(region_.Subregion(encoding.location_catalog.byte_offset,
1376                                                         encoding.location_catalog.num_bytes));
1377   }
1378
1379   ALWAYS_INLINE size_t GetNumberOfStackMaskBits(const CodeInfoEncoding& encoding) const {
1380     return encoding.stack_mask.encoding.BitSize();
1381   }
1382
1383   ALWAYS_INLINE StackMap GetStackMapAt(size_t index, const CodeInfoEncoding& encoding) const {
1384     return StackMap(encoding.stack_map.BitRegion(region_, index));
1385   }
1386
1387   BitMemoryRegion GetStackMask(size_t index, const CodeInfoEncoding& encoding) const {
1388     return encoding.stack_mask.BitRegion(region_, index);
1389   }
1390
1391   BitMemoryRegion GetStackMaskOf(const CodeInfoEncoding& encoding,
1392                                  const StackMap& stack_map) const {
1393     return GetStackMask(stack_map.GetStackMaskIndex(encoding.stack_map.encoding), encoding);
1394   }
1395
1396   BitMemoryRegion GetRegisterMask(size_t index, const CodeInfoEncoding& encoding) const {
1397     return encoding.register_mask.BitRegion(region_, index);
1398   }
1399
1400   uint32_t GetRegisterMaskOf(const CodeInfoEncoding& encoding, const StackMap& stack_map) const {
1401     size_t index = stack_map.GetRegisterMaskIndex(encoding.stack_map.encoding);
1402     return GetRegisterMask(index, encoding).LoadBits(0u, encoding.register_mask.encoding.BitSize());
1403   }
1404
1405   uint32_t GetNumberOfLocationCatalogEntries(const CodeInfoEncoding& encoding) const {
1406     return encoding.location_catalog.num_entries;
1407   }
1408
1409   uint32_t GetDexRegisterLocationCatalogSize(const CodeInfoEncoding& encoding) const {
1410     return encoding.location_catalog.num_bytes;
1411   }
1412
1413   uint32_t GetNumberOfStackMaps(const CodeInfoEncoding& encoding) const {
1414     return encoding.stack_map.num_entries;
1415   }
1416
1417   // Get the size of all the stack maps of this CodeInfo object, in bits. Not byte aligned.
1418   ALWAYS_INLINE size_t GetStackMapsSizeInBits(const CodeInfoEncoding& encoding) const {
1419     return encoding.stack_map.encoding.BitSize() * GetNumberOfStackMaps(encoding);
1420   }
1421
1422   InvokeInfo GetInvokeInfo(const CodeInfoEncoding& encoding, size_t index) const {
1423     return InvokeInfo(encoding.invoke_info.BitRegion(region_, index));
1424   }
1425
1426   DexRegisterMap GetDexRegisterMapOf(StackMap stack_map,
1427                                      const CodeInfoEncoding& encoding,
1428                                      size_t number_of_dex_registers) const {
1429     if (!stack_map.HasDexRegisterMap(encoding.stack_map.encoding)) {
1430       return DexRegisterMap();
1431     }
1432     const uint32_t offset = encoding.dex_register_map.byte_offset +
1433         stack_map.GetDexRegisterMapOffset(encoding.stack_map.encoding);
1434     size_t size = ComputeDexRegisterMapSizeOf(encoding, offset, number_of_dex_registers);
1435     return DexRegisterMap(region_.Subregion(offset, size));
1436   }
1437
1438   size_t GetDexRegisterMapsSize(const CodeInfoEncoding& encoding,
1439                                 uint32_t number_of_dex_registers) const {
1440     size_t total = 0;
1441     for (size_t i = 0, e = GetNumberOfStackMaps(encoding); i < e; ++i) {
1442       StackMap stack_map = GetStackMapAt(i, encoding);
1443       DexRegisterMap map(GetDexRegisterMapOf(stack_map, encoding, number_of_dex_registers));
1444       total += map.Size();
1445     }
1446     return total;
1447   }
1448
1449   // Return the `DexRegisterMap` pointed by `inline_info` at depth `depth`.
1450   DexRegisterMap GetDexRegisterMapAtDepth(uint8_t depth,
1451                                           InlineInfo inline_info,
1452                                           const CodeInfoEncoding& encoding,
1453                                           uint32_t number_of_dex_registers) const {
1454     if (!inline_info.HasDexRegisterMapAtDepth(encoding.inline_info.encoding, depth)) {
1455       return DexRegisterMap();
1456     } else {
1457       uint32_t offset = encoding.dex_register_map.byte_offset +
1458           inline_info.GetDexRegisterMapOffsetAtDepth(encoding.inline_info.encoding, depth);
1459       size_t size = ComputeDexRegisterMapSizeOf(encoding, offset, number_of_dex_registers);
1460       return DexRegisterMap(region_.Subregion(offset, size));
1461     }
1462   }
1463
1464   InlineInfo GetInlineInfo(size_t index, const CodeInfoEncoding& encoding) const {
1465     // Since we do not know the depth, we just return the whole remaining map. The caller may
1466     // access the inline info for arbitrary depths. To return the precise inline info we would need
1467     // to count the depth before returning.
1468     // TODO: Clean this up.
1469     const size_t bit_offset = encoding.inline_info.bit_offset +
1470         index * encoding.inline_info.encoding.BitSize();
1471     return InlineInfo(BitMemoryRegion(region_, bit_offset, region_.size_in_bits() - bit_offset));
1472   }
1473
1474   InlineInfo GetInlineInfoOf(StackMap stack_map, const CodeInfoEncoding& encoding) const {
1475     DCHECK(stack_map.HasInlineInfo(encoding.stack_map.encoding));
1476     uint32_t index = stack_map.GetInlineInfoIndex(encoding.stack_map.encoding);
1477     return GetInlineInfo(index, encoding);
1478   }
1479
1480   StackMap GetStackMapForDexPc(uint32_t dex_pc, const CodeInfoEncoding& encoding) const {
1481     for (size_t i = 0, e = GetNumberOfStackMaps(encoding); i < e; ++i) {
1482       StackMap stack_map = GetStackMapAt(i, encoding);
1483       if (stack_map.GetDexPc(encoding.stack_map.encoding) == dex_pc) {
1484         return stack_map;
1485       }
1486     }
1487     return StackMap();
1488   }
1489
1490   // Searches the stack map list backwards because catch stack maps are stored
1491   // at the end.
1492   StackMap GetCatchStackMapForDexPc(uint32_t dex_pc, const CodeInfoEncoding& encoding) const {
1493     for (size_t i = GetNumberOfStackMaps(encoding); i > 0; --i) {
1494       StackMap stack_map = GetStackMapAt(i - 1, encoding);
1495       if (stack_map.GetDexPc(encoding.stack_map.encoding) == dex_pc) {
1496         return stack_map;
1497       }
1498     }
1499     return StackMap();
1500   }
1501
1502   StackMap GetOsrStackMapForDexPc(uint32_t dex_pc, const CodeInfoEncoding& encoding) const {
1503     size_t e = GetNumberOfStackMaps(encoding);
1504     if (e == 0) {
1505       // There cannot be OSR stack map if there is no stack map.
1506       return StackMap();
1507     }
1508     // Walk over all stack maps. If two consecutive stack maps are identical, then we
1509     // have found a stack map suitable for OSR.
1510     const StackMapEncoding& stack_map_encoding = encoding.stack_map.encoding;
1511     for (size_t i = 0; i < e - 1; ++i) {
1512       StackMap stack_map = GetStackMapAt(i, encoding);
1513       if (stack_map.GetDexPc(stack_map_encoding) == dex_pc) {
1514         StackMap other = GetStackMapAt(i + 1, encoding);
1515         if (other.GetDexPc(stack_map_encoding) == dex_pc &&
1516             other.GetNativePcOffset(stack_map_encoding, kRuntimeISA) ==
1517                 stack_map.GetNativePcOffset(stack_map_encoding, kRuntimeISA)) {
1518           DCHECK_EQ(other.GetDexRegisterMapOffset(stack_map_encoding),
1519                     stack_map.GetDexRegisterMapOffset(stack_map_encoding));
1520           DCHECK(!stack_map.HasInlineInfo(stack_map_encoding));
1521           if (i < e - 2) {
1522             // Make sure there are not three identical stack maps following each other.
1523             DCHECK_NE(
1524                 stack_map.GetNativePcOffset(stack_map_encoding, kRuntimeISA),
1525                 GetStackMapAt(i + 2, encoding).GetNativePcOffset(stack_map_encoding, kRuntimeISA));
1526           }
1527           return stack_map;
1528         }
1529       }
1530     }
1531     return StackMap();
1532   }
1533
1534   StackMap GetStackMapForNativePcOffset(uint32_t native_pc_offset,
1535                                         const CodeInfoEncoding& encoding) const {
1536     // TODO: Safepoint stack maps are sorted by native_pc_offset but catch stack
1537     //       maps are not. If we knew that the method does not have try/catch,
1538     //       we could do binary search.
1539     for (size_t i = 0, e = GetNumberOfStackMaps(encoding); i < e; ++i) {
1540       StackMap stack_map = GetStackMapAt(i, encoding);
1541       if (stack_map.GetNativePcOffset(encoding.stack_map.encoding, kRuntimeISA) ==
1542           native_pc_offset) {
1543         return stack_map;
1544       }
1545     }
1546     return StackMap();
1547   }
1548
1549   InvokeInfo GetInvokeInfoForNativePcOffset(uint32_t native_pc_offset,
1550                                             const CodeInfoEncoding& encoding) {
1551     for (size_t index = 0; index < encoding.invoke_info.num_entries; index++) {
1552       InvokeInfo item = GetInvokeInfo(encoding, index);
1553       if (item.GetNativePcOffset(encoding.invoke_info.encoding, kRuntimeISA) == native_pc_offset) {
1554         return item;
1555       }
1556     }
1557     return InvokeInfo(BitMemoryRegion());
1558   }
1559
1560   // Dump this CodeInfo object on `os`.  `code_offset` is the (absolute)
1561   // native PC of the compiled method and `number_of_dex_registers` the
1562   // number of Dex virtual registers used in this method.  If
1563   // `dump_stack_maps` is true, also dump the stack maps and the
1564   // associated Dex register maps.
1565   void Dump(VariableIndentationOutputStream* vios,
1566             uint32_t code_offset,
1567             uint16_t number_of_dex_registers,
1568             bool dump_stack_maps,
1569             InstructionSet instruction_set,
1570             const MethodInfo& method_info) const;
1571
1572   // Check that the code info has valid stack map and abort if it does not.
1573   void AssertValidStackMap(const CodeInfoEncoding& encoding) const {
1574     if (region_.size() != 0 && region_.size_in_bits() < GetStackMapsSizeInBits(encoding)) {
1575       LOG(FATAL) << region_.size() << "\n"
1576                  << encoding.HeaderSize() << "\n"
1577                  << encoding.NonHeaderSize() << "\n"
1578                  << encoding.location_catalog.num_entries << "\n"
1579                  << encoding.stack_map.num_entries << "\n"
1580                  << encoding.stack_map.encoding.BitSize();
1581     }
1582   }
1583
1584  private:
1585   // Compute the size of the Dex register map associated to the stack map at
1586   // `dex_register_map_offset_in_code_info`.
1587   size_t ComputeDexRegisterMapSizeOf(const CodeInfoEncoding& encoding,
1588                                      uint32_t dex_register_map_offset_in_code_info,
1589                                      uint16_t number_of_dex_registers) const {
1590     // Offset where the actual mapping data starts within art::DexRegisterMap.
1591     size_t location_mapping_data_offset_in_dex_register_map =
1592         DexRegisterMap::GetLocationMappingDataOffset(number_of_dex_registers);
1593     // Create a temporary art::DexRegisterMap to be able to call
1594     // art::DexRegisterMap::GetNumberOfLiveDexRegisters and
1595     DexRegisterMap dex_register_map_without_locations(
1596         MemoryRegion(region_.Subregion(dex_register_map_offset_in_code_info,
1597                                        location_mapping_data_offset_in_dex_register_map)));
1598     size_t number_of_live_dex_registers =
1599         dex_register_map_without_locations.GetNumberOfLiveDexRegisters(number_of_dex_registers);
1600     size_t location_mapping_data_size_in_bits =
1601         DexRegisterMap::SingleEntrySizeInBits(GetNumberOfLocationCatalogEntries(encoding))
1602         * number_of_live_dex_registers;
1603     size_t location_mapping_data_size_in_bytes =
1604         RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte;
1605     size_t dex_register_map_size =
1606         location_mapping_data_offset_in_dex_register_map + location_mapping_data_size_in_bytes;
1607     return dex_register_map_size;
1608   }
1609
1610   // Compute the size of a Dex register location catalog starting at offset `origin`
1611   // in `region_` and containing `number_of_dex_locations` entries.
1612   size_t ComputeDexRegisterLocationCatalogSize(uint32_t origin,
1613                                                uint32_t number_of_dex_locations) const {
1614     // TODO: Ideally, we would like to use art::DexRegisterLocationCatalog::Size or
1615     // art::DexRegisterLocationCatalog::FindLocationOffset, but the
1616     // DexRegisterLocationCatalog is not yet built.  Try to factor common code.
1617     size_t offset = origin + DexRegisterLocationCatalog::kFixedSize;
1618
1619     // Skip the first `number_of_dex_locations - 1` entries.
1620     for (uint16_t i = 0; i < number_of_dex_locations; ++i) {
1621       // Read the first next byte and inspect its first 3 bits to decide
1622       // whether it is a short or a large location.
1623       DexRegisterLocationCatalog::ShortLocation first_byte =
1624           region_.LoadUnaligned<DexRegisterLocationCatalog::ShortLocation>(offset);
1625       DexRegisterLocation::Kind kind =
1626           DexRegisterLocationCatalog::ExtractKindFromShortLocation(first_byte);
1627       if (DexRegisterLocation::IsShortLocationKind(kind)) {
1628         // Short location.  Skip the current byte.
1629         offset += DexRegisterLocationCatalog::SingleShortEntrySize();
1630       } else {
1631         // Large location.  Skip the 5 next bytes.
1632         offset += DexRegisterLocationCatalog::SingleLargeEntrySize();
1633       }
1634     }
1635     size_t size = offset - origin;
1636     return size;
1637   }
1638
1639   MemoryRegion region_;
1640   friend class StackMapStream;
1641 };
1642
1643 #undef ELEMENT_BYTE_OFFSET_AFTER
1644 #undef ELEMENT_BIT_OFFSET_AFTER
1645
1646 }  // namespace art
1647
1648 #endif  // ART_RUNTIME_STACK_MAP_H_