Redesign TestOps

[apt1002]

Redesign TestOps

[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.