From: eplmst AT lu DOT erisoft DOT se (Martin Stromberg)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: gcc optimizes divisons!
Date: 23 Sep 1999 10:15:41 GMT
Organization: Ericsson Erisoft AB, Sweden
Lines: 53
Message-ID: <7scukd$rm6$1@antares.lu.erisoft.se>
References: <37e37095 AT news DOT xenologics DOT com>
NNTP-Posting-Host: propus-144.lu.erisoft.se
X-Newsreader: TIN [version 1.2 PL2]
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Oliver Roese (oroese AT edina DOT xnc DOT com) wrote:
: Yesterday i found out by accident, that gcc knows how to divide by constants.
: This is a optimization technique, mentioned by several experts (http://www.agner.org/ or
: http://www.azillionmonkeys.com/qed/index .html). If you know about this, i am sure you are
: interested to hear, that gcc 2.95 can do that for you.
: Example:
: #include <stdio.h>
: int Divc (int u)
: { return u / 3;}    // u%3 would work
: too.

: int main(void)
: {
:  int u = (int)&u;
:  printf ("%d",Div3(u));
:  return 0;
: }

: compile: gcc -S <filename>
: I have seen that gcc sometimes inlines short functions, but it doesent do that here, even with -O6.
: Anyway here is the result:
: ...
: .globl _Divc
: _Divc:
:  pushl %ebp
:  movl %esp,%ebp
:  movl $1431655766,%edx
:  movl 8(%ebp),%ecx
:  movl %ecx,%eax
:  imull %edx
:  sarl $31,%ecx
:  movl %ebp,%esp
:  popl %ebp
:  subl %ecx,%edx
:  movl %edx,%eax
:  ret
: ...
: I dont tried to decipher it.

[Klippa, klapp, kluppit unsigned version.]

: The documents mentioned above are rather sketchy. They dont explain the signed case either. If
: someone could shed some light on this, this would be great! (or point to some internetstuff.)

Well... Obviously(?) x/3 == 1431655766*x + (x<0?1:0) (mod 2^32)
Or perhaps (mod 2^32) should be (mod 2^31)...

It's very probably mathematically provable using rings and fields and such.


Sallinen, Chamber Music I,

							MartinS