add an IL with self-contained continuations

[zerbina]

Summary

Add an intermediate language extending L3 where values must be passed explicitly between local continuations.

Details

The IL is aimed at providing all information necessary for register allocation in an efficient to process format.

pass4 is responsible for allocating and assigning registers (which are just locals in L3) to Continuation locals and parameters, turning moves into either renames or copies, the former being preferred.

Language Changes

• replace duplicate Continue grammar with goto references in the L1 grammar

Other Changes

• support inserting and replacing at the same position with ChangeSet; insertions are now always applied first
• add an builders.insert overload for leaf nodes
• add the filter iterator to trees

---

To-Do

• [x] implement a working lowering pass
• [x] fix expression lowering
• [x] complete the test suite for the pass
• [x] write a proper commit message

[zerbina]

Two observations I made while implementing the pass/IL:

• procedure exit continuations are impractical. They were intended to make the languages more streamlined, by treating the exit as "just" another continuation, but - so far - they only complicate things, as the exit Continuation needs to be guarded against by all continuation processing, and "return" detection (which has been needed relatively often, so far) becomes non-local.

• L4 and L1 should probably be merged. Register allocation and stack management are closely related, and merging both passes/ILs would have multiple benefits, among them that the "active locals" set doesn't need to be preserved.

[zerbina]

Okay, so the register allocation works properly now. The main goal for the current algorithm was that it should be simple yet still produced reasonably good results, and I think I was able to achieve both.

I've also made a few changes to the IL:

• MoveAddr is named Rename now (I believe it's clearer and communicates intent better)
• drop lists are removed -- neither the new algorithm nor other possible algorithms need them them
• some other simplifications that reduce that amount of work pass4 has to do (there are still more to come)

When reading the tests, do keep in mind that they're contrived -- in a normal setting (i.e., when the IL code comes from source code), no code where locals are spawned and passed between continuations without ever being written to or read from would be produced.

[zerbina]

As can be seen in t02_different_types.test, due to the three different types, the locals all map to separate registers, even though they all use the same register type underneath (there's only a single integer type in the VM).

More broadly speaking, the different current and future target languages have different capabilities regarding integers:

• VM: 64-bit integer registers
• Wasm: 32 and 64-bit integer registers
• asm.js: 32-bit integer registers (well, variables)
• C: 8, 16, 32, and 64-bit integer, both signed and unsigned

My plan here is to introduce a lowering pass (happening before pass4) that changes the types of all integer locals into ones that are supported by the target language, together with injecting masking and sign extension operations where necessary for the correct behaviour.

For example:

var n = 0'u8
n = n + 1 

would become:

var n: int = 0
n = (n + 1) and 0xFF

which is equivalent to what pass0 already does.

Beyond allowing reusing the same registers for the various integer types, lowering integers and integer operations early also means that the bit masking is visible to optimization passes, allowing them to be optimized away, if unnecessary (such as is the case in the example above).