Loop optimizer misses simple optimisation?

[Michael Meissner <meissner at cygnus dot com>]

Kamil Iskra writes:
| 
| Hi,
| 
| In a debate on comp.sys.amiga.programmer, a debate that I would sum up as
| "Does GCC really optimize so well as some people claim?" I came across a
| relatively simple source where GCC indeed does perform rather poorly:

It depends on the machine.  I believe that GCC doesn't do as good of a
job with udivmod operations where it produces two outputs, as on
machines where it has a more normal division instruction (with
possibly a remainder instruction).

| #define N (1UL<<22)
| #define eN N
| 
| unsigned char a[N + 1];
| 
| main ()
| {
|   unsigned int i;
| 
|   for (i = 2; i <= (1UL << 11); i++)
|       if (a[i])
|       {
| 	  unsigned int j;
| 	  for (j = 2; j <= eN / i; j++)
| 	      a[i * j] = 0;
|       }
| }

For example, the powerpc-eabi-gcc compiler generates:

	.file	"foo.c"

 # rs6000/powerpc options: -msdata=data -G 8
 # GNU C version egcs-2.91.24 19980418 (gcc2 ss-980401 experimental) (powerpc-eabi) compiled by GNU C version egcs-2.90.27 980315 (egcs-1.0.2 release).
 # options passed:  -O2 -fverbose-asm
 # options enabled:  -fdefer-pop -fomit-frame-pointer -fcse-follow-jumps
 # -fcse-skip-blocks -fexpensive-optimizations -fthread-jumps
 # -fstrength-reduce -fpeephole -fforce-mem -ffunction-cse -finline
 # -fkeep-static-consts -fcaller-saves -fpcc-struct-return
 # -frerun-cse-after-loop -frerun-loop-opt -fschedule-insns
 # -fschedule-insns2 -fsched-interblock -fsched-spec -fsjlj-exceptions
 # -fcommon -fverbose-asm -fgnu-linker -fregmove -fargument-alias -mpowerpc
 # -mnew-mnemonics -meabi -mcall-sysv -msdata=data

gcc2_compiled.:
	.section ".text"
	.align 2
	.globl main
	.type	 main,@function
main:
	stwu 1,-8(1)
	mflr 0
	stw 0,12(1)
	bl __eabi
	addis 9,0,a@ha
	addi 9,9,a@l
	li 8,2
	lis 3,0x40
	li 5,0
	add 6,9,8
	mr 4,3
	li 7,4
.L5:
	lbz 0,0(6)
	addi 6,6,1
	cmpwi 0,0,0
	bc 12,2,.L4
	divwu 0,3,8
	li 10,2
	cmplw 0,10,0
	bc 12,1,.L4
	divwu 0,4,8
	add 11,7,9
.L10:
	addi 10,10,1
	cmplw 0,10,0
	stb 5,0(11)
	add 11,11,8
	bc 4,1,.L10
.L4:
	addi 8,8,1
	cmplwi 0,8,2048
	addi 7,7,2
	bc 4,1,.L5
	lwz 0,12(1)
	mtlr 0
	addi 1,1,8
	blr
.Lfe1:
	.size	 main,.Lfe1-main
	.comm	a,4194305,1
	.ident	"GCC: (GNU) egcs-2.91.24 19980418 (gcc2 ss-980401 experimental)"

-- 
Michael Meissner, Cygnus Solutions (Massachusetts office)
4th floor, 955 Massachusetts Avenue, Cambridge, MA 02139, USA
meissner@cygnus.com,	617-354-5416 (office),	617-354-7161 (fax)