An ordinary GoSSR page needs more registers than my interpreter can name. My eight-bit register operands can name 256 slots. The page builder can generate a function needing more. The page isn't doing compiler research. It wants to render.
Getting real programs through the interpreter felt great, after all that work underneath it was one of those moments where I couldn't quite believe it was working. Had I accidentally run a compiled version? Seeing the program run was almost suspicious.
I'd also prefer this perfectly ordinary page to render. First I'm looking at whether the values really need all those slots at once.
Count the slots before asking for more
These registers are slots in the interpreter's memory, split into banks for different kinds of value. (Reading Scriggo, another Go interpreter, helped make that arrangement concrete for me.) They aren't the processor's hardware registers.
A bigger backing slice would give me more space, but even with that storage waiting for me, no instruction can name slot 256 through an eight-bit operand. I'm short of names, not space.
Buying a longer bookshelf doesn't give the label printer another digit.
I did choose this limit myself, which has rather spoiled my chance to blame someone else. Wider register numbers would let me name more slots, but I still prefer compact instructions for the common case. Spilling gives the extra values somewhere to live without widening every instruction.
An eight-bit allocation counter has the same limit as the instruction, with an especially unhelpful way of crossing it:
var next uint8 = 255
next++
fmt.Println(next) // 0
This is ordinary unsigned arithmetic in Go. In a register allocator, it can assign a new variable a slot that already belongs to an earlier one. It can also leave the recorded peak below the amount of storage the function needed.
The allocator needs a count wider than the operand it's checking, so it can notice reaching 256 instead of wrapping round and losing the evidence. The instructions can stay compact while the compiler keeps an honest count.
Now I can get an honest overflow error. That's progress of a limited kind. To render the page, I need to ask a smaller question than how many variables it declares. How many of their values are alive together?
Imagine this sequence of work:
calculate a label
send the label to an output operation that doesn't retain it
calculate the next label
Once the first label has no remaining reader, the second can use its register. Both declarations exist in the source. Their working lifetimes don't overlap.
I recycle dead slots before asking for fresh ones. Scratch registers hold a statement's temporary values. Once the statement finishes, I can release them while keeping the function's ordinary locals live.
The page can be long and still build one label after another, and I don't want to reserve a slot forever for every label it has already written. I can give that slot away. The compiler must establish when. A closure or a pointer can preserve a reader that isn't visible as a later use of the local's name, so counting those uses alone won't tell me when the value is finished. Until the analysis can show that reuse is safe, the slot stays occupied.
Give the excess values a home
A spilled value lives outside the compact register range, so the interpreter reloads it into an ordinary register for an operation and writes the result back if the value changes.
I start spilling new declarations at index 246. Ten slots stay spare for temporary work. A spill slot is still memory in the interpreter. Nothing is being sent to disk. The compact instruction is staying, but now I have more work around it.
An update is easy to get halfway right. Suppose the spilled variable contains 41, and I reload it to increment it.
Write back the result and reserve enough space
The increment happens in a scratch register, but the variable needs to keep the answer:
If I miss the writeback, the next read finds 41 again. Wait, where's forty-two?
I did the increment in a temporary and then threw the answer away. I have to hold the scratch register until the writeback is done, because letting another operation use it first would lose the update I was supposed to save. Reassignment, increments and compound assignments all need to leave the spill slot with the current value.
A pointer makes the relationship visible from another direction:
n := 41
p := &n
n++
fmt.Println(*p) // 42
p points to n. So it must see the update. Pointing it at a temporary copy would preserve the first value while losing the relationship the program asked for. I could keep checking reassignments and increments and reads through a pointer and.... Every write, basically.
A call's frame holds its local and temporary slots, and the final size must cover the largest amount of storage needed anywhere in the function. The cursor can rewind. The peak can't. This is a number I mustn't let the tidying lose. A later branch may finish with fewer slots while an earlier branch needed more, so reserving only the final count can send that earlier branch beyond the storage supplied by the runtime. The allocator keeps the peak separately, even while its current position moves backwards.
For the page, reuse, spill writeback and enough room for the busiest point have to produce the same HTML as the compiled version, including values read back after spilling. I'm working towards rendering the page as written. Its author shouldn't have to split a normal function to suit my eight-bit operands.