Note: I've just migrated to a different physical server to run Spivey's Corner,
with a new architecture, a new operating system, a new version of PHP, and an updated version of MediaWiki.
Please let me know if anything needs adjustment! – Mike

Keiko instructions in stages

From Compilers
Revision as of 13:14, 11 May 2022 by Mike (talk | contribs)
Jump to navigation Jump to search

Each lab adds more Keiko instructions to the set used by the compiler. Listed here are the instructions that are used by the compiler's code generator, and not the ones that are used in boilerplate code that surrounds it, or in fixed patterns to translate special constructs. For example, the compiler for Lab 1 translates the whole program into a single procedure, so the compiler output contains a PROC directive as boilerplate; the print statement in the language is implemented as a procedure call, so the code generator can produce a PCALL instruction, though the language does not have subroutine calls in general. Therefore I haven't listed those instructions under Lab 1.

Lab 1 – Expressions and statements

CONST
push a constant.
LDGW
load a word from a global address.
STGW
store a word to a global address.
UMINUS, etc.
unary arithmetic operations.
PLUS, etc.
binary arithmetic operations.
JEQ, etc.
conditional jumps.
JUMP
unconditional jump.
CASEJUMP
jump table.
LABEL
directive to place label.
NOP
null operation.

Lab 2 – Data structures

All instructions from Lab 1, plus the following.

LOADW
load word from arbitrary address.
LOADC
load character.
STOREW
store word to arbitrary address.
STOREC
store character.
GLOBAL
push address of global variable.
BOUND
array bound check.
OFFSET
add address and offset.
GLOVAR
reserve space for global variable.

Other instructions can be introduced by the peephole optimiser.

LDNW
load word at constant offset.
STNW
store word at constant offset.

Lab 3 – Procedures

Additional instructions as follows.

LOCAL
push address of local variable.
PCALLW
call procedure with word-sized result.
RETURNW
return from procedure with word-sized result.
PACK
pack code and frame addresses as a closure.
UNPACK
unpack a closure.
PROC
announce beginning of a procedure.

Also, introduced by the peephole optimiser.

LDLW
load local word.
STLW
store local word.

Lab 4 – Machine code

The code generator produces operator trees rather postfix code, but many of the operators are similar to Keiko instructions.

<LOCAL off>
address of local variable, at offset off from the frame pointer.
<GLOBAL _name>
address of global variable.
<OFFSET, x, y>
add address x and offset y.
<CONST n>
constant with value n.
<REGVAR n>
location of register variable n.
<LOADW, x>
load word from address x.
<LOADC, x>
load character from address x.
<STOREW, x, y>
store word x at address y.
<STOREC, x, y>
store character x at address y.
<ARG n, x>
pass procedure argument n with value x.
<PLUS, x, y>, etc.
binary arithmetic operations.
<UMINUS, x>, etc.
unary arithmetic operations.
<PCALL, x>
call procedure x.
<JEQ lab, x, y>, etc.
conditional jumps.
<JUMP lab>
unconditional jump.
<LABEL lab>
place label as jump target.
<JCASE ([l0; ...; ln-1], lab), x>
jump table.
<NOP>
null operation.
<RESULTW, x>
specify procedure result.

Like the Keiko-based compilers, this one has a simplifier that works on the code output by the intermediate code generator. Unlike the peephole optimiser, however, the simplifier does not try to merge operations together, but leaves the translator to recognise combinations that can be implemented in single machine instructions.