[Bug driver/13677] New: Generates Sub-Optimal Code in 'for' Loops

["theman at josephdwagner dot info" <gcc-bugzilla at gcc dot gnu dot org>]

Here's the code in C: 
 
-------------------------------------------------------------------------- 
 
for(u_int32_t index = 1; 
    index <= frag_log.total_frag_files; 
    index++) 
{ 
    if(dir_entry->inode == *(frag_log.inode_id + index)) 
    { 
        *(frag_log.parent_inode_id + index) = dir_inode_id; 
    } 
} 
 
return 0; 
 
-------------------------------------------------------------------------- 
 
Now here's the same code in Assembly after going through GNU GCC 3.3.2: 
 
-------------------------------------------------------------------------- 
 
        mov     DWORD PTR [%ebp-8], 1      ; part 1 of 'for' loop 
                                           ; only executed once 
 
.L90: 
        mov     %eax, DWORD PTR [%ebp-8]   ; part 2 of 'for' loop 
        cmp     %eax, DWORD PTR frag_log   ; tests condition in 'for' loop 
        jbe     .L93                       ; if true, does loop 
        jmp     .L91                       ; if not, does not do loop 
 
.L93:                                      ; the loop that it does 
        mov     %ebx, DWORD PTR [%ebp+16] 
        mov     %eax, DWORD PTR [%ebp-8] 
        lea     %ecx, [0+%eax*4] 
        mov     %edx, DWORD PTR frag_log+8 
        mov     %eax, DWORD PTR [%ebx] 
        cmp     %eax, DWORD PTR [%edx+%ecx] 
        jne     .L92 
        mov     %eax, DWORD PTR [%ebp-8] 
        lea     %ecx, [0+%eax*4] 
        mov     %edx, DWORD PTR frag_log+24 
        mov     %eax, DWORD PTR [%ebp+8] 
        mov     DWORD PTR [%edx+%ecx], %eax 
.L92: 
        lea     %eax, [%ebp-8]             ; part 3 of 'for' loop 
        inc     DWORD PTR [%eax]           ; increments counter 
        jmp     .L90                       ; goes to test condition 
.L91: 
        mov     %eax, 0 
        add     %esp, 4 
        pop     %ebx 
        pop     %ebp 
        ret 
 
-------------------------------------------------------------------------- 
 
Take a look at the L90 section and the 2 jump instructions (jbe, jmp).  Why 
are there two?  The first instruction says, "Skip the next step" resulting in 
performing the loop.  The second says, "Skip the loop."  Seems kind of 
redundant, doesn't it? 
 
A better way would have been: 
 
-------------------------------------------------------------------------- 
 
.L90: 
        mov     %eax, DWORD PTR [%ebp-8]   ; part 2 of 'for' loop 
        cmp     %eax, DWORD PTR frag_log   ; tests condition in 'for' loop 
        ja      .L91                       ; if false, does not do loop 
 
-------------------------------------------------------------------------- 
 
Now take a look at the L92 section.  Why is it there?  By placing it before 
the L90 section, the jump instruction at the end can be dumped.  So here's the 
whole thing, with my modifications. 
 
-------------------------------------------------------------------------- 
 
        mov     DWORD PTR [%ebp-8], 1      ; part 1 of 'for' loop 
                                           ; only executed once 
        jmp     .L90                       ; <= I added this line 
 
.L92: 
        lea     %eax, [%ebp-8]             ; part 3 of 'for' loop 
        inc     DWORD PTR [%eax]           ; increments counter 
 
.L90: 
        mov     %eax, DWORD PTR [%ebp-8]   ; part 2 of 'for' loop 
        cmp     %eax, DWORD PTR frag_log   ; tests condition in 'for' loop 
        ja      .L91                       ; if false, does not do loop 
 
.L93:                                      ; the loop that it does 
        mov     %ebx, DWORD PTR [%ebp+16] 
        mov     %eax, DWORD PTR [%ebp-8] 
        lea     %ecx, [0+%eax*4] 
        mov     %edx, DWORD PTR frag_log+8 
        mov     %eax, DWORD PTR [%ebx] 
        cmp     %eax, DWORD PTR [%edx+%ecx] 
        jne     .L92 
        mov     %eax, DWORD PTR [%ebp-8] 
        lea     %ecx, [0+%eax*4] 
        mov     %edx, DWORD PTR frag_log+24 
        mov     %eax, DWORD PTR [%ebp+8] 
        mov     DWORD PTR [%edx+%ecx], %eax 
        jmp     .L92                       ; <= I added this line 
.L91: 
        mov     %eax, 0 
        add     %esp, 4 
        pop     %ebx 
        pop     %ebp 
        ret 
 
-------------------------------------------------------------------------- 
 
You may have noticed that I added two jump instructions and ask, "What's the 
point?  You're back up to the same number of jumps!" 
 
Remember, the first jump instruction I added is only executed once before the 
loop begins, which is better than each time through the loop.  The second jump 
instruction I added is only executed if the 'if' condition is true and the 
'if' code executes.  While the second jump instruction IF EXECUTED would make 
the optimization as bad as originally generated by GNU GCC, the second jump 
instruction I added isn't always executed, and being executed some of the time 
is better than being executed all of the time. 
 
I may have only saved 2 instructions, but it's still 2 instructions.  Multiply 
it out by several dozen or several hundred 'for' loops and you've got real 
savings. 
 
To make a long story short, GNU GCC is generating sub-optimal code. 
 
Joseph D. Wagner

-- 
           Summary: Generates Sub-Optimal Code in 'for' Loops
           Product: gcc
           Version: 3.3.2
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: driver
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: theman at josephdwagner dot info
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13677