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

В продолжении статьи об оптимизации кода компилятором GCC, поговорим о базовой оптимизации. Как я уже отмечал ранее, основные режимы оптимизации задаются ключами -01, -02, -03 и -Os. Что они означают? Давайте разберёмся.

Ключ -01 включает режим минимальной оптимизации (включает методы оптимизации, не требующие больших затрат времени на этапе компиляции, например, встраивание inline-функций). Ключ -02 включает практически все виды оптимизации, не приводящие к увеличению размеров программы, в том числе такую полезную опцию, как перенос переменных в регистры. Ключ -03, в дополнение к методам, включаемым -02, включает опции -finline-functions и -frename-registers options (подробнее см. ниже). И наконец, ключ -Os выполняет оптимизацию по критерию уменьшения длины кода.

Давайте попробуем скомпилировать программу test.c (её листинг можно найти тут) с ключом -02. Результирующий ассемблерный код приводится ниже.

main:
pushl 4ebp
movl %esp, %ebp
pushl %ebx
pushl %eax
xorl %ebx, Ssebx
.p2align 4,,7
L21:
testl $1, %ebx
jne .L22
subl $12, %esp
pushl $.LCO
jmp .L26
.p2align 4,,7
L22:
subl $12, %esp
pushl $.LC1
L26:
call printf
addl $16, %esp
incl %ebx
cmpw $9, %bx
jle .121
movl -4(%ebp), %ebx
movl %ebp, %esp
xorl %eax, %eax
popl %ebp
ret


Опция -02 включает режим -fforce-mem, в результате чего переменная i сохранится в регистре ЕВХ. Кроме того, -02 также включает опцию -fomit-frame-pointer, которая отменяет формирование указателя на стековый фрейм в регистре EBP, если таковой не нужен. Однако, хотя стековый фрейм в процедуре main не используется, команды формирования указателя остались. Для того чтобы удалить эти команды, в нашем случае следует указать опцию -fomit-frame-pointer явным образом, что ускорит вызов процедуры. Кроме оптимизаций, указанных выше, следует отметить улучшение механизма проверки на четность и оптимизацию команд подготовки вызова функции printf.

При включенной оптимизации -fforce-mem компилятор GCC стремится разместить в регистрах процессора максимальное число переменных. При этом используется специальный прием - построение графа совместности переменных и его последующая раскраска. Каждой переменной соответствует одна вершина графа. Две вершины связываются ребром, если соответствующие им переменные существуют в один и тот же момент выполнения программы. Распределение переменных по регистрам процессора осуществляется следующим образом: выделяется N цветов, соответствующих N свободным регистрам процессора, затем вершины графа раскрашиваются так, чтобы связанные вершины не были окрашены одинаково (в один регистр нельзя записать две переменные одновременно). Следует отметить, что задача о раскраске графа в общем случае относится к классу трудновычислимых (NP-полных) задач. По этой причине использование данного метода оптимизации заметно увеличивает время, затрачиваемое на компиляцию.

GNU С позволяет указывать регистр для размещения локальной переменной непосредственно. Например, для размещения переменной tmp в регистре EDX, пишем: register int tmp asm ("%edx"). Такой механизм лучше всего подходит для временных переменных, используемых в небольших фрагментах кода, а также при использовании ассемблерных вставок. Выделенный регистр может использоваться для других целей за пределами сферы действия назначенной ему переменной.

Какие переменные следует размещать в регистрах, а какие - нет? Прежде всего, это переменные, используемые с префиксом &. Если программе необходим адрес переменной, эта переменная должна храниться в памяти. Если вы объявите переменную с директивой register, а затем примените к ней оператор &, в процессе компиляции программы компилятор выдаст предупреждение, но программа скомпилируется. Действия, предпринимаемые компилятором для разрешения этого противоречия зависят от ситуации. Если вы компилируете программу с включенной оптимизацией, и конструкция, связанная с получением адреса, в процессе оптимизации может быть удалена, регистровая переменная останется в регистре. В противном случае переменная будет размещена в памяти.

Количество свободных регистров процессора может быть ограничено при модификации формата вызова функции (об этом мы поговорим в следующем разделе). Декларация register в объявлении переменной создает для данной переменной приоритет при выделении регистров. Пользуйтесь этой декларацией, только если вы уверены, что сможете разместить переменные в регистрах более оптимально, чем это сделает компилятор.

Оптимизация ветвлений

GCC предоставляет несколько опций, контролирующих оптимизацию ветвлений (англ. branch optimization). Классическим примером такого рода оптимизации является удаление инструкции перехода, целью которой является другая инструкция перехода.

Опция -fthread-jumps, включаемая всеми командами -Ох, оптимизирует условные переходы. Если целью условного перехода после первой проверки является вторая проверка, результат которой представляет собой логическое следствие результата исходной проверки, вторая проверка пропускается, и целью первого условного перехода становится цель второго условного перехода. Например, конструкция: if (А) { if (A II B) {} else {} будет заменена на if (А) {} else {}. Опция -falign-labels=n, где n - целое число, вызывает выравнивание меток по адресам, кратным степени 2. При этом до n байтов может быть заполнено кодами "нет операции" (nop). Использование этой опции может замедлить работу программы. Более безопасна опция -falign-jumps=n, которая выравнивает целевые блоки переходов, если соответствующий блок не может быть достигнут иначе, чем в результате перехода. Использование этой опции может увеличить размеры модуля, но никогда не создает более медленный код.

Оптимизация циклов

Теперь давайте рассмотрим фрагмент кода, в котором элементы целочисленного вектора длины m*n умножаются на выражение (а+b):

int * V;
int i, m, n, a, b;
for (i=0; i *= a + b;


Ниже приводятся последовательность ассемблерных команд для последней строки до оптимизации.

.L12:
movl -80(%ebp), %еах
imull -84(%ebp), %еах
cinpl %еах, -76(%ebp)
jl .L15
jmp .L13
.p2align 4,,7

.L15:
movl -76(%ebp), %eax
movl %eax, %eax
leal 0(,%eax,4), %edi
leal -72(%ebp), %eax
movl %eax, %esi
movl -76(%ebp), %eax
movl ?seax, %eax
leal 0(,%eax,4), %ebx
leal -72(%ebp), %eax
movl %eax, %ecx
movl -92(%ebp), %eax
movl -88(%ebp), %edx
addl %eax, %edx
movl (%ebx,%есх), %eax
imull %edx, %eax
movl %eax, (%edi,%esi)
leal -76{%ebp), %eax
incl (%eax)
jmp .L12
.p2align 4,,7

.L13:
...


В неоптимизированном варианте выражения m*n и а+b вычисляются столько же раз, сколько выполняется тело цикла. В процессе оптимизации компилятор старается вынести выражения, значения которых в цикле не меняются, за пределы цикла. Этот вид оптимизации контролируется опцией -fmove-all-mov-ables, которая, как и большинство приемов оптимизации циклов, включается опцией -02. После оптимизации код выглядит так:

movl $2, %eax
addl $16, %esp
imull $5, %eax, %eax
testl %eax, %eax
je .L36
movl $5, %ebx
xorl %ecx, %ecx
movl %eax, %edx
.p2align 4,,7

.L33:
movl -56(%ebp,%ecx), %eax
imull %ebx, %eax
movl %eax, -5 6(%ebp,%ecx)
addl $4, %ecx
decl %edx
jne .L33

.L36:
...


Оптимизированный командой -02 код стал гораздо компактнее, однако минимальные размеры кода не всегда являются наиболее желаемой целью оптимизации. Так как код проверки условия цикла и связанные с ним переходы требуют сравнительно много машинного времени, для повышения быстродействия приложения применяют метод разворачивания циклов (англ. loops unrolling). Суть метода заключается в сокращении числа итераций цикла за счет повторения блоков тела цикла. Попробуем оптимизировать код, добавив к опции -02 опцию -funroll-loops (по умолчанию включается ключом -03). Лучше всего разворачивание циклов получается тогда, когда число итераций представляет собой степень двойки, поэтому для следующего примера m=n=4.

.L53:
movl -72(%ebp,%ecx), %edx
leal 4(%ecx), %eax
imull %ebx, %edx
movl %edx, -72(%ebp, %есх)
movl -72(%ebp,%eax), %edx
imull %ebx, %edx
movl %edx, -72(%ebp,%eax)
leal 8(%ecx), %eax
movl -72(%ebp,%eax), %edx
imull %ebx, %edx
movl %edx, -72(%ebp,%eax)
leal 12(%ecx), %eax
addl $16, %ecx
movl -72(%ebp,%eax), %edx
imull %ebx, %edx
subl $4, %esi
movl %edx, -72 (%ebp Деах)
jne .L53


Заметьте, что число итераций в этом примере сократилось с 16 до 4. Опция -funroll-loops оптимизирует только те циклы, число итераций которых известно во время компиляции. Для оптимизации циклов, число итераций которых во время компиляции неизвестно, можно воспользоваться опцией -funroll-all-loops, которая, однако, сгенерирует чуть более медленный код.

Ключ -02 задействует опцию -fstrength-reduce, выполняющую над циклами еще один вид оптимизации, называемый strength reduction. Сущность метода заключается в том, что сложные математические операции (умножение, деление) по возможности заменяются более простыми (сложение, вычитание, побитовые операции). Часто для оптимизации кода бывает полезно выполнить операцию strength reduction над переменными-счетчиками цикла. Этот метод оптимизация включается опцией -freduce-all-givs. При использовании -freduce-all-givs цикл

for (i=0; i<10; i++)
a(i) = ...;


где адрес a(i) вычисляется, например, как a+i*4, может быть заменен циклом (для наглядности ассемблерный код заменён C-эквивалентом):

for(р=0; р<40; р+=4)
*(а+р) = ...;


Иногда в процессе такой оптимизации удаётся вообще удалить явную переменную-счетчик. Опция -frerun-cse-after-loop заставляет компилятор выполнять повторный проход с целью удаления повторяющихся подвыражений после оптимизации циклов, а опция -frerun-loop-opt заставляет подсистему оптимизации циклов делать повторный проход, применяя все доступные методы оптимизаций. Эта опция может быть полезна при оптимизации конструкций, содержащих вложенные циклы. Опция -fprefetch-loop-arrays позволяет организовать предвыборку памяти для циклов, обрабатывающих большие массивы.