P code machine

Benefits and weaknesses of implementing p-code

Compared to direct translation into native machine code, a two-stage approach involving translation into p-code and execution by an interpreter or just-in-time compiler offers several advantages.

It is much easier to write a small p-code interpreter for a new machine than it is to modify a compiler to generate native code for the same machine.

Generating machine code is one of the more complicated parts of writing a compiler. By comparison, generating p-code is much easier because no machine-dependent behaviour must be considered in the generation of the bytecode. This makes it useful for getting a compiler up and running quickly.

Since p-code is based on an ideal virtual machine, a p-code program is often much smaller than the same program translated to machine code.

When the p-code is interpreted, the interpreter can apply additional run-time checks that are difficult to implement with native code.

One of the significant disadvantages of p-code is execution speed, which can sometimes be remedied through the use of a JIT compiler. P-code is often also easier to reverse-engineer than native code.

In the early 1980s, at least two operating systems achieved machine independence through extensive use of p-code. The Business Operating System (BOS) was a cross-platform operating system designed to run p-code programs exclusively. The UCSD p-System, developed at The University of California, San Diego, was a self-compiling and self-hosted operating system based on p-code optimized for generation by the Pascal programming language.

In the 1990s, translation into p-code became a popular strategy for implementations of languages such as Python, Microsoft P-Code in Visual Basic and Java bytecode in Java.

Architecture

Like many other p-code machines, the UCSD p-Machine is a stack machine, which means that most instructions take their operands from the stack, and place results back on the stack. Thus, the "add" instruction replaces the two topmost elements of the stack with their sum. A few instructions take an immediate argument. Like Pascal, the p-code is strongly typed, supporting boolean (b), character (c), integer (i), real (r), set (s), and pointer (a) types natively.

Some simple instructions:

Insn. Stack Stack Description before after adi i1 i2 i1+i2 add two integersadr r1 r2 r1+r2 add two realsdvi i1 i2 i1/i2 integer divisioninn i1 s1 b1 set membership; b1 = whether i1 is a member of s1ldci i1 i1 load integer constantmov a1 a2 movenot b1 ~b1 boolean negation

Environment

Unlike other stack-based environments (such as Forth and the Java Virtual Machine) but very similar to a real target CPU, the p-System has only one stack shared by procedure stack frames (providing return address, etc.) and the arguments to local instructions. Three of the machine's registers point into the stack (which grows upwards):

SP points to the top of the stack (the stack pointer).

MP marks the beginning of the active stack frame (the mark pointer).

EP points to the highest stack location used in the current procedure (the extreme pointer).

Also present is a constant area, and, below that, the heap growing down towards the stack. The NP (the new pointer) register points to the top (lowest used address) of the heap. When EP gets greater than NP, the machine's memory is exhausted.

The fifth register, PC, points at the current instruction in the code area.

Calling conventions

Stack frames look like this:

EP -> local stackSP -> ... locals ... parameters ... return address (previous PC) previous EP dynamic link (previous MP) static link (MP of surrounding procedure)MP -> function return value

The procedure calling sequence works as follows: The call is introduced with

mst n

where n specifies the difference in nesting levels (remember that Pascal supports nested procedures). This instruction will mark the stack, i.e. reserve the first five cells of the above stack frame, and initialise previous EP, dynamic, and static link. The caller then computes and pushes any parameters for the procedure, and then issues

cup n, p

to call a user procedure (n being the number of parameters, p the procedure's address). This will save the PC in the return address cell, and set the procedure's address as the new PC.

User procedures begin with the two instructions

ent 1, i ent 2, j

The first sets SP to MP + i, the second sets EP to SP + j. So i essentially specifies the space reserved for locals (plus the number of parameters plus 5), and j gives the number of entries needed locally for the stack. Memory exhaustion is checked at this point.

Returning to the caller is accomplished via

retC

with C giving the return type (i, r, c, b, a as above, and p for no return value). The return value has to be stored in the appropriate cell previously. On all types except p, returning will leave this value on the stack.

Instead of calling a user procedure (cup), standard procedure q can be called with

csp q

These standard procedures are Pascal procedures like readln() (csp rln), sin() (csp sin), etc. Peculiarly eof() is a p-Code instruction instead.

Example machine

Niklaus Wirth specified a simple p-code machine in the 1976 book Algorithms + Data Structures = Programs. The machine had 3 registers - a program counter p, a base register b, and a top-of-stack register t. There were 8 instructions, with one (opr) having multiple forms.

This is the code for the machine, written in Pascal:

This machine was used to run Wirth's PL/0, which was a Pascal subset compiler used to teach compiler development.