User account creation filtered due to spam.

Bug 30314 - optimize multiply-by-constant overflow (wrap) test
Summary: optimize multiply-by-constant overflow (wrap) test
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: unknown
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
Depends on:
Reported: 2006-12-28 06:46 UTC by Ken Raeburn
Modified: 2006-12-28 09:44 UTC (History)
1 user (show)

See Also:
Target: i386-unknown-linux
Build: powerpc-apple-darwin
Known to work:
Known to fail:
Last reconfirmed:


Note You need to log in before you can comment on or make changes to this bug.
Description Ken Raeburn 2006-12-28 06:46:08 UTC
I was experimenting with some code to test for overflow (wrapping) in unsigned multiplication in C.  My test code:

typedef unsigned long size_t;
extern void *malloc(size_t), abort(void);
void *allocate(size_t num) {
    const size_t size = 140;
    size_t total = num * size;

    if (total / size != num) abort();
    /* call malloc, whatever */
    return 0;

With snapshot gcc-4.3-20061223, hosted on ppc Mac, targeted for i386-linux, options "-O9 -fomit-frame-pointer -fexpensive-optimizations -S", the generated assembly code is:

        subl    $12, %esp
        movl    16(%esp), %ecx
        leal    (%ecx,%ecx,4), %eax
        leal    0(,%eax,8), %edx
        subl    %eax, %edx
        andl    $1073741823, %edx
        movl    $981706811, %eax
        mull    %edx
        shrl    $3, %edx
        cmpl    %ecx, %edx
        jne     .L6
        xorl    %eax, %eax
        addl    $12, %esp
        call    abort

In this assembly code, the division has been implemented via multiplication, and the result is compared against the original value.

Dividing 2**32-1 by 140 gives 30678337 and a fraction.  If the supplied NUM is larger than that, it can't be equal to the quotient of any 32-bit number divided by 140.  If it's 30678337 or less, the multiplication can't wrap, and thus the quotient must be equal to the original value.

Since the quotient, as such, isn't of any other use in this code, I think it would be more efficient, and give the same result, to test NUM<=30678337, and omit the division altogether.  (And since the malloc call in the comment isn't actually made in this example, the product stored in TOTAL isn't needed either, if we don't do the division.)

I think on x86 we could also test the carry flag after the multiply operation.