CODEWITHSUNDEEP
cperformanceoptimizationgcc
auselen
auselen

Reputation: 28087

Explanation of gcc optimization

Out of hacker curiosity, I wonder how gcc can manage to optimize the function below this smartly?

int c() {
        int i, j = 0;
        for (i = 0; i < 10; i++) {
                j += i;
        }
        return j;
}

$objdump -D c.o below is for arm but x86 is no different in logic.

00000000 <c>:
   0:   202d        movs    r0, #45 ; 0x2d
   2:   4770        bx  lr

I mostly wonder if this is result of a chain of optimizations or something like a template match? Are there any documentation on such optimizations?

Upvotes: 9

Views: 1031

Answers (1)

amdn
amdn

Reputation: 11582

The optimizer does this in phases/passes... when you specify -O2 there are many optimizations that are enabled. The principal optimizations that come into play here are

  1. loop unrolling
  2. constant propagation
  3. constant folding
  4. dead-code elimination

http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

so this code

int i, j = 0;
for (i = 0; i < 10; i++) {
    j += i;
}
return j;

after loop unrolling becomes

int i, j = 0;
i=0; j += i;
i=1; j += i;
i=2; j += i;
i=3; j += i;
i=4; j += i;
i=5; j += i;
i=6; j += i;
i=7; j += i;
i=8; j += i;
i=9; j += i;
return j;

after constant propagation pass

int i, j = 0;
i=0; j += 0;
i=1; j += 1;
i=2; j += 2;
i=3; j += 3;
i=4; j += 4;
i=5; j += 5;
i=6; j += 6;
i=7; j += 7;
i=8; j += 8;
i=9; j += 9;
return j;

after dead-code elimination

j = 0;
j += 0;
j += 1;
j += 2;
j += 3;
j += 4;
j += 5;
j += 6;
j += 7;
j += 8;
j += 9;
return j;

after constant folding

j = 45;
return j;

and finally,

return 45;

Upvotes: 12

Related Questions