Store code in a more abstract form

[apt1002]

Mijit keeps a copy of the code it has compiled, in case it needs to specialize and recompile it. Currently, the code is stored as a tree of basic blocks, each consisting of a list of Actions followed by a Switch. Instead, represent code using a separate data-flow graph and decision tree.

Advantages of representing code as a tree of blocks include:

• It is "easy" to concatenate code blocks. It's not really; it's just that all the difficulties have been shunted into register allocation.
• Side-effects happen in the "right" order. Again, this is deceptive; representing one correct ordering of Actions is not as good as knowing what can affect what.
• It's a representation that is close to the code that has actually been compiled. However, this is not actually a requirement.

The goal of this issue is to avoid representing the order of the Actions. Mijit needs to be able to execute code speculatively and in any order, unless explicitly constrained to do otherwise. The optimizer must be free to schedule Actions on the hot path before it is sure that the hot path will be taken. The optimizer must be able to move Action::Loads backwards until they meet the corresponding Action::Stores. It is of course necessary to put some constraints on reordering, but representing just one correct order of the Actions is too prescriptive and inflexible.

This particularly affects memory accesses, which until now have been relying on execution order to disambiguate what happens if there are several accesses to the same location. It is extremely common, especially in auto-generated code, for a value (call it x) to be stored in memory and then soon afterwards loaded back into a register, and ideally this should not obstruct optimizations involving x. However, unaided, Mijit can't easily tell whether two memory accesses might be to the same location, and if there is another store that might modify x while it is in memory then no optimization is possible. Mijit therefore should not be relying on instruction order, but should instead use hints in the Mijit code (and if the hints are lies, the behaviour is undefined). Mijit's memory model is the subject of #14.

To be continued...