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

#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;

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