DESCRIPTION OF A MACHINE
ARCHITECTURE FOR USE WITH
BLOCK STRUCTURED LANGUAGES

Andrew S. Tanenbaum
Hans van Staveren
Ed G. Keizer
Johan W. Stevenson*

August 1983

Informatica Rapport IR-81

Abstract

1

1. INTRODUCTION

EM is a family of intermediate languages designed for producing portable compilers. The general strategy is for a program called front end to translate the source program to EM. Another program, back end, translates EM to target assembly language. Alternatively, the EM code can be assembled to a binary form and interpreted. These considerations led to the following goals:

The basic architecture is based on the concept of a stack. The stack is used for procedure return addresses, actual parameters, local variables, and arithmetic operations. There are several built-in object types, for example, signed and unsigned integers, floating point numbers, pointers and sets of bits. There are instructions to push and pop objects to and from the stack. The push and pop instructions are not typed. They only care about the size of the objects. For each built-in type there are reverse Polish type instructions that pop one or more objects from the top of the stack, perform an operation, and push the result back onto the stack. For all types except pointers, these instructions have the object size as argument.

There are no visible general registers used for arithmetic operands etc. This is in contrast to most third generation computers, which usually have 8 or 16 general registers. The decision not to have a group of general registers was fully intentional, and follows W.L. Van der Poel’s dictum that a machine should have 0, 1, or an infinite number of any feature. General registers have two primary uses: to hold intermediate results of complicated expressions, e.g.

     ((a*b + c*d)/e + f*g/h) * i

and to hold local variables.

Various studies have shown that the average expression has fewer than two operands, making the former use of registers of doubtful value. The present trend toward structured programs consisting of many small procedures greatly reduces the value of registers to hold local variables because the large number of procedure calls implies a large overhead in saving and restoring the registers at every call.

Although there are no general purpose registers, there are a few internal registers with specific functions as follows:

Furthermore, reverse Polish code is much easier to generate than multi-register machine code, especially if highly efficient code is desired. When translating to assembly language the back end can make good use of the target machine’s registers. An EM machine can achieve high performance by keeping part of the stack in high speed storage (a cache or microprogram scratchpad memory) rather than in primary memory.

Again according to van der Poel’s dictum, all EM instructions have zero or one argument. We believe that instructions needing two arguments can be split into two simpler ones. The simpler ones can probably be used in other circumstances as well. Moreover, these two instructions together often have a shorter encoding than the single instruction before.

This document describes EM at three different levels: the abstract level, the assembly language level and the machine language level.
The most important level is that of the abstract EM architecture. This level deals with the basic design issues. Only the functional capabilities of instructions are relevant, not their format or encoding. Most chapters of this document refer to the abstract level and it is explicitly stated whenever another level is described.
The assembly language is intended for the compiler writer. It presents a more or less orthogonal instruction set and provides symbolic names for data. Moreover, it facilitates the linking of separately compiled ’modules’ into a single program by providing several pseudoinstructions.
The machine language is designed for interpretation with a compact program text and easy decoding. The binary representation of the machine language instruction set is far from orthogonal. Frequent instructions have a short opcode. The encoding is fully byte oriented. These bytes do not contain small bit fields, because bit fields would slow down decoding considerably.

A common use for EM is for producing portable (cross) compilers. When used this way, the compilers produce EM assembly language as their output. To run the compiled program on the target machine, the back end, translates the EM assembly language to the target machine’s assembly language. When this approach is used, the format of the EM machine language instructions is irrelevant. On the other hand, when writing an interpreter for EM machine language programs, the interpreter must deal with the machine language and not with the symbolic assembly language.

As mentioned above, the current microcomputer technology offers 8, 16 and 32 bit machines with address spaces ranging from 2 16 to 2 32 bytes. Having one size of pointers and integers restricts the usefulness of the language. We decided to have a different language for each combination of word and pointer size. All languages offer the same instruction set and differ only in memory alignment restrictions and the implicit size assumed in several instructions. The languages differ slightly for the different size combinations. For example: the size of any object on the stack and alignment restrictions. The wordsize is restricted to powers of 2 and the pointer size must be a multiple of the wordsize. Almost all programs handling EM will be parametrized with word and pointer size.

2

2. MEMORY

The EM machine has two distinct address spaces, one for instructions and one for data. The data space is divided up into 8-bit bytes. The smallest addressable unit is a byte. Bytes are numbered consecutively from 0 to some maximum. All sizes in EM are expressed in bytes.

Some EM instructions can transfer objects containing several bytes to and/or from memory. The size of all objects larger than a word must be a multiple of the wordsize. The size of all objects smaller than a word must be a divisor of the wordsize. For example: if the wordsize is 2 bytes, objects of the sizes 1, 2, 4, 6,... are allowed. The address of such an object is the lowest address of all bytes it contains. For objects smaller than the wordsize, the address must be a multiple of the object size. For all other objects the address must be a multiple of the wordsize. For example, if an instruction transfers a 4-byte object to memory at location m and the wordsize is 2, m must be a multiple of 2 and the bytes at locations m, m+1,m+2 and m+3 are overwritten.

The size of almost all objects in EM is an integral number of words. Only two operations are allowed on objects whose size is a divisor of the wordsize: push it onto the stack and pop it from the stack. The addressing of these objects in memory is always indirect. If such a small object is pushed onto the stack it is assumed to be a small integer and stored in the least significant part of a word. The rest of the word is cleared to zero, although EM provides a way to sign-extend a small integer. Popping a small object from the stack removes a word from the stack, stores the least significant byte(s) of this word in memory and discards the rest of the word.

The format of pointers into both address spaces is explicitly undefined. The size of a pointer, however, is fixed for a member of EM, so that the compiler writer knows how much storage to allocate for a pointer.

A minor problem is raised by the undefined pointer format. Some languages, notably Pascal, require a special, otherwise illegal, pointer value to represent the nil pointer. The current Pascal-VU compiler uses the integer value 0 as nil pointer. This value is also used by many C programs as a normally impossible address. A better solution would be to have a special instruction loading an illegal pointer value, but it is hard to imagine an implementation for which the current solution is inadequate, especially because the first word in the EM data space is special and probably not the target of any pointer.

The next two chapters describe the EM memory in more detail. One describes the instruction address space, the other the data address space.

A design goal of EM has been to allow its implementation on a wide range of existing machines, as well as allowing a new one to be built in hardware. To this extent we have tried to minimize the demands of EM on the memory structure of the target machine. Therefore, apart from the logical partitioning, EM memory is divided into ’fragments’. A fragment consists of consecutive machine words and has a base address and a size. Pointer arithmetic is only defined within a fragment. The only exception to this rule is comparison with the null pointer. All fragments must be word aligned.

3

3. INSTRUCTION ADDRESS SPACE

The instruction space of the EM machine contains the code for procedures. Tables necessary for the execution of this code, for example, procedure descriptor tables, may also be present. The instruction space does not change during the execution of a program, so that it may be protected. No further restrictions to the instruction address space are necessary for the abstract and assembly language level.

Each procedure has a single entry point: the first instruction. A special type of pointer identifies a procedure. Pointers into the instruction address space have the same size as pointers into data space and can, for example, contain the address of the first instruction or an index in a procedure descriptor table.

There is a single EM program counter, PC, pointing to the next instruction to be executed. The procedure pointed to by PC is called the ’current’ procedure. A procedure may call another procedure using the CAL or CAI instruction. The calling procedure remains ’active’ and is resumed whenever the called procedure returns. Note that a procedure has several ’active’ invocations when called recursively.

Each procedure must return properly. It is not allowed to fall through to the code of the next procedure. There are several ways to exit from a procedure:

All branch instructions can transfer control to any label within the same procedure. Branch instructions can never jump out of a procedure.

Several language implementations use a so called procedure instance identifier, a combination of a procedure identifier and the LB of a stack frame, also called static link.

The program text for each procedure, as well as any tables, are fragments and can be allocated anywhere in the instruction address space.

4

4. DATA ADDRESS SPACE

The data address space is divided into three parts, called ’areas’, each with its own addressing method: global data area, local data area (including the stack), and heap data area. These data areas must be part of the same address space because all data is accessed by the same type of pointers.

Space for global data is reserved using several pseudoinstructions in the assembly language, as described in the next paragraph and chapter 11. The size of the global data area is fixed per program.

Global data is addressed absolutely in the machine language. Many instructions are available to address global data. They all have an absolute address as argument. Examples are LOE, LAE and STE.

Part of the global data area is initialized by the compiler, the rest is not initialized at all or is initialized with a value, typically −32768 or 0. Part of the initialized global data may be made read-only if the implementation supports protection.

The local data area is used as a stack, which grows from high to low addresses and contains some data for each active procedure invocation, called a ’frame’. The size of the local data area varies dynamically during execution. Below the current procedure frame resides the operand stack. The stack pointer SP always points to the bottom of the local data area. Local data is addressed by offsetting from the local base pointer LB. LB always points to the frame of the current procedure. Only the words of the current frame and the parameters can be addressed directly. Variables in other active procedures are addressed by following the chain of statically enclosing procedures using the LXL or LXA instruction. The variables in dynamically enclosing procedures can be addressed with the use of the DCH instruction.

Many instructions have offsets to LB as argument, for instance LOL, LAL and STL. The arguments of these instructions range from −1 to some (negative) minimum for the access of local storage and from 0 to some (positive) maximum for parameter access.

The procedure call instructions CAL and CAI each create a new frame on the stack. Each procedure has an assembly-time parameter specifying the number of bytes needed for local storage. This storage is allocated each time the procedure is called and must be a multiple of the wordsize. Each procedure, therefore, starts with a stack with the local variables already allocated. The return instructions RET and RTT remove a frame. The actual parameters must be removed by the calling procedure.

RET may copy some words from the stack of the returning procedure to an unnamed ’function return area’. This area is available for ’READ-ONCE’ access using the LFR instruction. The result of a LFR is only defined if the size used to fetch is identical to the size used in the last return. The instruction ASP, used to remove the parameters from the stack, the branch instruction BRA and the non-local goto instruction GTO are the only ones that leave the contents of the ’function return area’ intact. All other instructions are allowed to destroy the function return area. Thus parameters can be popped before fetching the function result. The maximum size of all function return areas is implementation dependent, but should allow procedure instance identifiers and all implemented objects of type integer, unsigned, float and pointer to be returned. In most implementations the maximum size of the function return area is twice the pointer size, because we want to be able to handle ’procedure instance identifiers’ which consist of a procedure identifier and the LB of a frame belonging to that procedure.

The heap data area grows upwards, to higher numbered addresses. It is initially empty. The initial value of the heap pointer HP marks the low end. The heap pointer may be manipulated by the LOR and STR instructions. The heap can only be addressed indirectly, by pointers derived from previous values of HP.

4.1 Global data area

The initial size of the global data area is determined at assembly time. Global data is allocated by several pseudoinstructions in the EM assembly language. Each pseudoinstruction allocates one or more bytes. The bytes allocated for a single pseudo form a ’block’. A block differs from a fragment, because, under certain conditions, several blocks are allocated in a single fragment. This guarantees that the bytes of these blocks are consecutive.

Global data is addressed absolutely in binary machine language. Most compilers, however, cannot assign absolute addresses to their global variables, especially not if the language allows programs to be composed of several separately compiled modules. The assembly language therefore allows the compiler to name the first address of a global data block with an alphanumeric label. Moreover, the only way to address such a named global data block in the assembly language is by using its name. It is the task of the assembler/loader to translate these labels into absolute addresses. These labels may also be used in CON and ROM pseudoinstructions to initialize pointers.

The pseudoinstruction CON allocates initialized data. ROM acts like CON but indicates that the initialized data will not change during execution of the program. The pseudoinstruction BSS allocates a block of uninitialized or identically initialized data. The pseudoinstruction HOL is similar to BSS, but it alters the meaning of subsequent absolute addressing in the assembly language.

Another type of global data is a small block, called the ABS block, with an implementation defined size. Storage in this type of block can only be addressed absolutely in assembly language. The first word has address 0 and is used to maintain the source line number. Special instructions LIN and LNI are provided to update this counter. A pointer at location 4 points to a string containing the current source file name. The instruction FIL can be used to update the pointer.

All numeric arguments of the instructions that address the global data area refer to locations in the ABS block unless they are preceded by at least one HOL pseudo in the same module, in which case they refer to the storage area allocated by the last HOL pseudoinstruction. Thus LOE 0 loads the zeroth word of the most recent HOL, unless no HOL has appeared in the current file so far, in which case it loads the zeroth word of the ABS fragment.

The global data area is highly fragmented. The ABS block and each HOL and BSS block are separate fragments. The way fragments are formed from CON and ROM blocks is more complex. The assemblers group several blocks into a single fragment. A fragment only contains blocks of the same type: CON or ROM. It is guaranteed that the bytes allocated for two consecutive CON pseudos are allocated consecutively in a single fragment, unless these CON pseudos are separated in the assembly language program by a data label definition or one or more of the following pseudos:

     ROM, BSS, HOL and END

An analogous rule holds for ROM pseudos.

4.2 Local data area

The local data area consists of a sequence of frames, one for each active procedure. Below the frame of the current procedure resides the expression stack. Frames are generated by procedure calls and are removed by procedure returns. A procedure frame consists of six ’zones’:

     1.  The return status block
     2.  The local variables and compiler temporaries
     3.  The register save block
     4.  The dynamic local generators
     5.  The operand stack.
     6.  The parameters of a procedure one level deeper

A sample frame is shown in Figure 1.

Before a procedure call is performed the actual parameters are pushed onto the stack of the calling procedure. The exact details are compiler dependent. EM allows procedures to be called with a variable number of parameters. The implementation of the C-language almost forces its runtime system to push the parameters in reverse order, that is, the first positional parameter last. Most compilers use the C calling convention to be compatible. The parameters of a procedure belong to the frame of the calling procedure. Note that the evaluation of the actual parameters may imply the calling of procedures. The parameters can be accessed with certain instructions using offsets of 0 and greater. The first byte of the last parameter pushed has offset 0. Note that the parameter at offset 0 has a special use in the instructions following the static chain (LXL and LXA). These instructions assume that this parameter contains the LB of the statically enclosing procedure. Procedures that do not have a dynamically enclosing procedure do not need a static link at offset 0.

Two instructions are available to perform procedure calls, CAL and CAI. Several tasks are performed by these call instructions.

First, a part of the status of the calling procedure is saved on the stack in the return status block. This block should contain the return address of the calling procedure, its LB and other implementation dependent data. The size of this block is fixed for any given implementation because the lexical instructions LPB, LXL and LXA must be able to obtain the base addresses of the procedure parameters and local variables. An alternative solution can be used on machines with a highly segmented address space. The stack frames need not be contiguous then and the first status save area can contain the parameter base AB, which has the value of SP just after the last parameter has been pushed.

Second, the LB is changed to point to the first word above the local variables. The new LB is a copy of the SP after the return status block has been pushed.

Third, the amount of local storage needed by the procedure is reserved. The parameters and local storage are accessed by the same instructions. Negative offsets are used for access to local variables. The highest byte, that is the byte nearest to LB, has to be accessed with offset −1. The pseudoinstruction specifying the entry point of a procedure, has an argument that specifies the amount of local storage needed. The local variables allocated by the CAI or CAL instructions are the only ones that can be accessed with a fixed negative offset. The initial value of the allocated words is not defined, but implementations that check for undefined values will probably initialize them with a special ’undefined’ pattern, typically −32768.

Fourth, any EM implementation is allowed to reserve a variable size block beneath the local variables. This block could, for example, be used to save a variable number of registers.

Finally, the address of the entry point of the called procedure is loaded into the Program Counter.

The ASP instruction can be used to allocate further (dynamic) local storage. The base address of such storage must be obtained with a LOR SP instruction. This same instruction ASP may also be used to remove some words from the stack.

There is a version of ASP, called ASS, which fetches the number of bytes to allocate from the stack. It can be used to allocate space for local objects whose size is unknown at compile time, so called ’dynamic local generators’.

Control is returned to the calling procedure with a RET instruction. Any return value is then copied to the ’function return area’. The frame created by the call is deallocated and the status of the calling procedure is restored. The value of SP just after the return value has been popped must be the same as the value of SP just before executing the first instruction of this invocation. This means that when a RET is executed the operand stack can only contain the return value and all dynamically generated locals must be deallocated. Violating this restriction might result in hard to detect errors. The calling procedure has to remove the parameters from the stack. This can be done with the aforementioned ASP instruction.

Each procedure frame is a separate fragment. Because any fragment may be placed anywhere in memory, procedure frames need not be contiguous.

|===============================| | actual parameter n-1 | |-------------------------------| | . | | . | | . | |-------------------------------| | actual parameter 0 | ( <− AB ) |===============================|

|===============================| |///////////////////////////////| |///// return status block /////| |///////////////////////////////| <− LB |===============================| | | | local variables | | | |-------------------------------| | | | compiler temporaries | | | |===============================| |///////////////////////////////| |///// register save block /////| |///////////////////////////////| |===============================| | | | dynamic local generators | | | |===============================| | operand | |-------------------------------| | operand | |===============================| | parameter m-1 | |-------------------------------| | . | | . | | . | |-------------------------------| | parameter 0 | <− SP |===============================|

Figure 1. A sample procedure frame and parameters.

4.3 Heap data area

The heap area starts empty, with HP pointing to the low end of it. HP always contains a word address. A copy of HP can always be obtained with the LOR instruction. A new value may be stored in the heap pointer using the STR instruction. If the new value is greater than the old one, then the heap grows. If it is smaller, then the heap shrinks. HP may never point below its original value. All words between the current HP and the original HP are allocated to the heap. The heap may not grow into a part of memory that is already allocated. When this is attempted, the STR instruction will cause a trap to occur. In this case, HP retains its old value.

The only way to address the heap is indirectly. Whenever an object is allocated by increasing HP, then the old HP value must be saved and can be used later to address the allocated object. If, in the meantime, HP is decreased so that the object is no longer part of the heap, then an attempt to access the object is not allowed. Furthermore, if the heap pointer is increased again to above the object address, then access to the old object gives undefined results.

The heap is a single fragment. All bytes have consecutive addresses. No limits are imposed on the size of the heap as long as it fits in the available data address space.

5

5. MAPPING OF EM DATA MEMORY ONTO TARGET MACHINE MEMORY

The EM architecture is designed to be implemented on many existing and future machines. EM memory is highly fragmented to make adaptation to various memory architectures possible. Format and encoding of pointers is explicitly undefined.

This chapter gives solutions to some of the anticipated problems. First, we describe a possible memory layout for machines with 64K bytes of address space. Here we use a member of the EM family with 2-byte word and pointer size. The most straightforward layout is shown in figure 2.

65534 −> |-------------------------------| |///////////////////////////////| |//// unimplemented memory /////| |///////////////////////////////| ML −> |-------------------------------| | | | | <− LB | stack and local area | | | |-------------------------------| <− SP |///////////////////////////////| |//////// inaccessible /////////| |///////////////////////////////| |-------------------------------| <− HP | | | heap area | | | | | HB −> |-------------------------------| | | | global data area | | | EB −> |-------------------------------| | | | program text | <− PC | | | ( and tables ) | | | | | PB −> |-------------------------------| |///////////////////////////////| |////////// undefined //////////| |///////////////////////////////| 0 −> |-------------------------------|

Figure 2. Memory layout showing typical register
positions during execution of an EM program.

The base registers for the various memory pieces can be stored in target machine registers or memory.

The stack grows from high EM addresses to low EM addresses, and the heap the other way. The memory between SP and HP is not accessible, but may be allocated later to the stack or the heap if needed. The local data area is allocated starting at the high end of memory.

Because EM address 0 is not mapped onto target address 0, a problem arises when pointers are used. If a program pushed a constant, say 6, onto the stack, and then tried to indirect through it, the wrong word would be fetched, because EM address 6 is mapped onto target address EB+6 and not target address 6 itself. This particular problem is solved by explicitly declaring the format of a pointer to be undefined, so that using a constant as a pointer is completely illegal. However, the general problem of mapping pointers still exists.

There are two possible solutions. In the first solution, EM pointers are represented in the target machine as true EM addresses, for example, a pointer to EM address 6 really is stored as a 6 in the target machine. This solution implies that every time a pointer is fetched EB must be added before referencing the target machine’s memory. If the target machine has powerful indexing facilities, EB can be kept in a target machine register, and the relocation can indeed be done on every reference to the data address space at a modest cost in speed.

The other solution consists of having EM pointers refer to the true target machine address. Thus the instruction LAE 6 (Load Address of External 6) would push the value of EB+6 onto the stack. When this approach is chosen, back ends must know how to offset from EB, to translate all instructions that manipulate EM addresses. However, the problem is not completely solved, because a front end may have to initialize a pointer in CON or ROM data to point to a global address. This pointer must also be relocated by the back end or the interpreter.

Although the EM stack grows from high to low EM addresses, some machines have hardware PUSH and POP instructions that require the stack to grow upwards. If reasons of efficiency demand the use of these instructions, then EM can be implemented with the memory layout upside down, as shown in figure 3. This is possible because the pointer format is explicitly undefined. The first element of a word array will have a lower physical address than the second element.

| | | | | EB=60 | | ^ | | | | | | |-----------------| |-----------------| 105 | 45 | 44 | 104 214 | 41 | 40 | 215 |-----------------| |-----------------| 103 | 43 | 42 | 102 212 | 43 | 42 | 213 |-----------------| |-----------------| 101 | 41 | 40 | 100 210 | 45 | 44 | 211 |-----------------| |-----------------| | | | | | | v | | EB=255 | | | | |

Type A Type B

Figure 3. Two possible memory implementations.
Numbers within the boxes are EM addresses.
The other numbers are physical addresses.

So, we have two different EM memory implementations:

For each of these two possibilities we give the translation of the EM instructions to push the third byte of a global data block starting at EM address 40 onto the stack and to load the word at address 40. All translations assume a word and pointer size of two bytes. The target machine used is a PDP-11 augmented with push and pop instructions. Registers ’r0’ and ’r1’ are used and suffer from sign extension for byte transfers. Push $40 means push the constant 40, not word 40.

The translation of the EM instructions depends on the pointer representation used. For each of the two solutions explained above the translation is given.

First, the translation for the two implementations using EM addresses as pointer representation:

The translation for the two implementations, if the target machine address is used as pointer representation, is:

The translation presented above is not intended to be optimal. Most machines can handle these simple cases in one or two instructions. It demonstrates, however, the flexibility of the EM design.

There are several possibilities to implement EM on machines with address spaces larger than 64k bytes. For EM with two byte pointers one could allocate instruction and data space each in a separate 64k piece of memory. EM pointers still have to fit in two bytes, but the base registers PB and EB may be loaded in hardware registers wider than 16 bits, if available. EM implementations can also make efficient use of a machine with separate instruction and data space.

EM with 32 bit pointers allows one to make use of machines with large address spaces. In a virtual, segmented memory system one could use a separate segment for each fragment.

6

6. TYPE REPRESENTATIONS

The representations used for typed objects are not precisely specified by EM. Sometimes we only specify that a typed object occupies a certain amount of space and state no further restrictions. If one wants to have a different representation of the value of an object on the stack one has to use a convert instruction in most cases. We do specify some relations between the representations of types. This allows some intermixed use of operators for different types on the same object(s). For example, the instruction ZER pushes signed and unsigned integers with the value zero and empty sets. ZER has as only argument the size of the object.

The representation of floating point numbers is a good example, it allows widely varying implementations. The only ways to create floating point numbers are via initialization and via conversions from integer numbers. Only by using conversions to integers and comparing two floating point numbers with each other, can these numbers be converted to human readable output. Implementations may use base 10, base 2 or any other base for exponents, and have freedom in choosing the range of exponent and mantissa.

Other types are more precisely described. In the following paragraphs a description will be given of the restrictions imposed on the representation of the types used. A number n used in these paragraphs indicates the size of the object in bits.

6.1 Unsigned integers

The range of unsigned integers is 0.. 2 n -1. A binary representation is assumed. The order of the bits within an object is knowingly left unspecified. Discussing bit order within each 8-bit byte is academic, so the only real freedom of this specification lies in the byte order. We really do not care whether an implementation of a 4-byte integer has its bytes in a particular order of significance. This of course means that some sequences of instructions have unpredictable effects. For example:

     LOC 258 ; STL 0 ; LAL 0 ; LOI 1      ( wordsize >=2 )

The value on the stack after executing this sequence can be anything, but will most likely be 1 or 2.

Conversion between unsigned integers of different sizes have to be done with explicit convert instructions. One cannot simply pad an unsigned integer with zero’s at either end and expect a correct result.

We assume existence of at least single word unsigned arithmetic in any implementation.

6.2 Signed Integers

The range of signed integers is −2 n−1 .. 2 n−1 −1, in other words the range of signed integers of n bits using two’s complement arithmetic. The representation is the same as for unsigned integers except the range 2 n−1 .. 2 n −1 is mapped on the range −2 n−1 .. −1. In other words, the most significant bit is used as sign bit. The convert instructions between signed and unsigned integers of the same size can be used to catch errors.

The value −2 n−1 is used for undefined signed integers. EM implementations should trap when this value is used in an operation on signed integers. The instruction mask, accessed with SIM and LIM − see chapter 9 −, can be used to disable such traps.

We assume existence of at least single word signed arithmetic in any implementation.

6.3 Floating point values

Floating point values must have a signed mantissa and a signed exponent. Although no base is specified, base 2 is the normal choice, because the FEF instruction pushes the exponent in base 2.

The implementation of floating point arithmetic is optional. The compilers currently in use have runtime parameters for the size of the floating point values they should use. Common choices are 4 and/or 8 bytes.

6.4 Pointers

EM has two kinds of pointers: for instruction and for data space. Each kind can only be used for its own space, conversion between these two subtypes is impossible. We assume that pointers have a range from 0 upwards. Any implementation may have holes in the pointer range between fragments. One can of course not expect to be able to address two megabyte of memory using a 2-byte pointer. Normally, a 2-byte pointer allows up to 65536 bytes of addressable memory.

Pointer representation has one restriction. The pointer with the same representation as the integer zero of the same size should be invalid. Some languages and/or runtime systems represent the nil pointer as zero.

6.5 Bit sets

All bit sets of size n are subsets of the set { i | i>=0, i<n }. A bit set contains a bit for each element showing its presence or absence. Bit sets are subdivided into words. The word with the lowest EM address governs the subset { i | i>=0, i<m }, where m is the number of bits in a word. The next higher words each govern the next higher m set elements. The relation between a set with size of a word and an unsigned integer word is that the value of the unsigned integer is the summation of the 2i where i is in the set.

Example: a 2-word bit set (wordsize 2) containing the elements 1, 6, 8, 15, 18, 21, 27 and 28 is composed of two integers, e.g. at addresses 40 and 42. The word at 40 contains the value 33090 (or −32446), the word at 42 contains the value 6180.

7

7. DESCRIPTORS

Several instructions use descriptors, notably the range check instruction, the array instructions, the goto instruction and the case jump instructions. Descriptors reside in data space. They may be constructed at run time, but more often they are fixed and allocated in ROM data.

All instructions using descriptors, except GTO, have as argument the size of the integers in the descriptor. All implementations have to allow integers of the size of a word in descriptors. All integers popped from the stack and used for indexing or comparing must have the same size as the integers in the descriptor.

7.1 Range check descriptors

Range check descriptors consist of two integers:

The range check instruction checks an integer on the stack against these bounds and causes a trap if the value is outside the interval. The value itself is neither changed nor removed from the stack.

7.2 Array descriptors

Each array descriptor describes a single dimension. For multi-dimensional arrays, several array instructions are needed to access a single element. Array descriptors contain the following three integers:

The array instructions LAR, SAR and AAR have the pointer to the start of the descriptor as operand on the stack.

The element A[I] is fetched as follows:

All array instructions first pop the address of the descriptor and the index. If the index is not within the bounds specified, a trap occurs. If ok, (I − lower bound) is multiplied by the number of bytes per element (the third word). The result is added to the address of A and replaces A on the stack.

At this point LAR, SAR and AAR diverge. AAR is finished. LAR pops the address and fetches the data item, the size being specified by the descriptor. The usual restrictions for memory access must be obeyed. SAR pops the address and stores the data item now exposed.

7.3 Non-local goto descriptors

The GTO instruction provides a way of returning directly to any active procedure invocation. The argument of the instruction is the address of a descriptor containing three pointers:

GTO replaces the loads PC, SP and LB from the descriptor, thereby jumping to a procedure and removing zero or more frames from the stack. The LB, SP and PC in the descriptor must belong to a dynamically enclosing procedure, because some EM implementations will need to backtrack through the dynamic chain and use the implementation dependent data in frames to restore registers etc.

7.4 Case descriptors

The case jump instructions CSA and CSB both provide multiway branches selected by a case index. Both fetch two operands from the stack: first a pointer to the low address of the case descriptor and then the case index. CSA uses the case index as index in the descriptor table, but CSB searches the table for an occurrence of the case index. Therefore, the descriptors for CSA and CSB, as shown in figure 4, are different. All pointers in the table must be addresses of instructions in the procedure executing the case instruction.

CSA selects the new PC by indexing. If the index, a signed integer, is greater than or equal to the lower bound and less than or equal to the upper bound, then fetch the new PC from the list of instruction pointers by indexing with index-lower. The table does not contain the value of the upper bound, but the value of upper-lower as an unsigned integer. The default instruction pointer is used when the index is out of bounds. If the resulting PC is 0, then trap.

CSB selects the new PC by searching. The table is searched for an entry with index value equal to the case index. That entry or, if none is found, the default entry contains the new PC. When the resulting PC is 0, a trap is performed.

The choice of which case instruction to use for each source language case statement is up to the front end. If the range of the index value is dense, i.e

     (highest value − lowest value) / number of cases

is less than some threshold, then CSA is the obvious choice. If the range is sparse, CSB is better.

|--------------------| |--------------------| high address | pointer for upb | | pointer n-1 | |--------------------| |- - - - - - - | | . | | index n-1 | | . | |--------------------| | . | | . | | . | | . | | . | | . | | . | |--------------------| | . | | pointer 1 | |--------------------| |- - - - - - - | | pointer for lwb+1 | | index 1 | |--------------------| |--------------------| | pointer for lwb | | pointer 0 | |--------------------| |- - - - - - - | | upper - lower | | index 0 | |--------------------| |--------------------| | lower bound | | number of entries | |--------------------| |--------------------| | default pointer | | default pointer | low address |--------------------| |--------------------|

CSA descriptor CSB descriptor

Figure 4. Descriptor layout for CSA and CSB

8

8. ENVIRONMENT INTERACTIONS

EM programs can interact with their environment in three ways. Two, starting/stopping and monitor calls, are dealt with in this chapter. The remaining way to interact, interrupts, will be treated together with traps in chapter 9.

8.1 Program starting and stopping

EM user programs start with a call to a procedure called _m_a_i_n. The assembler and backends look for the definition of a procedure with this name in their input. The call passes three parameters to the procedure. The parameters are similar to the parameters supplied by the UNIX ® operating system to C programs. These parameters are often called argc, argv and envp. Argc is the parameter nearest to LB and is a wordsized integer. The other two are pointers to the first element of an array of string pointers. The argv array contains argc strings, the first of which contains the program call name. The other strings in the argv array are the program parameters.

The envp array contains strings in the form "name=string", where ’name’ is the name of an environment variable and string its value. The envp is terminated by a zero pointer.

An EM user program stops if the program returns from the first invocation of _m_a_i_n. The contents of the function return area are used to procure a wordsized program return code. EM programs also stop when traps and interrupts occur that are not caught and when the exit monitor call is executed.

8.2 Input/Output and other monitor calls

EM differs from most conventional machines in that it has high level i/o instructions. Typical instructions are OPEN FILE and READ FROM FILE instead of low level instructions such as setting and clearing bits in device registers. By providing such high level i/o primitives, the task of implementing EM on various non EM machines is made considerably easier.

I/O is initiated by the MON instruction, which expects an iocode on top of the stack. Often there are also parameters which are pushed on the stack in reverse order, that is: last parameter first. Some i/o functions also provide results, which are returned on the stack. In the list of monitor calls we use several types of parameters and results, these types consist of integers and unsigneds of varying sizes, but never smaller than the wordsize, and the two pointer types.

The names of the types used are:

The table below lists the i/o codes with their results and parameters. This list is similar to the system calls of the UNIX Version 7 operating system.

To execute a monitor call, proceed as follows:

An error code is present on the top of the stack after execution of most monitor calls. If this error code is zero, the call performed the action requested and the results are available on top of the stack. Non-zero error codes indicate a failure, in this case no results are available and the error code has been pushed twice. This construction enables programs to test for failure with a single instruction ( TEQ or TNE ) and still find out the cause of the failure. The result name ’e’ is reserved for the error code.

List of monitor calls.

nr  name     parameters      results                function

Codes 0, 11, 13, 17, 31, 32, 38, 39, 40, 45, 49, 50, 52, 55, 57, 58, 62, and 63 are not used.

All monitor calls, except fork and sigtrp are the same as the UNIX version 7 system calls.

The sigtrp entry maps UNIX signals onto EM interrupts. Normally, trapno is in the range 0 to 252. In that case it requests that signal signo will cause trap trapno to occur. When given trap number −2, default signal handling is reset, and when given trap number −3, the signal is ignored.

The flag returned by fork is 1 in the child process and 0 in the parent. The pid returned is the process-id of the other process.

9

9. TRAPS AND INTERRUPTS

EM provides a means for the user program to catch all traps generated by the program itself, the hardware, or external conditions. This mechanism uses five instructions: LIM, SIM, SIG, TRP and RTT. This section of the manual may be omitted on the first reading since it presupposes knowledge of the EM instruction set.

The action taken when a trap occurs is determined by the value of an internal EM trap register. This register contains a pointer to a procedure. Initially the pointer used is zero and all traps halt the program with, hopefully, a useful message to the outside world. The SIG instruction can be used to alter the trap register, it pops a procedure pointer from the stack into the trap register. When a trap occurs after storing a nonzero value in the trap register, the procedure pointed to by the trap register is called with the trap number as the only parameter (see below). SIG returns the previous value of the trap register on the stack. Two consecutive SIGs are a no-op. When a trap occurs, the trap register is reset to its initial condition, to prevent recursive traps from hanging the machine up, e.g. stack overflow in the stack overflow handling procedure.

The runtime systems for some languages need to ignore some EM traps. EM offers a feature called the ignore mask. It contains one bit for each of the lowest 16 trap numbers. The bits are numbered 0 to 15, with the least significant bit having number 0. If a certain bit is 1 the corresponding trap never occurs and processing simply continues. The actions performed by the offending instruction are described by the Pascal program in appendix A.
If the bit is 0, traps are not ignored. The instructions LIM and SIM allow copying and replacement of the ignore mask.

The TRP instruction generates a trap, the trap number being found on the stack. This is, among other things, useful for library procedures and runtime systems. It can also be used by a low level trap procedure to pass the trap to a higher level one (see example below).

The RTT instruction returns from the trap procedure and continues after the trap. In the list below all traps marked with an asterisk (’*’) are considered to be fatal and it is explicitly undefined what happens when restarting after the trap.

The way a trap procedure is called is completely compatible with normal calling conventions. The only way a trap procedure differs from normal procedures is the return. It has to use RTT instead of RET. This is necessary because the complete runtime status is saved on the stack before calling the procedure and all this status has to be reloaded. Error numbers are in the range 0 to 252. The trap numbers are divided into three categories:

0−15

Reserved for use by compilers, run time systems, etc.

EM machine errors are numbered as follows:

As an example, suppose a subprocedure has to be written to do a numeric calculation. When an overflow occurs the computation has to be stopped and the higher level procedure must be resumed. This can be programmed as follows using the mechanism described above:

ersave

msave

jmpbuf

Example of catch procedure

10

10. EM MACHINE LANGUAGE

The EM machine language is designed to make program text compact and to make decoding easy. Compact program text has many advantages: programs execute faster, programs occupy less primary and secondary storage and loading programs into satellite processors is faster. The decoding of EM machine language is so simple, that it is feasible to use interpreters as long as EM hardware machines are not available. This chapter is irrelevant when back ends are used to produce executable target machine code.

10.1 Instruction encoding

A design goal of EM is to make the program text as compact as possible. Decoding must be easy, however. The encoding is fully byte oriented, without any small bit fields. There are 256 primary opcodes, two of which are an escape to two groups of 256 secondary opcodes each.

EM instructions without arguments have a single opcode assigned, possibly escaped:

|--------------| | opcode | |--------------|

|--------------|--------------| | escape | opcode | |--------------|--------------|

The encoding for instructions with an argument is more complex. Several instructions have an address from the global data area as argument. Other instructions have different opcodes for positive and negative arguments.

There is always an opcode that takes the next two bytes as argument, high byte first:

|--------------|--------------|--------------| | opcode | hibyte | lobyte | |--------------|--------------|--------------|

|--------------|--------------|--------------|--------------| | escape | opcode | hibyte | lobyte | |--------------|--------------|--------------|--------------|

An extra escape is provided for instructions with four or eight byte arguments.

|--------------|--------------|--------------| |--------------| | ESCAPE | opcode | hibyte |...| lobyte | |--------------|--------------|--------------| |--------------|

For most instructions some argument values predominate. The most frequent combinations of instruction and argument will be encoded in a single byte, called a mini:

|---------------| |opcode+argument| (mini) |---------------|

The number of minis is restricted, because only 254 primary opcodes are available. Many instructions have the bulk of their arguments fall in the range 0 to 255. Instructions that address global data have their arguments distributed over a wider range, but small values of the high byte are common. For all these cases there is another encoding that combines the instruction and the high byte of the argument into a single opcode. These opcodes are called shorties. Shorties may be escaped.

|--------------|--------------| | opcode+high | lobyte | (shortie) |--------------|--------------|

|--------------|--------------|--------------| | escape | opcode+high | lobyte | |--------------|--------------|--------------|

Escaped shorties are useless if the normal encoding has a primary opcode. Note that for some instruction-argument combinations several different encodings are available. It is the task of the assembler to select the shortest of these. The savings by these mini and shortie opcodes are considerable, about 55%.

Further improvements are possible: the arguments of many instructions are a multiple of the wordsize. Some do also not allow zero as an argument. If these arguments are divided by the wordsize and, when zero is not allowed, then decremented by 1, more of them can be encoded as shortie or mini. The arguments of some other instructions rarely or never assume the value 0, but start at 1. The value 1 is then encoded as 0, 2 as 1 and so on.

Assigning opcodes to instructions by the assembler is completely table driven. For details see appendix B.

10.2 Procedure descriptors

The procedure identifiers used in the interpreter are indices into a table of procedure descriptors. Each descriptor contains:

10.3 Load format

The EM machine language load format defines the interface between the EM assembler/loader and the EM machine itself. A load file consists of a header, the program text to be executed, a description of the global data area and the procedure descriptor table, in this order. All integers in the load file are presented with the least significant byte first.

The header has two parts: the first half (eight 16-bit integers) aids in selecting the correct EM machine or interpreter. Some EM machines, for instance, may have hardware floating point instructions. The header entries are as follows (bit 0 is rightmost):

The second part of the header (eight entries, of pointer size bytes each) describes the load file itself:

The program text consists of NTEXT bytes. NTEXT is always a multiple of the wordsize. The first byte of the program text is the first byte of the instruction address space, i.e. it has address 0. Pointers into the program text are found in the procedure descriptor table where relocation is simple and in the global data area. The initialization of the global data area allows easy relocation of pointers into both address spaces.

The global data area is described by the NDATA descriptors. Each descriptor describes a number of consecutive words (of wordsize) and consists of a sequence of bytes. While reading the descriptors from the load file, one can initialize the global data area from low to high addresses. The size of the initialized data area is given by SZDATA, this number can be used to check the initialization.
The header of each descriptor consists of a byte, describing the type, and a count. The number of bytes used for this (unsigned) count depends on the type of the descriptor and is either a pointer-sized integer or one byte. The meaning of the count depends on the descriptor type. At load time an interpreter can perform any conversion deemed necessary, such as reordering bytes in integers and pointers and adding base addresses to pointers.

In the following pictures we show a graphical notation of the initializers. The leftmost rectangle represents the leading byte.

Fields marked with

------------------- | 0 | n | repeat last initialization n times -------------------

--------- | 1 | m | m uninitialized words ---------

____________ / bytes \ ----------------- ----- | 2 | m | b | b |...| b | m initialized bytes ----------------- -----

_________ / word \ ----------------------- | 3 | m | w |... m initialized wordsized integers -----------------------

_________ / pointer \ ----------------------- | 4 | m | p |... m initialized data pointers -----------------------

_________ / pointer \ ----------------------- | 5 | m | p |... m initialized instruction pointers -----------------------

____________ / bytes \ ------------------------- | 6 | m | b | b |...| b | initialized integer of size m -------------------------

____________ / bytes \ ------------------------- | 7 | m | b | b |...| b | initialized unsigned of size m -------------------------

____________ / string \ ------------------------- | 8 | m | s | initialized float of size m -------------------------

The NPROC procedure descriptors on the load file consist of an instruction space address (of pointer size) and an integer (of pointer size) specifying the number of bytes for locals.

11

11. EM ASSEMBLY LANGUAGE

We use two representations for assembly language programs, one is in ASCII and the other is the compact assembly language. The latter needs less space than the first for the same program and therefore allows faster processing. Our only program accepting ASCII assembly language converts it to the compact form. All other programs expect compact assembly input. The first part of the chapter describes the ASCII assembly language and its semantics. The second part describes the syntax of the compact assembly language. The last part lists the EM instructions with the type of arguments allowed and an indication of the function. Appendix A gives a detailed description of the effect of all instructions in the form of a Pascal program.

11.1 ASCII assembly language

An assembly language program consists of a series of lines, each line may be blank, contain one (pseudo)instruction or contain one label. Input to the assembler is in lower case. Upper case is used in this document merely to distinguish keywords from the surrounding prose. Comment is allowed at the end of each line and starts with a semicolon ";". This kind of comment does not exist in the compact form.

Labels must be placed all by themselves on a line and start in column 1. There are two kinds of labels, instruction and data labels. Instruction labels are unsigned positive integers. The scope of an instruction label is its procedure.

The pseudoinstructions CON, ROM and BSS may be preceded by a line containing a 1−8 character data label, the first character of which is a letter, period or underscore. The period may only be followed by digits, the others may be followed by letters, digits and underscores. The use of the character "." followed by a constant, which must be in the range 1 to 32767 (e.g. ".40") is recommended for compiler generated programs. These labels are considered as a special case and handled more efficiently in compact assembly language (see below). Note that a data label on its own or two consecutive labels are not allowed.

Each statement may contain an instruction mnemonic or pseudoinstruction. These must begin in column 2 or later (not column 1) and must be followed by a space, tab, semicolon or LF. Everything on the line following a semicolon is taken as a comment.

Each input file contains one module. A module may contain many procedures, which may be nested. A procedure consists of a PRO statement, a (possibly empty) collection of instructions and pseudoinstructions and finally an END statement. Pseudoinstructions are also allowed between procedures. They do not belong to a specific procedure.

All constants in EM are interpreted in the decimal base. The ASCII assembly language accepts constant expressions wherever constants are allowed. The operators recognized are: +, −, *, % and / with the usual precedence order. Use of the parentheses ( and ) to alter the precedence order is allowed.

11.1.1 Instruction arguments

Unlike many other assembly languages, the EM assembly language requires all arguments of normal and pseudoinstructions to be either a constant or an identifier, but not a combination of these two. There is one exception to this rule: when a data label is used for initialization or as an instruction argument, expressions of the form ’label+constant’ and ’label-constant’ are allowed. This makes it possible to address, for example, the third word of a ten word BSS block directly. Thus LOE LABEL+4 is permitted and so is CON LABEL+3. The resulting address is must be in the same fragment as the label. It is not allowed to add or subtract from instruction labels or procedure identifiers, which certainly is not a severe restriction and greatly aids optimization.

Instruction arguments can be constants, data labels, data labels offsetted by a constant, instruction labels and procedure identifiers. The range of integers allowed depends on the instruction. Most instructions allow only integers (signed or unsigned) that fit in a word. Arguments used as offsets to pointers should fit in a pointer-sized integer. Finally, arguments to LDC should fit in a double-word integer.

Several instructions have two possible forms: with an explicit argument and with an implicit argument on top of the stack. The size of the implicit argument is the wordsize. The implicit argument is always popped before all other operands. For example: ’CMI 4’ specifies that two four-byte signed integers on top of the stack are to be compared. ’CMI’ without an argument expects a wordsized integer on top of the stack that specifies the size of the integers to be compared. Thus the following two sequences are equivalent:

Section 11.1.6 shows the arguments allowed for each instruction.

11.1.2 Pseudoinstruction arguments

Pseudoinstruction arguments can be divided in two classes: Initializers and others. The following initializers are allowed: signed integer constants, unsigned integer constants, floating-point constants, strings, data labels, data labels offsetted by a constant, instruction labels and procedure identifiers.

Constant initializers in BSS, HOL, CON and ROM pseudoinstructions can be followed by a letter I, U or F. This indicator specifies the type of the initializer: Integer, Unsigned or Float. If no indicator is present I is assumed. The size of the initializer is the wordsize unless the indicator is followed by an integer specifying the initializer’s size. This integer is governed by the same restrictions as for transfer of objects to/from memory. As in instruction arguments, initializers include expressions of the form: "LABEL+offset" and "LABEL−offset". The offset must be an unsigned decimal constant. The ’IUF’ indicators cannot be used in the offsets.

Data labels are referred to by their name.

Strings are surrounded by double quotes ("). Semicolon’s in string do not indicate the start of comment. In the ASCII representation the escape character \ (backslash) alters the meaning of subsequent character(s). This feature allows inclusion of zeroes, graphic characters and the double quote in the string. The following escape sequences exist:

The escape \ddd consists of the backslash followed by 1, 2, or 3 octal digits specifying the value of the desired character. If the character following a backslash is not one of those specified, the backslash is ignored. Example: CON "hello\012\0". Each string element initializes a single byte. The ASCII character set is used to map characters onto values.

Instruction labels are referred to as *1, *2, etc. in both branch instructions and as initializers.

The notation $procname means the identifier for the procedure with the specified name. This identifier has the size of a pointer.

11.1.3 Notation

First, the notation used for the arguments, classes of instructions and pseudoinstructions.

11.1.4 Pseudoinstructions

11.1.4.1 Storage declaration

Initialized global data is allocated by the pseudoinstruction CON, which needs at least one argument. Each argument is used to allocate and initialize a number of consecutive bytes in data memory. The number of bytes to be allocated and the alignment depend on the type of the argument. For each argument, an integral number of words, determined by the argument type, is allocated and initialized.

The pseudoinstruction ROM is the same as CON, except that it guarantees that the initialized words will not change during the execution of the program. This information allows optimizers to do certain calculations such as array indexing and subrange checking at compile time instead of at run time.

The pseudoinstruction BSS allocates uninitialized global data or large blocks of data initialized by the same value. The first argument to this pseudo is the number of bytes required, which must be a multiple of the wordsize. The other arguments specify the value used for initialization and whether the initialization is only for convenience or a strict necessity. The pseudoinstruction HOL is similar to BSS in that it requests an (un)initialized global data block. Addressing of a HOL block, however, is quasi absolute. The first byte is addressed by 0, the second byte by 1 etc. in assembly language. The assembler/loader adds the base address of the HOL block to these numbers to obtain the absolute address in the machine language.

The scope of a HOL block starts at the HOL pseudo and ends at the next HOL pseudo or at the end of a module whatever comes first. Each instruction falls in the scope of at most one HOL block, the current HOL block. It is not allowed to have more than one HOL block per procedure.

The alignment restrictions are enforced by the pseudoinstructions. All initializers are aligned on a multiple of their size or the wordsize whichever is smaller. Strings form an exception, they are to be seen as a sequence of initializers each for one byte, i.e. strings are not padded with zero bytes. Switching to another type of fragment or placing a label forces word-alignment. There are three types of fragments in global data space: CON, ROM and BSS/HOL.

BSS <cst1>,<val>,<cst2>

HOL <cst1>,<val>,<cst2>

CON <val>+

ROM <val>+

11.1.4.2 Partitioning

Two pseudoinstructions partition the input into procedures:

PRO <pro>[,<cst>]

END [<cst>]

11.1.4.3 Visibility

Names of data and procedures in an EM module can either be internal or external. External names are known outside the module and are used to link several pieces of a program. Internal names are not known outside the modules they are used in. Other modules will not ’see’ an internal name.

To reduce the number of passes needed, it must be known at the first occurrence whether a name is internal or external. If the first occurrence of a name is in a definition, the name is considered to be internal. If the first occurrence of a name is a reference, the name is considered to be external. If the first occurrence is in one of the following pseudoinstructions, the effect of the pseudo has precedence.

EXA <dlb>

EXP <pro>

INA <dlb>

INP <pro>

11.1.4.4 Miscellaneous

Two other pseudoinstructions provide miscellaneous features:

EXC <cst1>,<cst2>

MES <cst>[,<par>]*

11.2 The Compact Assembly Language

The assembler accepts input in a highly encoded form. This form is intended to reduce the amount of file transport between the front ends, optimizers and back ends, and also reduces the amount of storage required for storing libraries. Libraries are stored as archived compact assembly language, not mac