[kaffe] Re: Computing remainders

[Tony Wyatt]

Hi Luca and Dalibor,

On 28/06/03, you wrote:

>> The Motorola M68k series and (it would seem) the PowerPC series
>> processors do not generate an exception, but silently generate the wrong
>> answer.
> 
> Actually, I think the answer may be permitted by the ISO C 89 standard.
> See http://www.lysator.liu.se/c/rat/c3.html#3-3-5 for the rationale why
> C89 allowed some flexibility with respect to the result of the remainder
> operation.
> 
On my m68k processor, the actual answer depends on the time of day and phase
of the moon. I get very different results on the Amiga OS and Linux. The
"answer", whatever may be allowable, is inconsistent.

> One still has to special-case the MIN_VALUE % -1 == 0 case, though. Since
> for example LONG_MIN / -1 => LONG_MAX + 1 => overflow, resulting in
> undefined behaviour.
> 
 
According to the Java spec 15.17.2 (just above the "Remainder" para you
quoted, the result of (LONG_MIN / -1L) is well defined and is equal to the
dividend. It is this single point in the dividend/divisor plane that is in error on
the m68k hardware. However, I agree that a special case is the most expedient fix.

> I've "back-ported" your patch to configure.in, and checked it in. I think
> that the patched test is causing the problems now, but I didn't notice it
> since on ix86 the test fails with a floating point exception anyway.
Well, humph. BTW, I think you mean an "Arithmetic exception" There is no FP
involved.

> Here's the current test:
> 
> #include <limits.h>
> #define T long
> #ifndef LONG_MIN
> # define LONG_MIN ((((unsigned T)(~(T)0))>>1)+1)
> #endif
> T foo(T i, T j);
> int main() { return foo(LONG_MIN, -1l) == 0; }
The "==" sign is the only change I made. It requires the result to be equal
to zero, whereas the original test only required the test to complete without
error. 

> T foo(T i, T j) { return i % j; }
> 
> According to what I've said above, the test is broken anyway, since
> LONG_MIN % -1 will always overflow, resulting in undefined behavior. It
> has to be special cased.
> 
> The other issue is % with negative operands, which is not well-defined by
> C89. So I'd like to propose something along these lines for icode.h :
> 
Why can't we rely on the java spec for the required behaviour? It defines
the result according to standard mathematical principles (those that I
learned many years ago, anyway).

<snip>

> Analogous implementations should be made for long remainder, and both int
> and long division. As usual, I'd like to hear your comments.
> 
Sorry, DT, but I think you're over-reacting. I don't think the solution
needs to be that verbose. I think that the single special case we had
previously is sufficient. Unless there is another platform that gives the
wrong result, the two erring processors are well served by the fix we have
(the x86 gives an exception, the m68k gives a randomly wrong result).

All that code makes me shiver. I guess it's not likely to slow an
interpreter much further, but in the JIT, it'd be murder.

Now I don't know about other platforms, but I did a trick with the JIT(1)
on the m68k platform. In "jit-m68k.def", I made a new "remainder" function
that checks the divisor and returns zero if the divisor is (-1L). I haven't
yet implemented this trick in JIT3, since the remainder function there is
quite different.

Of course, this trick is only needed for 32/32 bits (ints). For 64 bits,
software emulation is required on the m68k platform, anyway.

#if defined(LONG_MODULO_BROKEN) && defined(FIX_BROKEN_LONG_MODULO)
static inline void
op_divsl_dddx(int src, int r, int q)
{
    debug(("divsl %s, %s:%s\n", regname(src), regname(r), regname(q)));
    assert_dreg(src);
    assert_dreg(r);
    assert_dreg(q);
    protect_ireg(r);
    protect_ireg(q);
    
    //    if divisor = -1, result is always zero
    debug(("addql    #1, %s        ; if divisor\n", regname(src)));
    WOUT = 0x5280 | (src & 7);
    debug(("bcss    lbl        ; non-zero\n"));
    WOUT = 0x6506;
    debug(("subq    #-1, %s        ; restore it\n", regname(src)));
    WOUT = 0x5380 | (src & 7);
    WOUT = 0x4C40 | (MODE_d << 3) | (src & 7);
    WOUT = 0x0800 | (q << 12) | r;
    debug(("lbl:\n"));
}
#endif    // fix broken long modulo

"FIX_BROKEN_LONG_MODULO" is one of my switches to enable/disable my patches
(that's another story).
"protect_ireg()" is a macro call that maintains a register save/restore mask.

tony