GCC Unrolling Simple Loop Generates Rubbish Code?

GCC Unrolling Simple Loop Generates Rubbish Code?

[Lei Ming]

Dear GCC Hackers,

This simple code:

int
main (void)
{
  int s = 0;
  int i;
  for (i = 0; i < 100; i++)
    s += i;
  return 0;
}

After compiled with "-O3 -funroll-all-loops",  will generate this piece of 
assembly code for the loop:

        movl    $99, %eax
.L6:
        subl    $25, %eax        <==
        jns     .L6
        xorl    %eax, %eax
        leave
        ret

I wonder what's the purpose of "subl    $25, %eax"? If the compiler knows that 
the whole loop is useless, since we don't really use the result, why not just 
eliminate this loop and simply return zero? If it choose to execute the loop, 
why it is the number 25 instead of other number? Why not 42? :-)

The logic here seems confusing to me, but I don't know much about GCC's 
optimizing algorithms. Could someone kindly explain it to me?

I'm using GCC 3.2.3:

Reading specs from /usr/lib/gcc-lib/i386-asianux-linux/3.2.3/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man 
--infodir=/usr/share/info --enable-shared --enable-threads=posix 
--disable-checking --with-system-zlib --enable-__cxa_atexit 
--host=i386-asianux-linux
Thread model: posix
gcc version 3.2.3 20030502

I've asked other people to test this with their different GCC version, and all 
their GCC versions generate this kind of  code, with maybe different numbers 
than 25. Even GCC 4, it was said. I don't have GCC 4 currently.

Yesterday I asked this in #gcc on IRC, they suggested that this is a bug. But 
I think I should ask it here before sending a stupid fake bug report :-)

So what will you say?

Best Regards,
Lei Ming

Re: GCC Unrolling Simple Loop Generates Rubbish Code?

[Ian Lance Taylor]

Lei Ming <ming.lei@oracle.com> writes:

> This simple code:
> 
> int
> main (void)
> {
>   int s = 0;
>   int i;
>   for (i = 0; i < 100; i++)
>     s += i;
>   return 0;
> }
> 
> After compiled with "-O3 -funroll-all-loops",  will generate this piece of 
> assembly code for the loop:
> 
>         movl    $99, %eax
> .L6:
>         subl    $25, %eax        <==
>         jns     .L6
>         xorl    %eax, %eax
>         leave
>         ret

I tried compiling with current gcc mainline with -O3
-funroll-all-loops.  I got this:

   0:   55                      push   %ebp
   1:   31 c0                   xor    %eax,%eax
   3:   89 e5                   mov    %esp,%ebp
   5:   83 ec 08                sub    $0x8,%esp
   8:   83 e4 f0                and    $0xfffffff0,%esp
   b:   83 ec 10                sub    $0x10,%esp
   e:   c9                      leave
   f:   c3                      ret

So I think things are better now.

I also see the behaviour you report with gcc 3.2.3.  It does seem
pretty incomprehensible.  Since it seems to be fixed, I haven't
bothered to figure out why it used to behave like that.

Ian

Re: GCC Unrolling Simple Loop Generates Rubbish Code?

[jlh]

[-- Attachment #1: Type: text/plain, Size: 1781 bytes --]


> I wonder what's the purpose of "subl $25, %eax"? If the compiler knows that
> the whole loop is useless, since we don't really use the result, why not just
> eliminate this loop and simply return zero? If it choose to execute the loop,
> why it is the number 25 instead of other number? Why not 42? :-)

GCC hasn't removed empty loops in the past and I think this topic has had long
discussions already.  It's probably not worth starting a new one, on whether
it shall or shall not do it.  But reading Ian's reply, it seems this is now
different on mainline.  Good thing.

GCC is able to do optimization of the style:
    for (i = 0; i < 100; i++) do_something();
to
    for (i = 0; i < 100; i += 2) { do_something(); do_something(); }
to reduce the overhead of the loop.  (There's a name for it, but I don't
remember.)  In this example, it always does 2 loop iterations at a time,
and only needs to 'loop' 50 times.  In your example, it makes 25 steps at
a time and therefore increments the iterator by 25 on each cycle.  42 won't
trivially work in the same way, because it is not a divisor of 100.

> I'm using GCC 3.2.3:

That's an old version.  I suggest you upgrade to 3.4.4 (or to 4.0.x if you
want) unless you have reasons not to do that.  I'm not even sure whether bug
reports for 3.2.x version and below are welcome anyway, given that's pretty old.

This is the output of 3.4.4 on my i686-pc-linux-gnu (-O3 -funroll-all-loops)

main:   pushl   %ebp
        xorl    %eax, %eax
        movl    %esp, %ebp
        subl    $8, %esp
        andl    $-16, %esp
        subl    $16, %esp
        .p2align 4,,7
.L5:    addl    $10, %eax
        cmpl    $99, %eax
        jle     .L5
        leave
        xorl    %eax, %eax
        ret

It takes steps of 10 here.

Cheers,
jlh

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]