Integer division by zero

[agner]

I have almost finished making the division hardware for the ForwardCom softcore (using a radix-4 division loop). Now I have to decide what to do with integer division by zero. I have tried to google what other microprocessors do with integer division by zero. X86 makes an error trap. ARM and PowerPC give 0 when dividing by zero. Atmel gives -1. Since there appears to be no sensible standard, it is necessary to make a decision.

It is part of the design philosophy of ForwardCom to avoid "undefined" behavior. Ideally, every situation should have a predictable outcome. I will not use error traps because this is inefficient and bad for vector processing, so I decided that the most sensible solution is to return INT_MAX or INT_MIN, depending on the sign of the dividend. Unsigned division by zero will give UINT_MAX.

Now, I am not sure what to do with an integer modulo zero. I am considering three possible solutions:

• a % 0 = 0
• a % 0 = INT_MIN or some other extreme value to indicate an error
• a % 0 = a

I am most in favor of the last solution because it allows the compiler to optimize

Code: Select all

q = a / b;   r = a % b;

to

Code: Select all

q  = a / b;  r = a - q * b;

The latter code is faster, and r can be calculated with a single mul_add instruction.

What do you think? Are there any strong reasons to choose another solution?

[HubertLamontagne]

Clearly it's best if a % b should be equal to a - (a/b)*b in all cases including error ones yes (/0, and -0x80000000/-1 in signed 32 bits), that way the CPU doesn't need a modulo instruction and can replace it with a - d*b in all cases yeah.

As for n/0 returning 0 or int min/max, there's something inside of me that feels like returning "0" is simpler, but what do I know...

One thing that always really bugged me is that division of negative numbers rounds upwards rather than downwards, which makes it impossible to optimize /8 as >>3 and requires conditionals if you want rounding to stay consistent, but I have to admit that these sign change shenanigans make sense in their own way and probably are what programmers expect and probably can't be changed.

[agner]

Hubert, a % b = a will satisfy a % b == a - (a/b)*b in all cases. There is a modulo instruction, and it is easy to implement because the existing division hardware gives the remainder as well, whether you need it or not.

I have considered to make division by 0 give 0, but this would increase the risk that an error goes undetected. Giving an extreme result is more in line with floating point giving ∞.

Integer division on ForwardCom has option bits for different rounding modes: truncate, floor, ceiling, round to nearest or even. This works fine in my softcore (not published yet). Division by a power of 2 with rounding to floor will equal signed shift right. I have considered making a shift right instruction with rounding mode options, but this might be a little complicated. Another possibility would be to make a special case out of division by a power of 2 with shorter latency. However, this will be useful only if the compiler knows which implementation of signed division by a power of 2 is the fastest on a particular microprocessor model. The programmer can help by specifying unsigned numbers, but not all programming languages have unsigned integers.

I wonder why other microprocessors don't have integer division with optional rounding. At least I am not aware of any. It requires a lot of code to correctly round a rational number on traditional microprocessors without using floating point. This is easy on ForwardCom. Think of embedded systems without floating point processor.

[Webenson Diolen]

Hello Mr Fog,

I understand that the concept of processor flags is outdated and making superscalarity much harder to implement. But just as an idea,
if your ISA concept had a single debug register to store the program counter of the failing calculation, wouldn't this mitigate the underlying
problem?

The application can decide to check for such a flag and an adress that is stored to the debug register, or ignore it. If you limit
the ability of this register on holding and returning a value of the program counter, without any direct access to the memory system,
it could be with little hardware cost than a regular register.

It is obvious that this brings up more questions, like how to manage and store such a register for every cpu thread, but I would find
this very convinient to us.

Because integers where historicly not intended to deliver a payload over implicit store values, one should not try to do it.
I would treat divsion with 0 like ARM and PowerPc and return 0.

[agner]

Hi Webenson

What you propose is indeed the solution I have implemented. Performance counter number 16 will count various errors and show the code address where the first error occurred. This is a cheap solution to implement in hardware.

Division by 0 gives INT_MAX, INT_MIN, or UINT_MAX. Returning 0 would increase the risk that an error goes undetected. You should not rely on any specific behavior of integer division by 0 in C/C++ because it is officially undefined so there is no guarantee that it will behave the same on all types of processors.