P-code machine
In computer programming, a p-code machine, or portable code machine is a virtual machine designed to execute p-code. This term is applied both generically to all such machines, and to specific implementations, the most famous being the p-Machine of the Pascal-P system, particularly the UCSD Pascal implementation .
Although the concept was first implemented circa 1966, the term p-code first appeared in the early 1970s. Two early compilers generating p-code were the Pascal-P compiler in 1973, by Kesav V. Nori, Urs Ammann, Kathleen Jensen, Hans-Heinrich Nägeli, and Christian Jacobi, and the Pascal-S compiler in 1975, by Niklaus Wirth.
Programs that have been translated to p-code can either be interpreted by a software program that emulates the behavior of the hypothetical CPU, or translated into the machine code of the CPU on which the program is to run and then executed. If there is sufficient commercial interest, a hardware implementation of the CPU specification may be built.
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.
In the early 1980s, at least two operating systems achieved machine independence through extensive use of p-code. The Business Operating System 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.
The Go programming language uses a generic, portable assembly as a form of p-code, implemented by Ken Thompson as an extension of the work on Plan 9 from Bell Labs. Unlike CLR bytecode or JVM bytecode, there is no stable specification, and the Go build tools do not emit a bytecode format to be used at a later time. The Go assembler uses the generic assembly language as an intermediate representation, and Go executables are machine-specific statically linked binaries.
UCSD p-Machine
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, character, integer, real, set, and pointer types natively.Some simple instructions:
Insn. Stack Stack Description
before after
adi i1 i2 i1+i2 add two integers
adr r1 r2 r1+r2 add two reals
dvi i1 i2 i1/i2 integer division
inn i1 s1 b1 set membership; b1 = whether i1 is a member of s1
ldci i1 i1 load integer constant
mov a1 a2 move
not b1 ~b1 boolean negation
Environment
Unlike other stack-based environments but very similar to a real target CPU, the p-System has only one stack shared by procedure stack frames and the arguments to local instructions. Three of the machine's registers point into the stack :- SP points to the top of the stack.
- MP marks the beginning of the active stack frame.
- EP points to the highest stack location used in the current procedure.
The fifth register, PC, points at the current instruction in the code area.
Calling conventions
Stack frames look like this:EP ->
local stack
SP ->...
locals
...
parameters
...
return address
previous EP
dynamic link
static link
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. 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 issuescup n, p
to call a user procedure. 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, 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. 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, standard procedure
q can be called withcsp q
These standard procedures are Pascal procedures like
readln, 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:- lit 0, a : load constant a
- opr 0, a : execute operation a
- lod l, a : load variable l,a
- sto l, a : store variable l,a
- cal l, a : call procedure a at level l
- int 0, a : increment t-register by a
- jmp 0, a : jump to a
- jpc 0, a : jump conditional to a
const
amax=2047;
levmax=3;
cxmax=200;
type
fct=;
instruction=packed record
f:fct;
l:0..levmax;
a:0..amax;
end;
var
code: array of instruction;
procedure interpret;
const stacksize = 500;
var
p, b, t: integer;
i: instruction;
s: array of integer;
function base: integer;
var b1: integer;
begin
b1 := b;
while l > 0 do begin
b1 := s;
l := l - 1
end;
base := b1
end ;
begin
writeln;
t := 0; b := 1; p := 0;
s := 0; s := 0; s := 0;
repeat
i := code; p := p + 1;
with i do
case f of
lit: begin t := t + 1; s := a end;
opr:
case a of
0:
begin
t := b - 1; p := s; b := s;
end;
1: s := -s;
2: begin t := t - 1; s := s + s end;
3: begin t := t - 1; s := s - s end;
4: begin t := t - 1; s := s * s end;
5: begin t := t - 1; s := s div s end;
6: s := ord;
8: begin t := t - 1; s := ord end;
9: begin t := t - 1; s := ord end;
10: begin t := t - 1; s := ord end;
11: begin t := t - 1; s := ord end;
12: begin t := t - 1; s := ord end;
13: begin t := t - 1; s := ord end;
end;
lod: begin t := t + 1; s := s end;
sto: begin s := s; writeln; t := t - 1 end;
cal:
begin
s := base; s := b; s := p;
b := t + 1; p := a
end;
int: t := t + a;
jmp: p := a;
jpc: begin if s = 0 then p := a; t := t - 1 end
end
until p = 0;
writeln;
end ;
This machine was used to run Wirth's PL/0, a Pascal subset compiler used to teach compiler development.