stack_map.h revision a552e1c0584b8ab63150510286478c68cdbce13f 
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 "memory_region.h"
22#include "utils.h"
23
24namespace 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.
29static constexpr ssize_t kFrameSlotSize = 4;
30
31// Size of Dex virtual registers.
32static constexpr size_t kVRegSize = 4;
33
34class 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 */
46class 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.
84class 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 */
234class 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 */
472class 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 */
682class StackMap {
683 public:
684  explicit StackMap(MemoryRegion region) : region_(region) {}
685
686  uint32_t GetDexPc(const CodeInfo& info) const;
687
688  void SetDexPc(const CodeInfo& info, uint32_t dex_pc);
689
690  uint32_t GetNativePcOffset(const CodeInfo& info) const;
691
692  void SetNativePcOffset(const CodeInfo& info, uint32_t native_pc_offset);
693
694  uint32_t GetDexRegisterMapOffset(const CodeInfo& info) const;
695
696  void SetDexRegisterMapOffset(const CodeInfo& info, uint32_t offset);
697
698  uint32_t GetInlineDescriptorOffset(const CodeInfo& info) const;
699
700  void SetInlineDescriptorOffset(const CodeInfo& info, uint32_t offset);
701
702  uint32_t GetRegisterMask(const CodeInfo& info) const;
703
704  void SetRegisterMask(const CodeInfo& info, uint32_t mask);
705
706  MemoryRegion GetStackMask(const CodeInfo& info) const;
707
708  void SetStackMask(const CodeInfo& info, const BitVector& sp_map) {
709    MemoryRegion region = GetStackMask(info);
710    for (size_t i = 0; i < region.size_in_bits(); i++) {
711      region.StoreBit(i, sp_map.IsBitSet(i));
712    }
713  }
714
715  bool HasDexRegisterMap(const CodeInfo& info) const {
716    return GetDexRegisterMapOffset(info) != kNoDexRegisterMap;
717  }
718
719  bool HasInlineInfo(const CodeInfo& info) const {
720    return GetInlineDescriptorOffset(info) != kNoInlineInfo;
721  }
722
723  bool Equals(const StackMap& other) const {
724    return region_.pointer() == other.region_.pointer()
725       && region_.size() == other.region_.size();
726  }
727
728  static size_t ComputeStackMapSize(size_t stack_mask_size,
729                                    bool has_inline_info,
730                                    bool is_small_inline_info,
731                                    bool is_small_dex_map,
732                                    bool is_small_dex_pc,
733                                    bool is_small_native_pc);
734
735  static size_t ComputeStackMapSize(size_t stack_mask_size,
736                                    size_t inline_info_size,
737                                    size_t dex_register_map_size,
738                                    size_t dex_pc_max,
739                                    size_t native_pc_max);
740
741  // TODO: Revisit this abstraction if we allow 3 bytes encoding.
742  typedef uint8_t kSmallEncoding;
743  typedef uint32_t kLargeEncoding;
744  static constexpr size_t kBytesForSmallEncoding = sizeof(kSmallEncoding);
745  static constexpr size_t kBitsForSmallEncoding = kBitsPerByte * kBytesForSmallEncoding;
746  static constexpr size_t kBytesForLargeEncoding = sizeof(kLargeEncoding);
747  static constexpr size_t kBitsForLargeEncoding = kBitsPerByte * kBytesForLargeEncoding;
748
749  // Special (invalid) offset for the DexRegisterMapOffset field meaning
750  // that there is no Dex register map for this stack map.
751  static constexpr uint32_t kNoDexRegisterMap = -1;
752  static constexpr uint32_t kNoDexRegisterMapSmallEncoding =
753      std::numeric_limits<kSmallEncoding>::max();
754
755  // Special (invalid) offset for the InlineDescriptorOffset field meaning
756  // that there is no inline info for this stack map.
757  static constexpr uint32_t kNoInlineInfo = -1;
758  static constexpr uint32_t kNoInlineInfoSmallEncoding =
759    std::numeric_limits<kSmallEncoding>::max();
760
761  // Returns the number of bytes needed for an entry in the StackMap.
762  static size_t NumberOfBytesForEntry(bool small_encoding) {
763    return small_encoding ? kBytesForSmallEncoding : kBytesForLargeEncoding;
764  }
765
766 private:
767  // TODO: Instead of plain types such as "uint32_t", introduce
768  // typedefs (and document the memory layout of StackMap).
769  static constexpr int kRegisterMaskOffset = 0;
770  static constexpr int kFixedSize = kRegisterMaskOffset + sizeof(uint32_t);
771  static constexpr int kStackMaskOffset = kFixedSize;
772
773  MemoryRegion region_;
774
775  friend class CodeInfo;
776  friend class StackMapStream;
777};
778
779
780/**
781 * Wrapper around all compiler information collected for a method.
782 * The information is of the form:
783 * [overall_size, number_of_location_catalog_entries, number_of_stack_maps, stack_mask_size,
784 * DexRegisterLocationCatalog+, StackMap+, DexRegisterMap+, InlineInfo*].
785 */
786class CodeInfo {
787 public:
788  explicit CodeInfo(MemoryRegion region) : region_(region) {}
789
790  explicit CodeInfo(const void* data) {
791    uint32_t size = reinterpret_cast<const uint32_t*>(data)[0];
792    region_ = MemoryRegion(const_cast<void*>(data), size);
793  }
794
795  void SetEncoding(size_t inline_info_size,
796                   size_t dex_register_map_size,
797                   size_t dex_pc_max,
798                   size_t native_pc_max) {
799    if (inline_info_size != 0) {
800      region_.StoreBit(kHasInlineInfoBitOffset, 1);
801      region_.StoreBit(kHasSmallInlineInfoBitOffset, IsUint<StackMap::kBitsForSmallEncoding>(
802          // + 1 to also encode kNoInlineInfo: if an inline info offset
803          // is at 0xFF, we want to overflow to a larger encoding, because it will
804          // conflict with kNoInlineInfo.
805          // The offset is relative to the dex register map. TODO: Change this.
806          inline_info_size + dex_register_map_size + 1));
807    } else {
808      region_.StoreBit(kHasInlineInfoBitOffset, 0);
809      region_.StoreBit(kHasSmallInlineInfoBitOffset, 0);
810    }
811    region_.StoreBit(kHasSmallDexRegisterMapBitOffset,
812                     // + 1 to also encode kNoDexRegisterMap: if a dex register map offset
813                     // is at 0xFF, we want to overflow to a larger encoding, because it will
814                     // conflict with kNoDexRegisterMap.
815                     IsUint<StackMap::kBitsForSmallEncoding>(dex_register_map_size + 1));
816    region_.StoreBit(kHasSmallDexPcBitOffset, IsUint<StackMap::kBitsForSmallEncoding>(dex_pc_max));
817    region_.StoreBit(kHasSmallNativePcBitOffset,
818                     IsUint<StackMap::kBitsForSmallEncoding>(native_pc_max));
819  }
820
821  bool HasInlineInfo() const {
822    return region_.LoadBit(kHasInlineInfoBitOffset);
823  }
824
825  bool HasSmallInlineInfo() const {
826    return region_.LoadBit(kHasSmallInlineInfoBitOffset);
827  }
828
829  bool HasSmallDexRegisterMap() const {
830    return region_.LoadBit(kHasSmallDexRegisterMapBitOffset);
831  }
832
833  bool HasSmallNativePc() const {
834    return region_.LoadBit(kHasSmallNativePcBitOffset);
835  }
836
837  bool HasSmallDexPc() const {
838    return region_.LoadBit(kHasSmallDexPcBitOffset);
839  }
840
841  size_t ComputeStackMapRegisterMaskOffset() const {
842    return StackMap::kRegisterMaskOffset;
843  }
844
845  size_t ComputeStackMapStackMaskOffset() const {
846    return StackMap::kStackMaskOffset;
847  }
848
849  size_t ComputeStackMapDexPcOffset() const {
850    return ComputeStackMapStackMaskOffset() + GetStackMaskSize();
851  }
852
853  size_t ComputeStackMapNativePcOffset() const {
854    return ComputeStackMapDexPcOffset()
855        + (HasSmallDexPc() ? sizeof(uint8_t) : sizeof(uint32_t));
856  }
857
858  size_t ComputeStackMapDexRegisterMapOffset() const {
859    return ComputeStackMapNativePcOffset()
860        + (HasSmallNativePc() ? sizeof(uint8_t) : sizeof(uint32_t));
861  }
862
863  size_t ComputeStackMapInlineInfoOffset() const {
864    CHECK(HasInlineInfo());
865    return ComputeStackMapDexRegisterMapOffset()
866        + (HasSmallDexRegisterMap() ? sizeof(uint8_t) : sizeof(uint32_t));
867  }
868
869  uint32_t GetDexRegisterLocationCatalogOffset() const {
870    return kFixedSize;
871  }
872
873  DexRegisterLocationCatalog GetDexRegisterLocationCatalog() const {
874    return DexRegisterLocationCatalog(region_.Subregion(
875        GetDexRegisterLocationCatalogOffset(),
876        GetDexRegisterLocationCatalogSize()));
877  }
878
879  StackMap GetStackMapAt(size_t i) const {
880    size_t size = StackMapSize();
881    return StackMap(GetStackMaps().Subregion(i * size, size));
882  }
883
884  uint32_t GetOverallSize() const {
885    return region_.LoadUnaligned<uint32_t>(kOverallSizeOffset);
886  }
887
888  void SetOverallSize(uint32_t size) {
889    region_.StoreUnaligned<uint32_t>(kOverallSizeOffset, size);
890  }
891
892  uint32_t GetNumberOfDexRegisterLocationCatalogEntries() const {
893    return region_.LoadUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset);
894  }
895
896  void SetNumberOfDexRegisterLocationCatalogEntries(uint32_t num_entries) {
897    region_.StoreUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset, num_entries);
898  }
899
900  uint32_t GetDexRegisterLocationCatalogSize() const {
901    return ComputeDexRegisterLocationCatalogSize(GetDexRegisterLocationCatalogOffset(),
902                                                 GetNumberOfDexRegisterLocationCatalogEntries());
903  }
904
905  uint32_t GetStackMaskSize() const {
906    return region_.LoadUnaligned<uint32_t>(kStackMaskSizeOffset);
907  }
908
909  void SetStackMaskSize(uint32_t size) {
910    region_.StoreUnaligned<uint32_t>(kStackMaskSizeOffset, size);
911  }
912
913  size_t GetNumberOfStackMaps() const {
914    return region_.LoadUnaligned<uint32_t>(kNumberOfStackMapsOffset);
915  }
916
917  void SetNumberOfStackMaps(uint32_t number_of_stack_maps) {
918    region_.StoreUnaligned<uint32_t>(kNumberOfStackMapsOffset, number_of_stack_maps);
919  }
920
921  // Get the size of one stack map of this CodeInfo object, in bytes.
922  // All stack maps of a CodeInfo have the same size.
923  size_t StackMapSize() const {
924    return StackMap::ComputeStackMapSize(GetStackMaskSize(),
925                                         HasInlineInfo(),
926                                         HasSmallInlineInfo(),
927                                         HasSmallDexRegisterMap(),
928                                         HasSmallDexPc(),
929                                         HasSmallNativePc());
930  }
931
932  // Get the size all the stack maps of this CodeInfo object, in bytes.
933  size_t GetStackMapsSize() const {
934    return StackMapSize() * GetNumberOfStackMaps();
935  }
936
937  size_t GetDexRegisterMapsOffset() const {
938    return GetStackMapsOffset() + GetStackMapsSize();
939  }
940
941  uint32_t GetStackMapsOffset() const {
942    return GetDexRegisterLocationCatalogOffset() + GetDexRegisterLocationCatalogSize();
943  }
944
945  DexRegisterMap GetDexRegisterMapOf(StackMap stack_map, uint32_t number_of_dex_registers) const {
946    DCHECK(stack_map.HasDexRegisterMap(*this));
947    uint32_t offset = GetDexRegisterMapsOffset() + stack_map.GetDexRegisterMapOffset(*this);
948    size_t size = ComputeDexRegisterMapSizeOf(offset, number_of_dex_registers);
949    return DexRegisterMap(region_.Subregion(offset, size));
950  }
951
952  InlineInfo GetInlineInfoOf(StackMap stack_map) const {
953    DCHECK(stack_map.HasInlineInfo(*this));
954    uint32_t offset = stack_map.GetInlineDescriptorOffset(*this) + GetDexRegisterMapsOffset();
955    uint8_t depth = region_.LoadUnaligned<uint8_t>(offset);
956    return InlineInfo(region_.Subregion(offset,
957        InlineInfo::kFixedSize + depth * InlineInfo::SingleEntrySize()));
958  }
959
960  StackMap GetStackMapForDexPc(uint32_t dex_pc) const {
961    for (size_t i = 0, e = GetNumberOfStackMaps(); i < e; ++i) {
962      StackMap stack_map = GetStackMapAt(i);
963      if (stack_map.GetDexPc(*this) == dex_pc) {
964        return stack_map;
965      }
966    }
967    LOG(FATAL) << "Unreachable";
968    UNREACHABLE();
969  }
970
971  StackMap GetStackMapForNativePcOffset(uint32_t native_pc_offset) const {
972    // TODO: stack maps are sorted by native pc, we can do a binary search.
973    for (size_t i = 0, e = GetNumberOfStackMaps(); i < e; ++i) {
974      StackMap stack_map = GetStackMapAt(i);
975      if (stack_map.GetNativePcOffset(*this) == native_pc_offset) {
976        return stack_map;
977      }
978    }
979    LOG(FATAL) << "Unreachable";
980    UNREACHABLE();
981  }
982
983  void Dump(std::ostream& os, uint16_t number_of_dex_registers) const;
984  void DumpStackMapHeader(std::ostream& os, size_t stack_map_num) const;
985
986 private:
987  // TODO: Instead of plain types such as "uint32_t", introduce
988  // typedefs (and document the memory layout of CodeInfo).
989  static constexpr int kOverallSizeOffset = 0;
990  static constexpr int kEncodingInfoOffset = kOverallSizeOffset + sizeof(uint32_t);
991  static constexpr int kNumberOfDexRegisterLocationCatalogEntriesOffset =
992      kEncodingInfoOffset + sizeof(uint8_t);
993  static constexpr int kNumberOfStackMapsOffset =
994      kNumberOfDexRegisterLocationCatalogEntriesOffset + sizeof(uint32_t);
995  static constexpr int kStackMaskSizeOffset = kNumberOfStackMapsOffset + sizeof(uint32_t);
996  static constexpr int kFixedSize = kStackMaskSizeOffset + sizeof(uint32_t);
997
998  static constexpr int kHasInlineInfoBitOffset = (kEncodingInfoOffset * kBitsPerByte);
999  static constexpr int kHasSmallInlineInfoBitOffset = kHasInlineInfoBitOffset + 1;
1000  static constexpr int kHasSmallDexRegisterMapBitOffset = kHasSmallInlineInfoBitOffset + 1;
1001  static constexpr int kHasSmallDexPcBitOffset = kHasSmallDexRegisterMapBitOffset + 1;
1002  static constexpr int kHasSmallNativePcBitOffset = kHasSmallDexPcBitOffset + 1;
1003
1004  MemoryRegion GetStackMaps() const {
1005    return region_.size() == 0
1006        ? MemoryRegion()
1007        : region_.Subregion(GetStackMapsOffset(), GetStackMapsSize());
1008  }
1009
1010  // Compute the size of the Dex register map associated to the stack map at
1011  // `dex_register_map_offset_in_code_info`.
1012  size_t ComputeDexRegisterMapSizeOf(uint32_t dex_register_map_offset_in_code_info,
1013                                     uint16_t number_of_dex_registers) const {
1014    // Offset where the actual mapping data starts within art::DexRegisterMap.
1015    size_t location_mapping_data_offset_in_dex_register_map =
1016        DexRegisterMap::GetLocationMappingDataOffset(number_of_dex_registers);
1017    // Create a temporary art::DexRegisterMap to be able to call
1018    // art::DexRegisterMap::GetNumberOfLiveDexRegisters and
1019    DexRegisterMap dex_register_map_without_locations(
1020        MemoryRegion(region_.Subregion(dex_register_map_offset_in_code_info,
1021                                       location_mapping_data_offset_in_dex_register_map)));
1022    size_t number_of_live_dex_registers =
1023        dex_register_map_without_locations.GetNumberOfLiveDexRegisters(number_of_dex_registers);
1024    size_t location_mapping_data_size_in_bits =
1025        DexRegisterMap::SingleEntrySizeInBits(GetNumberOfDexRegisterLocationCatalogEntries())
1026        * number_of_live_dex_registers;
1027    size_t location_mapping_data_size_in_bytes =
1028        RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte;
1029    size_t dex_register_map_size =
1030        location_mapping_data_offset_in_dex_register_map + location_mapping_data_size_in_bytes;
1031    return dex_register_map_size;
1032  }
1033
1034  // Compute the size of a Dex register location catalog starting at offset `origin`
1035  // in `region_` and containing `number_of_dex_locations` entries.
1036  size_t ComputeDexRegisterLocationCatalogSize(uint32_t origin,
1037                                               uint32_t number_of_dex_locations) const {
1038    // TODO: Ideally, we would like to use art::DexRegisterLocationCatalog::Size or
1039    // art::DexRegisterLocationCatalog::FindLocationOffset, but the
1040    // DexRegisterLocationCatalog is not yet built.  Try to factor common code.
1041    size_t offset = origin + DexRegisterLocationCatalog::kFixedSize;
1042
1043    // Skip the first `number_of_dex_locations - 1` entries.
1044    for (uint16_t i = 0; i < number_of_dex_locations; ++i) {
1045      // Read the first next byte and inspect its first 3 bits to decide
1046      // whether it is a short or a large location.
1047      DexRegisterLocationCatalog::ShortLocation first_byte =
1048          region_.LoadUnaligned<DexRegisterLocationCatalog::ShortLocation>(offset);
1049      DexRegisterLocation::Kind kind =
1050          DexRegisterLocationCatalog::ExtractKindFromShortLocation(first_byte);
1051      if (DexRegisterLocation::IsShortLocationKind(kind)) {
1052        // Short location.  Skip the current byte.
1053        offset += DexRegisterLocationCatalog::SingleShortEntrySize();
1054      } else {
1055        // Large location.  Skip the 5 next bytes.
1056        offset += DexRegisterLocationCatalog::SingleLargeEntrySize();
1057      }
1058    }
1059    size_t size = offset - origin;
1060    return size;
1061  }
1062
1063  MemoryRegion region_;
1064  friend class StackMapStream;
1065};
1066
1067}  // namespace art
1068
1069#endif  // ART_RUNTIME_STACK_MAP_H_
1070