Хотя все компиляторы с языка Си предназначены для генерации наиболее быстрых и компактных программ, качество оптимизации кода у них может быть совершенно различное. Разработчики компиляторов с языка Си первоначально стремились к полному согласию со стандартом Кернигана и Ричи. В последствии - к уменьшению времени компиляции. Затем - к полной поддержке моделей памяти семейства микропроцессоров 80х86. Затем пытались поддерживать переносимость исходных текстов программ путем предоставления совместимых с UNIX библиотек функций. После этого создавали специализированные библиотеки функций для обеспечения низкоуровневого доступа к характерным для персональных компьютеров (PC) возможностям. За этим следовали попытки придерживаться развивающегося стандарта ANSI C. После чего следовал возврат к началу, но с развитым интегрированным окружением. И так далее.
Самое последнее направление в развитии компиляторов Си - оптимизация. Это можно продемонстрировать такими сегодняшними заявлениями поставщиков компиляторов: "Наиболее мощный оптимизирующий компилятор!" (Turbo C, Borland); "Новые методы оптимизации генерируют самый быстрый код!" (C 5.0, Microsoft); "Оптимизатор неутомимо ищет пути ускорения выполнения и минимизации используемой памяти" (Optimum C, Datalight). Учитывая эту моду, PC Tech Journal разработал тест для проверки возможностей
оптимизации кода у Си компиляторов, имеющихся на PC. Этот тест был выполнен на девяти компиляторах: Borland Turbo C 1.5, Computer Innovations C86Plus 1.10, Datalight Optimum-C 3.14, Lattice MS-DOS C 3.2, Manx Aztec C86 4.0, Metaware High C 1.4, Microsoft C 5.0 и QuickC 1.0, а также WATCOM C 6.0. Эти изделия представляют лучшие компиляторы Си, доступные на PC. Проверка показала, что различные компиляторы применяют различные приемы оптимизации с различным успехом. Доступны и другие компиляторы, но их характеристики значительно хуже, чем у перечисленных. Большинство этих компиляторов описаны в февральском номере PC Tech Journal 1988 года в
статье "The State of C" (см. "C Contenders" и "Turbo and Quick Weigh In", Marty Franz, стр. 52 и 72 соответственно).
Поскольку современные компиляторы Си близки по предоставляемым возможностям, оптимизация остается одним важным отличием, по которому их можно дифференцировать. Работа компилятора заключается в том, чтобы странслировать процедурное описание задачи и эффективно отобразить его в выделенное множество машинных команд целевого процессора. Степень эффективности генерации компилятором машинно-уровневого кода может иметь существенное влияние на скорость выполнения программы и ее размер.
Основная цель оптимизации - выработка более быстрого и меньшего по размеру кода. В обычной среде компьютера, где количество доступной оперативной памяти есть ограниченный ресурс, разделяемый несколькими пользователями, важна оптимизация размера кода. В среде PC оптимизация скорости имеет более высокий приоритет, поскольку PC обычно используется одним лицом и доступен большой объем памяти (большинство PC имеют по крайней мере 640KB основной памяти и многие имеют несколько мегабайт дополнительной или
расширенной памяти). Следовательно, лучший способ оценки возможностей оптимизации кода компилятора Си, предназначенного для PC, - оценка скорости.
Тщательный анализ задачи и чистая программная реализация обеспечивают прочную основу для любых последующих усовершенствований, которые могут быть внесены оптимизирующим компилятором. Нельзя ожидать, что оптимизация кода компенсирует программам плохо организованную структуру задачи или выбор неподходящего алгоритма. Например, существующая технология оптимизации никак не сможет автоматически подставить алгоритм быстрой сортировки вместо записанного алгоритма пузырьковой сортировки, хотя, возможно, будет получена программа, работающая быстрее. К тому же, программисты могут просто влиять на некоторые способы оптимизации кода,
такие как вычисление константных выражений, вынесение инвариантов циклов и совмещение циклов.
Методы оптимизации
Существуют различные методы машинно-зависимой и машинно-независимой
оптимизации кода. Они могут применяться на всех синтаксических уровнях.
Одним из простейших методов является "размножение констант". При его
применении любая ссылка на константное значение замещается самим
значением. В следующем примере повышается эффективность благодаря удалению
трех адресных ссылок и замене их константами:
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--------------------------------------------------------------
Сфера применения оптимизации
Термин "оптимизирующий компилятор" применяется поставщиками компиляторов в общем смысле, для обозначения компиляторов, которые обеспечивают какой-либо уровень оптимизации - от простейшего до наиболее сложного. Чтобы различать степень оптимизации, предоставляемую компиляторами, необходимо более точное определение терминов. Методы оптимизации кода могут применяться на разных уровнях синтаксических конструкций. От самого первичного уровня до наиболее укрупненного, т.е. на уровне оператора,
блока, цикла, процедуры и программы. Чем выше уровень оптимизации, тем больше возможности повышения общей эффективности программного модуля. Однако затраты на применение большей степени оптимизации могут значительно увеличить время компиляции.
Оператор - это первичная синтаксическая единица в программе. Большинство компиляторов выполняют некоторую оптимизацию на этом уровне. Блок - это последовательность операторов, для которой существуют единственная точка входа и единственная точка выхода. Линейный вид блока инструкций позволяет компилятору выполнять оптимизацию, основывающуюся на промежутках жизни различных данных и выражений, используемых внутри блока. Оптимизирующий компилятор выделяет операционную структуру программ путем
конструирования ориентированного потокового графа программ, в котором каждая вершина представляет основной блок, а связи между вершинами представляют потоки управления. Большинство компиляторов производят оптимизацию на уровне блока.
Цикл содержит выполняемую многократно последовательность операторов. Поскольку многие программы проводят в циклах большую часть времени своего выполнения, оптимизация в этой области может дать существенное улучшение характеристик исполнения программы. Являясь обычной для компиляторов на больших компьютерах и миникомпьютерах, оптимизация на уровне цикла является новой для компиляторов Си на PC.
Процедуры - это операторы, которые содержат целые подпрограммы или функции. Оптимизация на этом уровне вообще не выполняется компиляторами для PC.
Наиболее сложный уровень оптимизации, уровень программы, в настоящее время рассматривается чисто теоретически и не включается ни одним доступным на PС, миникомпьютерах, и больших компьютерах компилятором Си. Производители, которые утверждают, что их компиляторы выполняют глобальную оптимизацию, имеют в виду уровень процедур, но не программы. Оптимизирующие преобразования могут быть зависящими или независящими от архитектуры компьютера. Процесс компиляции компьютерной программы включает два основных действия: синтаксичесикй/семантический анализ и генерацию кода. Синтаксический/семантический анализ существенно зависит от
грамматики и специфичен для языка. Генерация кода является общей и прекрасно может быть использована для поддержки первой стадии для любого количества языков программирования.
Исходный текст конкретного языка первым делом транслируется в общую промежуточную форму, которая последовательно обрабатывается для выработки на стадии генерации машинно-зависимого кода. Машинно-независимая оптимизация, такая как выделение общих подвыражений и вынесение инвариантного кода, применяется к промежуточному коду. Машинно-зависимая оптимизация применяется к результату стадии генерации кода и использует набор команд конкретного процессора. Эта оптимизация известна как "щелевая" оптимизация, потому что эти преобразования выполняются внутри маленького окна (5 - 10 инструкций машинного уровня). Типичные примеры
щелевой оптимизации включают удаление излишних операций загрузки/сохранения регистров, удаление недостижимого кода, выпрямление
передач управления, алгебраические упрощения, снижение мощности (команд) и использование команд, специфических для конкретного процессора.