The compiler from inside

The Oberon compiler is four modules, a hundred and nine kilobytes of source. It can be read over a weekend, and that is perhaps the main reason to take this system in particular: the whole path from text to machine code is in view.

The scheme has no intermediate representation: parsing emits code directly. ORP reads a token, works out what it is, and calls ORG on the spot to emit instructions. No tree, no optimisation passes. Hence the speed: the whole system rebuilds in minutes on a four-megahertz machine.

The item

The central notion of the code generator is the item. It describes where a value currently is: in a register, in memory at an offset from a base, in an instruction's immediate field, or as a branch condition not yet evaluated.

Item = RECORD
  mode: INTEGER;      (* where it sits: Const, Var, Par, Reg, RegI, Cond *)
  type: ORB.Type;
  a, b, r: LONGINT;   (* offset, base, register *)
  rdo: BOOLEAN        (* read-only *)
END

Code generation is a matter of moving an item from one state to another. load(x) drags the value into a register if it is not there already. Register allocation is a simple stack: RH ("register high") points at the first free one, incR and DEC(RH) move it.

How a[i] becomes instructions

A good example, because the whole style shows in it. The Index procedure in ORG.Mod:

1. If the index is a constant and the array length is known, the bounds are checked at compile time (bad index) and the offset is simply added to the address. Not a single instruction at run time.

2. Otherwise the index is loaded into a register and a bounds check is inserted:

Put1a(Cmp, RH, y.r, lim) ; compare the index against the length Trap(10, 1) ; if not below — trap number 1

Cmp is a Sub whose destination is discarded: only the flags are wanted. Trap(10, 1) gives a branch-with-link through the MT register on condition CC, with error number 1 in the body of the instruction.

3. The index is multiplied by the element size. For four-byte elements that is a left shift by two (Lsl); for the rest, a real multiplication.

4. The offset is added to the base, giving the address.

So every index operation with a variable subscript costs two extra instructions: a comparison and a conditional branch. How much that is in practice is in the chapter what we measured.

For an open array the length is not known at compile time and has to be read from the stack, where it sits beside the parameter itself.

Traps

All run-time checks are built the same way: a comparison, then a conditional branch through MT with a link. Into the instruction's spare bits the code generator puts the position in the source and the error number:

PROCEDURE Trap(cond, num: LONGINT);
BEGIN Put3(BLR, cond, ORS.Pos()*100H + num*10H + MT)
END Trap;

The hardware ignores those bits — to it this is an ordinary branch through a register. The trap handler digs them out by reading the instruction that broke. The trick is economical: no address table, no separate structures — all the information about the error is already in the instruction.

The numbers you will meet most often:

Fixups

The compiler emits code in one pass, so when a procedure declared further down is called, its address is not yet known. The solution is classical: the offset field holds a reference to the previous such place, forming a chain. Once the address is known, FixLink walks the chain and substitutes the real value.

The loader does the same for calls into other modules: the object file holds chains that Modules patches up on loading. That is why in an .rsc a branch field is not yet an offset but a fixup record.

What is worth reading yourself

If you take on the source, a sensible order is:

1. ORS.Mod entire — it is small and sets the vocabulary.
2. In ORB.Mod — Import and Export: how a symbol file is built.
3. In ORG.Mod — Item, load, Index, Trap, Put0…Put3. That is the core.
4. In ORP.Mod — expression, StatSequence: you will see parsing and code generation proceeding in one motion.

The four modules you are reading are the very ones that build themselves. That is the next chapter.