diff options
Diffstat (limited to 'docs/history/15-o3/code/README.md')
| -rw-r--r-- | docs/history/15-o3/code/README.md | 511 |
1 files changed, 0 insertions, 511 deletions
diff --git a/docs/history/15-o3/code/README.md b/docs/history/15-o3/code/README.md deleted file mode 100644 index e4859f2..0000000 --- a/docs/history/15-o3/code/README.md +++ /dev/null @@ -1,511 +0,0 @@ -# tinyvm zygote: notes and transcript - -a tiny stack cpu that started as a c89 code golf entry and ended up as a self-hosting runtime. a small native core runs vm code: jit-compiled to arm64, compiled through llvm on other hosts if you build with it, or interpreted. the genome it boots is a compiler for zc, a c-like language that keeps the forth habits. the compiler lives in vm memory next to your program, and your program can call into it, patch its tables, add syntax to it and compile new code while it runs. heap objects carry an ownership tag (u, m or d) that a static analyzer inside the compiler checks, with deterministic frees at scope ends and a mark-sweep collector underneath. types are a compiler primitive, with structs, generics, reflection and an optional typechecker. a program can also wire up to 512 custom opcodes into the cpu (virtual enhancements), which the jits inline as native code. and code marked `o3` skips the stack machine: the core compiles it as a whole region, with its variables in registers. - -this folder has the latest code. `history/` is the scrapbook: notes for every stage, plus frozen code from the stages that still have it. - -## files - -`core.c` is the native core and the only native code at runtime: the arm64 jit, the llvm backend (behind `-DZYLLVM`), the portable interpreter, the enhancement unit (recipe parser, vm-code lifter, optimizer and lowering) and the o3 region compiler. `src/rt.zc` is the runtime (i/o, the native division enhancements, the heap and the collector) and `src/compiler.zc` is the compiler, both written in zc. together they are the genome. `zc0.c` is stage 0 of the bootstrap, a compiler in c for the subset of zc that `compiler.zc` is written in. `tools/build.zc` makes the resident compiler compile its own source into a fresh image, and `mkgenome.c` turns that image into `genome.h`, which is generated and checked in. `examples/` has the small ones (hello, factorial, echo, self-patching code, an owning list, a repl, a typed program, an enhancement demo) and some bigger proofs of concept: - -- `mandel.zc`: the mandelbrot set in 16.16 fixed point, with the fixed-point multiply wired in as a custom opcode. -- `bf.zc`: a brainfuck compiler. it turns brainfuck into zc source, has the resident compiler compile it, and runs it (native code on the jit). it takes a program after a backtick, or runs hello world. -- `dump.zc`: prints any heap struct, nested ones included, with no printing code, by walking its type through reflection. -- `tree.zc`: a binary search tree whose nodes own their children. there's no `free` anywhere, and the live object count drops back to 0 when the root's block ends. -- `lang.zc`: grows the language while it compiles: a `|>` pipe operator (one table entry, since on a stack machine it's just `call`), `unless`, an `assert` that knows its source line, and `times n { }`. -- `staged.zc`: writes a polynomial as source with its coefficients baked in, compiles it while running, and finds it by name. -- `quine.zc`: prints its own source. -- `life.zc`: conway's life on a typed 2d board, with a glider wrapping around a torus. -- `primes.zc`: an o3 sieve over a fixed array, the primes gathered into a growable one, then twin primes and the widest gap. - -`tests/` has feature tests, `tests/errors/` (programs the lifetime analyzer has to reject), `tests/typeerrors/` (programs the typechecker has to reject) and `tests/langerrors/` (o3 and array misuse). each of those starts with the message it expects, and `tests/runerr.sh` runs a folder of them. `test.sh` does the whole bootstrap and runs everything on all three backends. `bench.sh` times o3 against plain code on each backend. `history/` is the scrapbook. - -## build - -``` -cc -O2 core.c io_linux.c -o zy # io_linux.c provides Q, G and J -./zy <examples/hello.zc -cc -O2 -DZYLLVM $(llvm-config --cflags) core.c io_linux.c -o zy $(llvm-config --ldflags --libs) -``` - -on arm64 the first line builds the jit, anywhere else the interpreter. the second line builds the llvm backend (non-arm64, or arm64 with `-DZYINTERP`). `-DZYINTERP` forces the plain interpreter. `J` is a `char` by default, so compile with `-DJTYPE=int` if yours is an int. the source ends at eof or at a backtick, and anything after the backtick stays unread for the program itself. environment: `ZYTRACE=1` logs translations, installs and the optimized enhancement code on stderr, and on the llvm build `ZYHOT=n` sets how many runs a block needs before it gets compiled (default 5000) and `ZYPASSES` the llvm pass pipeline (default `default<O2>`). `ZYNOLLVM=1` turns the llvm tier off. with `ZYTRACE=1`, `ZYO3DUMP=1` also prints every o3 block's micro-ops. - -regenerating the genome after changing `src/`: - -``` -cc zc0.c -o zc0 && cc mkgenome.c -o mkgenome -cat src/rt.zc src/compiler.zc | ./zc0 >genome.h # stage 0, from c -cc -O2 core.c io_linux.c -o zy -(cat tools/build.zc; printf '`'; cat src/rt.zc src/compiler.zc) | ./zy | ./mkgenome >g.h -mv g.h genome.h && cc -O2 core.c io_linux.c -o zy # now built by itself -``` - -run the last two lines once more and `genome.h` should come out byte for byte the same. `test.sh` checks that, on every backend. - -## zc, the language - -it reads like c. underneath every value is a 32 bit word and memory is word addressed, so `p + 1` is the next word whatever `p` points at, and strings are one char per word with a 0 at the end. types are optional: untyped code is typed `word`, which goes with anything. - -``` -const N = 10; -[N]int table; // a global array -int fib(int n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); } -fn main() { - for (int i = 0; i < N; i++) table[i] = fib(i); - let sq = { let t = table[5]; t * t }; // a block is an expression too, its last line is its value - let x = asm { 2 3 + }; // raw vm code, leaves one value - putn(sq + x); putc(10); - return 0; -} -``` - -declarations are c-style, type first: `int a = 1, b;`, `*node p = new(node);`, `[4]char buf;`, `point origin;`. `let` declares without a type: it infers pointer, struct and function types from the initializer and keeps numbers as plain words, and `let a[10];` is an untyped array. statements are declarations, `if`/`else`, `while`, `for`, `switch`, `break`, `continue`, `return`, `{ }` blocks, `asm { }` and expressions. `switch (e) { case 1, 2: ... default: ... }` takes constant labels, and its cases don't fall through: each ends where the next begins, and `break` leaves early. operators are c's with c's precedence, including `c ? a : b`, plus `p.x` and `p->x` (the same thing: `.` goes through a pointer on its own), `e as T` to change a type without changing the bits, and the casts below. comparisons and `&& ||` give 0 or 1. `/`, `%` and `<<` compile to native enhancement opcodes. character literals, `0x` hex and the usual escapes are there. - -functions are declared like c, return type first: `int f(int x)`, `*node.u make()`, `.u grab()` (a tag on its own), `void log(*char s)`. `fn f(a, b)` is the untyped form, returning a word. a generic function puts its type parameters in front, `<T> T first(*list<T> l)`. function types are written the same way, `int(int, *char)`, and `fn(int)` for one that returns a word. the earlier `fn f(...) -> T` spelling is gone. - -arrays come in three kinds. `[n]T` has its size in the type and lives in place. `[]T` is a growable array: a small handle object that owns its items, made with `new([]T)` or `new([]T, n)`, indexed with a bounds check, and changed with `push(a, x)`, `pop(a)` and `resize(a, n)`. `len(a)` works on both (for `[n]T` it's the constant) and `cap(a)` gives the room before the next grow. `fixed []T` is a `[]T` that can't change size: `new(fixed []T, n)` needs the length, and `push`, `pop` and `resize` on it are compile errors. a `fixed []T` can't be passed where a `[]T` is expected, the other way round is fine, and a constant index outside a `[n]T` is caught at compile time. the items belong to the array, so freeing it frees them, and objects stored into a `[]*T` are its children like any container's. - -a unit is read whole and scanned for function signatures before it compiles, so calls can come before definitions, tags included, and prototypes are optional. `main` runs after the whole program has compiled. every function returns one word, 0 if it falls off the end. - -builtins from the runtime: `putc`, `getc`, `eof`, `puts`, `putn`, `halt`, `strlen`, `streq`, `wcopy`, `wfill`, `new`, `new_t`, `new_raw`, `free`, `gc`, `isobj`, `osize`, `typeof_obj`, `live_objects`, `install`, `zdiv`, `zmod`, `zshl`. - -## memory model: u, m and d - -`new(n)` or `new(T)` gives back a fresh object. bind it to a local and the local owns it, tagged **m**. tags live on local variables and parameters, the analyzer follows them through the code, and the compiler inserts `free` calls where owned objects die. a tag is written after the type, `*node.u p`, or alone, `.d x`. `u`, `m` and `d` are reserved words. - -**m** means the object belongs to this block and has to be used in it. you can lend it to callees as often as you like, and when the block ends it's freed. an m object that's never used anywhere in its block is an error. - -**d** means the object is going down. the first time it's handed to a lower scope its life here is over: passing it to a `.d` parameter, or touching it inside an inner block, which then owns it as m and frees it when that block ends. using it afterwards is an error, and so is ending the block with a d object that never left. - -**u** means the object is going up. it has to leave this block for the one above, where it arrives as m. it leaves through `return` (the function's return type has to carry `.u`, like `*node.u make()` or just `.u make()`), as the value of a block expression, or by assignment to a variable of the directly enclosing block. letting it fall out of scope, or throwing away a u result, is an error. - -recasting is multiplication by the tag: `u*x`, `d*x`, `m*x`. it only goes away from m: m can become u or d (and u and d can swap), but nothing goes back to m in the same scope. a declaration can carry a tag too, `.u r;`, and then whatever lands in it gets that tag. - -parameters: an untagged parameter is m from the caller's side, a lend, and the callee sees a plain word. `.m` makes it a checked borrow: the callee can read and write it but can't free it, return it, recast it or store it anywhere. `.d` hands the object over, and it arrives as m. - -``` -*int.u box(int v) { *int b = new(int); *b = v; return u*b; } -fn add(*list l, *int.d item) { l.items[l.len] = d*item; l.len++; return 0; } -``` - -containers own what you store in them. `p[i] = c` or `p.f = c` needs `c` to carry the same tag as `p` (or be a fresh object), and from then on `c` follows `p`: if `p` is recast, so is `c`, if `p` is given away `c` goes with it, and when `p` is freed its children are freed too. a child can't be recast or given away on its own. storing into an object you only borrowed gives the child away: it's dead here afterwards, and the caller's object owns it. the runtime records the owner in the child's header, so freeing a container frees exactly the objects it owns. - -globals, plain pointers and arrays aren't tracked. storing an owned object there needs `d*`, and the mark-sweep collector takes it over. a fresh object can go straight in. - -where paths join (after an `if`, a loop, a `switch` or `?:`) every variable has to be in the same state on every path that reaches the join, with one exception. a variable that became d, or was given away, on some path is dead afterwards, and the compiler frees it on the paths where it's still alive, on their way in. a loop's exit state is the join of its `break`s and its normal exit, so giving something away and breaking is fine. what a loop can't do is give something away on a path that comes back around to the top, since the next pass would use it dead. a u object doesn't get the dead treatment: it still has to leave. - -### the analyzer - -it runs inside the compiler on every function, including code compiled at runtime by `eval` and friends, and reports each violation with a line number and the variable's name. the compiler keeps going after errors, up to 20: a syntax error skips to the next `;` or `}` (or the next top-level declaration), and analyzer and type errors just get reported, since the parse is still in step. a unit with errors doesn't run. `tests/errors/` has one small program per rule. to turn it off: `unchecked fn f() { }` for one function, `unchecked { }` for a block, and a top-level `unchecked;` for the rest of the unit (a parse word can also set `check_on = 0`). unchecked code doesn't track anything, so what it allocates belongs to the collector, and checked variables can't be touched from inside an unchecked block. - -## types - -types are a compiler primitive. the compiler keeps them as records in a type area at 0x9C000, hash-consed so the same type is always the same pointer. they stay in memory after compiling, so programs and parse words can look at them. - -``` -struct point { int x, y; }; -struct list<T> { int len; *T items; }; -type num = int; -<T> T first(*list<T> l) { return l.items[0]; } -<T> *list<T>.u mk(int cap) { *list<T> l = new(list<T>); l.items = new(T, cap); return u*l; } -... -*list<*point> ps = mk<*point>(8); // explicit type arguments, or inferred from the arguments -``` - -the kinds are `word`, `int`, `char`, `bool`, `void`, pointers `*T`, arrays `[n]T`, `[]T` and `fixed []T`, function types `int(int, *char)`, structs, generic structs and generic functions. structs and arrays live in place (in a frame, a global or inside another struct), and their value is their address, so they're passed around by pointer. `sizeof` counts words. type arguments have to be one word (a number, a pointer or another parameter), so a generic function is compiled once and works for every instance. indexing scales by the element's size, while plain pointer arithmetic stays in words, like b. `new(T)` and `new(T, n)` stamp the type into the object's header. - -### reflection - -`typeof(e)` and `typeof(T)` give a type record and `sizeof(...)` its size. both work on any expression, which is compiled dry and never runs. at runtime: `tkind(t)` (one of the `TY_` constants), `tsize`, `tname`, `tlen`, `tnfields`, `tfname(t, i)`, `tftype`, `tfoff`, `tret`, `tnparams`, `tparam`, `tparamtag` (the u/m/d tag of a parameter), `tretu`, `tnargs` and `targ` for generic instances, and `tprint(t)`. `sigof(f)` gives the type of a function by address (untyped ones get a signature built from their arity and tags), `sigofs("name")` by name, and `typeof_obj(p)` reads the type stamped on a heap object. - -### the typechecker - -off by default. `typecheck on;` turns it on for what follows and `typecheck off;` turns it back off (a parse word can flip `tc_on`). it checks initializers, assignments, arguments (unifying generic parameters), return values, arithmetic, comparisons, dereferencing, indexing and calls. `word` matches anything, numbers mix with each other, a literal 0 is a null pointer, and arrays decay to pointers. it stops at the first error, printing what it expected and what it got. `tests/typeerrors/` has one per rule. some things are checked whatever the setting, because the compiler needs them to generate code: field names, and field access on something that isn't a struct. - -## virtual enhancements - -the cpu has room for 512 custom opcodes (22 to 533), and opcode 21 (`%` in asm) installs one at runtime. it's the closest a soft cpu gets to rewiring itself. an enhancement takes up to 8 inputs off the data stack and leaves up to 8 outputs, and it's written one of two ways: - -``` -enhance clamp(x, lo, hi) micro "x = max x lo; x = min x hi"; -enhance 2 divmod(a, b) micro "r2 = sdiv a b; r1 = srem a b; r0 = r2"; // the number is how many outputs -enhance cube(x) vm { 0 $ 0 $ * * }; -enhance noisy(x) vm { 0 $ . } else soft_noisy; // can't be lifted (it does i/o), so calls use the fallback -``` - -a micro recipe works on registers `r0`..`r15`, which the inputs arrive in (also under the parameter names), and the outputs leave from `r0` up. the micro-ops are `li mov add sub mul sdiv udiv srem urem and or xor shl shr sar neg not lt ltu eq ne min max minu maxu mulhs mulhu clz abs sel ld st`. a `vm` body is straight-line vm code that gets lifted by running it symbolically. both turn into ssa, and the core's optimizer folds constants, simplifies algebra, removes common subexpressions and dead code, and turns division by a constant into a multiply-high sequence (`ZYTRACE=1` prints the result). the arm64 jit then inlines the code at every use with registers allocated, the llvm backend inlines it as ir, and the interpreter runs the optimized list. if something doesn't fit in registers, the jit calls the interpreter for that op. when literals feed an enhancement's last inputs (`x / 7` is `x 7 idiv`), the arm64 jit specializes that use on them: the literals become constants, the optimizer runs again, and `x / 7` turns into a multiply-high and two shifts instead of a divide. - -an enhancement is called like a function when it has one output, or by name from asm. `enhance` installs at compile time, so the wiring is there before `main` runs, and a parse word can use it right away. an image installs its own enhancements when it boots, from its symbol table. that's how `/`, `%` and `<<` work: `rt.zc` declares `idiv`, `imod` and `ishl` as one-instruction recipes. `install(desc)` is the raw interface, and its descriptor format is documented in `core.c`. stores done by an enhancement don't invalidate compiled code, so use them for data. - -this replaces my first plan for enhancements, which compiled c or llvm ir sources at runtime. part of that reply got stopped by a safety check, and once it turned out llvm was meant for portability, it moved into the backend below instead. - -## o3 - -`o3` marks code for the optimizing tier. it goes on a function, a block or a single variable: - -``` -o3 int sum(fixed []int a) { int s = 0; for (int i = 0; i < len(a); i++) s += a[i]; return s; } -fn main() { - o3 int hits = 0; // one o3 variable - o3 { for (int i = 0; i < 1000; i++) if (i % 7 == 3) hits++; } - ... -} -``` - -what it gives up, as asked: variables declared in o3 code must be typed (`let` and untyped parameters are errors), they have no address (`&x` and naming one from `asm` are errors), `new` in o3 code returns raw memory with no type stamp and no zero fill (`new_raw`), and an o3 function skips the frame stack check in its prologue. what it gets: the compiler hands each o3 function body and each o3 block to the core as a region (install kind 2: the range of vm words plus the frame slots of up to 7 typed variables, picked in declaration order), and the core compiles the region right away. - -inside the core, a region is cut into basic blocks at jump targets, branch fallthroughs and call return points. each block is lifted to ssa the way enhancements are: the vm stack becomes values, and only what's still on it at the end of the block is written to memory. the frame pointer and the promoted slots become variables that live in registers across the whole region, so `i++` on an o3 int is one add. enhancements are spliced into the block, so `/`, `%` and `<<` become one instruction or a magic-number sequence. every block then goes through the same optimizer (folding, algebra, cse, dce, division by constants). in o3 code `a[i]` on a `[]T` is compiled inline with its bounds check (`outside(i, len)`, one enhancement), and `len(a)` is a load. - -the backends: on arm64 the region becomes one piece of native code. variables sit in w0..w7, block values in w8..w14 and w26..w28, constants are folded into instructions where they fit, loads from a fixed address are one `ldr`, and blocks branch to each other directly with no dispatch and no stack checks. on the llvm build the region becomes one function, with the variables in allocas that mem2reg turns into ssa across blocks, and it goes through llvm's O3 pipeline. on the plain interpreter, a small region interpreter runs the optimized blocks with the variables in locals. - -calls, returns, jumps out of the region, i/o, `install`, a store to the frame pointer and anything else a block can't lift all leave the region: the variables are written back to the frame first, so outside code sees ordinary memory. a call's return point is an entry, which loads them again. stores inside a region still check the coverage map, so writing to compiled code works, and a store into the region's own code drops it (it lifts again at its next entry). to keep variable addresses from waiting on the stack across a branch, assignment to an o3 variable in o3 code evaluates the value first and the address after. the lifter refuses a block that would leave such an address on the stack, rather than miscompile it. single o3 variables outside o3 code are reached through `lfa(k)`, an enhancement for `fp + k`, which the arm64 jit specializes into a load and an add. - -`bench.sh` runs four kernels from `tests/bench.zc` with and without `o3`. milliseconds per run, start-up and compile time removed (arm64 is under qemu on an x86 host, so only its ratios mean much): - -``` -backend kernel plain ms o3 ms speedup -interp collatz 309.63 209.87 1.5x -interp sieve 45.58 15.95 2.8x -interp digits 191.32 92.29 2.1x -interp fib 6.70 5.50 1.2x -llvm collatz 27.69 3.48 7.9x -llvm sieve 17.32 0.17 101.9x -llvm digits 24.72 1.60 15.4x -llvm fib 1.82 0.84 2.2x -arm64 (qemu) collatz 327.33 16.78 19.5x -arm64 (qemu) sieve 90.23 3.85 23.4x -arm64 (qemu) digits 147.67 3.46 42.7x -arm64 (qemu) fib 22.62 5.73 3.9x -``` - -fib is the weak one, since every call leaves the region and comes back through the dispatcher. llvm's sieve number is llvm's loop optimizations doing their work on a region with no stack traffic left in it. - -## the llvm backend - -a tiered jit for hosts the arm64 backend doesn't cover. the interpreter counts how often each block start gets reached, and a hot block is translated to llvm ir using the same block rules as the arm64 jit: it ends at call, jump, ret or halt, keeps going past a jz, and literal targets are fused. the ir goes through the O2 pipeline and gets compiled by orc's lljit. stores into compiled words drop the blocks covering them, like on arm64. it pays off for long-running code: a loop-and-recursion benchmark runs about 3.3x faster than the interpreter. short bursty work like the self-compile is slower, since compile time dominates there. `ZYHOT=1` compiles every block, which is a good stress test, and the test suite runs that way too. - -## the heap - -0x40000 to 0x9BFFF, managed by a buddy allocator. the heap is split into aligned power-of-two chunks, every block is a power of two words, and a freed block merges with its buddy whenever that one is free too, so freed space can be reused at any size. (stage 15 fixed a bug here: `release` marked a container free before freeing its children, so a child whose buddy was the container merged into it while the container was still being freed, and corrupted a free list. growable arrays hit it every time, since a handle and its items are often buddies.) allocation finds the smallest free block that fits and splits it down. free blocks sit on a doubly linked list per class, so taking a buddy off its list during a merge is constant time. checked code frees deterministically. under that runs a mark-sweep collector, conservative and non-moving, which handles globals, unchecked code and anything given to it. it runs on `gc()`, which returns how many objects it freed, or when an allocation doesn't fit. the sweep frees through the same merging path. - -## code as data - -the compiler is in memory with your program and every name in it is callable. - -`asm { }` emits raw vm words: numbers push, `-5` pushes a negative, `#n` emits a raw word, one-char tokens from the mnemonic table are opcodes, `:name` defines a label local to the block, enhancement names emit their opcode, and other names push the address of a variable or function. - -`quote { ... }` is a token list as a fresh object: `[n, kind, value, line, kind, value, line, ...]`, so errors inside a macro expansion point at the line the tokens came from, where names, strings and operators are interned pointers (`intern("while")` gets one). `tokens(s)` makes one from a string, and `qdup(q)` copies one. - -`eval(q)` compiles a token list as a function body and runs it. `compile(q)` returns its address instead, `load(q)` compiles top-level declarations, and `evals(s)` runs `eval` on a string. - -parse words: `immediate fn name() { }` runs at compile time whenever `name` shows up as a statement, inside an expression or at the top level. it starts with the current token on its own name and works the compiler directly: `next()`, `peek()` and `peekat(k)` (up to 4 tokens ahead), `tk`/`tv` (current token kind and value), `expect`, `accept`, `expr()`, `stmt()`, `substmt()`, `ptype()`, `emit`, `lit`, `op`, `hole`/`setlit` for jumps, and `here`. `grab()` reads a `{ }` group into a token list, and `feed(q)` pushes a list back into the input, which is all a macro needs. parse words can call `eval` partway through a compile: the compiler saves its state and emits the new function in place with a jump around it. the built-in keywords are entries in the same table, so a parse word called `while` replaces `while`. - -tables: `add_binop("**", 11, "ipow c")` adds or replaces a binary operator with a precedence and its code, written like asm (names resolve when it's used). `add_unop` does the same for prefix operators, and the lexer learns new spellings from both. `mnem` is the asm mnemonic table, `q@!$_~cjzr,?.+-*&|^><%`, and can be rewritten. - -## the bootstrap - -`zc0.c` compiles the subset `compiler.zc` uses (no analyzer, types, quote, parse words or block expressions, but it does lay out `enhance` declarations) into a first genome. that genome compiles `compiler.zc` again on the vm. that's where the real compiler, the analyzer and native division first meet their own source, and `compiler.zc` passes its own lifetime checks. the result compiles itself into identical words, on all three backends, and that's the `genome.h` that ships (78217 words). an image build (`build_image(org, dst)`) compiles with only the image's own names visible (plus keywords and builtin types), writes code meant for one address into another, and appends a symbol table so the booted genome knows its own names and enhancements. - -## the instruction set - -every word is 32 bits. an odd word is a literal that pushes `w>>1` (31 bits, sign extended). an even word is an opcode, `w/2`. there's a data stack and a return stack, both stored inside memory. - -``` -0 q halt 5 ~ swap 10 , in (Q) 15 * mul 20 < less -1 @ load 6 c call 11 ? empty (J) 16 & and 21 % install -2 ! store 7 j jump 12 . out (G) 17 | or 22..533 enhancements -3 $ pick 8 z jz 13 + add 18 ^ xor -4 _ drop 9 r ret 14 - sub 19 > shr -``` - -stack effects: `!` is `(v addr --)`, `$` is `(n -- copy of the nth item)` so `0 $` is dup, `z` is `(cond addr --)` and jumps when cond is 0, `c` and `j` take their target from the stack, and `%` is `(descriptor -- status)`. there's still no div or mod in the base set, because a divider can't finish in one cycle in hardware. an enhancement can add one. - -## memory map and abi - -memory is 1m (1048576) words. it could grow until the host runs out (literals already reach 1g words), but that would mean reserving the jit tables with mmap instead of static arrays, and 1m is plenty for now. - -``` -0x00000.. the program: code, with globals between functions -0x40000..0x9BFFF heap -0x9C000..0x9FFFF type records -0xA0000 frame pointer word -0xA0100..0xBFFFF compiler data: interned names, symbol table, locals, tables -0xC0000.. genome: 0xC0000 entry, 0xC0005 symbol table address, 0xC0006 image end -0xE0000..0xEFFFF frame stack, grows down from 0xF0000 -0xF0000.. return stack, grows up -0xF8000.. mark stack -0xFC000..0xFFFF0 data stack, grows down -``` - -calls push the arguments left to right and the callee's prologue pops them into its frame. locals live in the frame at `*0xA0000 + slot`. every function leaves exactly one word on the data stack. heap objects have a 6 word header: size, size class, flags, a check word, owner, type. - -## how the core works - -registers: x19 holds the memory base, x20 the data stack pointer, x21 the return stack pointer, x22 the translation table and x23 the state block (memory, s, r, table, coverage map, Q, G, &J, store hook, install hook, enhancement fallback). o3 regions also use x26..x28, which the entry stub saves. - -compilation is lazy. the first time control reaches an address, that block is translated from live memory. a block ends at call, jump, ret or halt. a `z` doesn't end it: the not-taken side keeps compiling, which makes superblocks. a literal followed by `c`, `j` or `z` is fused into a constant target. every exit goes through a dispatch stub that checks both stack pointers against their limits (kept in x24 and x25), bounds-checks the target, loads `tab[t]`, and branches straight to it when it's already compiled. otherwise it returns to c, which compiles the block and re-enters. enhancements are inlined: inputs load from the data stack into w0..w15, the optimized micro-ops run in registers with x16 and x17 as scratch, and the outputs go back. an install calls into c and then returns to the loop, which flushes every translation, since code built before the install may have inlined the old version. a flush drops o3 regions too, and they lift again on their next entry. when the loop reaches an o3 entry point, it compiles the region (or reuses it) instead of translating a block. - -self-modification is handled with a byte map of which words some live translation covers. a store checks that byte inline: an uncovered target, the usual case, gets a plain store. a covered target calls the hook, which drops every translation containing that word and makes the jit code return to c at the next instruction, so even patches to the very next word take effect. writing back the same value is a no-op. if the 16 mb code buffer fills, everything is flushed. - -the stacks are checked. the data and return stacks are checked at every block exit on all three backends, so the cost is a couple of compares per block rather than per push. a block pushes at most about 1024 words, which the data stack limit leaves room for. overflowing either one stops the cpu with `zy: data stack overflow` or `zy: return stack overflow`. the frame stack is checked in every function prologue, which resets the frame pointer and stops with `zy: frame stack overflow`. - -platform: the darwin path uses `MAP_JIT`, `pthread_jit_write_protect_np` and `sys_icache_invalidate`. linux uses rwx mmap and `__builtin___clear_cache`. only linux arm64 has actually been run, under qemu. the darwin path follows apple's documented recipe but hasn't been tested, and under the hardened runtime it also needs the allow-jit entitlement. every host shares the same semantics: shift counts wrap at 32, stores outside memory are ignored, loads outside memory read 0, and jumping outside memory or to an unwired opcode halts. - -## test results - -`test.sh` passes all 125 checks on x86-64 linux: the fixpoint, an up-to-date `genome.h`, and then every example and feature test on the interpreter, on the arm64 jit under qemu, and on the llvm backend, all with identical output. it also covers joins and fixup frees (with a leak count), `switch` and `?:`, the buddy allocator, several errors in one run, all three stack overflows, growable and fixed arrays, and `tests/o3.zc` (loops, recursion, calls inside loops, `switch`, `&& ||`, structs through pointers, arrays, division by constants, and a function with more variables than registers), whose output matches the same file with `o3` taken out. it checks that every o3 region in that test lifts, and gets compiled on the jit and on llvm, that the o3 bounds check fires, and that all 22 programs in `tests/errors/`, all 10 in `tests/typeerrors/` and all 8 in `tests/langerrors/` get rejected with the expected message on each backend, that llvm agrees when it compiles every block, and that the self-compile matches byte for byte on all three. separately, 80000 random divisions through enhancements matched the software routine, covering divide by zero, INT_MIN/-1, negatives and the magic-number path for constants. - -## open ends - -fixed in stage 13 (details in `history/13-gap-fixes`): branch and loop joins, free lists that never merged (now a buddy allocator), missing stack checks, stopping at the first error, macro line numbers, required prototypes, `d*` for storing into borrowed objects, `**` declarations, and `?:` and `switch`. still open: - -**untracked aliases.** the analyzer only follows bare variable names, so `let q = p + 0;` or `let c = list[1];` is a plain word nobody tracks, and it dangles once the owner is freed. two cheap fixes, and they combine well. at runtime: don't reuse a freed block right away. `free` would put it on a quarantine list, and the collector's next sweep only releases quarantined blocks that no word points at. the conservative mark already finds such words, so that's maybe 30 lines in rt.zc. a stale alias then reads a dead but intact block, and a second free through it is a no-op, because the header's flags say free. at compile time: now that there are types, a pointer-typed value computed from a tracked variable (`p + k`, `p.field`, `p[i]` when the element is a pointer) can carry a "borrowed from p" mark into the local it's stored in. using that local after `p` dies becomes an error. that's the same machinery children already use. - -**the conservative collector.** it scans the whole data stack region, because the vm can't read its own stack pointer, and stale words keep garbage alive a little longer. the fix is one base opcode that pushes the data stack depth, which is trivial in hardware since the register already exists. then the collector scans only the live part. zeroing a frame in the prologue would do the same for the frame stack, at a few words per call. - -**coarse invalidation.** a store to a covered word rescans every block, and an install flushes everything. three fixes, in order of payoff. first, index blocks by page (say 64 words): a covered store only looks at the blocks touching its page, and dropping a block only rebuilds the coverage bytes for that block. second, record which enhancement slots each translation inlines, so an install only drops those. third, on llvm, give each block its own resource tracker, so dropped code actually gets freed. - -**automatic tiering.** o3 is the explicit version of what you asked about in message 14. doing it without the keyword means a run counter per block (about 4 instructions per block entry) and, for a hot loop, finding its region and its variables without the compiler's help. the hard part is the variables: o3 can keep them in registers because the compiler promises nothing takes their address, and code without that promise would need the lifter to prove it. - -**o3's own gaps.** calls always leave the region through the dispatcher, so call-heavy code gains least (fib above). a direct call from one compiled region into another, with the variables spilled only for the slots the callee can't see, would fix most of that. only 7 variables get registers, picked by declaration order rather than by use. a fixed array's length and items pointer can't change, so o3 code could load them once per region instead of at every index, and doesn't yet. the core's own optimizer works one block at a time (no loop-invariant motion or cross-block cse); llvm does that on its build. regions aren't built into images, so `rt.zc` and the compiler can't use o3. and o3 code that rewrites its own region sees the change at the next entry, not right away. - -**generics are erased.** a generic function is compiled once, so the type stamped by `new(T)` inside it says `T`, and type arguments have to be one word. - -**the rest.** the prescan only knows tags, not types, so a call to a typed function that's defined further down gets `word` as its result type until the definition shows up. the llvm backend compiles one module per block, so it warms up slowly. stores done by enhancements don't invalidate compiled code. a parse word that changes the syntax can confuse the prescan. it only records signatures, though, and a real definition always overrides what the prescan guessed. - ---- - -## transcript - -each of my messages is quoted exactly, followed by a summary of the reply. - -### 1 - -> codegolf a tiny cpu vm in C89. the goal is to achieve the lowest character count possible. include an assembler as well (scored separately) and a hello world program (not scored, but elegance and simplicity is a bonus) -> it must be capable of re-entrant code and a realistically workable instruction set. - -**summary:** a two-stack forth-style machine. the vm was 384 bytes: one ternary chain inside `while(o=m[p++])`, the top two stack items cached in `a` and `b`, the program loaded with `read(open(...))` so it needs no headers, and both stacks inside the 65536-word memory. it had 22 opcodes including div and mod, a two-word literal, and jump/call targets popped from the stack. the assembler was 348 bytes and two-pass, using `strcspn` instead of `strchr` so the implicit int return stays safe on 64-bit. hello world was a pointer loop over a string with a zero terminator. re-entrancy was shown with a recursive factorial plus a recursive decimal printer. - -### 2 - -> your cpu should also be realistically close to hardware (translating it to logical circuitry hardware should be fairly easy) and sport an acceptably fast execution (if hypothetically ported to hardware, not in software) -> -> assume i/o is handled by two external functions, `char Q()` (getchar) and `void G(char)` (putchar) and a state variable J (boolean, shows if input is empty). -> -> don't be afraid to use macros. - -**summary:** no reply was sent to this message at the time. it was answered together with message 3. - -### 3 - -> pro tip: if you define a macro as `!o--`, you can save 2 characters per if condition -> oh and btw, newlines are free - -**summary:** used the tip as `#define X !--o?`, with pre-decrement because opcode 0 (halt) is already handled by the loop, and with the `?` folded into the macro and free newlines used as separators. the hardware-oriented redesign: bit 0 of each word is a literal flag, so literals take one cycle like the j1 cpu. div and mod were dropped because they can't finish in one cycle and were replaced by an arithmetic shift right, giving 8 alu ops that decode from 3 bits. every instruction does a fixed amount of work with at most one data memory access, and call and jump share a datapath (`r-=o`). i/o now goes through `Q`, `G` and a `?` op that reads `J`. the result was the vm at 339 bytes and the assembler at 346. the final golfed code: - -```c -#define X !--o? -int m[1<<16],p,s=65e3,r=6e4,o,a,b;main(c,v)char**v;{read(open(v[1],0),m,s);while(o=m[p++])a=m[s],b=m[s+1],o&1?m[--s]=o>>1:(o/=2,X -m[s]=m[a]:X -m[a]=b,s+=2:X -m[s]=m[s-~a]:X -s++:X -m[s]=b,m[s+1]=a:(o-=2)<1?m[r]=p,r-=o,p=a,s++:X -p=b?p:a,s+=2:X -p=m[--r]:X -m[--s]=Q():X -m[--s]=J:X -G(a),s++:(m[++s]=X -b+a:X -b-a:X -b*a:X -b&a:X -b|a:X -b^a:X -b>>a:b<a));} -``` - -```c -char t[9999][99],*o="q@!$_~cjzr,?.+-*&|^><",*q;A[9999],k,i,j,n,P;E(y){n++;write(P,&y,4);}V(char*s){for(j=k;j--&&(*t[j]-58||strcmp(t[j]+1,s)););return~j?A[j]:atoi(s);}main(){while(~scanf("%s",t[k]))k++;for(;P<2;P++)for(n=i=0;i<k;i++)if(*(q=t[i])==34)while(*++q)E(*q);else*q==58?A[i]=n:!q[1]&&o[j=strcspn(o,q)]?E(j*2):*q==35?E(V(q+1)):E(V(q)*2+1);} -``` - -### 4 - -> now let's move in stages. write a compiler that takes this assembler's code and converts it into darwin arm - -**summary:** an ungolfed c89 compiler from vm assembly to darwin arm64 assembly. every word got its own label, the image was emitted as an addressable data array, x19/x20/x21 held the memory base and the two stack pointers, and computed jumps went through a table of offsets. a literal followed by a jump became a direct branch. `Q` and `G` went through `sxtb`, since char is signed on apple arm64, and `J` was read with `ldrb`. it was verified by assembling with llvm-mc for darwin, then rewriting to linux with sed and running under qemu, where it matched the vm byte for byte. this version couldn't handle self-modifying code. - -### 5 - -> can you write the assembler in assembly and pair the code with the assembly and the assembler so that it can re-wire itself at runtime? or maybe include an interp for self-modification, otherwise fns are exec'd native - -**summary:** both. `aslib.s` is the assembler written in vm assembly as a library (`a.src`, `a.dst`, `a.org`, `a.lab`, then `a.run c`), and with `asmain.s` it's a 568-word standalone assembler. it's byte-identical to the c assembler and reaches a fixpoint when assembling itself. this is also where the `:;comment` trick came from. the compiler became a hybrid. the image is split into basic blocks, each block counts how many of its words differ from the original image, and stores into code go through a slow path that updates the counters. clean blocks run native, while dirty blocks and anything past the image run in an interpreter compiled into the same binary, which hands control back to native code whenever it lands in a clean block. `cc -t` printed `[` and `]` at each switch. the demo rewired a function at runtime to point at freshly assembled code and then restored it. - -### 6 - -> which one do you like more? and which is more performant? -> keep that one, then port to using llvm ir so that it can be platform independent - -**summary:** no reply was sent at the time. the llvm port was dropped when message 7 changed direction. the question was answered at the start of the reply to message 7: the hybrid was the favorite because it kept the vm's semantics exact. the plain compiler was slightly faster on code that never rewrites itself, but it silently ran stale code once anything did. the zygote beats both. - -### 7 - -> can you make it a zygote approach? -> a minimal core loads first, reads and compiles the program (either wholly or partially, for speed) and replaces it with itself. so it's like a jvm but self-contained and on the same level as itself, where the assembler can itself be modified in-memory to assemble different code. for this we need to ditch llvm - -**summary:** the current design, described above. the native core only does jit and glue. it loads the genome (boot loader + assembler, both vm code) at 48000. the boot loader reads source until eof or a backtick, assembles it at 0 and jumps there. compilation is lazy per block, straight from live memory, with superblocks through `z`, fused constant targets, and dispatch chained through a table. invalidation uses the coverage byte map plus a store hook, so self-modified code gets retranslated instead of interpreted. the resident assembler sits at fixed addresses, and `repl.s` rewrites its mnemonic table so `p` means out, then assembles and runs input chunks in a loop, overwriting the same address each time. verified under qemu on linux arm64, including the self-hosted assembler running on the zygote. about 4x faster than the golfed interpreter. - -### 8 - -> damn dawg you made an entire baremetal os? -> -> let's move to cowork. pack everything up alongside a transcript of every message i've sent and your own notes on what you've implemented in an md file, with the code, so i can move it. - -**summary:** not quite an os. it's a userland runtime. it still runs on darwin or linux, uses their mmap for executable memory, and gets i/o from the host through `Q`, `G` and `J`. there's no scheduler, no drivers and no hardware access, so a closer description is a tiny self-hosting jit, in the spirit of a jvm. the first packing attempt bundled every stage's code with a full test script. - -### 9 - -> nono we don't need all the code, just the recent ones. my msgs and your summaries are more important and all should be there - -**summary:** this package. only the zygote stack plus its examples and tests are included, and earlier stages appear only as summaries. the golfed reference vm and assembler are inlined under message 3, because they define the instruction set. - -### 10 - -> we're gonna make this thing cooler. make the syntax C-like whilst still keeping the forth capabilities like super-homiconicity and the likes, add explicit and automatic gc (use a fast approach) and memory management that looks like this: -> every heap object has a classifier u m d, up middle down. up means the object will die at the scope above (becomes m when returned to the parent scope, and it must be returned and cannot be discarded). m means it must be used here and can be passed down (but once it's recasted as u or d it can't be casted back to m in this scope). d means the variable is passed down, and its lifetime ends after it's given for the first time to a scope lower than the current one. -> ask me questions to clarify this approach, then add it to the code and also add a simple static analyzer which checks these lifetimes - -my answers to the clarifying questions, exactly: - -> scope: every { } block -> -> lending an m object to a callee: borrow, no escape (Recommended) -> -> storing a heap object inside another object or a global: container gets ownership. putting a value inside a container requires its umd to match the parent, and from then on, the umd for that is also inherited from the parent (as in if a parent m is casted to d, so is the child heap object) -> -> gc: free lists + mark-sweep (Recommended) -> -> where the compiler lives: resident in vm code. bootstrap it step by step, by writing a c-like in core.c and then rewriting the compiler inside the c-like. also bring back llvm if you think it'll make your job easier -> -> homoiconic features: parse words, quoted code blocks, inline stack code, patchable compiler tables -> -> how an inner block hands a u object up: expression and assign, both -> -> when the analyzer runs: inside the compiler but can be turned off if the code requests it - -**summary:** the genome is now zc, a typeless c-like language, described above. stage 0 is `zc0.c` (kept as its own file next to core.c rather than inside it, so the runtime still has one native file), and the resident compiler is `src/compiler.zc` plus `src/rt.zc`, which reached a byte-identical fixpoint compiling itself. llvm wasn't brought back, since the target is the vm itself. memory went to 1m words, and core.c gained an interpreter for non-arm64 hosts. calls i made without asking: tags go on signatures (`fn f(m a, d b) -> u`) and recasts are `x as u` / `x as d`; a d object touched inside an inner block moves into that block; storing into a borrowed object, a global or untracked memory needs `as d`; handing a u up by assignment only reaches the directly enclosing block; unchecked code gives its objects to the collector. the old asm genome moved to `legacy/`. - -### 11 - -> progress report? -> add types please :) -> mostly as a compiler primitive though, plus type-inspection via reflection -> and a small optional typechecker (default off) -> oh and keep the stuff you write as a history scrapbook -> if it helps, add a path to the hardware which is called "virtual enhancements", and allows up to 512 custom operations to be compiled down via jit into hardware-level speeds and interoped directly into a fast path in the vm to become essentially custom wiring. useful for division and other stuff as a dynamic runtime path - -my answers to the clarifying questions, exactly: - -> types: words + structs + generics -> -> reflection: runtime type of heap objects, function signatures, typeof at compile time -> -> how an enhancement is defined: either actual C or llvm ir code or vm code or micro-ops passed through an optimizer. since for example, micro-ops and vm code are not sufficient for optimizing things like division -> -> scrapbook: notes + code snapshots - -**summary:** the progress report said the previous round was finished and shipped. i then laid out a plan where the core would compile c or llvm ir enhancement sources at runtime with the host toolchain and load the result. part of that reply was stopped by a safety check before it finished, so i stopped and checked in instead of building it. - -### 12 - -> also make the umd syntax like `type.u name`, and casting is multiplication `u*name` -> ideally i'd prefer memory to be unlimited words growing until system oom, but 1m is fine -> core.c plain interp is also nice -> zc0.c own file is fine -> i mentioned llvm for portability to non-arm targets -> yes, d object semantic that was intended -> u object hands up one block and becomes an m, that's fine. the code can make it a u or a d or whatever -> explain your gaps more -> -> wait why safety check? what's wrong with that - -my answers to the clarifying questions, exactly: - -> declarations: c-style, var -> let -> -> tags on untyped values and the names u, m, d: names reserved, bare .u allowed, untype is m by default -> -> llvm: llvm jit backend (Recommended) - -**summary:** on the safety check: nothing was wrong with the request. my best guess was that it tripped on the plan for a program inside the vm handing source text to the system compiler and loading the result into the running process, since that pattern also shows up in malware. with llvm meant for portability, that path wasn't needed. the gaps got the longer explanations that are now under open ends above. then the round itself: - -**syntax.** declarations are c-style (`int x`, `*node.m p`), `let` replaces `var` for untyped and inferred declarations, tags are `.u .m .d` after the type or on their own, recasts are `u*x` / `d*x` / `m*x`, `u m d` are reserved, and an untagged parameter counts as an m lend. - -**types.** a compiler primitive: hash-consed records with structs, generic structs and functions, fixed arrays, function types, `typeof`/`sizeof`, `as` casts and a reflection api, with object headers carrying their type. the typechecker is off by default and turned on with `typecheck on;`. - -**virtual enhancements.** opcode 21 installs, 22 to 533 are the slots. micro-op recipes and lifted vm code go through an optimizer in the core (folding, cse, dce, multiply-high division by constants) and get inlined by both jits. the language's own `/ % <<` now run on them. - -**backends.** a tiered llvm backend (`-DZYLLVM`) for non-arm hosts. - -**bootstrap and history.** it still reaches its fixpoint on all three backends. `history/` holds notes for every stage and code from stages 7, 10 and this one (in 11-types-enhancements). - -### 13 - -> gaps -> 1. when there's a var state change to d, mark that var as dead by default for any other scope that can access it afterwards. u is fine since it just returns -> 2. any suggestions for a cheap fix? -> 3. it's fine, rare occurrence (probably?), suggest a fix -> 4. fix that -> 5. suggest a fix -> 6. fix -> 7. fix - -**summary:** the numbers followed the gap list from my previous chat message. here's what each one got. - -**1. joins.** a variable that became d, or was given away, on any path is dead after the join, and fixup code frees it on the paths that still own it. a loop's exit state is the join of its breaks and its normal exit. giving something away on a path that loops back is still an error. u and borrows don't get the dead treatment. - -**2, 3 and 5.** suggestions only, now under open ends: a quarantine on reuse plus "borrowed from" marks on pointer-typed values for aliases, a stack-depth opcode for the collector, and page-indexed invalidation plus per-slot install tracking for the jit. - -**4. heap.** a buddy allocator. - -**6. stack checks.** all three stacks are checked: data and return at every block exit on all backends, and frames in every prologue. - -**7. the small stuff.** error recovery with up to 20 reported errors, line numbers carried in token lists, a signature prescan over the whole unit so prototypes are optional, storing into a borrowed object moving the object automatically, `?:`, and go-style `switch`. on the side, a 4-token lookahead fixed `**` declarations. - -### 14 - -> how costly is it if we add a counter to each block to see how many times it runs, then run the optimizer on it if it's a hot path? - -> continue - -**summary:** answered without building anything. about 4 instructions per block entry while a block is being counted, and nothing once its optimized translation replaces it. the optimizing pass would reuse the enhancement lifter, optimizer and register allocator. lifting whole blocks would need jz side exits and barriers at calls and i/o. compiling a block that way takes microseconds, against milliseconds for llvm, and keeping values in registers instead of the memory stack likely gives 2 to 4x on tight loops. it's listed under open ends. then the gap fixes continued. - -### 15 - -> write some really cool examples for this language - -> no, wdym building a fresh vm?? just pocs 😠we already have a compiler and everything - -**summary:** my progress note had said "building a fresh vm", which only meant compiling core.c into a binary to run the examples. eight proofs of concept went into `examples/`: mandel, bf, dump, tree, lang, staged, quine and life, each described under files above and checked by `test.sh` on all three backends. - -### 16 - -> add opt keywords, for example `optim` (or o3, i prefer o3 as the keyword) will cause any vars in a scope to not assign heap type metadata, compiles with opt level o3 and is immediately compiled down to native, and when used with variables they must be always typed and it reduces the perf cost for accessing or modifying them, etc etc. add a `fixed` keyword which says that an array has a fixed size and cannot be resized, etc - -my answers to the clarifying questions, exactly: - -> where o3 goes: functions, blocks and single vars -> -> how far o3 goes: real optimizing tier (Recommended) -> -> what o3 code may give up: type stamps on objects, zero-filling new objects, the address of o3 vars, stack and frame checks, also i don't like the -> return type syntax. please replace it with the c-like syntax -> -> arrays: add growable arrays too (Recommended) - -**summary:** three things changed. - -**return types.** functions are declared c-style now, `int f(int x)`, `*node.u make()`, `<T> T first(*list<T> l)`, with fn types written `int(int, *char)`. `->` is gone from the compiler, zc0, the tests and the examples. - -**arrays.** `[]T` grows (`push`, `pop`, `resize`, `len`, `cap`), and `fixed []T` can't change size after `new(fixed []T, n)`. both are bounds-checked. `[n]T` stays as it was, plus a compile-time check for constant indexes. - -**o3.** on functions, blocks and single variables, with the trade-offs you picked, and a real optimizing tier in the core, described in the o3 section above. it compiles at install time on arm64 and llvm and has a region interpreter for the plain build. measured gains are 1.5 to 2.8x on the interpreter, 8 to 100x on llvm and 20 to 43x on arm64 (under qemu) for loop-heavy kernels, and much less for call-heavy ones. on the way, the arm64 jit learned to specialize an enhancement on literal inputs, so `x / 7` is a multiply-high everywhere, not only in o3 code. tests for arrays and o3 turned up an old heap bug: freeing a container could merge one of its children into it while it was still being freed, which corrupted a free list. growable arrays hit it every time. it's fixed. |