spec: specify behavior of x := int8(-128); x /= -1

[rsc]

Same for other int sizes (with corresponding most negative value).

Right now panics sometimes, not others.
Should at least be consistent.

Should it just be -128?  Or panic?

Assigned to gri for discussion & spec change.

---------- Forwarded message ----------
From: Chris Mihelich <umbricola@gmail.com>
Date: Thu, Apr 28, 2011 at 12:23
Subject: [go-nuts] Signed integer division overflow
To: golang-nuts@googlegroups.com

Hi Go implementors,

I thank you that the language spec makes some effort to specify the behavior of
overflowing signed integer arithmetic, a pleasing contrast to C's unhelpful stance on
that subject.

But the spec neglects to say what happens when you overflow an m-bit signed integer
representation by dividing -2^(m-1) by -1 in that type.

With x86-64 gc tools (compiled from source earlier this week) on my Intel Mac (OS X
10.5.8), I find that dividing intm(-2^(m-1)) by intm(-1) panics for m = 16, 32, and 64
with the somewhat misleading error string "integer divide by zero". 
Strangely, for m = 8, there is no panic and the result is int8(-128); i.e., the
infinite-width result is reduced modulo 2^8.  The underlying causes seem to be as
follows.

For m >= 16 the division uses the x86 idiv instruction for that integer width.  If
that instruction cannot represent its result in m bits, either because of overflow or
because the divisor is zero, the CPU raises the #DE (divide error) exception.  That
translates into SIGFPE with si_code = FPE_INTDIV.  In principle we should get si_code =
FPE_INTDIV if the divisor was zero but si_code = FPE_INTOVF if the divisor was nonzero
and the division overflowed, but in practice we can't count on the kernel to try that
hard, apparently.

For m = 8 the division is compiled differently: the arguments are sign-extended to 32
bits by movsx, then divided by a 32-bit idiv, and finally the low 8 bits are written out
as the result.  Because int32(-128)/int32(-1) gives int32(128) with no overflow, this
sequence produces the overwrapped value int8(128) without faulting.

The remainder extraction intm(-2^(m-1)) % intm(-1) also panics for m = 16, 32, 64 (and
not for m = 8) even though its result, namely 0, is representable.  That's because it
does an idiv on the way to finding the remainder, and the idiv blows up.

Is there any reason why Go shouldn't specify that overflowing divisions overwrap without
panicking, like other overflowing signed integer arithmetic operations?  It doesn't
cost much running time relative to the fairly high cost of an integer division to guard
the idiv instructions when we can't prove statically that the divisor isn't -1.

I would also suggest that on x86 platforms, the runtime FPE handler should do the work
the kernel is neglecting to do to differentiate between division by 0 and division by -1
with overflow and return a sensible error message for each.  The FPE handler knows the
integer register values and instruction pointer at the fault, so it could read the
faulting instruction to figure out which register contains the dividend and then check
whether the saved value of that register has -1 in the relevant subrange of its bits. 
I could write you this code if you like.

Chris

[griesemer]

Comment 1:

The result should be -128 in this case and no overflow should occur (TBD in the spec).
The spec should be clarified, but there appears to be a bug in the gc compiler tool
chain. The result is as expected (and without panic) for x/-1, but not for x /= -1
(analogous for % operation):
package main
func main() {
    // / operations
    {   var x int8 = -1<<(8-1)
        println(x, x/-1)
    }
    {   var x int16 = -1<<(16-1)
        println(x, x/-1)
    }
    {   var x int32 = -1<<(32-1)
        println(x, x/-1)
    }
    {   var x int64 = -1<<(64-1)
        println(x, x/-1)
    }
    println()
    {   var x int8 = -1<<(8-1)
        y := x/-1
        println(x, y)
    }
    {   var x int16 = -1<<(16-1)
        y := x/-1
        println(x, y)
    }
    {   var x int32 = -1<<(32-1)
        y := x/-1
        println(x, y)
    }
    {   var x int64 = -1<<(64-1)
        y := x/-1
        println(x, y)
    }
    println()
    {   var x int8 = -1<<(8-1)
        x /= -1
        println(x)
    }
    // The following panic with 6g.
    {   var x int16 = -1<<(16-1)
        x /= -1
        println(x)
    }
    {   var x int32 = -1<<(32-1)
        x /= -1
        println(x)
    }
    {   var x int64 = -1<<(64-1)
        x /= -1
        println(x)
    }
    println()
}

[rsc]

Comment 2:

Yes, the gc tool chain is most definitely inconsistent about this.
How's gccgo?

[griesemer]

Comment 3:

package main
func main() {
    // / operations
    {   var x int8 = -1<<(8-1)
        println(x, x/-1)
    }
    {   var x int16 = -1<<(16-1)
        println(x, x/-1)
    }
    {   var x int32 = -1<<(32-1)
        println(x, x/-1)
    }
    {   var x int64 = -1<<(64-1)
        println(x, x/-1)
    }
    println()
    {   var x int8 = -1<<(8-1)
        y := x/-1
        println(x, y)
    }
    {   var x int16 = -1<<(16-1)
        y := x/-1
        println(x, y)
    }
    {   var x int32 = -1<<(32-1)
        y := x/-1
        println(x, y)
    }
    {   var x int64 = -1<<(64-1)
        y := x/-1
        println(x, y)
    }
    println()
    {   var x int8 = -1<<(8-1)
        x /= -1
        println(x)
    }
    {   var x int16 = -1<<(16-1)
        x /= -1
        println(x)
    }
    {   var x int32 = -1<<(32-1)
        x /= -1
        println(x)
    }
    {   var x int64 = -1<<(64-1)
        x /= -1
        println(x)
    }
    println()

    // % operations
    {   var x int8 = -1<<(8-1)
        println(x, x%-1)
    }
    {   var x int16 = -1<<(16-1)
        println(x, x%-1)
    }
    {   var x int32 = -1<<(32-1)
        println(x, x%-1)
    }
    {   var x int64 = -1<<(64-1)
        println(x, x%-1)
    }
    println()
    {   var x int8 = -1<<(8-1)
        y := x%-1
        println(x, y)
    }
    {   var x int16 = -1<<(16-1)
        y := x%-1
        println(x, y)
    }
    {   var x int32 = -1<<(32-1)
        y := x%-1
        println(x, y)
    }
    {   var x int64 = -1<<(64-1)
        y := x%-1
        println(x, y)
    }
    println()
    {   var x int8 = -1<<(8-1)
        x %= -1
        println(x)
    }
    {   var x int16 = -1<<(16-1)
        x %= -1
        println(x)
    }
    {   var x int32 = -1<<(32-1)
        x %= -1
        println(x)
    }
    {   var x int64 = -1<<(64-1)
        x %= -1
        println(x)
    }
    println()
}
-128 -128
-32768 -32768
-2147483648 -2147483648
-9223372036854775808 -9223372036854775808
-128 -128
-32768 -32768
-2147483648 -2147483648
-9223372036854775808 -9223372036854775808
-128
-32768
-2147483648
-9223372036854775808
gri@r45:~/go2/tmp$ gccgo test11.go 
gri@r45:~/go2/tmp$ a.out
-128 -128
-32768 -32768
-2147483648 -2147483648
-9223372036854775808 -9223372036854775808
-128 -128
-32768 -32768
-2147483648 -2147483648
-9223372036854775808 -9223372036854775808
-128
-32768
-2147483648
-9223372036854775808
-128 0
-32768 0
-2147483648 0
-9223372036854775808 0
-128 0
-32768 0
-2147483648 0
-9223372036854775808 0

[griesemer]

Comment 4:

gccgo produces the expected results (-1<<(n-1) for n = 8, 16, 32, 64) and 0 for %.

[ianlancetaylor]

Comment 5:

Note that current gccgo will panic if you change the constant -1 values to use a
variable set to -1 instead.

[griesemer]

Comment 6:

This issue was closed by revision bb7eb4002e54720e829cc9e2344252741411ccd.

Status changed to Fixed.