Блог → Компилятор GCC: искусство оптимизации кода. Часть 1

Что скрывается за командами -01, -02, -03, и все ли возможности оптимизации компилятора GCC охватываются этими командами? Какой метод оптимизации следует выбрать? Может ли попытка большей оптимизации кода привести к получению худшего с точки зрения производительности или размеров кода по сравнению с менее оптимизированным? Когда и почему оптимизацию следует отключать и как проверить, что именно делает компилятор в том или ином случае? На эти вопросы я попытаюсь ответить в этой статье. Замечу, что статья рассчитана на подготовленного читателя - требуется умение программировать на С, так как все примеры программ приводятся на этом языке, а также знания ассемблера для анализа результатов работы компилятора.

В отличие от многих других, в том числе и коммерческих, компиляторов, компилятор GCC предоставляет весьма тонкие средства оптимизации программ, позволяющие выбирать наиболее подходящие методы оптимизации для разных фрагментов программы и даже для отдельных функций. В компиляторе GCC определены опции для включения, отключения и указания параметров практически каждого поддерживаемого метода оптимизации. Команды -0x можно рассматривать как "тяжёлую артиллерию" оптимизации, так как эти команды управляют целыми блоками более тонких опций. Далее мы рассмотрим, как различные опции и директивы компилятора GCC влияют на результирующий код, а также затронем вопрос об ограничениях, присущих подсистеме оптимизации текущих версий GCC (исследовались версии GCC 2.96 и 3.04 на платформе IA32 - Linux).

Основные методы оптимизации

Методы автоматической оптимизации можно разделить на следующие классы:
• Оптимизация, удаляющая "лишний" код. К этому классу следует отнести методы оптимизации, удаляющие недоступный код, удаление повторяющихся подвыражений (common sub-expression elimination, CSE). Сюда же относятся такие методы, как вычисление выражений, содержащих константы, на этапе компиляции (constant folding) и, иногда, встраивание функций.
• Оптимизация, улучшающая машинный код на локальном уровне. К этому классу относятся методы оптимизации, уменьшающие число машинных команд, заменяющие короткие последовательности команд более эффективными командами и выполняющие перестановку инструкций с целью уменьшения времени ожидания (peephole optimization).
• Оптимизация работы с памятью. Методы этой группы повышают эффективность кэширования, и организуют упреждающую предвыборку. К этому же классу следует отнести методы выравнивания (alignment) адресов меток и переменных.
• Оптимизация ветвлений и циклов. В этот класс входят методы, удаляющие избыточные условия ветвлений и оптимизирующие операции перехода. К оптимизации циклов относятся методы, разворачивающие циклы, оптимизирующие счетчики и т.п.
• Оптимизация вызова функций. Включает управление формированием стекового фрейма, передачу аргументов в регистрах, оптимизацию кода возврата из функции и встраивание функций (function inlining).
• Интеллектуальная оптимизация. Включает такие методы, как перестановка блоков (block reordering) и исключение концевой рекурсии.

Следует отметить, что все перечисленные методы оптимизации применяются комплексно и выделенные классы часто перекрываются. Все указанные выше типы оптимизации реализованы в компиляторе GCC. Прежде чем перейти к подробному рассмотрению методов оптимизации, следует дать определение важному понятию базового блока. Базовым блоком называется последовательность смежных инструкций, в которые поток управления входит в их начале и покидает в конце, без останова программы или возможности ветвления. Иными словами, базовый блок представляет собой непрерывную (в памяти) последовательность инструкций, которая всегда выполняется в одном и том же порядке. Операции ветвления и выхода из процедуры или программы, могут быть лишь заключительными операциями базового блока.

По отношению к базовым блокам все методы оптимизации можно разделить на три группы:
1. Методы оптимизации, применяющиеся сразу к нескольким базовым блокам, например, глобальное удаление повторяющихся подвыражений.
2. Методы оптимизации, применяющиеся к отдельным блокам. К этой категории относится большинство применяемых методов оптимизации.
3. Методы оптимизации, применяющиеся к отдельным фрагментам внутри базового блока. Сюда следует отнести локальные методы оптимизации.

Пример неоптимизированного кода

Напишем простую программу на языке С (назовём файл test.c):

#include
int main() {
int i;
for(i=0; i<10; i++) (
if (!(i << 31)) printf("Чёт
");
else printf("Нечёт
");
)
return 0;
)


Скомпилируем её командой: gcc -с test.c -S. Опция -S чрезвычайно полезна в нашем исследовании работы компилятора GCC, так как она позволяет просматривать сгенерированный код в виде ассемблерного листинга. После компиляции с ключом -S в текущем каталоге появится файл test.s, содержащий нечто вроде прототипа ассемблерной программы, эквивалентной программе test.c. Обычный ассемблерный листинг не содержит дополнительных данных о работе компилятора, однако использование опции -fverbose-asm позволяет получить дополнительную информацию об опциях, используемых в процессе компиляции. В частности, с её помощью можно получить полный список задействованных параметров оптимизации. Ниже приводится основной фрагмент файла test.s. Для облегчения понимания в
текст добавлены комментарии.

.section .rodata
# Раздел данных
.LC0:
.string "Чёт
"
.LC1:
.string "Нечёт
"
.text
.align 16
.globl main
.type main, @function

main:
# Точка входа функции int main ()
pushl %ebp
movl Ssesp, %ebp
subl $8, %esp
nop
movw $0, -4(%ebp)
.p2align 4,,7

.L3:
# Блок проверки условия выхода из цикла
cmpw $9, -2(%ebp)
jle .L6
jmp ,L4
.p2align 4,,7

.L6:
# Проверка "чёт/нечёт"
movswl -4(%ebp),%eax
sail $31, %eax
testl %eax, %eax
jne

.L7
# Вызов функции printf("Чёт
")
subl $12, %esp
pushl $.LC0
call printf
addl $16, %esp
jmp .L5
.p2align 4,,7

.L7:
# Вызов функции printf ("Нечёт
")
subl $12, %esp
pushl $.LC1
call printf
addl $16, %esp

.L5:
# Увеличение счетчика и переход
# в блок проверки выхода из цикла
leal -2(%ebp), %еах
incw (%еах)
jmp .L3
.p2align 4,,7

.L4:
# Выход из процедуры int main()
movl $0, %еах
movl %ebp, %esp
popl %ebp
ret


Если вы привыкли к синтаксису трансляторов Microsoft и Borland, синтаксис приведённого выше листинга может показаться вам непонятным. Дело в том, что ассемблер GNU следует синтаксису AT&T, являющемуся стандартом в мире Unix. Отличия синтаксиса Intel от синтаксиса AT&T подробно описаны в литературе, так что подробно на них я останавливаться не буду. Перечислю лишь основные из них:
• Порядок перечисления операндов в формате AT&T противоположен порядку, принятому Microsoft.
• Имена регистров процессора получают префикс "%".
• Мнемоники команд с 32-битными операндами получают суффикс "I" (например 32-битная команда movsw имеет мнемонику movswl).
• Круглые скобки вокруг имени регистра означают, что регистр используется как указатель на ячейку памяти. Числа перед скобками, указывают положительное или отрицательное смещение в байтах относительно адреса, хранящегося в регистре (например -2(%ebp)).

Впрочем, GCC можно заставить генерировать ассемблерные листинги и в формате Intel. Для этого в командной строке следует указать опцию -masm=intel (эта опция доступна начиная с версии GCC 3.0). Обратите также внимание на адресацию стекового фрейма. Напомню, что стековым фреймом (stack frame) называется область стека, хранящая аргументы и локальные переменные данной функции. Адресация содержимого стекового фрейма осуществляется относительно регистра ЕВР. Указатель на стековый фрейм формируется в результате последовательности операций: pushl %ebp movl %esp, %ebp

Таким образом, параметры функции получают положительное смещение относительно EBP, а локальные переменные - отрицательное, так как указатель на вершину стека движется от больших адресов к меньшим (напомню еще раз, что передача значений в movl происходит из левого операнда правому).

Теперь мы можем проанализировать получившийся код. Прежде всего, замечаем, что локальная переменная i хранится в памяти, а не в регистре. Команды, работающие с памятью, не так эффективны с точки зрения скорости доступа к переменным, как инструкции, обращающиеся к регистрам. Кроме того, в блоке L5 появляется команда leal, которая была бы не нужна, если бы переменная i хранилась в регистре. Во-вторых, можно заметить, что хотя функции main не передается никаких параметров, в начале тела функции предпринимаются некоторые действия по организации стекового фрейма.

Как видим, при компиляции по умолчанию никакой оптимизации не производится, но это не следует считать упущением. Отсутствие оптимизации может быть иногда полезно. Например при просмотре значений переменных в процессе отладки кода вы не получите сообщения "variable is not accessible here due to optimization". Специально отмечу, что если оптимизирующие опции не указаны, компилятор действительно не выполняет никакой оптимизации кода, так что даже константные выражения вроде 2*2 не заменяются своими значениями.