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

Хислей Филипп Н.

c = x;s

переводится в

x = 2;

if(a < 2 && b < 2)

c = 2;

Целиком связано с размножением констант "размножение копий". В этом методе копируются переменные вместо константных значений. Например,

x = y;

if(a < x && b < x)

c = x;

переводится в

x = y;

if(a < y && b < y)

c = y;

Размножение констант и копий также может удалить излишние присваивания (x = 2 и x = y в примерах). Среди описываемых компиляторов только Microsoft C 5.0 и WATCOM C 6.0 применяют размножение констант.

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

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