Shen/JIT instructions and frames

The lowerer (src/lowerer/lower.shen), written in Shen, turns KLambda into the symbolic instructions below. They are plain Shen lists, so the same form serves as the stage 0 file (printed as text) and as the value eval-kl passes to the shen-jit.install primitive at runtime. C encodes them; the lowerer never deals with numeric opcodes, so no encoder needs to be generated for it.

C encodes each instruction as 32-bit words: the opcode, then its operands (ops.h). A code object keeps them packed (bytecode_pack): each word rotated left by one bit, so that the constant-operand flag (bit 31) becomes bit 0, then written as a variable-length integer, seven bits per byte. Nearly every word takes one byte. The JIT unpacks a function's words when it compiles it, which is the only time they are read.

Frames

A frame is a run of slots on the guest stack, numbered from 0 at the frame pointer:

Slot Contents
0 Return address (raw, 4-byte aligned).
1 The running procedure, which is also its closure environment.
2 .. arity+1 Parameters.
above Let-bound variables and temporaries, allocated by the lowerer.

A call window at offset A occupies slots A (return address), A+1 (callee) and A+2 .. A+1+N (arguments). The lowerer places every window above every slot that is live across the call, and evaluates arguments directly into the window. Evaluating argument i may itself use windows, which then start above A+2+i. A code object's frame size is the highest slot it uses plus one, including all of its windows, so a function writes only inside its own frame.

A named tail call uses window 0: its arguments go straight to slots 2 .. N+1, where the callee expects them, so nothing is copied. Argument i is computed into slot 2+i unless a later argument reads that slot. In that case it is computed into a temporary above every parameter slot, and moved into 2+i after the last argument. An argument that is already in its slot, such as an unchanged parameter, costs nothing.

Code objects

(code Name Arity FrameSize Constants Instructions Codes Inline)

A stage 0 file is a sequence of (defun Name Code) forms, one per line, in ASCII. Lists use parentheses; strings escape " and \ with a backslash and every byte outside 32–126 as \xHH; reals always contain . or e; and no symbol is printed in a form that reads as a number. A non-defun expression lowered for eval-kl is a code object of arity 0 named eval-kl.

Instructions

D, S and A are slot numbers; K, C and I are indices; L is a label number, local to its code object; F is a symbol; N is an argument count. O is an operand: a slot number, or (const K) for constant K, which the lowerer uses for every literal operand instead of copying it into a slot first. Native code takes a constant that is not a pointer (a fixnum, [], a Boolean) as an immediate, and reads any other from its constant cell.

Form Meaning
(move D S) Slot D := slot S.
(const D K) D := constant K.
(capture D I) D := capture I of the running closure (slot 1).
(closure D C S1 ... Sn) D := a new closure of code C capturing slots S1..Sn, in that order.
(prim D Op O1 ... On) D := primitive Op (a KLambda primitive name) applied to O1..On. N must equal Op's arity.
(label L) Marks L.
(jump L) Continue at L.
(jump-if-false O L) If O is false, continue at L; if true, fall through; otherwise raise "X is not a boolean".
(call D A F N) Open named call: the callee is F's function binding, the arguments are in A+2..A+1+N, the result goes to D.
(call-sealed D A F N) As call, but F is a stage 0 definition and the target is fixed when the code is installed.
(call-value D A N) Dynamic call: the callee is already in A+1. N is 0 or 1, or more after jump-unless-entry.
(tail-call A F N) Open named tail call; the arguments are in A+2..A+1+N and move to slots 2..N+1, or are already there when A is 0.
(tail-call-sealed A F N) Sealed named tail call.
(tail-call-value A N) Dynamic tail call; the callee is in A+1.
(return O) Return O.
(push-handler L) Install a handler: if anything raises before the matching pop-handler, continue at L. When L is not followed by exception, the handler is quiet: it never reads the exception, so none is built for it.
(pop-handler) Remove the innermost handler.
(exception D) D := the exception being handled; the first instruction at a handler label.
(entry N L) First, in a lambda that returns lambdas: a call with N arguments, more than the arity, continues at L with them in slots 2..N+1.
(jump-unless-entry S N L) Continue at L unless slot S holds a closure whose code has (entry N _).
(inline F N) The next N instructions are a body of F inlined here: no code, but backtraces name F for errors raised in them. Not in stage 0 code.

Primitive names are the 39 KLambda primitives, except eval-kl (see below), plus:

input+ is not a primitive; the port defines it.

Byte buffers and bit operations

A byte buffer is a T_BYTES object: a length and that many bytes, which the collector does not scan. It lives in the heap like a string, so:

A pointer with a length is memory outside the heap (Calling C), and all of these except bytes? and string->bytes take one in place of a buffer, with the same checks against its length. u8, u16, u32, s32, f64, bytes-length and the stores u8!, u16!, u32! and f64! compile inline for both; the others call C for both. f64 allocates where it reads, and its real holds the word as it is in memory, so it takes no floating point. f64! takes a real inline, and leaves an integer to C. A read-only pointer differs in its header, which a store tests whole, so no other access pays for it.

Code that loops, calls nothing and has no handlers, and reads or stores through a parameter it never changes, works out that memory's base and lengths once, on the way in, for any code, written by hand or not, however many loops it has, for four parameters at most. They hold until C runs, as only C can collect or kill a pointer, and they are worked out again each time it has. What is not memory gets length 0, so that its first access raises as it would have, and a read-only pointer gets 0 for stores. Memory reached at one width, and only at word indices, keeps limits in place of lengths, the first index without room for that width, so that an access is one comparison, and what is in registers is used where it is.

Form Result
(shen-jit.bytes N) A new buffer of N zero bytes.
(shen-jit.bytes? X), (shen-jit.bytes-length B) Whether X is a buffer; B's length.
(shen-jit.u8 B I), u16, u32 The unsigned value at byte offset I, little-endian, at any alignment.
(shen-jit.s32 B I), s64 The signed value there. An s64 that does not fit a fixnum raises.
(shen-jit.f32 B I), f64 The floating-point value there, as a new real.
(shen-jit.u8! B I X), u16!, u32! Stores X at I and returns B. X must fit: 0 to 255 for u8!.
(shen-jit.s32! B I X), s64! The same, signed.
(shen-jit.f32! B I X), f64! The same for a number, rounded to fit.
(shen-jit.string->bytes S) A new buffer with S's bytes.
(shen-jit.bytes->string B I N) A new string of the N bytes from I.
(shen-jit.copy-bytes To I From J N) Copies N bytes from J in From to I in To, which may overlap, and returns To.

= compares buffers by contents, as it does strings, and shen-jit.hash agrees.

Bit operations work on a fixnum's 62 bits in two's complement. A real raises, even one with no fraction.

Form Result
(shen-jit.bit-and X Y), bit-or, bit-xor, (shen-jit.bit-not X) As named.
(shen-jit.shift-left X K) X shifted left by K, from 0 to 63. What leaves the 62 bits is gone: unlike *, it does not raise.
(shen-jit.shift-right X K) X shifted right by K, from 0 to 63, keeping the sign.
(shen-jit.rotate32 X K) X, from 0 to 2^32 - 1, rotated left by K, from 0 to 63, modulo 32.
(shen-jit.bswap32 X) X, from 0 to 2^32 - 1, with its four bytes reversed.
(shen-jit.popcount X), clz, ctz The bits set, and the leading and trailing zeros, of the 62 bits; clz and ctz of 0 are 62.

The JIT inlines the accesses named above, and bit-and, bit-or, bit-xor, bit-not and the shifts. The others are calls to C.

Lowering rules

Guarantees of lowered code

The lowerer's output also satisfies the following, which src/lowerer/check.shen verifies and the JIT may rely on:

The JIT relies on the jumps, the slots and the handlers among these, and on two things more, also checked: handlers nest in the order of the code, since it tracks them that way, and a handler reads no slot written since its push, since it may not store a result that the code after it never reads. The lowerer's other habits, such as leaving parameters alone, are its own: code written by hand need not share them.

Slot assignment is scope-based, so windows sit above every variable in scope and every pending temporary. A chain of cons with constant heads takes one slot (see the lowering rules), and most frames are 16 slots or fewer. The lowerer also keeps a call's result slot below its window, which is not checked.

Native code written by hand

lib/native.shen lets a Shen program write these instructions itself. It stays out of the image: load it under (tc -), before the file that uses it, since a macro applies only to files read after it is defined.

(define-native sum-list (Xs Acc)
  (prim T cons? Xs)
  (jump-if-false T done)
  (prim H hd Xs)
  (prim Acc + Acc H)
  (prim Xs tl Xs)
  (tail-call sum-list Xs Acc)
  (label done)
  (return Acc))

An operand follows Shen's conventions: a variable is a slot, a symbol is itself, and anything else is a constant, so [1 2] is a list. (const E) is the value of the expression E when the definition is evaluated, which may be any value, or a variable of the function around it when define-native is used inside one.

Form Meaning
(move D O) D := O.
(prim D Op O1 ... On) D := primitive Op applied to O1..On.
(label L), (jump L), (jump-if-false O L) As above, with L a symbol. Jumps only go forward; again, below, goes back.
(call D F O1 ... On) D := F applied to O1..On, sealed if F is. If F is a variable, a call of its value, with no or one argument.
(tail-call F O1 ... On) The same in tail position.
(return O) Return O.
(closure D (P) (C1 ... Cn) I1 ... Im) D := a closure of the instructions I, taking P or nothing, and seeing C1..Cn under the same names.
(push-handler L), (pop-handler), (exception D) As above.

The builder numbers the slots: the parameters from 2, then the other variables as they first appear, with call windows above them all, and it works out the frame. These decide what a loop costs:

Structured control

These forms become the labels, loops and jumps above, with labels of their own, before anything else is done, so what they make is checked like any other code and runs the same:

Form Meaning
(if Test Then), (if Test Then Else) One statement or the other. (do S1 ... Sn) is several as one.
(when Test S1 ... Sn), (unless Test S1 ... Sn) The statements if Test holds, or if it does not.
(while Test S1 ... Sn) The statements for as long as Test holds, tested first.
(for I From To S1 ... Sn) Word register I from From up to and not including To, by 1, To read each time round.
(block Name S1 ... Sn) The statements, which (exit Name) leaves.
(exit), (next) Leave the innermost loop, or go round it again.
(exit Name), (next Name) The same for the loop or block named. A loop is named by a symbol after while or for.

A test is a comparison of two operands, (< A B), with >, <=, >=, =, !=, and unsigned u<, u>, u<= and u>= for words; (and T1 ... Tn), (or T1 ... Tn) and (not T); true and false; or a slot holding a boolean. A comparison is of reals if either side is a real register or something only reals give, as f64, sqrt, / or a number with a fraction, and of words otherwise. NaN makes a comparison of reals false.

(define-native count-byte (Data Start End Byte)
  (word Count 0)
  (for I Start End
    (when (= (u8 Data I) Byte)
      (word Count (+ Count 1))))
  (return-word Count))

A join that nothing reaches is left out: an if whose arms both return has nothing after it, and a loop whose body always leaves it does not go round, as the checker refuses code it cannot reach. Code after a form still has to be reachable, or the function has to return, as anywhere. (shen-jit.expand-native Statements) gives the instructions these become, for reading or for a program to build on.

Code a program generates is data, not forms:

  • (shen-jit.assemble Name Params Body) gives the code object of instructions in the same shape, as lists. There [const X] is a constant, and (protect X) writes a variable.
  • (shen-jit.install-code Form) checks and installs a code object, from assemble or written by hand with slot numbers and any instruction of the table above. (defun F Code) publishes F and returns it; a code object returns a closure of it, with no name, so generating many procedures uses up no symbols.
  • shen-jit.install, which eval-kl uses, checks only operand shapes and ranges, windows, labels and how the code ends. Wrong code given to it can crash.

The checker holds the rules the lowerer's output is checked against, in native.shen: see "Guarantees of lowered code". Hand-written code differs in that it may overwrite parameters, a sealed call needs only a sealed target, and constants may be any value. make test-native has code to run and code to refuse, and make fuzz-native mutates code objects and runs what the checker accepts: a crash means it accepted something the JIT cannot compile.

What is in a slot stays tagged, also with byte buffers and bit operations.

Real and word registers

Doubles can live unboxed in 48 real registers, and 64-bit integers, which wrap, in 16 word registers, each a namespace of its own. The JIT gives machine registers to what is used most, each loop counting 8 times what is around it, so the numbers and the order of the names make no difference: 27 float registers on arm64 and 12 on x86-64, and the integer registers a target has to spare, 11 on arm64, 2 on x86-64 and none on Windows, which the base and limits of kept memory compete for too. Code with loops that has more than fits also takes the saved registers its slots would have had, 6, 2 and 4, and its slots stay in the frame. The rest are places in the native frame. The collector does not look at any of them, and the JIT saves what C does not keep to the native frame around any call to C that returns: a collection, a primitive, an interrupt check. Nothing saves them across a call of a function, so code using them calls nothing and has no handlers, though it may tail call. That is what makes raw values safe here, where a raw frame slot could not be: the collector reads every slot as a value.

Form Meaning
(real X E) Register X := the value of E. X is then a register wherever it is named.
(f64! M I E) Store E at byte offset I of M, checked as shen-jit.f64! is.
(jump-unless (Op E1 E2) L) Jump to L unless E1 Op E2, with Op one of <, >, <=, >= and =. NaN compares false.
(real-box D E) Slot D := a new real holding E.
(return-real E) Return a new real holding E.
(word X W) Word register X := the value of W.
(u8! M I W), u16!, u32!, u64! Store the low bits of W at byte offset I of M.
(jump-unless-word (Op W1 W2) L) Jump to L unless W1 Op W2, with Op one of <, >, <=, >=, =, and unsigned u<, u>, u<=, u>=.
(word-box D W), (return-word W) Slot D := W as an integer, or return that. What does not fit a fixnum raises.
(loop L) The head of a loop named L. Code only falls into it, and comes back to it with again. Loops nest, and a function may have many.
(again L) Jump back to the head of loop L, which must come before this.

A real expression E is a real register; a word register, converted; a number, a slot or (const K), whose number is read with a check, an integer converted, and anything else raising; (+ E1 E2), (- E1 E2), (* E1 E2), (/ E1 E2); (neg E), (abs E), (sqrt E); (f64 M I), read and checked as shen-jit.f64 is; or any word expression below that only words can be, converted. (+ A B C) is (+ A (+ B C)), as Shen's macro makes it.

A word expression W is a word register; an integer, or (const K); a slot, which must hold an integer; (+ W1 W2), (- W1 W2), (* W1 W2), (neg W); (bit-and W1 W2), (bit-or W1 W2), (bit-xor W1 W2), (bit-not W); (shift-left W N), (shift-right W N), which fills with zeroes, (shift-right-signed W N), (rotate-left W N), (rotate-right W N), whose counts are taken modulo 64; (u8 M I), (u16 M I), (u32 M I), (s32 M I), (u64 M I); or (truncate E), toward zero, of a real expression, which is the machine's own beyond 64 bits. Arithmetic wraps and raises nothing. A literal has to fit a fixnum, so a wider constant is built, once, before the loop.

The index of u8 to u64 and their stores is a word expression. So is that of f64 and f64! when it is an integer or mentions a word register, with no tag to check and only the bound; any other is integer arithmetic through prim, as (+ I 8) on slots. A word index is checked as an unsigned number, so a negative one fails the bound. Intermediate values take registers too, and more than the registers there are is refused.

  • Division is IEEE's: dividing by zero gives an infinity or a NaN, where / raises.
  • A register or slot keeps its value round a loop, and what comes before a loop's head runs once. To leave a loop, jump forward. A loop is checked in one pass: going back must bring everything that was set at the head, and what the head's code reads has to be set before the loop, the first time round.
  • A loop checks for an interrupt each time it goes back, at the REPL, as a self tail call does.
  • Every access is checked, and those checks are what is left between these loops and C.

The builder turns these into instructions that shen-jit.install-code takes too, with registers numbered from 0: (real-number F O), (real-box D F), (real-move D F), (real-neg D F), (real-abs D F), (real-sqrt D F), (real+ D A B), (real- D A B), (real* D A B), (real/ D A B), (real-unless< A B L), with >, <=, >= and =, (real-load F M I), (real-store M I F), (real-load-at F M W), (real-store-at M W F), (real-from-word F W), (word-from-real W F), (word-number W O), (word-box D W), (word-move W V), (word+ D A B), with -, *, word-and, word-or, word-xor, word-shl, word-shr, word-sar, word-rotl and word-rotr, (word-unless< A B L), with >, <=, >=, =, -u<, -u>, -u<= and -u>=, (word-load8 D M W), with 16, 32, -s32 and 64, (word-store8 M W V), with 16, 32 and 64, (loop L) and (again L). An operand of a word instruction that it only reads may be (const K).