Оптимизация
Оптимизация кода с использованием GNU C Compiler
Эта статья описывает технику оптимизации кода для GNU C Compiler.
Компилятор - это программа , которая читает исходный код и транслирует его
в машинные команды . Этот процесс можно разбить на несколько стадий ,
одной из которых является оптимизация результирующего кода.
GNU C Compiler использует большой массив методов оптимизации.
Asm-код для C программы
GCC берет исходный С-код и производит из него бинарный машинный код .
Его также можно заставить сгенерировать читабельный промежуточный asm-код .
Для генерации такого asm-кода создадим файл test1.c и выполним команду :
$ gcc -c -S test1.c
Будет сгенерирован файл test1.s
Код :
6 : #include <stdio.h>
7 :
8 : int main()
9 : {
10 : printf("Hello, World\n");
11 : return 0;
12 :}
13 :
14 : /* end test1.c */
15 : /* ---------------------------------------------------- */
16 : /* generated assembly language file */
17 : .file "test1.c" /* some assembler directives to be */
18 : .version "01.01" /* ignored */
19 : gcc2_compiled.:
20 : .section .rodata /* this segment has read-only data */
21 : .LC0:
22 : .string "Hello, World\n"
23 : .text
24 : .align 4
25 : .globl main
26 : .type main,@function
27 : main: /* main function begins */
28 : pushl $.LC0 /* помещаем параметр для printf() в стек */
29 : call printf /* вызываем функцию */
30 : addl $4,%esp /* очищаем стек */
31 :
32 : xorl %eax,%eax /* обнуляем EAX = 0, functions use register */
33 : jmp .L1 /* EAX to return values */
34 : .p2align 4,,7 /* выравнивание */
35 : .L1:
36 : ret /* return from main, done */
37 : .Lfe1:
38 : /* пропускаем */
39 : .size main,.Lfe1-main
40 : .ident "GCC: (GNU) egcs-2.91.66 (egcs-1.1.2 release)"
41 : /* конец */
42 : /* -------------------------------------------------------- */
Линуксовый компилятор генерит код с AT&T-синтаксисом , который отличается от
Intel/Microsoft Assembler/Turbo Assembler-синтаксиса.
Некоторые директивы мы опустили .
В 20-й строке инициализируется сегмент данных на чтение , в котором хранится строка "Hello,World\n" .
Этой строке была присвоена метка .LC0 .
В 27-й строке начинается код для функции main().
Параметры функции передаются через стек в обратном порядке , т.е. от последнего к первому.
Для printf() таким параметром будет строка "Hello, World\n".
Строка pushl $.LC0 размещает адрес строки "Hello, World\n" в стек.
Префикс "l" в команде pushl говорит о типе "long" для 32-битной строки .
Повторений этого префикса дя других команд будет означать то же самое.
Префикс "$" перед .LC0 означает адрес строки .
Следующий оператор вызывает вызов функции printf() .
После ее выполнения нужно очистить стек , для этого мы к регистру ESP прибавляем 4 ,
т.к. адрес строки был 4-битный.
Стандартный интеловский синтаксис имеет формат инструкций <instruction> dest, src.
А в строке 30 мы видим , что у AT&T все наоборот - <instruction> src, dest.
Первый операнд этой команды идет с префиксом "доллар" , второй - с префиксом "процент".
Это сделано специально для совместимости с BSD-ассемблером.
Следующий оператор XOR обнуляет регистр EAX = 0 . И т.д.
Constant Folding
Ну а теперь приступим собственно к оптимизации.
Термин "Constant folding" - пример простейшей оптимизации .
Предположим в С программе есть выражение x = 45 * 88; .
Неоптимизированный код добросовестно перемножит эти 2 числа .
А оптимизатор обнаружит , что и 45 и 88 - это констаны , и результат константа ,
поэтому он на этапе компиляции заранее вычислит результат и скопирует его в х .
Это и есть constant folding.
В качестве иллюстрации приводим код test2.c :
1 : /* test2.c */
2 : /* Demonstration of constant propagation */
3 : #include <stdio.h>
4 :
5 : int main()
6 : {
7 : int x, y, z;
8 : x = 10;
9 : y = x + 45;
10 : z = y + 4;
11 : printf("The value of z = %d", z);
12 : return 0;
13 : }
14 : /* end of test2.c */
15 :
16 : /* ------------------------------------------- */
17 : /* assembly language file без оптимизации */
18 : .file "test2.c"
19 : .version "01.01"
20 : gcc2_compiled.:
21 : .section .rodata
22 : .LC0:
23 : .string "The value of z = %d"
24 : .text
25 : .align 4
26 : .globl main
27 : .type main,@function
28 : main:
29 : pushl %ebp /* save EBP register on stack */
30 : movl %esp,%ebp /* EBP = ESP */
31 : subl $12,%esp /* Create stack frame. 3 variables x 4 bytes */
32 :
33 : /* x = 10; */
34 : movl $10,-4(%ebp) /* x = 10. x is topmost on the stack */
35 :
36 : /* y = x + 45; */
37 : movl -4(%ebp),%edx /* EDX = x */
38 : addl $45,%edx /* EDX = EDX + 45 */
39 : movl %edx,-8(%ebp) /* y = EDX. y is second from top of stack */
40 :
41 : /* z = y + 4 */
42 : movl -8(%ebp),%edx /* EDX = y */
43 : addl $4,%edx /* EDX = EDX + 4 */
44 : movl %edx,-12(%ebp) /* z = EDX. z is third from top of stack */
45 :
46 : /* printf("The value of z = ", z); */
47 : movl -12(%ebp),%eax /* EAX = z */
48 : pushl %eax /* push EAX(=z) as first parameter of printf */
49 : pushl $.LC0 /* second parameter for printf */
50 : call printf
51 : addl $8,%esp /* clear stack */
52 :
53 : /* return 0; */
54 : xorl %eax,%eax /* for return 0 */
55 : jmp .L1
56 : .p2align 4,,7
57 : .L1:
58 : leave
59 : ret
60 : .Lfe1:
61 : .size main,.Lfe1-main
62 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
63 : /* end of assembly language code */
64 : /* ---------------------------------------------------------------- */
65 :
66 : /* ---------------------------------------------------------------- */
67 : /* оптимизированный asm-код*/
68 :
69 : .file "test2.c"
70 : .version "01.01"
71 : gcc2_compiled.:
72 : .section .rodata
73 : .LC0:
74 : .string "The value of z = %d"
75 : .text
76 : .align 4
77 : .globl main
78 : .type main,@function
79 : main:
80 : pushl %ebp /* Save EBP register on stack */
81 : movl %esp,%ebp /* EBP = ESP */
82 :
83 : /* by constant propagation, z will always be 59 */
84 : /* printf("The value of z = %d", z); */
85 : pushl $59 /* first printf parameter */
86 : pushl $.LC0 /* second printf parameter */
87 : call printf
88 : /* no need of cleanup, we are exiting anyway */
89 : /* return 0; */
90 : xorl %eax,%eax
91 : leave
92 : ret
93 : .Lfe1:
94 : .size main,.Lfe1-main
95 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
96 : /* end of assembly language code */
97 : /* ----------------------------------------------------------------- */
В главной функции определяются 3 локальных переменных , которые размещаются в стеке.
Для доступа к ним будет использована индексная адресация с помощью EBP .
Для этого в него копируется указатель стека ESP . Из ESP мы вычитаем 12 = 3*4 байт,
отчего размер стека увеличивается на 12 байт.
Диаграмма стека :
EBP-----> ---------------
| x | 4 Bytes
---------------
| y | 4 Bytes
---------------
| z | 4 Bytes
ESP-----> ---------------
| |
| |
^ | |
| ...
Адресация растет | | |
снизу вверх | 0 ---------------
Теперь рассмотрим операцию x = 10;.
Оно реализовано в 34-й строке выражением movl $10, -4(%ebp).
Индексная адресация записана в форме <offset>(<base register>).
10 копируется в стек по адресу (EBP - 4) т.е. по адресу x .
По аналогии, -8(%ebp) используется для доступа к y и -12(%ebp) для доступа к z.
Линии 37, 38 и 39 вычисляют x + 45 и присваивают y. Для этого используетс EDX .
Аналогично для z = y + 4 is similar.
В 47 параметры для printf() передаются в стек.
Последний параметр (z) ложится в стек первым . В 51 строке стек очищается .
Как видно из вычислений , результат для y всегда равен 55 , а для z = 59 .
Оптимизатор в состоянии это определить .
Для разрешения оптимизации нужно использовать опцию -O2 :
gcc -c -S -O2 test2.c
Оптимизированный код показан в строках с 69 по 95. В этом куске отсутствуют переменные x,y,x .
Бывает , что одно и тоже выражение с одним и тем же результатом вычисляется несколько раз .
Компилятор оптимизирует такие случаи с помощью common subexpression elimination .
Рассмотрим следующий пример :
1 : /* test3.c */
2 : /* common subexpression elimination, and also of constant propagation */
3 : #include <stdio.h>
4 :
5 : int main()
6 : {
7 : int a, b;
8 : int x, y, z;
9 : scanf("%d %d", &a, &b);
10 : x = a * b;
11 :
12 : if(b >= 4)
13 : {
14 : y = a * b;
15 : z = 0;
16 : }
17 : else
18 : {
19 : z = a * b * 4;
20 : y = 0;
21 : }
22 :
23 : printf("x = %d, y = %d, z = %d\n", x, y, z);
24 : return 0;
25 : }
26 : /* end of test3.c */
27 :
28 : /* ----------------------------------------------------------------- */
29 : /* generated unoptimized assembly language code */
30 : .file "test3.c"
31 : .version "01.01"
32 : gcc2_compiled.:
33 : .section .rodata
34 : .LC0:
35 : .string "%d %d"
36 : .LC1:
37 : .string "x = %d, y = %d, z = %d\n"
38 : .text
39 : .align 4
40 : .globl main
41 : .type main,@function
42 : main:
43 : pushl %ebp /* save EBP */
44 : movl %esp,%ebp /* EBP = ESP */
45 : subl $20,%esp /* Create space for 5 variables */
46 :
47 : /* scanf("%d %d". &a, &b); */
48 : leal -8(%ebp),%eax
49 : pushl %eax /* push address of b on stack */
50 : leal -4(%ebp),%eax
51 : pushl %eax /* push address of a on stack */
52 : pushl $.LC0 /* push address of string */
53 : call scanf
54 : addl $12,%esp /* stack cleanup after scanf */
55 :
56 : /* x = a * b; */
57 : movl -4(%ebp),%eax /* EAX = a */
58 : imull -8(%ebp),%eax /* EAX = EAX * b = a * b */
59 : movl %eax,-12(%ebp) /* x = EAX = a * b */
60 :
61 : /* if( b >= 4)... */
62 : cmpl $3,-8(%ebp) /* compare b with 3 */
63 : jle .L2 /* else part at label .L2, if follows */
64 :
65 : /* y = a * b; */
66 : movl -4(%ebp),%eax /* EAX = a */
67 : imull -8(%ebp),%eax /* EAX = EAX * b = a * b */
68 : movl %eax,-16(%ebp) /* y = EAX = a * b */
69 : /* z = 0; */
70 : movl $0,-20(%ebp)
71 : jmp .L3 /* jump over the else part */
72 :
73 : .p2align 4,,7
74 : .L2:
75 : /* else part begins here */
76 :
77 : /* z = a * b * 4; */
78 : movl -4(%ebp),%eax /* EAX = a */
79 : imull -8(%ebp),%eax /* EAX = EAX * b = a * b */
80 : leal 0(,%eax,4),%edx /* EDX = EAX*4 + 0 */
81 : movl %edx,-20(%ebp) /* z = EDX */
82 : /* y = 0; */
83 : movl $0,-16(%ebp)
84 : .L3:
85 : /* if..else is over here */
86 :
87 : /* printf("x = %d, y = %d, z = %d\n", x, y, x); */
88 : movl -20(%ebp),%eax
89 : pushl %eax /* push address of z on stack */
90 : movl -16(%ebp),%eax
91 : pushl %eax /* push address of y on stack */
92 : movl -12(%ebp),%eax
93 : pushl %eax /* push address of x on stack */
94 : pushl $.LC1 /* address of string */
95 : call printf
96 : addl $16,%esp /* stack cleanup after printf */
97 :
98 : /* return 0 */
99 : xorl %eax,%eax
100 : jmp .L1
101 : .p2align 4,,7
102 : .L1:
103 : leave
104 : ret
105 : .Lfe1:
106 : .size main,.Lfe1-main
107 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
108 : /* end of unoptimized assembly language code */
109 : /* --------------------------------------------------------------- */
110 :
111 : /* --------------------------------------------------------------- */
112 : /* generated optimized assembly language code */
113 : .file "test3.c"
114 : .version "01.01"
115 : gcc2_compiled.:
116 : .section .rodata
117 : .LC0:
118 : .string "%d %d"
119 : .LC1:
120 : .string "x = %d, y = %d, z = %d\n"
121 : .text
122 : .align 4
123 : .globl main
124 : .type main,@function
125 : main:
126 : pushl %ebp /* save EBP */
127 : movl %esp,%ebp /* EBP = ESP */
128 : subl $8,%esp /* space for just 2 variables on stack */
129 :
130 : /* scanf("%d %d", &a, &b); */
131 : leal -4(%ebp),%eax
132 : pushl %eax /* push address of b on stack */
133 : leal -8(%ebp),%eax
134 : pushl %eax /* push address of a on stack */
135 : pushl $.LC0 /* address of string */
136 : call scanf
137 :
138 : /* x = a * b; */
139 : movl -4(%ebp),%eax /* EAX = b */
140 : movl %eax,%edx /* EDX = EAX = b */
141 : imull -8(%ebp),%edx /* EDX = EDX * a = b * a = a * b */
142 :
143 : addl $12,%esp /* delayed stack cleanup */
144 : /* if( b >= 4).... */
145 : cmpl $3,%eax /* compare EAX = b with 3 */
146 : jle .L17 /* else part from label .L17 */
147 :
148 : /* y stored in ECX, z in EAX, x in EDX */
149 : /* y = a * b; */
150 : movl %edx,%ecx
151 : /* z = 0; */
152 : xorl %eax,%eax
153 : jmp .L18 /* jump over the else part */
154 : .p2align 4,,7
155 : .L17:
156 : /* z = a * b * 4; */
157 : leal 0(,%edx,4),%eax /* LEA EAX, [EDX*4]+0 */
158 : /* y = 0; */
159 : xorl %ecx,%ecx
160 : .L18:
161 : pushl %eax /* push value of z */
162 : pushl %ecx /* push value of y */
163 : pushl %edx /* push value of x */
164 : pushl $.LC1 /* push address of string */
165 : call printf
166 : /* stack cleanup after printf not necessary */
167 :
168 : /* return 0; */
169 : xorl %eax,%eax
170 : leave
171 : ret
172 : .Lfe1:
173 : .size main,.Lfe1-main
174 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
175 : /* end optimized assembly code */
176 : /* -------------------------------------------------------------- */
В данном примере одно и то же вычисление a * b делается несколько раз .
Код с 30 по 108 неоптимизирован и легко читаем .
Оптимизированный код представлен с 113 по 176 строки .
В стеке хранятся 2 переменные - a и b , поскольку их нельзя положить в регистр .
Для других переменных компилятор выбирает регистры : x в EDX, y в ECX и z в EAX.
Результат a * b хранится в EDX используется комбинация movl, imull :
movl %edx, %eax /* EAX = EDX = a * b */
imull $4, %eax /* EAX = EAX * 4 */
Также используется сдвиг (sall) вместо imull
Также для оптимизации используется
leal 0(,%edx,4), %eax
Последняя инструкция использует фичи 80386-го процессора : регистр EDX выполняет роль индексного регистра,
4 - масштаб и 0 - смешение,здесь вычисляется эфеективный адрес и хранится в EAX-регистре .
Регистр EAX получает значение EDX(=a*b)*4 + 0 , т.е. a * b * 4.
Инструкция leal выполняется за 2 цикла , в то время как сдвиг - за 7 циклов .
Удаление неиспользуемого кода
Это такой код в программе , который никогда не выполняется .
Например , если условие if никогда не выполняется , компилятор просто удалит этот код .
Cледующий пример это демонстрирует :
1 : /* test4.c */
2 : /* demonstration of dead code elimination */
3 : #include <stdio.h>
4 :
5 : int main()
6 : {
7 : int x;
8 :
9 : scanf("%d", &x);
10 :
11 : if(x < 0 && x > 0)
12 : {
13 : x = 99;
14 : printf("Hello. Inside the if!!!");
15 : }
16 :
17 : return 0;
18 : }
19 : /* end of test4.c */
20 :
21 : /* --------------------------------------------------------------- */
22 : /* optimized assembly code */
23 : .file "test4.c"
24 : .version "01.01"
25 : gcc2_compiled.:
26 : .section .rodata
27 : .LC0:
28 : .string "%d"
29 : .LC1:
30 : .string "Hello. Inside the if!!!"
31 : .text
32 : .align 4
33 : .globl main
34 : .type main,@function
35 : main:
36 : pushl %ebp /* save EBP on stack */
37 : movl %esp,%ebp /* EBP = ESP */
38 : subl $4,%esp /* create space for x on the stack */
39 :
40 : /* scanf("%d", &x); */
41 : leal -4(%ebp),%eax
42 : pushl %eax /* push address of a on stack */
43 : pushl $.LC0 /* push string on stack */
44 : call scanf
45 :
46 : /* the entire body of the if and the condition checking is dead code */
47 : /* return 0; */
48 : xorl %eax,%eax /* no stack cleanup, we are exiting anyway */
49 : leave
50 : ret
51 : .Lfe1:
52 : .size main,.Lfe1-main
53 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
54 : /* end optimized assembly code */
55 : /* ---------------------------------------------------------------- */
В коде условие в строке 11 есть x < 0 && x > 0,которое абсурдно .
Компилятор не будет его генерировать .
Strength Reduction using Induction Variable
Если например в цикле многократно выполняется вычисление x2 ,
имеет смысл вызову экспоненциальной функции предпочесть простое умножение x на x .
Такие переменные называются induction variable.
Пример :
1 : /* test5.c */
2 : /* demonstration of induction variable elimination */
3 : int main()
4 : {
5 : int i, j;
6 :
7 : for(i = 0; i < 10; i++)
8 : {
9 : j = i * 7;
10 : printf("i = %d, j = %d", i, j);
11 : }
12 : return 0;
13 : }
14 : /* end test5.c */
15 :
16 : /* --------------------------------------------------------------- */
17 : /* optimized assembly language code */
18 : .file "test5.c"
19 : .version "01.01"
20 : gcc2_compiled.:
21 : .section .rodata
22 : .LC0:
23 : .string "i = %d, j = %d"
24 : .text
25 : .align 4
26 : .globl main
27 : .type main,@function
28 : main:
29 : pushl %ebp /* save EBP on stack */
30 : movl %esp,%ebp /* ESP = EBP */
31 :
32 : pushl %esi /* ESI will hold 'j' */
33 : pushl %ebx /* EBX will hold 'i' */
34 : xorl %ebx,%ebx /* both are initialized to zero */
35 : xorl %esi,%esi
36 : .p2align 4,,7
37 : .L5:
38 : /* printf("i = %d, j = %d", i, j); */
39 : pushl %esi /* push value of j */
40 : pushl %ebx /* push value of i */
41 : pushl $.LC0 /* push address of string */
42 : call printf
43 : addl $12,%esp /* stack cleanup */
44 :
45 : /* instead of saying j = i * 7, its efficient to say j = j + 7 */
46 : addl $7,%esi
47 : incl %ebx /* i++ */
48 : cmpl $9,%ebx /* is i <= 9, then repeat the loop */
49 : jle .L5
50 :
51 : /* return 0; */
52 : xorl %eax,%eax
53 : leal -8(%ebp),%esp
54 : popl %ebx
55 : popl %esi
56 : leave
57 : ret
58 : .Lfe1:
59 : .size main,.Lfe1-main
60 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
61 :
62 : /* end optimized assembly code */
63 : /* ----------------------------------------------------------------- */
Здесь i счетчик цикла , j - induction variable .
В оптимизированном asm-коде используются регистры для хранения i и j в EBX в ESI.
В 34-й строке EBX(=i) обнуляется,в 35-й аналогично ESI = 0 .
Цикл начинается в 37 и продолжается до 49.
Переменная в цикле изменяется на 1 . Вместо умножения i на 7 , к j прибавляется 7
|
|
LINUX