public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/30314] New: optimize multiply-by-constant overflow (wrap) test
@ 2006-12-28 6:46 raeburn at raeburn dot org
0 siblings, 0 replies; only message in thread
From: raeburn at raeburn dot org @ 2006-12-28 6:46 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2006-12-28 6:46 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-12-28 6:46 [Bug tree-optimization/30314] New: optimize multiply-by-constant overflow (wrap) test raeburn at raeburn dot org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).