Redesign TestOps

[apt1002]

In Mijit's domain-specific language (mod code), basic blocks end with a "switch" statement that decides where execution should go next. Currently this is rather ad-hoc, and I'd like to redesign it. Here are some requirements:

1. Each switch should make its decision based on a single value.
2. We need several kinds of switch statement: interval trees; jump tables; binary "if"s; a no-op that always selects the same case. The different kinds of switch require different kinds of case, but it should be forbidden to mix different kinds of case in one switch. All kinds of switch are closed enumerations; we do not need indirect branches.
3. Many switches need a default case. For some kinds of switch it would be acceptable for the default case to be considered exceptional, such that Mijit won't optimize it. However, that would be unacceptable for the no-op switch and for binary "if"s.
4. The optimizer needs to be able to reorder the cases. It would be convenient if all the cases were mutually exclusive, but I don't think that will be possible. At least it would be nice to simplify the condition "case 2 and not case 1" to a single test. [Removed: Certainly, the tests should be side-effect free.]
5. The optimizer needs to be able to reorder the switches, where data flow allows it. A motivating example is replacing if (a && b) into if (b && a).
6. If a sequence of switches test the same value repeatedly, the optimizer will want to try to replace the common path by a single switch. A motivating example is a switch that tests the bottom 8 bits of a register, then shifts the register right 8 bits, and then tests the bottom 8 bits of the register. We would like to optimize this to a switch that tests the bottom 16 bits of the register.

Kinds of TestOp:

• [ ] Unconditional jump.
• [ ] Boolean "if".
• [ ] Bit tree (decoding a bit pattern).
• [ ] Interval tree (classifying a number).
• [ ] Trap.
• [ ] Counter.

[apt1002]

A common kind of TestOp is a decision tree, where the decisions are all based on bits of the same word. Let's call this a "bit tree". This is actually quite a nice case from the point of view of optimization.

Currently, each case is annotated with a bit mask and bit pattern, and we select the first one where discriminant & mask == pattern. This is too general, because it makes optimization into a boolean satisfiability problem.

Instead, we should impose a restriction that a bit tree is actually a tree. Examples:

• Valid: all the masks are 0xFF and all the patterns are different 8-bit numbers.
• Valid: one case is (0x80, 0x80), and the other two are (0x81, 0x00) and (0x81, 0x01).
• Valid: the only case is (0, 0).
• Valid: the only case is (0xFFFFFFFF, 0x01234567).
• Invalid: two cases are (0xFF, 0x5E). These cases overlap.
• Valid: one case is (0xF0, 0x50) and another is (0xFF, 0x5E). At runtime, we'd choose the most specific case that matches.
• Invalid: one case is (0x1F0, 0x150) and another is (0x10F, 0x10E). At runtime, if the discriminant were 0x15E, we would not know which case to choose.
• Invalid: one case is (0xFF0, 0x5E0), one case is (0x0FF, 0x05E), and the third is (0xF0F, 0xE05). There is no overlap but it's unclear which bit is the root decision.
• Invalid: one case is (0x1FF0, 0x15E0), one case is (0x10FF, 0x105E), and the third is (0x1F0F, 0x1E05). It's unclear which bit is the second decision.

It is not a requirement that a bit tree be exhaustive. However, I think it is desirable that a bit tree can have a default case, which is selected when none of the other cases is selected. The default case should have a mask of 0 and a pattern of 0. I also think it is desirable that if you nest two trees with the same discriminant, it can be optimized into a single tree. These requirements interact, meaning that it is desirable that any bit subtree can have a default case.

This might be a good formal definition of a valid bit tree:

• If there is exactly one (0, 0) case, it is the default case. Remove it.
• If no cases remain, the bit tree is valid.
• Otherwise, the & of all the masks must be non-zero. Let's call this the root.
• Partition the cases by pattern & root. For every part:
  • Replace each (mask, pattern) with (mask & ~root, pattern & ~root).
  • The part must be then be a valid bit tree.

[apt1002]

The concept of a "trap" is possibly a special case of a TestOp.

A trap is anything that the optimizer is not expected to understand. It includes: rare operations implemented as native code subroutines; input and output; returning control to the VM runtime; and errors and exceptions.

When a trap occurs, Mijit should flush all cached information so that the state of the VM literally conforms to the programmers' model. It then calls a trap handler (a native code subroutine) passing a pointer to the Pool. The trap handler thereby has read- and write-access to the machine's Globals, and thereby to the machine's memory. It works out why the trap occurred, and (if appropriate) performs some calculation and updates the registers and memory. Finally, it will return a value indicating what Mijit should do next. We distinguish two cases:

1. If the trap handler was able to completely handle the trap, it can instruct Mijit to resume execution. Execution resumes in a machine state that is statically encoded in the TestOp (the trap handler cannot choose it). This case is relatively efficient, being nothing but a subroutine call, but it is limited in its capabilities, because it executes while Mijit is running, and borrows the machine state in the same low-level form that Mijit does.
2. Otherwise, the trap handler can instruct Mijit to exit and return control to the VM runtime. It does this by returning an exit code. The VM runtime may or may not reenter Mijit after handling the trap; Mijit doesn't care. This case is relatively inefficient (it might even cross a language barrier), but it is more flexible and high-level.

I think we can keep traps pretty simple, at least from Mijit's point of view. It is useful for different TestOp::Traps to have different trap handlers, so that the work Mijit has done to arrive at the right TestOp is not wasted. However, all trap handlers have the same arguments (just the Pool pointer?) and the same return values (just the exit code?), such that Mijit only needs a limited understanding of the subroutine calling convention.

[apt1002]

A new kind of TestOp: a counter. The TestOp specifies a base pointer register, a constant offset, and a constant increment. The constant is added to the memory location. Two cases: the counter carries, or it doesn't.

This would be a TestOp with a side-effect; I don't see any big problems with that.

Counters are useful for updating reference counts, for example.

[apt1002]

Several kinds of TestOp are handled reasonably well by today's invention. Switch::Index is a multi-way jump in which the discriminant is an index into an array of jump targets. There is a default jump target which is used if the index is too large. Note that this satisfies requirements 1, 3 and 4. The cases this handles include:

• A boolean "if" is a Switch::Index with only one non-default case. The comparison is no longer part of the TestOp, and is instead an Action that precedes it.

• Each node of a decision tree is a Switch::Index. The logic operations are no longer part of the TestOp, and are instead Actions. A decision tree where the different branches do not all test the same bits requires several nested Switch::Indexes.

The quality of the code lowered from a Switch::Index is similar in the case where the TestOp was previously Eq or Ne, and slightly better for Bits. If trait Lower had an entry point for a jump table the code could get better still. Where the TestOp was Lt or Ult the lowered code has got worse, as it has to compute the condition as a boolean value and then test it again. This is a problem for the future.

Currently the other cases of enum Switch are Always and Halt. Switch::Halt is the only special case of of Trap implemented so far (see #38). Interval trees and counters are also TODO.

[apt1002]

I've since removed Switch::Halt and Switch::Always leaving only Switch::Index (which is therefore currently just called Switch).

Traps, including Halt, have proved unnecessary so far. Instead, we found another way to exit Mijit with a return code.

Always is never generated by the optimizer, which prefers to make a copy of the code that Always would have jumped to.

There's not much benefit in the cases of an Index being consecutive small integers. On the contrary, it feels like an unnecessary restriction. I think perhaps I should allow the cases to be numbered arbitrarily, and I should remove the default case. If at run time the discriminant value does not match any of the cases, then one of them should be chosen in an undefined way.