A PL/0 Processor

It is indeed remarkable that the PL/O compiler was so far developed without any knowledge of the machine for which it was supposed to generate code. But why should the structure of an object machine influence the parsing and error recovery scheme of a compiler! In fact, it must not do so. Instead, the proper scheme for code generation for any computer should be superimposed on the existing parser by the method of stepwise refinement of the existing program. Since we are about to do this, it becomes necessary to select a processor for which to compile.

In order to keep the description of the compiler reasonably simple and free from extraneous considerations of peculiar properties of a real, existing processor, we shall postulate a computer of our own choice, specifically tailored to the needs of PL/O. Since this processor does not really exist (in hardware), it is a hypothetical processor; it will be called the PL/O machine.

It is not the aim of this section to explain the detailed reasoning that led to the choice of exactly this kind of machine architecture. Instead, it is to serve as a descriptive manual consisting of an intuitive introduction, followed by a detailed definition of the processor in the form of an algorithm. This formalization may serve as an example for accurate and detailed algorithmic descriptions of actual processors. The algorithm interprets PL/O instructions sequentially, and is called an interpreter.

The PL/O machine consists of two stores: an instruction register and three address registers. The program store, called code, is loaded by the compiler and remains unchanged during interpretation of the code. It can then be considered as a read-only store. The data store S is organized as a stack, and all arithmetic operators operate on the two elements on top of the stack, replacing their operands by a result. The top element is addressed (indexed) by the top stack register T. The instruction register I contains the instruction that is currently being interpreted. The program address register P designates the next instruction to be fetched for interpretation.

Every procedure in PL/O may contain local variables. Since procedures may be activated recursively, storage for these local variables may not be allocated before the actual procedure call. Hence, the data segments for individual procedures are stacked up consecutively in the stack store S. Since procedure activations strictly obey the first-in-last-out scheme, the stack is the appropriate storage allocation strategy. Every procedure owns some internal information of its own, namely, the program address of its call (the so-called return address), and the address of the data segment of its caller. These two addresses are needed for proper resumption of program execution after termination of the procedure. They can be understood as internal or implicit local variables allocated in the procedure’s data segment.332 We call them the return address RA and the dynamic link DL. The origin of the dynamic link, that is, the address of the most recently allocated data segment, is retained in the base address register B.

Since the actual allocation of storage takes place during execution (interpretation) time, the compiler cannot equip the generated code with absolute addresses. Since it can only determine the location of variables within a data segment, it is capable of providing relative addresses only. The interpreter has to add to this so-called displacement to the base address of the appropriate data segment. If a variable is local to the procedure currently being interpreted, then this base address is given by the B register. Otherwise, it must be obtained by descending the chain of data segments. The compiler, however, can only know the static depth of an access path, whereas the dynamic link chain maintains the dynamic history of procedure activations. Unfortunately, these two access paths are not necessarily the same.

For example, assume that a procedure A calls a procedure B declared local to A, B calls C declared local to B, and C calls B (recursively). We say that A is declared at level 1, Bat level 2, C at level 3 (see Fig. 5.7). If a variable a declared in A is to be accessed in B, then the compiler knows that there exists a level difference of 1 between B and A. Descending one step along the dynamic link chain, however, would result in an access to a variable local to C!

Hence, it is plain that a second link chain has to be provided that properly links data segments in the way the compiler can see the situation. We call this the static link SL.

Addresses are therefore generated as pairs of numbers indicating the static level difference and the relative displacement within a data segment. We assume that each location of the data store is capable of holding an address or an integer.

The instruction set of the PL/O machine is tuned to the requirements of the PL/O language. It includes the following orders:

1. An instruction to load numbers (literals) onto the stack (LIT).

2. An instruction to fetch variables onto the top of the stack (LOD).

3. A store instruction corresponding to assignment statements (STO). 4. An introduction to activate a subroutine corresponding to a procedure call (CAL).

4. An instruction to allocate storage on the stack by incrementing the stack pointer T (INT).

5. Instructions for unconditional and conditional transfer of control, used in if- and while statements (JMP, JPC).

6. A set of arithmetic and relational operators (OPR).

The format of instructions is determined by the need for three components, namely, an operation code f and a parameter consisting of one or two parts (see Fig. 5.8). In the case of operators the parameter a determines the identity of the operator; in the other cases it is either a number (LIT, INT), a program address (JMP, JPC, CAL), or a data address (LOD, STO).

The details of operation of the PL/O machine should be evident from the procedure called interpret that is part of Program 5.6, which combines the completed compiler with the interpreter into a system that translates and subsequently executes PL/O programs. The modification of this program to generate code for an existing computer is left as an excercise for the interested reader. The resulting expansion of the compiler program may be taken as a measure of the appropriateness of the chosen computer for the present task.

There is no doubt that the presented PL/O computer could be expanded into a more sophisticated organization in order to make certain operations more efficient. One instance is the chosen addressing mechanism. The presented solution was chosen because of its inherent simplicity and because all improvements must essentially be based on it and derived from it.