Chapter 11 PC maps

It is necessary for the compiler to communicate information about the liveness and types of registers and stack-frame slots to the run-time and garbage collector. We use PC maps, which are a mapping from code addresses to liveness and type information, for this purpose. The compiler generates the PC maps (see Section 11.2) based on a static analysis of the code and the run-time system uses the static information from the PC map, along with the actual values in the live registers and stack-frame slots, to determine heap roots etc.

The original design and implementation of PC maps was done by Dan Grossman (Cornell University), this chapter describes a revised design.

11.1 The PC map representation

Each object file produced by the Moby compiler contains a PC map fragment for the code in that file. The run-time system constructs the global PC map from these fragments (see Section 11.3). A PC map fragment has three levels. The top level is called the cluster level, the the middle level is also called the block level, and bottom level is also called the instruction level. The instruction level is not generated is only generated for multi-threaded code (see Section ??).

11.1.1 The cluster level

typedef struct { addr_t _start; addr_t _end; pcmap_block_tbl_t *_blkTbl; #ifdef MOBY_MULTITHREADED pcmap_delta_t *_deltaTbl; #endif uint32_t _frameSz; uint32_t _fpSpillOffset; uint32_t _fpSpillSz; } pcmap_cluster_t; typedef struct { uint32_t _nClusters; pcmap_cluster_t _clusters[1]; } pcmap_t;

Figure 11.1: Cluster-level PC map data structures

A cluster-level entry contains the following fields:

_start: The address at which the cluster begins.¹
_end: The address at which the cluster end.²
_blkTbl: The address at which the block-level table for this cluster begins.
_deltaTbl: This field contains the address of the start of the instruction-level liveness-delta information. It is not present in the single-threaded version of the run-time system.
_frameSz: The number of words between the frame pointer and the top of the activation record for this cluster.
_fpSpillOffset: The number of words between the frame pointer and the beginning of the floating-point spill section of the activation record.
_fpSpillSz: The number of floating-point spill slots for the activation record.

In general, the cluster level describes the activation record, the encoding of lower-level tables, and the location of lower-level tables.

11.1.2 The block level

For each cluster in the object file, there is a block-level table that contains liveness and type information at specific code addresses.

typedef struct { uint16_t _pcOffset; #ifdef MOBY_MULTITHREADED uint16_t _deltaTblOffset; #endif uint8_t _blockKind; uint8_t _live[LIVE_VEC_SZ]; } pcmap_block_t; typedef struct { uint32_t _nEntries; pcmap_block_t _entries[1]; } pcmap_block_tbl_t;

Figure 11.2: Block-level PC map data structures

A block-level entry contains the following fields:

_pcOffset: A 16-bit byte offset from the cluster-level _start address that specifies the address of ``block.''
_deltaTblOffset: A 16-bit word offset from the cluster-level _deltaTbl address to the instruction-level liveness-delta information for this block. It is not present in the single-threaded version of the run-time system.
_live: A liveness vector that specifies the state of the general-purpose registers and spill slots at the given program point.

Since the _pcOffset and _deltaTblOffset fields are limited to 16-bits, it is possible that some clusters will be too large to describe. In such cases, we plan to introduce multiple cluster entries.

11.1.3 The instruction level

For multithreaded Moby programs, we want to support preemption at any instruction. Our approach to this problem is based on Shivers et al.'s design for ``atom heap transactions'' [SCM99].

For each instruction, there is a PC-map delta, which is represented by a variable-length sequence of one or more bytes. The first byte is a header byte, which is divided into four count fields as follows:

bits purpose

0-1 number of ``ignore'' indices

2-3 number of ``pointer'' indices

4-5 number of ``pointer or enum'' indices

6-7 number of ``any'' indices

Following the header are the sequences of indices, first for slots to ignore, then for pointer slots, etc.. A slot index is represented by one or two bytes. For slot indices in the range 0-127, one byte is used to directly represent the index, while for a slot index i in the range 128-32767, we store 128 + (i / 256) in the first byte and i mod 256 in the second byte.

11.2 Generating the PC map

11.3 Interpreting the PC map

1: By begins, we mean the lowest address; it need not be the entry point.
2: By begins, we mean the highest address; it need not be the entry point.