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

Итак, движемся дальше. В первых двух частях статьи мы поговорили об использовании различных опций компилятора, предназначенных для оптимизации кода и рассмотрели их на примерах. Также мы поговорили об оптимизации циклов и ветвлений. Если вы пропустили эти статьи, вы всегда можете найти их в моём блоге, а для тех, кто готов идти вперёд - извольте! Сегодня речь пойдёт об оптимизации рекурсивных функций. Довольно интересная тема, и уверен, что вы тоже так считаете.

Давайте напишем ещё одну программу на C:

#include
#define EPS le-6
double sqroot(double x, double a) {
double b = (a + x/a)/2
if ({ -EPS))
return b;
return sqroot(x, b);
}

int main() {
double x;
printf("Введите число (x > 1.0)");
scanf("%lf", &x);
printf ("Корень из %t равен %f
", x, sqroot(x, 1.));
return 0;
}


Теперь рассмотрим ассемблерный код не-оптимизированной функции sqroot.

sqroot:
pushl %ebp
movl ^esp, %еbр
subl $24, %esp
movl 8(%ebp), %eax
movl 12(%ebp), %edx
movl %eax, -8(%ebp)
movl %edx, -4(%ebp)
movl 16(%ebp), %eax
movl 20(%ebp), %edx
movl %eax, -16(%ebp)
movl %edx, -12(%ebp)

# вычисление b = (a + x/a)/2
fldl -8(5sebp)
fdivl -16(%ebp)
faddl -16(%ebp)
fldl .LC0
fdivrp %st, %st(l)
fstpl -24(%ebp)

# вычисление b*b - x
fldl -24(%ebp)
fmull -24(%ebp)
fsubl -8(%ebp)
fldl .LC1
fxch %8t(l)

# проверха (b*b - x) < EPS
fucompp
fnstsw %ax
andb $69, %ah
cmpb $1, %ah
je .L4
jmp .L3
.p2align 2

.L4:

# вычисление b*b - x
fldl -24(%ebp)
fmull -24(%ebp)
fsubl -8(%ebp)
fldl .LC2
fxch %st(l)

# проверка (b*b - x) > -EPS
fucompp
fnstsw %ax
testb $69, %ah
je .L5
jmp .L3
.p2align 2

.L5:
fldl -24(%ebp)
jmp .L2
.p2align 2

.L3:
pushl -20(%ebp)
pushl -24(%ebp)
pushl -4(%ebp)
pushl -8(%ebp)
call sgroot
addl $16, %esp

.L2:
leave ret


Обратите внимание, что оптимизированный вариант, кроме прочего, не содержит рекурсивного вызова sqroot:

ssqroot:
pushl %ebp
movl %esp, %ebp
fldl 8(%ebp)
fldl 16(%ebp)
fldl .LC0
fldl .LC1
fldl .LC2

.L21:
# вычисление b = (a + x/a)/2
fid %st(4)
fdiv %st(4), %st
faddp %8t, %st(4)
fxch %8t(3)
fmul %st(2), %et

# вычисление b*b - x
fid %st(0)
fmul %st(0), %8t
fsub %st(5), %st

# проверка (b*b - x) < EPS
fucom %st(2)
fnstsw %ax
andb $69, %ah
cmpb $1, %ah
jne .L22

# проверка (b*b - x) > -EPS
fucomp %st(4)
fnstsw %ax
testb $69, %ah
je .L17
jmp .L18

.L22:
fstp %st(0)

.L18:
fxch %st(3)
jmp .L21
.p2align 2

.L17:
fstp %st(l)
fstp %st{1)
fstp %st(l)
fstp %st(l)
popl %ebp
ret


Функция sqroot завершается рекурсивным вызовом. В этой ситуации рекурсивную функцию легко преобразовать в цикл. Такая операция называется удалением концевой рекурсии (англ. tail recursion elimination). В GCC этот тип оптимизации активируется опцией -foptimize-sibling-calls (ключ -02 включает эту опцию по умолчанию). Впрочем, возможности оптимизации рекурсивных функций компилятором не следует переоценивать. К примеру, в функции, приведённой ниже, рекурсия не будет оптимизирована:

unsigned int fact (unsigned int n) {
if (n < 2) return 1;
return n*fact(n-l);
}


Ещё одна возможность оптимизации, особенно полезная при использовании рекурсивных вызовов, связана с передачей аргументов функции через регистры процессора. Этот вид оптимизации задается отдельно для каждой функции при помощи встроенного макроса _attribute_ с ключевым словом regparm. В качестве аргумента передается число аргументов функции, которые следует передавать в регистрах. Максимальное число таких аргументов для платформы IA32 составляет 3 (аргументы передаются в регистрах ЕАХ, EDX и ЕСХ). Естественно, аргументы, передаваемые через регистры, должны быть приводимы к типу int. Объявление функции, передающей аргументы через регистры, может выглядеть так:

unsigned int fact(unsigned int n)
_attribute_ ((regparm (1)));


Передача аргументов через регистры не всегда повышает эффективность вызовов, так как при этом может уменьшиться число свободных регистров, а следовательно, и число локальных переменных, размещаемых в регистрах в процессе оптимизации. Аргументы типов float и double всегда передаются через память, а не через стек сопроцессора. Отмечу ещё один интересный момент. Если в теле функции sqroot мы не вставим оператор return перед рекурсивным вызовом sqroot, неоптимизированный вариант программы вернёт, естественно, nan' в качестве результата функции (переполнения стека сопроцессора при этом не произойдёт, так как параметры передаются через стек в памяти). В оптимизированном же варианте с удалением рекурсии, функция все работать нормально. Вероятно, это как раз тот случай, который в Jargon File обозначен термином "heisenbug".

Удаление повторяющихся подвыражений

Если сравнить ассемблерные коды оптимизированного и неоптимизированного вариантов функции sqroot, можно заметить, что во втором варианте выражение b*b - х вычисляется дважды - столько же раз, сколько оно встречается в исходном тексте программы, тогда как в первом варианте это выражение вычисляется только один раз. Методика оптимизации, называемая удаление повторяющихся подвыражений (обозначается УПП), применяется не только к математическим выражениям. С другим примером этого типа оптимизации мы с вами уже встречались раньше, при анализе оптимизированного кода программы test.c, где код вызова функции printf использовался только один раз.

Режим УПП включается по умолчанию всеми опциями -0х (х = 1, 2, 3, s), кроме того, компилятор GCC предоставляет ряд ключей, позволяющих управлять различными параметрами этого типа оптимизации. Большинство ключей GCC имеют положительную и отрицательную форму. В следующем ниже списке сначала приводится форма ключа, устанавливаемая по умолчанию опциями -0х:
• -ffunction-cse/-fno-function-cse - включает/отключает режим записи адресов вызываемых функций в регистры. Значение по умолчанию создает более оптимальный код.
• -fno-cse-follow-jumps/-fcse-follow-jumps - отключает/включает режим следования ветвлениям в процессе удаления подвыражений. Значение по умолчанию создает более оптимальный код.
• -fno-cse-skip-blocks-fcse/-fskip-blocks - отключает/включает режим следования ветвлениям, пропускающим блоки в процессе удаления подвыражений. Значение по умолчанию создает более оптимальный код.
• -fno-rerun-cse-after-loop/-frerun-cse-after-loop - отключает/включает режим повторного удаления подвыражений после оптимизации циклов, по умолчанию отключено. Включение этой опции иногда позволяет получить более оптимальный код.
• -fforce-mem/-fno-force-mem - перемещение операндов из памяти в регистры, по умолчанию включается опцией -02. Включенный режим облегчает УПП.
• -fno-force-addr/-fforce-addr - отключает/включает режим переноса адресных констант в регистры. По умолчанию отключено. Включенный режим облегчает УПП.

В последних версиях GCC введена новая опция -fgcse/-fno, позволяющая контролировать глобальное удаление повторяющихся подвыражений (англ. global common subexpression elimination), или ГУПП. При этом методе оптимизации удаляются одинаковые подвыражения, содержащиеся в разных базовых блоках. Принцип работы ГУПП достаточно прост - если подвыражение встречается в нескольких блоках, компилятор создает дополнительную глобальную переменную, которой присваивается значение выражения после первого вычисления. Все последующие вхождения данного выражения заменяются ссылкой на глобальную переменную. Единственная сложность, связанная с этим методом, заключается в том, что в процессе ГУПП подсистеме оптимизации приходится существенно расширить свой "кругозор", что может замедлить процесс компиляции.

Остальные опции компилятора, связанные с УПП, влияют, прежде всего, на оптимизацию циклов и будут рассмотрены позже. Удаление повторяющихся подвыражений позволяет упростить некоторые математические выражения, однако не следует ждать от этой системы слишком многого. При всех его плюсах, следует помнить, что компилятор GCC - не система компьютерной алгебры. Выражение типа а/с + b/с не будет преобразовано в (а + Ь)/с никакими методами оптимизации. Разумеется, такие преобразования следует выполнять вручную!