Architecture - I-Machine

An object can be stored:

1. as a list, which is built out of one or more conses (e.g., conses, compact lists, closures, big ratios, double-precision floating point numbers, complex numbers, generic functions),
2. as an immediate object, which does not require any additional memory for its representation (e.g., numbers, physical addresses, primitive types, instructions), or
3. as a structure, represented as a block of memory words, the first contains a header with a special data type code (e.g., compiled functions, instances, arrays, symbols, bignums).

Each word within the structure object may contain:

• an object reference,
• a header
• a forwarding pointer, or
• a special marker.

The components of stored representations found in Lisp Machine memory are:

• object references,
• headers,
• forwarding (invisible) pointers, or
• special markers.

• Immediate Data (22 type codes): dtp-fixnum, dtp-small-ratio, dtp-single-float, dtp-character, dtp-physical-address, dtp-packed-instruction, dtp-spare-immediate-1
• Pointer data (33 type codes): dtp-double-float, dtp-bignum, dtp-big-ratio, dtp-complex, dtp-spare-number, dtp-instance, dtp-list-instance, dtp-array-instance, dtp-string-instance, dtp-nil, dtp-list, dtp-array, dtp-string, dtp-symbol, dtp-locative, dtp-lexical-closure, dtp-dynamic-closure, dtp-compiled-function, dtp-generic-function, dtp-spare-pointer-1, dtp-spare-pointer-2, dtp-spare-pointer-3, dtp-spare-pointer-4, dtp-even-pc, dtp-odd-pc, dtp-call-compiled-even, dtp-call-compiled-odd, dtp-call-indirect, dtp-call-generic, dtp-call-compiled-even-prefetch, dtp-call-compiled-odd-prefetch, dtp-call-indirect-prefetch, dtp-call-generic-prefetch
• Null: dtp-null
• Immediate header: dtp-header-i
• Pointer Header: dtp-header-p
• HFWD: dtp-header-forward
• EFWD: dtp-element-forward
• 1FWD: dtp-one-q-forward
• EVCP: dtp-external-value-cell-pointer
• GC: dtp-gc-forward
• Monitor: dtp-monitor-forward
• Data (55 type codes): The union of immediate data and pointer data
• Header (2 type codes): The union of immediate header and pointer header
• Immediate (23 codes): The union of immediate data and immediate header
• Pointer (40 codes): The union of pointer data, null, pointer header, HFWD, EFWD, 1FWD, EVCP, and monitor
• Numeric (8 type codes): dtp-fixnum, dtp-small-ratio, dtp-single-float, dtp-double-float, dtp-bignum, dtp-big-ratio, dtp-complex, dtp-spare-number

Observe there are 64 type codes altogether: 55 from data, then the following 9 additional codes

• Null: dtp-null
• Immediate header: dtp-header-i
• Pointer Header: dtp-header-p
• HFWD: dtp-header-forward
• EFWD: dtp-element-forward
• 1FWD: dtp-one-q-forward
• EVCP: dtp-external-value-cell-pointer
• GC: dtp-gc-forward
• Monitor: dtp-monitor-forward

The object reference to a symbol is a word of data type dtp-symbol or dtp-nil. The address field of this word contains the address of a header of type dtp-header-p. This is followed by 4 words. The header's header-type field equals %header-type-symbol and the address of the header contains the symbol's name, a string. The five words that constitute a symbol object are:

A straightforward implementation would be:

struct Symbol {
    Word name;
    Word value;
    Word function;
    Word property; /* property list */
    Word package;
};

struct Word* make_symbol(name, value, ...) {
    struct Symbol *symbol = malloc(sizeof(*symbol));
    struct Word *symbol_ptr = malloc(sizeof(symbol_ptr));
    symbol_ptr->type = DTP_SYMBOL;
    symbol_ptr->data = (uint32_t)(symbol);
    symbol->name = name;
    symbol->name.type = DTP_HEADER_P;
    symbol->name.cdr = HEADER_TYPE_SYMBOL; /* == %header-type-symbol */
    symbol->value = value;
    /* etc. */
    return symbol_ptr;
}

The I-Machine reserved locations for nil and t in fixed memory locations (vma=pma 1011000) and (vma=pma 1011005), respectively (see the section Wired Addresses).

Before we had CLOS, we had Flavors.

An object reference to a character is an immediate object of type dtp-character. Characters seem to use the 32-bit data as follows:

As I can glean from this: the %%CHAR-SUBINDEX corresponds to what we would call the code point for the character, or perhaps the 16-bits from the character set & index correspond to the code point. (Arguably, the control, meta, super, hyper bits should be added, as well, giving a 20-bit character set.)

An object reference to a list has its type be dtp-list. The cdr-code tag of a memory word which constitutes an element of a list specifies how to get the cdr of its associated cons according to whether the list is stored in normal linked-list form or in compact ("cdr-coding") form. The cdr-code tag works as follows:

Basically cdr-coding works by reserving cells sequentially.

/* representation of '(a b) using normal lists */
struct Symbol *a, *b;
/* initialize a, b */
struct Word list;
list.type = DTP_LIST;

struct Word cons[2];
cons[0].cdr_code = CDR_NORMAL;
cons[0].type = DTP_SYMBOL;
cons[0].value = (int32_t)a; /* address of 'a */
cons[1].cdr = CDR_NIL;
cons[1].type = DTP_LIST;

struct Word next_cons[2];
next_word[0].cdr_code = CDR_NORMAL;
next_word[0].type = DTP_SYMBOL;
next_word[0].data = (int32_t)b; /* address of 'b */
next_word[1].cdr_code = CDR_NIL;
next_word[1].type = DTP_NIL;
next_word[1].data = NIL;

cons[1].data = (int32_t)&next_word[0];
list.data = &cons[0]; /* list's data is the address of first cons pair */

/* the same list compactified */
struct Word compact_list;
compact_list.type = DTP_LIST;
Word cells[2];
cells[0].cdr_code = CDR_NEXT;
cells[0].type = DTP_SYMBOL;
cells[0].data = (int32_t)a; /* address of 'a */
cells[1].cdr_code = CDR_NIL;
cells[1].type = DTP_SYMBOL;
cells[1].data = (int32_t)b; /* address of 'b */

compact_list.data = &cells[0];

We see see that cdr-coding requires half as many cells as a naive linked-list structure.

Object references to an array or string is a word with data type dtp-array or dtp-string.

Whether an array is refered to by dtp-array or dtp-string has no effect on its stored representation: the data type of the object reference simply serves to make the stringp predicate faster.

An array is a structure consisting of a prefix followed by optional data. A prefix is defined to be a word whose data type is dtp-header-i and whose header type is %header-type-array followed by zero or more additional words. The prefix defines the type and shape of the array.

The byte fields in a prefix header's 32-bit immediate field are:

• Bits <31:27> corresponds to the same bits of the control word of an array register. (Array registers are discussed in the next section.)
• Bits <26:24> are not used by the hardware.
• Bits <31:27.23> enable various spceial pieces of hardware or microcode dispatches.
• Bits <22:0> are used by hardware under microcode control.
• Bits <31:26> are sometimes grouped together as ARRAY-TYPE-FIELD

Some arrays include packed data in their stored representations. For example, character strings store each character in a single 8-bit byte. This is more efficient than general arrays, which require an entire word for each element. Accessing the n-th character of a string fetches the n/4 word of the string, extracts the mod(n,4) byte of that word, and constructs an object reference to the character whose code is equal to the contents of the byte.

(Machine instructions in compiled functions are stored in a similarly packed form.)

For uniformity, the stored representation of an object containing the packed data remains a sequence of object references. Each word in an array of element-type fixnum, boolean, or character is an immediate reference, data type dtp-fixnum, whose thirty-two bits are broken down into packed fields as required, such as four 8-bit bytes in the case of some character strings.

Array leader. An array can optionally be preceded by a leader, a sequence of object references that implements the array-leader feature. If there is a leader, the leader is preceded by a header of its own, tagged dtp-header-p and %header-type-leader; the address field of this header contains the address of the array's main header — i.e., the address of the header of the array prefix.

Note if an array has a leader, the address field of an object reference designating that array contains the address of the main header, the one after the leader, not the address of the header at the beginning of the array's store (before the leader). Schematically:

Word prefix; /* array prefix */
prefix.cdr = CDR_ARRAY;
prefix.type = DTP_HEADER_I;
prefix.data = ...;

Word *data = &prefix;
data++; /* next word after prefix */
data->type = DTP_FIXNUM;
data->data = 42; /* some random data */

data++; /* second array entry */
data->type = DTP_FIXNUM;
data->data = 31; /* some random data */


Word leader[]; /* array leader */
leader[0] = {cdr = CDR_LEADER, type = DTP_HEADER_P, data = &prefix};
/* leader[1] is a named-structure symbol */
leader[1] = {type = DTP_SYMBOL, data = &name};
leader[2] = {type = DTP_FIXNUM, data = ... };


Word array;
array.type = DTP_ARRAY;
array.data = (&prefix) + 1; /* start address of array data */

The two array formats — %array-prefix-short and %array-prefix-long — are provided to optimize speed and space for simple, small arays (which are the most common).

%array-prefix-short has the 15 bits in position <14:0>, with the symbolic name ARRAY-SHORT-LENGTH-FIELD, give the length of the array.

The prefix is one word, the array is one-dimensional and not displaced, but may have a leader. Most common arrays include defstructs, editor lines, and most arrays with fill-pointers use this type.

The address of data element i of a short-prefix array whose address is a and whose ARRAY-BYTE-PACKING field is b is given by (+ a (ash i (- b)) 1). When b is greater than zero, packed array elements are stored right-to-left within words, thus the right shift to right-justify data element i is (ash (logand i (1- (ash 1 b))) (- 5 b)).

%array-prefix-long has the following 15 bits in position <14:0>:

The long prefix format is used for displaced arrays (including indirect arrays), arrays that are too large to fit in the short-prefix format, and multidimensional (including zero-dimensional) arrays. The first word in the prefix contains the number of dimensions in place of the length of the data. The total length of the prefix is (+ 4 (* d 2)) where d is the number of dimensions.

The second word of the prefix is the length of the array. For conformally displaced arrays, this is the maximum legal linear subscript, not the number of elements (which may be smaller).

The third word of the prefix is the index offset. This is always present, even for non-indirect arrays. Zero should be stored here in non-displaced arrays, since this word is always added to the subscript.

The fourth word of the prefix is the address of the data. This is a locative to the first word after the prefix for normal arrays, except for arrays with no elements (in which case it is a locative to the array itself to avoid pointing to garbage). Fir displaced arrays, this is a locative or a fixnum. For indirect arrays, this is an array.

The remaining wods of the prefix consist of two words for each dimension. The first word is the length of that dimension and the second word is the value to multiply that subscript by.

Word prefix[];
Word array_data[];

union { int32_t data,
        struct {
            int32_t element_type : 2;
            int32_t byte_packing : 3;
            int32_t list_bit     : 1;
            int32_t named_structure_bit : 1;
            int32_t spare_1      : 1;
            int32_t long_prefix_bit : 1;
            int32_t leader_length : 8;
            int32_t displaced_bit : 1;
            int32_t discontiguous_bit : 1;
            int32_t long_spare : 12;
            int32_t long_dimensions : 3;
        } fields } prefix_data;
prefix_data.fields = {element_type        = ELEMENT_FIXNUM,
                      byte_packing        = 3,
                      list_bit            = 0,
                      named_structure_bit = 0,
                      spare_1             = 0,
                      long_prefix_bit     = 1,
                      leader_length       = 0,
                      displaced_bit       = 0,
                      discontiguous_bit   = 0,
                      long_spare          = 0
                      long_dimensions     = 2};
prefix[0] = {cdr = CDR_ARRAY, type = DTP_HEADER_I,
             data = prefix_data.data};
prefix[1] = {type = DTP_FIXNUM, data = 28}; /* array length */
prefix[2] = {type = DTP_FIXNUM, data = 0};  /* index offset */
prefix[3] = {type = DTP_LOCATIVE,
             data = &array_data[0]};
/* first dimension */
prefix[4] = {type = DTP_FIXNUM, data = 7}; /* length */
prefix[5] = {type = DTP_FIXNUM, data = 4}; /* multiplier */
/* second dimension */
prefix[6] = {type = DTP_FIXNUM, data = 4}; /* length */
prefix[7] = {type = DTP_FIXNUM, data = 1}; /* multiplier */

array_data[0] = {type = DTP_FIXNUM,
                 data = ...};
array_data[1] = {type = DTP_FIXNUM,
                 data = ...};
array_data[2] = {type = DTP_FIXNUM,
                 data = ...};
array_data[3] = {type = DTP_FIXNUM,
                 data = ...};

Word array_pointer = {type = DTP_ARRAY,
                      data = &prefix[0]};

The instructions ins a compiled function are a sequence of words whose data-type field selects among three types of words:

1. Packed instructions. Data types with codes 60–77 are used for words that contain two 18-bit instructions. These are the usual stack-machine type instructions.

2. Full-word instructions. Data types coded 50–57 are used for words that contain a single intsruction with an address field. These are used for starting function calls.

   In addition, data type dtp-external-value-cell-pointer (type code 4) is used to fetch the contents of the value cell of a special variable or the function cell of a function an push it on the stack. This is actually an optimization to save space and time; the value cell address could be pushed as a constant locative and then a car instruction could be executed.

   Besides these, there is one other full word instruction type, the entry instructions, which do not contain addresses, but instead look like pairs of half-word instructions. These are decoded by their opcode field, not by the data-type field.

3. Constants. All other data types encountered among the instructions in a compiled function are constants. The word from the instruction stream is pushed on the stack with the cdr code set to cdr-next. The hardware will signal an error if the word is a header or an invisible pointer.

The fields within various types of instructions are described in the chapter on the Macroinstruction Set.

The program counter (pc) is a register in the I-machine that contains the virtual address of the currently executing instruction. Since instructions are packed 2 to a word, we need to specify which half-word instruction is executing.

The information is included in the data-type code of the pc contents; thus there are two pc data types dtp-even-pc and dtp-odd-pc. Word of these data types are not usually found in the stored representations of Lisp objects, but occur within stack frames or inside compiled functions for long branches. See Function Calling, Message Passing, Stack-Group Switching.

A locative is a pointer to virtual memory implemented as an object with data type dtp-locative and an address field that is the address of the virtual memory word to which it points.

It is classified as a pointer object reference.

Locatives may point to locations within objects, such as the value cell of a symbol. Other uses include the pointer to the start of data in long format arrays and the base address of array registers.

The data type dtp-physical-address allows unmapped access to the full (up to 32 bits wide) physical address space. Since it is a separate data type it has restricted usage.

There are 11 primitive types:

Note codes 36, 37, 42, 44 are spare pointer data types and code 41 is a spare immediate data type.

Each word of this type contains two 18-bit instructions, which is why 16 types are used up. Bits <37:36> contain 3 to select the instruction data type. Bits <39:38>, the cdr code, contain sequencing information described in the chapter on theinstruction set. The instruction in bits <17:0> is executed before the instruction in bits <35:18>.

A virtual address is divided into two fields for mapping purposes: the virtual page number and the offset within page fields.

Virtual space occupies thirty-one zones. An internal processor register allows each zone to be specified as either old or new space.

The virtual address space is partitioned by software into regions, areas, and quanta. These have no direct hardware impact. Note, however, that the hardware hash function for the Page Hash Table is optimized for a quantum of size 65536 words (see Page Hash Table).

The lowest zone of the virtual address is reserved for the storage of ephemeral objects. This space is provided to support a garbage collection strategy that takes advantage of recently created objects usually having a short lifetime.

Ephemeral space is divided into thirty-two levels. Data within an ephemeral level is the same age. The relative ages of different levels is up to decide and would normally change dynamically. Each level is further divided into two halves (old and new space). An internal processor register specifies which half is old and which is new.

The thirty-two ephemeral levels are grouped into four groups of eight levels each. The ephemeral level groups referenced by a page are maintained in the PHT.

The cdr-code of instruction words specify the sequencing of instructions for execution.

The I-machine internal registers may be summarized in the following table. An asterisk by an address entry means the register may be defined by an implementation, and "reserved" means the register may be architecturally defined in the future. The information in this table is specific to Revision 0 of the Ivory chip.

Reading memory may not cause side effects. The architecture permits an implementation to start a memory read that it will not use, perhaps because of instruction prefetching, perhaps while starting an array reference before an out of bounds check is peformed, perhaps because of instruction pipelining, or perhaps for something else.

Writing memory using a dtp-physical-address is allowed to cause side effects; dtp-physical-address is guaranteed not to be cached, and the write is guaranteed to happen exactly once. Also both %coprocessor-read and %coprocessor-write instructions may cause side effects; they are guaranteed to be performed exactly once.