I can make an addition handler faster, but I'd also like to stop calling it when I've already got the answer.
The assembly work changes how execution reaches those handlers. Now I'm looking at the instructions themselves. Two additions with the same inputs, a field read repeated round a loop, another check of an index I've already checked.... There is work here I would happily stop doing.
I've started calling Piko's interpreter Pipit. It still lives inside the framework. Pipit is a small bird we have in Jersey. (I thought about Puffin, but that felt a bit stereotypical.) Pipit gets less attention, and a quick, agile little thing feels like a good namesake for the interpreter I'm trying to build.
Puffins are lovely, but I feel the smaller brown birds deserve some attention as well. They always look like they're halfway through an errand. I find that quite endearing.
The compiler turns typed Go syntax into bytecode, allocating registers as it goes. These are slots for the interpreted program's values, with different kinds kept in separate arrays called register banks. I'm optimising that bytecode directly. There isn't a separate static single assignment representation, or SSA, where each assignment gets a distinct name.
I like being able to follow the instructions from compilation into execution. But these slots get overwritten, branches skip instructions, and calls can change memory. Every shortcut needs some knowledge of that behaviour. The optimiser is becoming a sizeable pile of code devoted to making the rest of my code do less.
I've already added those
Start with two additions using the same values. Written with register names, the opportunity looks like this:
r1 = 2
r2 = 3
r3 = r1 + r2
r4 = r1 + r2
Both sums are five. If r3 still holds that result, I can copy it into r4 instead of doing the addition again. This is the sort of small, obvious saving that makes me want an optimiser in the first place.
Global value numbering, or GVN, finds calculations whose results can be reused by associating a calculation with the values it used, then looking for a later calculation that can use the earlier answer. I can only reuse that answer while its inputs and the saved result still hold the values I remembered.
Add one instruction:
r1 = 2
r2 = 3
r3 = r1 + r2
r1++
r4 = r1 + r2
The spelling of the second addition hasn't changed. Its answer has. Reusing five would lose the increment, so the optimiser has to stop treating the new r1 as the value it remembered. Overwriting r3 would spoil the shortcut too, even if the inputs stayed put.
This starts pulling instruction details into the analysis. Some instructions select another tier of operations rather than doing the work themselves, so execution follows that selection before it reaches the increment. If my write analysis stops at the outer instruction, it never sees the register change.
I can get the handler working and still be left wondering why the optimiser reused five, because it needs its own account of that write rather than learning it by watching execution. Register banks matter here too. Integer slot five and general-value slot five are separate storage despite sharing the number, so the optimiser has to identify the bank as well as the slot. Adding an instruction now gives me another job. Besides making its handler work, I have to describe its writes accurately enough for the optimiser. A pass is a stage that analyses or rewrites instructions. I can't expect every pass to rediscover those details independently and keep agreeing forever.
That information is useful beyond repeated arithmetic. If execution has already established that an index is within a slice, checking it again can be redundant. Removing that repeated work is bounds-check elimination.
But increment the index between the check and the access, and I'm back to needing the check. A channel receive can replace the index too. Its destination can be encoded somewhere other than the operands an arithmetic instruction uses, so looking only for an obvious assignment misses a write.
This is why I'm interested in getting write tracking right once. GVN needs to know whether its inputs changed. Bounds-check elimination needs to know whether its checked index changed. They are asking different questions about the same instructions.
There's also the route through the function. A check on a neighbouring branch doesn't help an access that can bypass it. The execution has to pass through the check first.
Put the check inside an if ready branch and the access after it. When ready is false, execution reaches the access without checking anything. I haven't learned that the index is safe on that route. Compiler terminology calls the required relationship dominance. A check dominates the access only when every route from the function's entry to that access passes through the check.
I'm already doing more than spotting matching instructions, following both the changing values and the paths that reach them. That work can support several optimisations, which is encouraging, although it is more involved than crossing out a second comparison.
Read it once, unless the loop doesn't run
A repeated field read offers another saving:
type T struct { Value int }
func sum(p *T, count int) int {
total := 0
for i := 0; i < count; i++ {
total += p.Value
}
return total
}
Nothing in this body changes p or its field. For a stable, valid object and a loop that runs, why keep loading the same value? Read it once and add the saved value each time. Moving an unchanged calculation out of a loop is loop-invariant code motion, or LICM.
The tempting transformation is small:
value := p.Value
for i := 0; i < count; i++ {
total += value
}
Call the original sum(nil, 0), though, and it returns zero without touching p. The transformed version reaches through nil before asking whether the loop runs. Now it panics. A value that won't change can still be one I'm not allowed to read yet.
The bytecode makes the changed order easier to see. Here are the relevant operations with register details left out:
read moved read guarded
---------- ------------
read p.Value compare i < count
compare i < count exit if false
exit if false read p.Value
add field to total add field to total
My implementation makes this worse. The hoist introduces the read, but the field-read handler returns zero for nil instead of panicking. The call still returns the expected zero.
Two mistakes agree on an answer.
Disabling hoisting keeps the read behind the guard and also returns zero. Reading the field directly, without a loop, exposes the handler's separate failure. I'm trying to get rid of one field read, and now I've got two bugs to fix. Going well, then.
There are useful cases left. An earlier successful dereference on every route can establish that the receiver isn't nil, provided it hasn't been replaced. The read also needs a destination I can write without changing an exit path's result, because an unused temporary and a live variable aren't interchangeable places to put it.
So I'm adding entry conditions and destination lifetimes to the information this pass needs. The amount of code inside the loop wasn't a good guide to the size of the optimisation.
The register stayed put. The object didn't
Put a call between two reads of the same field:
a := p.Value
use(p)
b := p.Value
If use changes the object, b needs the new value. The register holding p can stay exactly as it was throughout, so tracking writes to that register won't catch a write through the pointer into the object. Another reference can reach the same object too. Those references are aliases. A write through one can invalidate a value read through the other, even though their names have nothing in common. I can see a repeated field read and would like to remove it, but what does the function between the reads change? Which references can reach that memory? The extra read is looking cheaper by the paragraph.
Heap-purity analysis identifies functions that don't mutate that memory, including through the functions they call. Alias analysis helps distinguish writes to the same object from writes elsewhere. Together they can let repeated-read elimination and LICM keep useful information across operations they would otherwise have to distrust.
For an unknown call, I keep the read.
That leaves an opportunity unused, but I can still understand the resulting program, and guessing that an unfamiliar function leaves the object alone would make the shortcut much harder to justify.
My passes need to leave something for each other
These analyses also affect when the optimisations can run. Inlining puts a called function's body into its caller, changing the instructions the later analyses inspect. After inlining, I compute heap-purity and alias information, then give the relevant optimisations another pass through the bytecode.
An earlier pass can leave a field read in place because it doesn't know enough about a call. Once more information is available, it can reconsider the same read. I don't have to make the earlier pass guess.
Let neighbouring instructions share a handler
Instruction fusion has its own requirements. It combines neighbouring operations into one handler, saving trips through dispatch. A constant load, comparison and branch can become a candidate when their operands connect. Another reader of an intermediate value, or a jump into the middle, can prevent the combination.
A pass can only combine the instructions it recognises. Changing or consuming part of a sequence changes what the next pass can find. But preserving an opportunity isn't the only ordering problem. A rewrite can also make the analysis already attached to the bytecode stale.
Moving instructions moves their facts too
The hoister inserts instructions and shifts later positions. Jump offsets and source mappings have to move with them. Its alias information is indexed by instruction position, so leaving that information untouched could attach an old answer to a different instruction.
The implementation discards the alias information after insertion. Later questions then get a conservative answer unless the analysis runs again. That can cost another optimisation, but it stops the next pass trusting facts about instructions that have moved.
I can't treat this as a bag of independent tricks any more. One pass needs information another supplies, and a third can invalidate it. Even keeping error locations useful depends on remembering what a rewrite moved.
Keeping the optimiser small enough to understand
For the next optimisation, I have to ask what it needs to know, where that information comes from and what its rewrite leaves invalid. Those answers decide whether it joins the list of passes. A correct arithmetic handler has no say in it.
I'm keen to keep working on this, but I also need to be able to come back and follow it. Accurate descriptions of instruction effects can serve several passes. Unknown calls can keep their reads. A moved instruction can force an analysis to run again before another pass trusts it.
Those choices leave some work in the interpreted program. I'm happy with that while I can explain why it's still there. I don't want every small optimisation to require remembering how all the other ones work before I can safely change a line.