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.