1. Введение
Как мы знаем, компилятор -- это программа, которая читает исходный код на языке высокого уровня и переводит его (обычно) в машинный язык. Это сложный процесс, включающий в себя несколько стадий. Если компилятор является оптимизирующим компилятором, то одна из этих стадий "оптимизирует" код на машинном языке так, чтобы его исполнение занимало меньше времени, или он занимал меньше памяти, или и то и другое (иногда). Конечно, какую бы оптимизацию не делал компилятор, она не должны влиять на логику программы, т.е. оптимизация должна сохранять смысл (семантику) выполняемой программы. Вы можете спросить, какие же оптимизации делает компилятор, чтобы произвести эффективный машинный код? Так как не существует случаев, в которых можно менять логику компилируемой программы, компилятор должен очень тщательно изучить программу и найти возможности для оптимизации. Как можно догадаться, такой подробный анализ программы, нахождение и осуществление возможных оптимизаций -- это сложный и длительный процесс, детали которого выходят за рамки данной статьи.
В данной статье я собираюсь описать несколько типов оптимизации кода, которые использует компилятор GNU C, чтобы вы могли понять, как оптимизируется код и оценить сложность процесса оптимизации. Компилятор GNU C -- это изощренный оптимизирующий C-компилятор, использующий многие приемы оптимизации для того, чтобы создать более эффективный код. Описать их все невозможно, поэтому я выбрал лишь несколько таких подходов, которые показались мне наиболее интересными и легкими для понимания. Полный список способов оптимизации, применяемых в GNU C доступен по адресу http://www.redhat.com/products/support/gnupro/gnupro_gcc.html. Вместо того, чтобы просто объяснять то, что делает конкретный прием оптимизации, я буду описывать их, используя ассемблерный код, которые генерует компилятор GNU C. Кроме того, этот метод позволит читателям проводить дальнейшие исследование оптимизации, производимой компилятором, а также изучить 'продвинутую' технику оптимизации, в случае, если она их заинтересуют.
2. Ассемблерный код программы на C
Компилятор GNU C (далее просто GCC) читает исходный код C-программы и превращает его в объектный код, т.е. машинный код в двоичном виде. В тоже время, вместо объектного кода он может выдавать исходный код прогрммы на языке ассемблера, так что мы может посмотреть его и понять, как наша программа выглядит на языке ассемблера. Мы будем создавать файлы на языке ассемблера для того, чтобы посмотреть какую оптимизацию сделал компилятор, так что будет полезно посмотреть, как выглядит ассемблерный код простой C-программы. Хотя, нужно заметить, что нам не нужно понимать каждое ассемблерное выражение в сгенерированном коде, поэтому для простоты выражения, не критичные с точки зрения понимания оптимизации кода, объясняться не будут. Чтобы сгенерировать ассемблерный код, создайте файл test1.c как показано ниже и введите следующую команду:
$ gcc -c -S test1.c
Это создаст файл test1.s, который содержит листинг сгенерированного для C-программы кода на языке ассемблера. Файл test1.c вместе с ассемблерным кодом приведен ниже.
1 : /* test1.c */ 2 : /* Этот первый файл просто демонстрирует то, как выглядит ассемблерная программа 3 : созданная компилятором и некоторые особенности ассемблера GNU, 4 : который следует несколько иным соглашениям, чем MASM/TASM. 5 : */ 6 : #include7 : 8 : int main() 9 : { 10 : printf("Hello, World\n"); 11 : return 0; 12 : } 13 : 14 : /* end test1.c */ 15 : /* ----------------------------------------------------------------- */ 16 : /* сгенерированный ассемблерный файл */ 17 : .file "test1.c" /* Некоторые директивы ассемблера */ 18 : .version "01.01" /* которые можно проигнорировать */ 19 : gcc2_compiled.: 20 : .section .rodata /* Этот сегмент содержит данные только для чтения */ 21 : .LC0: 22 : .string "Hello, World\n" 23 : .text 24 : .align 4 25 : .globl main 26 : .type main,@function 27 : main: /* начало функции main */ 28 : pushl $.LC0 /* заталкивает параметр для printf() в стек */ 29 : call printf /* вызываем функцию */ 30 : addl $4,%esp /* очищаем стек */ 31 : 32 : xorl %eax,%eax /* установим EAX = 0, функции используют регистр */ 33 : jmp .L1 /* EAX чтобы возвращать значения */ 34 : .p2align 4,,7 /* это директива выравнивания */ 35 : .L1: 36 : ret /*возврат из main, готово */ 37 : .Lfe1: 38 : /* Другие ассемблерные директивы, которые можно проигнорировать */ 39 : .size main,.Lfe1-main 40 : .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)" 41 : /* конец сгенерированного ассемблерного файла */ 42 : /* ---------------------------------------------------------------- */
В случае, если вы знакомы с архитектурой 80386 или более новых микропроцессоров Intel и имеете опыт программирования на ассемблере, вы обнаружите, что ассемблерный листинг понятен вам только частично. Этот ассемблер следует синтаксису ассемблера AT&T который отличается от синтаксиса ассемблера Intel/Microsoft Assembler/Turbo Assembler, с которым знакомы большинство из нас. Давайте пройдемся по ассемблерному коду. Мы будем игнорировать директивы ассемблера, так как они не критичны для понимания. В строке 20 был определен сегмент данных только для чтения, содержащий строку "Hello, World\n". Строке была присвоена метка .LCO. На строке 27, начинается код функции main(). Как мы знаем, в C параметры, передаваемые функциям, помещаются в стек, причем в обратном порядке, т.е. последний параметр "заталкивается" в стек первым. В нашем случае, функция printf() вызывается с единственным параметром, строкой "Hello, World\n". Выражение pushl $.LC0 помещает в стек адрес строки "Hello, World\n". l в pushl означает "длинный", так как мы имеем дело с 32 битными переменными. Во всех ассемблерным программах, которые вы увидите, команды будут дополнены "l", чтобы показать то, что они работают с 32 битными переменными. "$" перед .LCO означает адрес строки. Следующее выражение вызывает функцию printf. После printf() функция завершает выполнение, мы должны очистить стек, поэтому нужно добавить 4 к ESP. (Почему 4? Потому что перед вызовом printf мы поместили в стек 4 байта.) Чтобы сделать это, мы обычно пишем, ADD ESP, 4. Согласно синтаксису Intel:
3. Сворачивание констант
Сворачивание констант [constant folding] -- это самая простая для понимания оптимизация. Предположим, что вы пишете в программе на C выражение вида x = 45*88;. Не-оптимизирующий компилятор сгенерирует код для умножения 45*88 и сохранит значение в x. Оптимизирующий компилятор обнаружит, что 45 и 88 являются константами, так что их произведение также будет константой. Следовательно он вычислит 45*88=3960 и сгенерирует код, который просто копирует в x значение 3960. Это называется Сворачиванием констант, и означает, что вычисления производятся лишь один раз, на этапе компиляции, а не при каждом запуске программы. Чтобы проиллюстрировать, создайте файл test2.c как показано ниже. Сгенерируйте для этой программы ассемблерный код, как было указано ранее. Т.к. по умолчанию GCC не оптимизирует программу, вы увидете, что ассемблерный код представляет собой прямолинейное преобразование C программы в машинный код (Строки с 18 по 62).
1 : /* test2.c */ 2 : /* Демонстрация сворачивания констант */ 3 : #include4 : 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 : /* ассемблерный файл без оптимизации */ 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 /* сохраним в стеке регистр EBP */ 30 : movl %esp,%ebp /* EBP = ESP */ 31 : subl $12,%esp /* Создадим стековый фрейм для 3 переменных по 4 байта */ 32 : 33 : /* x = 10; */ 34 : movl $10,-4(%ebp) /* x = 10. x на вершине стека */ 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 вторая от вершины стека */ 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 третья от вершины стека */ 45 : 46 : /* printf("The value of z = ", z); */ 47 : movl -12(%ebp),%eax /* EAX = z */ 48 : pushl %eax /* push EAX(=z) как первый параметр printf */ 49 : pushl $.LC0 /* второй параметр для printf */ 50 : call printf 51 : addl $8,%esp /* очистить стек */ 52 : 53 : /* return 0; */ 54 : xorl %eax,%eax /* чтобы вернуть 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 : /* конец ассемблерного кода */ 64 : /* ---------------------------------------------------------------- */ 65 : 66 : /* ---------------------------------------------------------------- */ 67 : /* сгенерированный код на языке ассемблера, после оптимизации */ 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 /* Сохраним в стеке регистр EBP */ 81 : movl %esp,%ebp /* EBP = ESP */ 82 : 83 : /* благодаря "распространению" констант [constant propagation], z всегда будет равен 59 */ 84 : /* printf("The value of z = %d", z); */ 85 : pushl $59 /* первый параметр printf */ 86 : pushl $.LC0 /* второй параметр printf */ 87 : call printf 88 : /* нет необходимости в очистке стека, мы все равно выходим */ 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 : /* конец кода на языке ассемблера */ 97 : /* ----------------------------------------------------------------- */
В ассемблерном коде есть несколько моментов, которые нам нужно понять. Во первых, main() определяет 3 локальных переменных, память под которые выделяется в стеке. Также, чтобы получить доступ к этим переменным, мы будем использовать индексный режим адресации [indexed addressing mode] с помощью регистра базы EBP. Поэтому первое выражение сохраняет текущее значение EBP в стеке. После этого указатель стека ESP копируется в EBP (заметьте, что "источник" ESP стоит первым), так что EBP может использоваться для доступа к локальным переменным. В завершение нам необходимо создать пространство для трех четырехбайтовых переменных в стеке, поэтому мы вычитаем из ESP 12, т.е., мы наращиваем стек на 12 байт. x будет самым нижним элементом стека по смещению -4 байта от EBP. Посмотрите на диаграмму приведенную ниже.
EBP-----> ---------------
| x | 4 Байта
---------------
| y | 4 Байта
---------------
| z | 4 Байта
ESP-----> ---------------
| |
| |
^ | |
| ...
Адрес увеличивается| | |
когда мы идем | 0 ---------------
вверх
Аналогично, смещение y относительно EBP = -8, а смещение z = -12. Теперь обдумайте операцию присвоения x = 10;. Реализующее его выражение находится в 34 строке: movl $10, -4(%ebp). Индексный режим адресации записывается как <смещение>(<базовый регистр>). Поэтому приведенное выше выражение скопирует константу 10, по адресу (EBP - 4), т.е. по адресу x в стеке. В аналогичной манере, -8(%ebp) используется для доступа к y и -12(%ebp) используется для доступа к z. Строки 37,38 и 39 выполняют действие x+45 и присваивают результат y. Чтобы сделать это, значение x сначала копируется в регистр EDX, 45 добавляется к нему и результат, находящийся в EDX, копируется в y. Код для z=y+4 аналогичен приведенному. В строке 47, параметры для printf() помещаются в стек. Последний параметр (z) помещается в стек первым и после этого в стек помещается адрес строки. В строке 51, мы очищаем стек, путем добавления значения 8 к ESP. Я думаю, что так как мы "затолкали" в стек два 4-х байтовых параметра, мы должны прибавить к ESP 8. В первом примере, мы поместили только один аргумент, и, поэтому, должны были прибавить к ESP только 4. Остальной код понять легко.
Теперь, если мы взглянем на приведенную выше программу, когда мы выполняем x+45, значение x всегда будет равно 10 из за присваивания x=10. Поэтому x+45 всегда будет равно 55. Итак, выражение всегда присваивает y значение 55. Аналогично, когда выполняется операция y + 4, результат всегда будет равен 59. Если включить оптимизацию, то компилятор будет способен это обнаружить. Чтобы активировать оптимизацию, используйте ключ -O2. Введите следующую команду:
gcc -c -S -O2 test2.c
Ассемблерный код, сгенерированный с оптимизацией, показан в строках с 69 по 95. Заметьте, что на строке 85 компилятор просто помещает в стек константу 59, а затем (после неё) адрес переменной, и вызывает printf(). Поэтому, при помощи сворачивания констант, различные выражения в программе вычисляются компилятором только 1 раз и итоговое значение вставляется в создаваемый код. Еще одна интересная вещь: после сворачивания констант нет необходимости в переменных x, y и z. Поэтому для них не выделяется место в стеке, что уменьшает требования программы к памяти. Это показывает, как выполнение одной оптимизации влечет за собой другую. В приведенном выше случае сворачивание констант приводит к уменьшению времени исполнения (так как все вычисления производятся на этапе компиляции), одновременно уменьшая требования программы к памяти.
4. Устранение повторяющихся подвыражений
Часто бывает так, что одно и то же выражение вычисляется в разных местах программы, а значение операндов выражения не изменяются в промежутке между выполнением двух участков кода. Например, программа может вычислять, скажем a*b в начале и в конце. Если значения a и b не изменяются между этими двумя вычислениями a*b , то, вместо вычисления a * b в конце, мы можем сохранить результат полученный при первом вычислении a * b во временной переменной и использовать в последствии. Это позволит исключить лишние вычисления в программе. Такая оптимизация называется устранение повторяющихся подвыражений. Рассмотрим следующую программу, демонстрирующую этот прием.
1 : /* test3.c */ 2 : /* устранение повторяющихся подвыражений и сворачивание констант */ 3 : #include4 : 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 : /* конец test3.c */ 27 : 28 : /* ----------------------------------------------------------------- */ 29 : /* неоптимизированный ассемблерный код */ 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 /* сохраним EBP */ 44 : movl %esp,%ebp /* EBP = ESP */ 45 : subl $20,%esp /* Создадим место для 5 переменных */ 46 : 47 : /* scanf("%d %d". &a, &b); */ 48 : leal -8(%ebp),%eax 49 : pushl %eax /* помещаем в стек адрес b */ 50 : leal -4(%ebp),%eax 51 : pushl %eax /* помещаем в стек адрес a */ 52 : pushl $.LC0 /* помещаем в стек адрес строки */ 53 : call scanf 54 : addl $12,%esp /* очистка стека после 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) /* сравним b и 3 */ 63 : jle .L2 /* блок else по метке .L2, сначала блок if */ 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 /* перескочим через блок else */ 72 : 73 : .p2align 4,,7 74 : .L2: 75 : /* блок else начинается здесь */ 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 заканчивается здесь */ 86 : 87 : /* printf("x = %d, y = %d, z = %d\n", x, y, x); */ 88 : movl -20(%ebp),%eax 89 : pushl %eax /* адрес z в стеке */ 90 : movl -16(%ebp),%eax 91 : pushl %eax /* адрес y в стеке */ 92 : movl -12(%ebp),%eax 93 : pushl %eax /* адрес x в стеке */ 94 : pushl $.LC1 /* address of string */ 95 : call printf 96 : addl $16,%esp /* очистка стека после printf */ 97 : 98 : /* возвращаем 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 : /* конец неоптимизированного ассемблерного кода */ 109 : /* --------------------------------------------------------------- */ 110 : 111 : /* --------------------------------------------------------------- */ 112 : /* оптимизированный ассемблерный код */ 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 /* сохраним EBP */ 127 : movl %esp,%ebp /* EBP = ESP */ 128 : subl $8,%esp /* место в стеке только для 2-х переменных */ 129 : 130 : /* scanf("%d %d", &a, &b); */ 131 : leal -4(%ebp),%eax 132 : pushl %eax /* помещаем в стек адрес b */ 133 : leal -8(%ebp),%eax 134 : pushl %eax /* помещаем в стек адрес a */ 135 : pushl $.LC0 /* адрес строки */ 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 /* отложенная очистка стека */ 144 : /* if( b >= 4).... */ 145 : cmpl $3,%eax /* сравним EAX = b с 3 */ 146 : jle .L17 /* блок else начинается с метки .L17 */ 147 : 148 : /* y сохранено в ECX, z в EAX, x в EDX */ 149 : /* y = a * b; */ 150 : movl %edx,%ecx 151 : /* z = 0; */ 152 : xorl %eax,%eax 153 : jmp .L18 /* перепрыгнем через блок else */ 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 /* значение z в стеке*/ 162 : pushl %ecx /* значение y в стеке */ 163 : pushl %edx /* значение x в стеке*/ 164 : pushl $.LC1 /* помещаем в стек адрес строки */ 165 : call printf 166 : /* очистка стека после printf необязательна */ 167 : 168 : /* возвращаем 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 : /* конец оптимизированного ассемблерного кода */ 176 : /* -------------------------------------------------------------- */
Эта программа содержит пример повторяющегося подвыражения. На строке 10, выражение a * b выполняется в первый раз,а затем еще два раза в строках 14 и 19. Последние два вычисления a * b излишни, так как значения a или b не изменялись после первого исполнения. Эти два вычисления -- 'повторяющиеся подвыражения', которые могут быть удалены. Строки листинга с 30 по 108 показывают не-оптимизированный ассемблерный код, который является прямым переводом кода на C и легко читается. Теперь взгляните на оптимизированный ассемблерный код в строках с 113 по 176. Первое, что нужно заметить -- теперь в стеке сохраняются только переменные a и b, следовательно, вместо 20 байтов стека в неотимизированной версии требуется только 8. Вы можете удивиться, что такого особенного в переменных a и b. Их уникальность состоит в том, что адреса переменных a и b используются в программе (для scanf()), а переменные, которые находятся в регистрах, не могут иметь адрес в памяти. Следовательно компилятор не может поместить их в регистры. Регистры которые компилятор выбрал для других переменных: x в EDX, y в ECX и z в EAX. Выражения на строках с 139 по 141 исполняют операцию a * b и сохраняют значение в EDX, который содержит x. Также, значение b доступно в регистре EAX. Нужно также отметить отложенную очистку стека после вызова scanf на строке 143. Возможно это дает какие-то преимущества, я не знаю точно.
Дальше начинается блок if. В блоке if выражение a * b выполняется еще раз и мы ожидаем, что компилятор будет использовать значение сохраненное в EDX. Это именно то, что он делает. Для выражения y = a*b, сгенерированный код на строке 150 просто копирует значение a*b из регистра EDX, в регистр ECX (который содержит y). В блоке else, опять встречается под-выражение в выражении z = a * b * 4. Поэтому мы ожидаем, что компилятор возмет значение a * b из EDX, умножит его на 4 и затем сохранит результат в EAX (который содержит z). Есть несколько возможностей сделать это. Одна из них -- использовать последовательность movl, imull, следующим образом
movl %edx, %eax /* EAX = EDX = a * b */ imull $4, %eax /* EAX = EAX * 4 */
Другой вариант -- использовать в вышеприведенной последовательности инструкций сдвига (sall) вместо imull (сдвиг на один двоичный разряд вслево - shift left или shl - эквивалентно умножению на два, но выполняется быстрее. -- Прим. редактора). Но, оказывается, GCC использует для оптимизации кода не совсем понятный прием. Он использует инструкцию
leal 0(,%edx,4), %eax
Эта инструкция использует возможности масштабирования и индексации адресов, имеющиеся у процессоров семейства 80386. Вышеприведенная инструкция использует регистр EDX в качестве индексного, 4 в качестве масштаба и 0 как смещение, расчитывает 'эффективный адрес' и сохраняет результат вычислений в регистре EAX. В результате регистр EAX получает значение EDX(=a*b)*4+0 т.е. a * b * 4. Инструкция leal (load effective address -- Прим. редактора) выполняется на 80386 всего за два такта, в то время, как простейший сдвиг займет около 7 тактов. Мы видим, что компилятор знает о особенностях процессора и использует их при генерации кода.
Итак можно видеть, что устранение 'повторяющихся подвыражений' сберегает много процессорного времени и памяти, требуемых для кода, осуществляющего излишние вычисления. На этой стадии можно понять, что компилятор, когда он анализирует программу с целью оптимизации, должен следить за тем, как и когда переменные изменяются, как и какие регистры используются в выражениях и как регистрый распределены для хранения переменных. В общем случае, анализ подобный тому, что компилятор осуществляет в отношении программы, называют анализом потока данных.
5. Устранение "мертвого" кода.
"Мертвый" код -- это такой код программы, который не будет выполнен никогда, ни при каких входных данных или условиях. Наиболее типичный пример - выражение if. Если компилятор обнаруживает, что условия, указанные в операторе if никогда не будут истинными, то тело оператора if никогда не будет выполняться. В этом случае компилятор может полностью удалить такой 'мертвый' код, тем самым уменьшая место, занимаемое программой в памяти. Следующий пример демонстрирует устранение 'мертвого' кода.
1 : /* test4.c */ 2 : /* Демонстрация устранение мертвого кода */ 3 : #include4 : 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 : /* конец test4.c */ 20 : 21 : /* --------------------------------------------------------------- */ 22 : /* Оптимизированный ассемблерный код */ 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 /* сохраним EBP в стеке */ 37 : movl %esp,%ebp /* EBP = ESP */ 38 : subl $4,%esp /* создадим пространство для x в стеке */ 39 : 40 : /* scanf("%d", &x); */ 41 : leal -4(%ebp),%eax 42 : pushl %eax /* поместим адрес a в стек */ 43 : pushl $.LC0 /* поместим строку в стек */ 44 : call scanf 45 : 46 : /* всё тело if и условие, это мертвый код */ 47 : /* return 0; */ 48 : xorl %eax,%eax /* нет очистки стека, мы все равно выходим*/ 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 : /* конец оптимизированного ассемблерного кода */ 55 : /* ---------------------------------------------------------------- */
Так как неоптимизированный ассемблерный код ничего не делает и легок в понимании, то я опустил его. Условие в строке 11 (x < 0 && x > 0) никогда не может быть правдой. Компилятор обнаруживает это и делает вывод, что тело оператора if формирует 'мертвый' код, поэтому не создает для него ничего. Обратите внимание, что после того, как тело if было "уничтожено", строка "Hello. Inside the if!!!" больше не нужна и поэтому может быть убрана из секции данных только для чтения. Выявление подобных возможностей, однако, может усложнить компилятор и поэтому не используется.
6. Снижение стоимости выполнения с использованием индуцированной переменной
Один из типов оптимизации кода -- это снижение стоимости выполнения [strength reduction], в котором "дорогая" операция заменяется на более дешевую (Хороший пример был приведен выше, когда умножение на степень 2 заменялось сдвигом или даже адресным вычислением! -- Прим. редактора). Например, выполнение возведения в квадрат x^2 более эффективно производить путем умножения x на x, вместо того, чтобы вызывать функцию вычисления экспоненты. Одно из возможных применений такой оптимизации -- циклы. Часто в цикле какая-либо переменная изменяется синхронно с управляющей переменной цикла. Такая переменная называется индуцированной переменной [Induced Variable]. Индукция переменной дает компилятору шанс применить снижение стоимости выполнения, что можно видеть в следующей программе.
1 : /* test5.c */
2 : /* демонстрация уничтожения индукции переменной */
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 : /* оптимизированный ассемблерный код */
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 /* сохраним EBP в стеке */
30 : movl %esp,%ebp /* ESP = EBP */
31 :
32 : pushl %esi /* ESI будет содержать 'j' */
33 : pushl %ebx /* EBX будет содержать 'i' */
34 : xorl %ebx,%ebx /* обе сбрасываются в 0 */
35 : xorl %esi,%esi
36 : .p2align 4,,7
37 : .L5:
38 : /* printf("i = %d, j = %d", i, j); */
39 : pushl %esi /* поместим в стек значение j */
40 : pushl %ebx /* поместим в стек значение i */
41 : pushl $.LC0 /* поместим в стек адрес строки */
42 : call printf
43 : addl $12,%esp /* очистка стека */
44 :
45 : /* вместо использования j = i * 7, эффективней будет использовать j = j + 7 */
46 : addl $7,%esi
47 : incl %ebx /* i++ */
48 : cmpl $9,%ebx /* проверяем i <= 9, если нет повторяем цикл */
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 : /* конец оптимизированного ассемблерного кода */
63 : /* ----------------------------------------------------------------- */
Здесь i -- управляющая переменная цикла, тогда как j -- индуцированная переменная, так как j изменяется в жесткой взаимосвязи с i. В сгенерированном ассемблерном коде компилятор использует регистры для хранения как i, так и j: i в EBX, а j в ESI. Строка 34 сбрасывает EBX(=i) в ноль, как указано в начальных условиях оператора цикла. Компилятор видит, что во время первого прохода, j будет присвоено значение 0, поэтому в строке 35 он также сбрасывает в 0 регистр ESI. Цикл начинается в строке 37 и продолжается до строки 49. Т.к. значение j уже присвоено, то первое, что нужно сделать компилятору внутри цикла -- вызвать функциюprintf(). Здесь компилятор изменил порядок следования выражений так, чтобы стало возможным использовать снижение стоимости выполнения инструкций. После анализа программы компилятор видит, что внутри цикла, значение i всегда будет увеличиваться на 1 и т.к. j -- переменная, 'индуцированная' переменной i, ее значение всегда будет увеличиваться на 7. В связи с этим вместо умножения i на 7 (что 'дорого' в циклах процессора), перед тем, как приступить к следующей итерации GCC добавляет 7 к старому значению j. Таким образом дорогая операция умножения была заменена сложением, что дешевле (в терминах времени выполнения).
7. Заключение
В этой статье, мы познакомились с некоторыми простейшими приемами, используемыми компилятором GNU C для оптимизации создаваемого им кода. На основании знания этих приемов и информации, необходимой для их применения, читатель может оценить то, сколь сложный и изощренный анализ программы должен быть проведен компилятором. Компилятор должен следить за различными аспектами выполнения программы: переменными, местом их хранения (в памяти или в регистрах), вычислением выражений, константными выражениями, 'мертвым' кодом и так далее. Из за сложности этого процесса, компиляция программы с включенной оптимизацией занимает значительно больше времени. Есть еще множество деталей, касающихся оптимизации и генерации кода, которые я не стал объяснять и которые я не знаю. Оптимизация кода предоставляет широкое поле исследований и заинтересованные читатели могут обратиться к [1] за дополнительной информацией.
8. Благодарности
Я хочу поблагодарить руководителя моего проекта в Bachelor, доктора Uday Khedker за то, что он пробудил во мне интерес к компиляторам и оптимизации кода. Также я хочу сказать спасибо Linux Gazette, Linux Documentation Project, PC Quest и Pune Linux User's Group (http://www.pluggies.org/) которые ранее приняли и опубликовали мои статьи, что воодушевило меня на то, чтобы писать еще.
9. Ссылки
- Compilers: Principles, Techniques, and Tools, A.V.Aho, Ravi Sethi and J.D.Ullman, Addison Wesley.
- Systems Programming and Operating Systems, D.M.Dhamdhere, Tata McGraw-Hill.
- Assembly HOWTO, Franois-Ren Rideau, Linux Documentation Project.
- Advanced 80386 Programming Techniques, James L. Turley, Osborne McGraw-Hill.