Филипп Хислей - Генерация высококачественного кода для программ, написанных на СИ

• Название: Генерация высококачественного кода для программ, написанных на СИ
• Автор: Филипп Хислей
• Жанр: Программирование

---

Метод "свертки констант" (константная арифметика) сводит выражения, которые содержат константные данные, к возможно простейшей форме. Константные данные обычно используются в программе либо непосредственно (как в случае чисел или цифр), либо косвенно (как в случае объявленных манифестных констант). Свертка констант сводит следующий оператор:

#define TWO 2

a = 1 + TWO;

к его эквивалентной форме,

a = 3;

во время компиляции, благодаря чему удаляются ненужные арифметические операции из стадии выполнения программы. В Си сворачивание констант применяют как к целым константам, так и к константам с плавающей точкой.

"Алгебраические упрощения" есть вид свертки констант, который удаляет арифметические тождества. Код, сгенерированный для таких операторов, как

x = y + 0;

x = y * 0;

x = y / 1.0;

x = y / 0;

должен быть простым константным присваиванием и не должен содержать команд для выполнения арифметических операций. Бдительный компилятор должен пометить последний оператор как ошибочный и не генерировать код для него.

"Извлечение общих подвыражений" - это процесс удаления лишних вычислений. Вместо того, чтобы генерировать код для вычисления значения каждый раз, когда оно используется, оптимизирующий компилятор пытается выделить выражение таким образом, чтобы его значение вычислялось только однажды. Там, где это возможно, последующие ссылки на такое же выражение используют ранее вычисленное значение. Выражения y * 3 и a[y*3] являются общими подвыражениями в следующем тексте:

if( a[y*3] < 0 || b[y*3] > 10)

a[y*3] = 0;

Выделение этих выражений приводит к логически эквивалентному тексту:

T1 = y*3;

A1 = &a[T1];

A2 = &b[T1];

if( *A1 < 0 || *A2 > 10)

*A1 = 0;

Выделение общих подвыражений обычно происходит внутри оператора или блока. "Глубокое выделение общих подвыражений" является более сложным и перекрывает базовые блоки. Выделение общего подвыражения, y*3, в операторе

if(a == 0)

a = y * 3;

else

b = y * 3;

приводит к логическому эквиваленту:

T1 = y * 3;

if(a == 0)

a = T1;

else

b = T1;

Рисунок 1 демонстрирует практический выигрыш от выделения общих подвыражений в реальном коде.

--------------------------------------------------------------¬

¦РИСУНОК 1: Выделение общих подвыражений ¦

+-------------------------------------------------------------+

¦Исходный текст на Си BORLAND LATTICE ¦

¦ Turbo C 1.5 MS-DOS C 3.2 ¦

+-------------------------------------------------------------+

¦if((h3 + k3) < 0 || mov AX,h3 mov AX,h3 ¦

¦ (h3 + k3) > 5) add AX,k3 add AX,k3 ¦

¦ printf("Common\ jl @18 js L0187 ¦

¦ subexpression\ mov AX,h3 cmp AX,5 ¦

¦ elimination"); add AX,k3 jle L0193 ¦

¦ cmp AX,5 L0187: ¦

¦ jle @17 mov AX,01.0000 ¦

¦ @18: push AX ¦

¦ mov AX,offset s@ call printf ¦

¦ push AX add SP,2 ¦

¦ call printf L0193: ¦

¦ mov SP,BP ¦

¦ @17: ¦

+-------------------------------------------------------------+

¦Многократные вхождения вычислений заменяются значением, ¦

¦которое является результатом единственного вхождения ¦

¦вычисления. Borland Turbo C вычисляет значение выделенного ¦

¦выражения h3+k3 дважды, тогда как LATTICE MS-DOS C и другие ¦

¦применяют выделение общих подвыражений и вычисляют ¦

¦выражение только один раз. ¦

L--------------------------------------------------------------

"Снижение мощности" подразумевает замещение операций, которые требуют большего времени выполнения, более быстрыми. Компилятор может применять снижение мощности несколькими способами. Например, применяя снижение мощности к сгенерированному коду, компилятор может подменять операции, которые умножают или делят целые числа на степени двойки, операциями сдвига.

"Удаление недостижимого кода" - еще один метод оптимизации. Недостижимый код – это некоторая последовательность инструкций программы, которая недостижима ни по одному пути в программе. Он может образоваться как следствие предыдущих операций оптимизации, кода условной отладки, или частых изменений программы многими программистами. Следующие операторы - это вариант кода для проверки компилятора на выполнение этого метода оптимизации.

#define DEBUG 0

if(DEBUG)

printf("Debug Function\n");

Манифестные константы часто могут скрывать существование недостижимого кода, особенно если такой код определяется внутри включаемого файла-заголовка.

"Удаление лишних присваиваний" включает нахождение промежутка жизни переменной и удаление присваиваний этой переменной, если эти присваивания не могут изменить логику программы. Этот метод освобождает ограниченные ресурсы, такие как пространство стека или машинные регистры. В следующей последовательности команд:

a = 5;

b = 0;

a = b;

первый оператор есть лишнее присваивание, и может быть удален безопасно. Лишние присваивания могут возникать непреднамеренно, когда промежуток жизни переменной велик и между вхождениями переменной имеется более-менее длинный код. Лишние присваивания могут быть также результатом предыдущих проходов оптимизации.

Цель "распределения переменных по регистрам" состоит в попытке обеспечить оптимальное назначение регистров путем сохранения часто используемых переменных в регистрах так долго, как это возможно, для того, чтобы исключить более медленный доступ к памяти. Количество регистров, доступных для использования, зависит от архитектуры процессора. Семейство микропроцессоров Intel 80x86 резервирует много регистров для специального использования и имеет несколько универсальных регистров. В помощь распределению переменных по регистрам язык Си предоставляет спецификатор класса регистровой памяти, который дает возможность программисту указывать, какие переменные должны располагаться в регистрах.

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

Поскольку оптимизирующему компилятору известен промежуток жизни переменной, он не будет намеренно генерировать "лишние операции сохранения и загрузки" (регистров). Лишние операции сохранения удаляются посредством удаления излишних присваиваний; лишние операции загрузки опускаются с помощью усовершенствованного распределения переменных по регистрам. Имея текст:

a = i + 2;

b = a + 3;

компилятор без возможностей оптимизации может сгенерировать следующий код:

mov AX,i

add AX,2

mov a,AX

mov AX,a

add AX,3

mov b,AX

тогда как оптимизирующий компилятор может использовать механизм размещения переменных в регистрах для удаления лишней четвертой инструкции (mov AX,a).

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

--------------------------------------------------------------¬

¦РИСУНОК 2: Простой цикл ¦

+-------------------------------------------------------------+

¦Исходный текст на Си BORLAND METAWARE ¦

¦ Turbo C 1.5 High C 1.4 ¦

¦(x) - врем. циклы (125) (87) ¦

+-------------------------------------------------------------+

¦k5 = 10000; mov j5,0 mov j5,0 ¦

¦j5 = 0; mov k5,10000 mov k5,10000 ¦

¦do { @10: L00e3: ¦

¦ k5 = k5 - 1; mov AX,k5 dec k5 ¦

¦ j5 = j5 + 1; dec AX inc j5 ¦

¦ i5 = (k5 * 3) / mov k5,AX mov AX,j5 ¦

¦ (j5 * constant5); mov AX,j5 mov SI,AX ¦