From: "Oliver Roese" <oroese AT edina DOT xnc DOT com>
Newsgroups: comp.os.msdos.djgpp
Subject: gcc optimizes divisons!
Date: Sat, 18 Sep 1999 12:57:34 +0200
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
NNTP-Posting-Host: pm1-87.xnc.de
Message-ID: <37e37095@news.xenologics.com>
X-Trace: 18 Sep 1999 12:59:33 +0100, pm1-87.xnc.de
Organization: .XNC GmbH
Lines: 69
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

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.
If you declare u as unsigned, you get this:

LC2:
 .long 0xaaaaaaab
 .p2align 2
.globl _Divc

_Divc:
 pushl %ebp
 movl %esp,%ebp
 movl 8(%ebp),%eax
 mull LC2
 movl %ebp,%esp
 popl %ebp
 shrl $1,%edx
 movl %edx,%eax
 ret

We learn from that:
floor(x/3) = floor((0xaaaaaaab*x)/2^33)  if 0<=x<2^32
Trickery is simpler here, but suffers from "mull", which is not as optimized as "imull".
Which case is faster?

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.)

Oliver Roese