This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug tree-optimization/30314] New: optimize multiply-by-constant overflow (wrap) test
- From: "raeburn at raeburn dot org" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 28 Dec 2006 06:46:09 -0000
- Subject: [Bug tree-optimization/30314] New: optimize multiply-by-constant overflow (wrap) test
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
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