Division

[apt1002]

x64_64 provides the ability to assemble an unsigned long division instruction. Expose it as a Mijit instruction.

The main task is to define the behaviour of the Mijit instruction in exceptional cases. For example, do we like Undefined Behaviour? Do we need a way to throw Exceptions? It eventually needs to abstract a variety of different native machine codes without excessive boiler-plate.

Also, we should provide signed division, which is harder still.

[apt1002]

I think there are going to be other ways in which undefined behaviour arises in Mijit (see e.g. #14) so perhaps it's fine here too.

[apt1002]

This is now done. We provided unsigned and signed division (UDiv and SDiv) as new BinaryOps. The semantics cover the cases where Arm and x86 do the same thing; everything else is missing or undefined behaviour.

Unsigned division is uncontroversial. The quotient is rounded down, and only division by zero is undefined behaviour. UDiv divides a one-word integer (32- or 64-bit) by another; there is no 128-bit by 64-bit division because it would be difficult to implement on Arm.

The quotient of a signed division is rounded towards zero, which is usually not what you want, but that's what the hardware does (both x86 and Arm). Again it's 64-bit by 64-bit division. There is one case in which signed division gives an answer that cannot be represented: -2⁶³ / -1. This is undefined behaviour in Mijit, because x86 and Arm handle it differently.

Mijit does not provide an instruction to compute the remainder of a division. The remainder can easily and relatively cheaply be computed using a division, a multiplication and a subtraction. This matches Arm's design.

Experience of implementing Beetle's five division and remainder instructions in terms of Mijit's new instructions suggests that UDiv is really all you need. SDiv is quite unlikely to be useful unless you are sure you want it's strange rounding mode and you can avoid it's undefined behaviour. For now we provide both UDiv and SDiv.