Strange multiplication behavior in Guile Scheme interpreter
stackoverflow.com
stackoverflow.com
Fixed by Mark H Weaver, on Fri, 7 Dec 2012.
Avoid signed integer overflow in scm_product
* libguile/numbers.c (scm_product): Avoid signed integer overflow, which modern C compilers are allowed to assume will never happen, thus allowing them to optimize out our overflow checks.
* test-suite/tests/numbers.test (*): Add tests.
(2^244 is being shown as zero. 2^488 is being shown as non-zero; presumably the right value though I haven't actually checked. If 2^244 is actually being computed as zero, then unless what's happening somehow depends on the depth of the stack -- surely not possible if this bug is the cause -- 2^488 should be computed as zero squared, which is zero.)
What am I missing here?
Although the specification says this behaviour is undefined in practice I used to map the undefined portion to being whatever my hardware did, not whatever the compiler felt like this week.
This ruins the C as a portable assembler use case and means if I was doing this sort of work I'd probably write these sort of routines in assembler rather than trying to fight with versions of C compiler.
> (* 4294967296 4294967296)
$1 = 0
My guess is that guile uses the native int type to store small numbers, and then switches to a bignums, backed by GNU MP when the native ints are too small. Maybe in that particular case, the check fails, and the computation overflows the native int.
Modern CPUs have wide multiplies (32x32->64), wide divides (64/32->32), a whole bunch of useful arithmetic status flags, yet C gives you access to nothing of that. Instead, it forces you to divide first (very slow) before multiplying to ensure that overflow won't happen.
Even a simple division check before multiplying isn't sufficient, since there's a border case where the two operands are INT_MIN and -1. In 2nd complement arithmetic, both division and multiplication will overflow. So you need yet another check.
But gcc folks are also obtuse: an implementation is allowed to define what is technically UB. Optimizing out operations that are perfectly defined on a 2nd-complement architecture seems to be against the "spirit" of C -- that you can guess the compiler's output with reasonable certainty. I'd call this outright maliciousness on the part of compiler implementors.
People dislike C++ saying too much is happening behind the curtains. But examples like this show that C is not much better either.
uint64_t foo(uint64_t x, uint64_t y) { return (uint64_t) x * (uint64_t) y; }
Big, ugly, as expected: 3 multiplies and 2 adds. Now compile this:
uint64_t foo(uint32_t x, uint32_t y) { return (uint64_t) x * (uint64_t) y; }
One instruction (mull). GCC totally knows about 32x32 -> 64 multiplies; you just don't know how to use them.
You're right, C11 doesn't have a 128-bit integer type; that should be remedied. Fortunately all major compilers (GCC, LLVM, VC++, and ICC) provide one.
Carry: "if (x + y < x)" compiles to code that uses the carry flag.
Overflow: "if ((int32_t) (x + y) < 0)" compiles to code that uses the overflow flag.
And the best part is, code written like this is portable to architectures such as TileGX that don't have status flags.
If x and y are signed, you're relying on UB, which the compiler might optimize out.
> "if ((int32_t) (x + y) < 0)" compiles to code that uses the overflow flag.
Again, which type are x and y? If signed, this code is UB. If unsigned, then the result of conversion to int32 may not fit into int32, in which case the result is implementation-defined, or and implementation-defined signal is raised.
Portable? Right.