Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Оптимизация

Оптимизация кода с использованием GNU C Compiler

By Rahul U Joshi

Эта статья описывает технику оптимизации кода для 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
Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье