Signed overflow detection on anti-80.md

Signed overflow detection on anti-80

Motivation

Rust would like to enable overflow checks (and does in debug mode) but many CPUs don't have great support. JS and many other languages need overflow checking.

For adding or subtracting a constant the overflow check is already fairly simple, but it's a bit longwinded for adding two registers.

Implementation

Overflow check inspired by RISCV's SLTI instruction uses a temp register. There is an overflow if the result is less than one of the inputs and the other input is not negative. Also an overflow if the result is >= one of the inputs and the other input is negative.

add rd rs1 rs2          // We want to check if this overflowed.
mov rt rs2              // Remove instruction if rs2 is dead.
skip ge rd rs1
xor rt rt #-1           // if (rd < rs1) flip sign of rt.
skip ge rt #0           // Check sign bit.
jump overflow_handler   // Normally skipped.

Alternative using two temp registers (inspired by V8 MIPS code).

add rd rs1 rs2          // Assume rd is distinct from both rs1 and rs2
xor rt1 rd rs1
xor rt2 rd rs2
and rt1 rt1 rt2
skip ge rt1 #0
jump overflow_handler

This is the same number of bytes, but only has one skip instruction which may be faster. If rd is identical with rs1 or rs2 then we need three temp registers for this version.

Alternative with a change to the instruction set

One of the spare comparisons could be signed overflow for subtraction. You would normally do this before the subtraction because that's where you have both operands.

add rd rs1 rs2          // Unchecked add.

// Checked version assuming rd and rs1 are distinct.
rsb rd rs2 0            // rd = -rs2
skip nooverflow rs1 rd  // Skip if rs1 - rd doesn't signed overflow.
jump overflow_handler   // Normally skipped.
rsb rd rs1 rd           // Perform the addition.

If rd and rs1 are not distinct then reverse rs1 and rs2 and do the same.

For add rd rd rd there's no good way that doesn't use a temp register?

Alternative with a bigger change to the instruction set

Clearly you could save an instruction with a skip instructions for signed overflow on addition, but I think this would require more silicon since all the other skip instructions do a subtraction. It is assumed that addition is more common that subtraction.

add rd rs1 rs2           // Unchecked add.

// Checked version.
skip nooverflow rs1 rs2  // Skip if rs1 + rs2 doesn't signed overflow.
jump overflow_handler    // Normally skipped.
add rd rs1 rs2

As an aside, the comma-less syntax is intriguing. Is there a precedence for that? I'd tempted to go with a C inspired syntax, like

rd = rs1 + rs2;            // We want to check if this overflowed.
rt = rs2;                  // Remove instruction if rs2 is dead.
if (rd < rs1)              // if (rd < rs1) flip sign of rt.
  rt = rt ^ -1;
if (rt < 0)                // Check sign bit.
  overflow_handler();

Another option, an explicit "add-and-skip-unless-overflow" instruction:

add.chk rd=rs1,rs2
jal overflow

As an aside, the comma-less syntax is intriguing. Is there a precedence for that? I'd tempted to go with a C inspired syntax, like

rd = rs1 + rs2;            // We want to check if this overflowed.
rt = rs2;                  // Remove instruction if rs2 is dead.
if (rd < rs1)              // if (rd < rs1) flip sign of rt.
  rt = rt ^ -1;
if (rt < 0)                // Check sign bit.
  overflow_handler();

I think I just used the comma free syntax because I've been doing a lot of Toit programming which is very light on punctuation. Since anti80 only allows non register arguments in terminal position (for the immediate) it world probably be easy to parse. The C syntax is very easy to read though. It would be especially nice if you ever went to a two-register ISA because x86 code has confused my brain about which argument comes first.

Another option, an explicit "add-and-skip-unless-overflow" instruction:

add.chk rd=rs1,rs2
jal overflow

I wouldn't presume to spend a whole opcode on this, whereas it feels less extravagant to take one or two condition codes.

Right, I'd certainly otherwise favor the IA-64 style

add rd=rs1,rs2

for that reason. The problem with the C syntax is that it doesn't always work well. Eg., the jal instruction sets r31 as well which isn't super easy to express. I fudge it by making all jumps calls in the example, but it's not hard to imagine instructions that doesn't map well to C.