|
Страница 3 из 17
Методы оптимизации Существуют различные методы машинно-зависимой и машинно-независимой
оптимизации кода. Они могут применяться на всех синтаксических уровнях.
Одним из простейших методов является "размножение констант". При его
применении любая ссылка на константное значение замещается самим
значением. В следующем примере повышается эффективность благодаря удалению
трех адресных ссылок и замене их константами:
x = 2;
if( a < x && b < x)
c = x;
переводится в
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-------------------------------------------------------------- |