From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-205803-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 21052 invoked by alias); 28 Dec 2006 06:46:20 -0000
Received: (qmail 20850 invoked by uid 48); 28 Dec 2006 06:46:09 -0000
Date: Thu, 28 Dec 2006 06:46:00 -0000
Subject: [Bug tree-optimization/30314]  New: optimize multiply-by-constant overflow (wrap) test
X-Bugzilla-Reason: CC
Message-ID: <bug-30314-11337@http.gcc.gnu.org/bugzilla/>
Reply-To: gcc-bugzilla@gcc.gnu.org
To: gcc-bugs@gcc.gnu.org
From: "raeburn at raeburn dot org" <gcc-bugzilla@gcc.gnu.org>
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
X-SW-Source: 2006-12/txt/msg01988.txt.bz2

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:

allocate:
        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
        ret
.L6:
        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.


-- 
           Summary: optimize multiply-by-constant overflow (wrap) test
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: raeburn at raeburn dot org
 GCC build triplet: powerpc-apple-darwin
  GCC host triplet: powerpc-apple-darwin
GCC target triplet: i386-unknown-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30314