Генерация высококачественного кода для программ, написанных на СИ
Хотя все компиляторы с языка Си предназначены для генерации наиболее быстрых и компактных программ, качество оптимизации кода у них может быть совершенно различное.
Разработчики компиляторов с языка Си первоначально стремились к полному согласию со стандартом Кернигана и Ричи. В последствии - к уменьшению времени компиляции. Затем - к полной поддержке моделей памяти семейства микропроцессоров 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, - оценка скорости.
Тщательный анализ задачи и чистая программная реализация обеспечивают прочную основу для любых последующих усовершенствований, которые могут быть внесены оптимизирующим компилятором. Нельзя ожидать, что оптимизация кода компенсирует программам плохо организованную структуру задачи или выбор неподходящего алгоритма. Например, существующая технология оптимизации никак не сможет автоматически подставить алгоритм быстрой сортировки вместо записанного алгоритма пузырьковой сортировки, хотя, возможно, будет получена программа, работающая быстрее. К тому же, программисты могут просто влиять на некоторые способы оптимизации кода, такие как вычисление константных выражений, вынесение инвариантов циклов и совмещение циклов.
Сфера применения оптимизации
Термин "
оптимизирующий компилятор" применяется поставщиками компиляторов в общем смысле, для обозначения компиляторов, которые обеспечивают какой-либо уровень оптимизации - от простейшего до наиболее сложного. Чтобы различать степень оптимизации, предоставляемую компиляторами, необходимо более точное определение терминов. Методы оптимизации кода могут применяться на разных уровнях синтаксических конструкций. От самого первичного уровня до наиболее укрупненного, т.е. на уровне оператора, блока, цикла, процедуры и программы. Чем выше уровень оптимизации, тем больше возможности повышения общей эффективности программного модуля. Однако затраты на применение большей степени оптимизации могут значительно увеличить время компиляции.
Оператор - это первичная синтаксическая единица в программе. Большинство компиляторов выполняют некоторую оптимизацию на этом уровне.
Блок - это последовательность операторов, для которой существуют единственная точка входа и единственная точка выхода. Линейный вид блока инструкций позволяет компилятору выполнять оптимизацию, основывающуюся на промежутках жизни различных данных и выражений, используемых внутри блока. Оптимизирующий компилятор выделяет операционную структуру программ путем конструирования ориентированного потокового графа программ, в котором каждая вершина представляет основной блок, а связи между вершинами представляют потоки управления. Большинство компиляторов производят оптимизацию на уровне блока.
Цикл содержит выполняемую многократно последовательность операторов. Поскольку многие программы проводят в циклах большую часть времени своего выполнения, оптимизация в этой области может дать существенное улучшение характеристик исполнения программы. Являясь обычной для компиляторов на больших компьютерах и миникомпьютерах, оптимизация на уровне цикла является новой для компиляторов Си на PC.
Процедуры - это операторы, которые содержат целые подпрограммы или функции. Оптимизация на этом уровне вообще не выполняется компиляторами для PC.
Наиболее сложный уровень оптимизации, уровень программы, в настоящее время рассматривается чисто теоретически и не включается ни одним доступным на PС, миникомпьютерах, и больших компьютерах компилятором Си. Производители, которые утверждают, что их компиляторы выполняют глобальную оптимизацию, имеют в виду уровень процедур, но не программы.
Оптимизирующие преобразования могут быть зависящими или независящими от архитектуры компьютера. Процесс компиляции компьютерной программы включает два основных действия: синтаксический/семантический анализ и генерацию кода. Синтаксический/семантический анализ существенно зависит от грамматики и специфичен для языка. Генерация кода является общей и прекрасно может быть использована для поддержки первой стадии для любого количества языков программирования.
Исходный текст конкретного языка первым делом транслируется в общую промежуточную форму, которая последовательно обрабатывается для выработки на стадии генерации машинно-зависимого кода. Машинно-независимая оптимизация, такая как выделение общих подвыражений и вынесение инвариантного кода, применяется к промежуточному коду. Машинно-зависимая оптимизация применяется к результату стадии генерации кода и использует набор команд конкретного процессора. Эта оптимизация известна как "щелевая" оптимизация, потому что эти преобразования выполняются внутри маленького окна (5 - 10 инструкций машинного уровня). Типичные примеры щелевой оптимизации включают удаление излишних операций загрузки/сохранения регистров, удаление недостижимого кода, выпрямление передач управления, алгебраические упрощения, снижение мощности (команд) и использование команд, специфических для конкретного процессора.
Методы оптимизации
Существуют различные методы машинно-зависимой и машинно-независимой оптимизации кода. Они могут применяться на всех синтаксических уровнях. Одним из простейших методов является "размножение констант". При его применении любая ссылка на константное значение замещается самим значением. В следующем примере повышается эффективность благодаря удалению трех адресных ссылок и замене их константами:
x = 2;
if( a < x && b < x)
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)
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 ¦
¦} while (k5 > 0); inc AX sal SI,2 ¦
¦ mov j5,AX add SI,AX ¦
¦ mov AX,k5 mov AX,k5 ¦
¦ imul AX,AX,3 mov DX,AX ¦
¦ push AX add DX,DX ¦
¦ mov AX,j5 add DX,AX ¦
¦ imul AX,AX,5 xchg AX,DX ¦
¦ mov BX,AX cwd ¦
¦ pop AX idiv SI ¦
¦ cwd mov I5,AX ¦
¦ idiv BX cmp k5,0 ¦
¦ mov i5,AX jnle L00e3 ¦
¦ cmp k5,0 ¦
¦ jg @10 ¦
+-------------------------------------------------------------+
¦ MICROSOFT WATCOM ¦
¦ C 5.0 C 6.0 ¦
¦ (46) (91) ¦
+-------------------------------------------------------------+
¦ mov j5,10000 mov j5,0 ¦
¦ mov k5,0 mov DI,10000 ¦
¦ mov CX,30000 L4 dec DI ¦
¦ sub SI,SI imul AX,DI,3 ¦
¦ $0265: inc j5 ¦
¦ sub CX,3 imul BX,j5,5 ¦
¦ add SI,5 cwd ¦
¦ mov AX,CX idiv BX ¦
¦ cwd mov i5,AX ¦
¦ idiv SI test DI,DI ¦
¦ mov DI,AX jg L4 ¦
¦ or CX,CX ¦
¦ jg $0265 ¦
¦ mov i5,DI ¦
+-------------------------------------------------------------+
¦ Компилятор Microsoft C 5.0 выполнил снижение мощности на ¦
¦ константном выражении и разместил в регистрах все ¦
¦ переменные внутри простого цикла, включая вычисляемое ¦
¦ значение i5. Высокая степень проведенного анализа цикла ¦
¦ демонстрируется тем, что заключительные состояния k5 и j5 ¦
¦ были определены заранее компилятором, а не позже, во ¦
¦ время выполнения. ¦
L--------------------------------------------------------------
"Вынесение инвариантного (неизменяющегося) кода" - один из путей ускорения циклов, заключающийся в вынесении выражений за пределы цикла, если значения, ими вычисляемые, являются неизменными во время выполнения цикла. Если инвариантный код выносится из следующего цикла:
unsigned char i,j,k,v,x;
for( i = 0; i < v; i++)
x = i * (j+k);
его логический эквивалент будет:
T1 = j + k;
for(i = 0; i < v; i++)
x = i * T1;
--------------------------------------------------------------¬
¦РИСУНОК 3: Вынесение инвариантного кода - Microsofr C 5.0 ¦
+-------------------------------------------------------------+
¦Исходный текст на Си MICROSOFT COMPUTER INNOVATIONS ¦
¦ C 5.0 C86Plus 1.10 ¦
+-------------------------------------------------------------+
¦for(i4=0;i4<=2;i4++) sub SI,SI mov i4,0 ¦
¦ ivector2[i4] =j*k; mov AX,j jmp L44@2 ¦
¦ imul k L9@2: ¦
¦ mov [BP-4],AL mov AX,j ¦
¦ $L20007: imul k ¦
¦ mov AL,[BP-4] mov SI,i4 ¦
¦ mov ivector2[SI],AL ¦
¦ inc SI mov ivector2[SI],AL¦
¦ cmp SI,2 inc i4 ¦
¦ jle $L20007 L44@2: ¦
¦ mov i4,SI cmp i4,2 ¦
¦ jle L9@2 ¦
+-------------------------------------------------------------+
¦ Вынесение инвариантного кода уменьшает время выполнения ¦
¦ цикла путем вынесения неизменяющихся выражений из тела ¦
¦ цикла. В отличие от Computer Innovations C86Plus 1.10, ¦
¦ компилятор Microsoft C 5.0 успешно выносит выражение j * h ¦
¦ за пределы цикла, так что оно выполняется только один раз, ¦
¦ вместо того, чтобы выполняться на каждой итерации цикла. ¦
L--------------------------------------------------------------
Рис. 3 демонстрирует вынесение инвариантного кода компилятором Microsoft C 5.0.
Дальнейший анализ примера показывает, что значение переменной i, индекса цикла, изменяется непосредственно с каждой итерацией. Отдельное присваивание i, известной
как "переменная индукции цикла", может быть удалено:
T1 = j + k;
for(x = 0; x< T1 * v; x += T1);
i = v;
Поскольку использование переменных - индексов цикла во внутренних выражениях цикла общеупотребительно, удаление переменных индукции цикла вместе со связанными с ними "снижениями мощности", может значительно улучшить исполнение программы. Рис. 4 показывает пример удаления переменной индукции цикла.
--------------------------------------------------------------¬
¦РИСУНОК 4: Удаление переменных индукции цикла ¦
+-------------------------------------------------------------+
¦Исходный текст на Си MICROSOFT DATALIGHT ¦
¦ C 5.0 Optimum-C 3.14 ¦
+-------------------------------------------------------------+
¦for(i=0;i<100;i++) mov AX,0 ¦
¦ ivector5[i*2+3]=5; mov i,100 mov i,AX ¦
¦ mov SI,OFFSET ivector5+6 cmp AX,100 ¦
¦ $L20006: jge L134 ¦
¦ mov [SI],5 L11B: ¦
¦ add SI,4 mov BX,i ¦
¦ cmp SI,OFFSET ivector5+406 shl BX,1 ¦
¦ jb $L20006 shl BX,1 ¦
¦ mov ivector+6[BX],5 ¦
¦ inc i ¦
¦ cmp i,100 ¦
¦ jl L11B ¦
¦ L134: ¦
+-------------------------------------------------------------+
¦ Удаление переменных индукции цикла помогает минимизировать ¦
¦ время, проводимое в каждой итерации цикла, путем вынесения ¦
¦ индексирующих цикл переменных (переменных индукции) из ¦
¦ тела цикла. В то время, как компилятор Datalight Optimum-C ¦
¦ использует переменную индукции i для индексации массива ¦
¦ ivector5, компилятор Microsoft C 5.0 удаляет ее благодаря ¦
¦ накоплению смещения для каждого элемента массива и ¦
¦ добавлению результата к базовому адресу массива. ¦
L--------------------------------------------------------------
"Слияние циклов" минимизирует управляющие заголовки циклов путем сращивания кода из циклов, имеющих одинаковые управляющие заголовки, в один цикл. Для того, чтобы удалить управляющий заголовок второго цикла, два простых цикла
for(i = 0; i < 10; i++)
a = b + c;
for(i = 0; i < 10; i++)
d = e + f;
могут быть объединены в один цикл
for(i = 0; i < 10; i++) {
a = b + c;
d = e + f;
}
Поскольку для поддержки слияния циклов требуется процедурная оптимизация, в общем случае это действие не выполняется. Ни один из включенных в обзор компиляторов этот метод не применяет.
Непосредственно связано со слиянием циклов "разворачивание циклов", которое минимизирует количество проходов через цикл путем увеличения числа операций, выполняемых внутри каждой итерации. Цикл инициализации массива
int a[3];
int i;
for(i = 0; i < 3; i++)
a[i] = 0;
странслированный компилятором без оптимизации, может получить следующий эквивалент в языке ассемблера:
mov i,0
LOOP:
mov BX,i
shl BX,1
mov a[BX],0
inc i
cmp i,3
jl LOOP
В том же коде, оптимизированном по методу разворачивания цикла, удаляется цикл путем замещения его тремя инструкциями присваивания:
mov a,0
mov a+2,0
mov a+4,0
Хотя ни один из компиляторов, включенных в обзор, не выполняет буквальное разворачивание циклов, некоторые из них оптимизируют цикл путем использования "специализированных инструкций прцессора". Многие процессоры предоставляют специализированные инструкции для управления перемещением блоков данных, инициализации памяти и других часто встречающихся ситуаций управления данными. К примеру, строковые инструкции с префиксом повторения (в семействе процессоров 80x86), выполняющиеся быстрее, чем посимвольные команды в цикле. Оптимизирующий компилятор использует, когда возможно, инструкции процессора для управления ситуациями в специальных случаях. Применение специализированных инструкций процессора к расширенной версии предыдущего примера разворачивания циклов
int a[10000];
int i;
for(i = 0; i < 10000; i++)
a[i] = 0;
дает приведенный ниже ассемблерный код процессора 80x86. Он гораздо быстрее, чем его аналог, записанный в виде цикла или набора инструкций непосредственной засылки в память, имеющего соответствующую длину:
mov CX,10000
mov i,CX
sub AX,AX
mov DI,offset a
push DS
pop ES
cld
rep stosw
"Минимизация заголовков вызова функций" может существенно уменьшить время выполнения в структурированной программе. При вызове функции параметры передаются вызываемой подпрограмме в стеке, находящемся в оперативной памяти. Набор инструкций некоторых процессоров содержит инструкции, которые поддерживают потребности Си и других структурированных языков высокого уровня в установке адресации фрейма стека перед выполнением кода функции и восстановлении стекового фрейма перед завершением.
Начиная с процессора Intel 80186, семейство микропроцессоров 80x86 предоставляет инструкции ENTER и LEAVE для обработки вызовов функций. Полезность инструкции ENTER снижается, так как ее выполнение занимает гораздо больше временных циклов процессора, чем выполнение последовательности команд, осуществляющих засылку в стек базового указателя и вычитание необходимого количества байт для фрейма из указателя стека.
Альтернативой использованию стека для передачи параметров функции является задание корректно определенного протокола для передачи стольких параметров, сколько возможно, в регистрах. Если доступно достаточное количество регистров чтобы передать все параметры функции, и вызываемая функция не использует локальные переменные, то отпадает необходимость генерации кода для пролога и эпилога функции (они обычно нужны для установки адресации фрейма стека). Компилятор WATCOM C 6.0 использует этот подход (см. рис. 5). Существенное приращение скорости получается потому, что не только удаляются инструкции, но и потому, что параметры уже регистровые и могут обрабатываться более эффективно.
--------------------------------------------------------------¬
¦РИСУНОК 5: Строение заголовка вызова функции ¦
+-------------------------------------------------------------+
¦Исходный текст на Си MICROSOFT WATCOM ¦
¦(x)-врем. циклы C 5.0 C 6.0 ¦
+-------------------------------------------------------------+
¦
/*Тест вызова funcall funcall ¦
¦ функции */ push bp push DX ¦
¦int funcall() mov BP,SP xor DX,DX ¦
¦{ sub SP,2 L4 mov AX,DX <-¬ ¦
¦ int i; push SI call dummy ¦ ¦
¦ sub SI,SI inc DX (23)¦
¦ for(i=0;i<20000;i++) $L20008: cmp DX,2000 ¦ ¦
¦ { dummy(i); } ; push SI <-¬ jl L4 <-- ¦
¦} call dummy ¦ pop DX ¦
¦ add SP,2 (31) ret ¦
¦int dummy(i) inc SI ¦ ¦
¦int i; cmp SI,20000 ¦ ¦
¦{ jl $L20008 <-- ¦
¦ return (i+1); mov [BP-2],SI ¦
¦} pop SI ¦
¦ leave ¦
¦ ret ¦
¦ ¦
¦ --> dummy push BP dummy inc AX <-¬(13)¦
¦ ¦ mov BP,SP ret <-- ¦
¦ (28)¦ mov AX,[BP+4] ¦
¦ ¦ inc AX ¦
¦ ¦ leave ¦
¦ L-> ret ¦
+-------------------------------------------------------------+
¦ Подобно большинству компиляторов Си Microsoft C 5.0 ¦
¦ передает параметры функциям путем засылки их в стек. ¦
¦ Всякий раз при вызове выполняется заголовок, так как ¦
¦ функция должна установить адресацию базирующихся на стеке ¦
¦ параметров. Однако компилятор WATCOM C 6.0 удаляет ¦
¦ стековый заголовок благодаря передаче в регистрах стольких ¦
¦ параметров, сколько возможно. ¦
L--------------------------------------------------------------
Большинство компиляторов Си позволяют пользователю указывать, какой набор команд процессора должен использоваться при генерации кода. Хотя специализированные инструкции конкретного процессора и могут ускорить выполнение программы, но их применение может ограничить количество машин, на которых программа может работать.
В случае, когда скорость является критическим параметром, "замена вызова функции ее телом" может помочь в удалении заголовков вызова функций. Некоторые компиляторы предоставляют возможность заменять операторами вызовы функций из некоторого набора, либо генерировать их вызовы. Набор таких функций содержит некоторые общеупотребительные функции, такие как abs. Функции из этого набора называются встроенными. Эта оптимизация полезна для внутренних циклов, которые выполняются многократно. Набор доступных встроенных функций зависит от компилятора.
Компилятор, который генерирует прямой код для математического сопроцессора, ускоряет программу, которая выполняет много операций с плавающей точкой. Для того, чтобы поддерживать сопроцессор и максимизировать эффективность плавающей арифметики, оптимизирующий компилятор может генерировать непосредственно последовательность команд сопроцессора в противоположность использованию программной эмуляции функций плавающей арифметики.
При трансляции условных операторов генератор кода компилятора иногда генерирует инструкции перехода, которые передают управление на другие инструкции перехода. "Сжатие цепочки переходов" просто превращает связанное множество переходов в единственный переход от начала цепочки переходов к конечной цели.
Оптимизировать или нет?
Оптимизация - не панацея, и ее применение не бесплатно. В зависимости от степени оптимизации время, требуемое для компиляции программы, может значительно возрастать. Для небольших программ требуемое время можно не принимать во внимание, но для больших оно может иметь значение.
Оптимизация также может усложнить отладку вследствие генерации кода, который трудно непосредственно связать с исходными операторами в программе. Оптимизация может неожиданно ввести ошибки в код, сгенерированный из вполне правильного текста программы. Ситуация, когда на переменную ссылаются как непосредственно по имени, так и посредством одного или нескольких указателей, может затруднить работу компилятора по определению того, "жива" ли еще переменная и, следовательно, должна оставаться в регистре, или она "умерла" и тогда должна быть сохранена в памяти.
Вынесение инвариантного кода может быть потенциальным источником ошибок. В цикле
int a[10], x, y;
for(i = 0; i < 10; i++)
if( y != 0 )
a[i] = x / y;
оптимизирующий компилятор может определить, что выражение x/y есть инвариант, и вынесет его за пределы цикла, игнорируя проверку на 0 и создавая возможность возникновения ситуации деления на 0.
Когда компилятор выполняет удаление переменных индукции цикла он может непреднамеренно породить ситуацию переполнения, потому что он может переструктурировать вычисления, включающие индексы цикла. В приведенном ранее примере, где выполняется оптимизация, используя вынесение инвариантного кода и удаление переменных индукции цикла, переменная индукции i была извлечена, в результате имеем:
T1 = j + k;
for(x = 0; x < T1 * v; x += T1);
В этом случае, поскольку значения j, k и v неизвестны, существует возможность переполнения для выражения T1 * v. Цикл может не закончиться.
Тестирование компиляторов
PC Tech Journal разработал тест оптимизации Си (см. листинг 1) как подспорье в оценке оптимизационных возможностей компиляторов Си. Тест проверяет степень оптимизации, проводимой компилятором. Для обеспечения основы для сравнения измерений времени выполнения для каждого компилятора запускался тест исполнения PC Tech Journal с ключами, разрешающими оптимизацию. Результаты его работы для каждого компилятора суммируются в таблице 1. Рисунок 6 демонстрирует опции оптимизации для каждого компилятора, которые использовались при компиляции обоих тестов. Характеристики выполнения программ можно сравнить с измерениями без оптимизации, приведенными в февральском номере за 1988 год (см. стр. 62 и 80).
Целью обоих тестов, исполнения и оптимизации, было получить наиболее быстрый код, который может дать каждый компилятор. Если компилятор предоставляет опции для генерации кода, они выбирались с приоритетом времени выполнения над размером программного кода, генерировались команды микропроцессора 80286 и непосредственные команды сопроцессора 80287, запрещалось проверять переполнение стека. Таким образом, минимальная конфигурация системы, требуемая для запуска тестов в том виде, в каком они компилировались, - машина с процессором 80286 и математическим сопроцессором 80287.
Многие компиляторы также имеют опции для генерации кода процессоров 80186 и NEC V20/V30, которые могут использоваться для машин класса XT (см. "Chips in transitions", Bob Smith, апрель 1986г., стр. 56). Эти процессоры имеют большинство средств 80286, исключая команды защищенного режима, так что сгенерированный для них код совпадает с кодом для 80286.
----------------------------------------------------¬
¦РИСУНОК 6: Командные строки ¦
+---------------------------------------------------+
¦ ¦
¦ BORLAND TURBO C 1.5 ¦
¦ : tcc -1 -f87 -N- -S -O -G -Z -r optbench.c ¦
¦ ¦
¦ COMPUTER INNOVATIONS C86PLUS 1.10 ¦
¦ : cc -DNO_ZERO_DIVIDE=1 -c -FPi87 -Oatx ¦
¦ -G2 -Fa optbench.c ¦
¦ ¦
¦ DATALIGHT OPTIMUM-C 3.14 ¦
¦ : dlc1 optbench.c -f-g ¦
¦ dlg optbench.tmp +vbe +all ¦
¦ dlc2 optbench.tmo ¦
¦ ¦
¦ LATTICE MS-DOS C 3.2 ¦
¦ : lc -d -k2 -f -v optbench.c ¦
¦ ¦
¦ MANX AZTEC C86 4.0 ¦
¦ : cc -A +A -B -T +F +2 +ef optbench.c ¦
¦ ¦
¦ METAWARE HIGH C 1.4 ¦
¦ : hc optbench.c -def NO_ZERO_DIVIDE=1 ¦
¦ pragma Off(Check_stack, Check_subscript) ¦
¦ pragma On(286, asm, auto_reg_alloc) ¦
¦ pragma On(floating_point, optimize_xjmp) ¦
¦ pragma On(optimize_xjmp_space, use_reg_vars) ¦
¦ ¦
¦ MICROSOFT C 5.0 ¦
¦ : cl -DNO_ZERO_DIVIDE=1 -c -G2 -Fc ¦
¦ -Ox optbench.c ¦
¦ ¦
¦ MICROSOFT QUICKC 1.0 ¦
¦ : qcl -c -G2 -FPi87 -Ox d:\optbench.c ¦
¦ ¦
¦ WATCOM C 6.0 ¦
¦ : wcc d:\optbench.c /d1 /oilt /s /2 /7 ¦
+---------------------------------------------------+
¦ Выполняемый код для тестов оптимизации и ¦
¦ исполнения, которые использованы в этой статье, ¦
¦ генерировался с помощью этих командных строк с ¦
¦ указанными директивами компиляторов. ¦
L----------------------------------------------------
Результаты теста исполнения для каждого компилятора в малой и большой моделях памяти приводятся в таблице 1. Тесты в наборе теста исполнения организованы в функции, которые вызывались из главной управляющей процедуры. Весь набор был скомпилирован и отредактирован в один файл EXE. Некоторые из процедур теста выполняются так быстро, что единственный вызов функции невозможно точно измерить. В этих случаях функции вызываются из управляющей процедуры многократно, чтобы увеличить время выполнения для получения возможности количественных измерений. В таблице 1 приводится количество итераций для каждого теста.
--------------------------------------------------------------¬
¦Таблица 1: Результаты оптимизированного теста выполнения ¦
+-------------------------------------------------------------+
¦ COMPUTER ¦
¦ BORLAND INNOVATIONS DATALIGHT ¦
+----------------------T------------T------------T------------+
¦КОМПИЛЯТОР ¦ Turbo C ¦ C86Plus ¦ Optimum-C ¦
+----------------------+------------+------------+------------+
¦ВЕРСИЯ ¦ 1.5 ¦ 1.10 ¦ 3.14 ¦
+----------------------+------------+------------+------------+
¦ЦЕНА ¦ $99.95 ¦ $497 ¦ $139 ¦
+----------------------+------------+------------+------------+
¦РАЗМЕР ПРГРАММЫ(KB) ¦ 35/40 ¦ 30/38 ¦ 33/40 ¦
+----------------------+------------+------------+------------+
¦ОБЩИЕ ОПЕРАЦИИ (*) ¦ ¦ ¦ ¦
¦Вызовы функций ¦ 6.0/7.2 ¦ 7.6/8.2 ¦ 6.0/7.6 ¦
¦Целочисл. арифметика ¦ 7.0/7.0 ¦ 8.5/8.5 ¦ 6.3/6.3 ¦
¦Арифм-ка длинных целых¦ 29.0/29.0 ¦ 23.4/23.9 ¦ 26.3/26.9 ¦
¦Индексация ¦ 7.9/9.9 ¦ 7.9/11.4 ¦ 5.9/7.9 ¦
¦Использ-е указателей ¦ 6.2/15.3 ¦ 12.9/19.2 ¦ 6.8/15.3 ¦
¦ С регистровыми ¦ ¦ ¦ ¦
¦ переменными ¦ 6.8/15.2 ¦ 10.3/19.8 ¦ 6.8/15.3 ¦
¦Решето (Sieve) ¦ 5.0/5.0 ¦ 5.8/5.8 ¦ 4.3/3.8 ¦
¦ С регистровыми ¦ ¦ ¦ ¦
¦ переменными ¦ 6.4/6.5 ¦ 4.6/4.6 ¦ 4.3/3.8 ¦
+----------------------+------------+------------+------------+
¦ОПЕРАЦИИ С ФАЙЛАМИ ¦ ¦ ¦ ¦
¦Чтение и запись (**) ¦ ¦ ¦ ¦
¦ С дискеты на дискету¦ 8.2/8.2 ¦ 8.3/8.3 ¦ 8.3/8.2 ¦
¦ С жесткого диска ¦ ¦ ¦ ¦
¦ на жесткий диск ¦ 3.9/3.4 ¦ 3.9/3.9 ¦ 3.9/3.3 ¦
¦Getc и putc (***) ¦ ¦ ¦ ¦
¦ С дискеты на дискету¦ 49.8/50.6 ¦ 45.6/50.1 ¦ !13.5!/49.4¦
¦ С жесткого диска ¦ ¦ ¦ ¦
¦ на жесткий диск ¦ 17.6/18.4 ¦ 18.9/21.1 ¦ !5.5!/17.3 ¦
+----------------------+------------+------------+------------+
¦ОПЕРАЦИИ 80x87 ¦ ¦ ¦ ¦
¦Сложение/умножение (*)¦ 3.1/3.1 ¦ 2.8/2.8 ¦ 3.1/3.1 ¦
¦Нат. логарифм (****) ¦ 1.0/1.0 ¦ 1.3/1.3 ¦ 1.3/1.2 ¦
¦Синус/тангенс(****) ¦ 1.1/1.1 ¦ 1.5/1.5 ¦ 1.2/1.3 ¦
+----------------------+------------+------------+------------+
¦ Время измерялось в секундах и приводится для ¦
¦ малой/большой моделей памяти. ¦
¦ Тесты выполнялись на IBM PC/AT с тактовой частотой 6 ¦
¦ мегагерц, с сопроцессором 80287, с параметрами в ¦
¦ CONFIG.SYS FILES = 20 и BUFFERS = 20. ¦
¦ Значения, входящие в 10%-ю окрестность лучшего ¦
¦ результата, заключены в восклицательные знаки. ¦
¦ * - 20 итераций, ** - 1 итерация, *** - 2 итерации, ¦
¦ **** - 10 итераций. ¦
L--------------------------------------------------------------
--------------------------------------------------------------¬
¦Таблица 1: Продолжение ¦
+-------------------------------------------------------------+
¦ ¦
¦ LATTICE MANX METAWARE MICROSOFT WATCOM ¦
+---------T---------T---------T---------T---------T-----------+
¦MS-DOS C ¦Aztec C ¦High C ¦ C ¦QuickC ¦WATCOM C ¦
+---------+---------+---------+---------+---------+-----------+
¦3.2 ¦4.0 ¦1.4 ¦5.0 ¦1.0 ¦6.0 ¦
+---------+---------+---------+---------+---------+-----------+
¦$500 ¦$499 ¦$595 ¦$450 ¦$99 ¦$295 ¦
+---------+---------+---------+---------+---------+-----------+
¦34/41 ¦20/24 ¦33/44 ¦28/39 ¦31/44 ¦25/30 ¦
+---------+---------+---------+---------+---------+-----------+
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦7.5/8.1 ¦7.9/8.6 ¦6.9/9.5 ¦6.1/6.0 ¦6.5/7.5 ¦!3.8/4.5! ¦
¦7.7/7.7 ¦9.1/9.2 ¦5.8/5.8 ¦5.3/5.2 ¦6.8/6.8 ¦!3.7/3.8! ¦
¦23.3/24.3¦23.9/24.2¦27.8/29.1¦23.9/24.8¦27.8/28.7¦!20.0/21.0!¦
¦11.0/34.9¦9.0/10.5 ¦7.1/7.8 ¦!4.8!/7.2¦7.9/11.3 ¦5.4/!5.5 ¦
¦12.3/58.5¦12.8/15.3¦5.4/15.3 ¦!5.1!/9.8¦7.8/17.8 ¦6.1/!6.2! ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦12.8/58.6¦7.8/15.3 ¦!5.2!/15.3!5.1!/9.8¦7.7/17.8 ¦5.6/!6.2! ¦
¦7.1/6.9 ¦7.6/7.6 ¦5.4/5.6 ¦4.2/4.3 ¦5.3/5.4 ¦!3.2/3.4! ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦6.9/7.0 ¦5.9/6.1 ¦5.8/6.0 ¦4.2/4.3 ¦6.5/6.5 ¦!3.2/3.4! ¦
+---------+---------+---------+---------+---------+-----------+
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦8.2/8.2 ¦8.3/8.2 ¦8.0/8.0 ¦8.3/8.2 ¦8.2/8.3 ¦8.2/8.2 ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦3.9/3.7 ¦3.9/2.8 ¦!1.0/0.9!¦3.3/3.8 ¦3.9/3.4 ¦3.4/3.4 ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦51.3/51.5¦28.6!27.7!39.8/39.8¦40.0/40.0¦40.0/40.0¦51.2/51.3 ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦21.0/26.0¦12.5!11.0!16.0/15.2¦14.8/15.7¦16.1/16.0¦19.2/20.1 ¦
+---------+---------+---------+---------+---------+-----------+
¦ ¦ ¦ ¦ ¦ ¦ ¦
¦4.7/4.7 ¦2.6/2.6 ¦2.6/2.1 ¦!1.7/1.7!¦3.1/3.0 ¦1.8/1.8 ¦
¦1.3/1.3 ¦1.1/1.1 ¦1.1/1.2 ¦1.0/1.0 ¦1.2/1.3 ¦!0.9/0.9! ¦
¦1.9/1.9 ¦1.3/1.3 ¦1.1/1.2 ¦1.1/1.1 ¦1.3/1.4 ¦!1.0/1.0! ¦
+---------+---------+---------+---------+---------+-----------+
¦ Компиляторам задавались ключи для оптимизации по ¦
¦ скорости, использования непосредственных инструкций ¦
¦ процессоров 80286 и 80287. Все тесты, интенсивно ¦
¦ использующие процессор, были выиграны компиляторами ¦
¦ WATCOM и Microsoft. Не нашлось компилятора, код которого ¦
¦ для тестов ввода/вывода выполнялся бы во время, близкое к ¦
¦ лучшему, в малой и в большой моделях памяти одновременно. ¦
L--------------------------------------------------------------
При сравнении результатов в таблице 1 и в номере за февраль 1988 необходимо отметить одно изменение. Два теста с использованием регистровых переменных (использования указателей и "решето"-sieve) в феврале были измерены для 100 итераций, а не для 20-ти. Поскольку полезно непосредственное сравнение тестов с использованием регистровых переменных и без их использования, тесты с регистровыми переменными в данном случае запускались с 20-ю итерациями. Также заметьте, что численные тесты, присутствующие в таблице 1, выполнялись для прямого кода процессоров 80x87 в малой и большой моделях памяти, а не с помощью программного эмулятора.
Поскольку текст теста оптимизации предназначен для проверки наличия или отсутствия отдельных типов
оптимизации, он состоит из набора отдельных, не связанных фрагментов программ, и не представляет собой целостное, проблемно-ориентированное тело программы. Тест организован как основная функция (main), содержащая большинство фрагментов кода для оптимизации, и несколько отдельных функций, с аргументами или без них. Эти функции демонстрируют не только отдельные методы оптимизации, но также оптимизацию пролога и эпилога выполняемых функций. С целью обеспечения максимальных возможностей для оптимизации, основанной на времени жизни отдельной переменной, большинство переменных теста являются глобальными. Многие возможности обеспечены специально для общих методов оптимизации, таких как удаление лишних сохранений (присваиваний), размножение констант и размещение переменных в регистрах.
Процесс оптимизации кода сложен, и степень повышения эффективности зависит не только от типа и изощренности методов оптимизации компилятора, но также и от того, как исходный текст программы написан и структурирован. Результат также зависит от того, как в исходном тексте используются переменные и выражения.
В таблице 2 собрана информация о том, какие приемы оптимизации выполнялись каждым компилятором на тексте теста. Каждый компилятор из рассматриваемого набора выполняет простейшие приемы оптимизации, такие как свертка констант и алгебраические упрощения. Большинство применяют методы оптимизации некоторого промежуточного уровня, включающего снижение мощности и удаление общих подвыражений. Некоторые выполняют оптимизацию высокого уровня, такую как вынесение инвариантного кода и удаление переменных индукции циклов. Ни один не выполняет успешно слияние циклов, и только Datalight Optimum-C делает попытки, далеко не удовлетворительные, применения глубокого удаления общих подвыражений.
--------------------------------------------------------------¬
¦Таблица 2: Результаты теста оптимизации ¦
+-------------------------T---T---T---T---T---T---T---T---T---+
¦ КОМПИЛЯТОР ВЕРСИЯ ¦ 1 ¦ 2 ¦ 3 ¦ 4 ¦ 5 ¦ 6 ¦ 7 ¦ 8 ¦ 9 ¦
+-------------------------+---+---+---+---+---+---+---+---+---+
¦МЕТОДЫ ОПТИМИЗАЦИИ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦Свертка констант (целых) ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦
¦Свертка констант (плав.) ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦
¦Размножение констант ¦ ¦ ¦ * ¦ ¦ ¦ * ¦ * ¦ ¦ * ¦
¦Размножение копий ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ ¦ * ¦
¦Алгебр.упрощения ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦
¦Подавление деления на 0 ¦ ¦ * ¦ ¦ ¦ ¦ * ¦ * ¦ ¦ * ¦
¦Удаление подвыражений ¦ ¦ ¦ * ¦ * ¦ * ¦ * ¦ * ¦ ¦ * ¦
¦Снижение мощности ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦
¦Удаление излишних ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ загрузок/сохранений ¦ * ¦ ¦ * ¦ * ¦ * ¦ * ¦ * ¦ ¦ * ¦
¦Удаление недостижи- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ мого кода ¦ * ¦ * ¦ * ¦ * ¦ ¦ * ¦ * ¦ ¦ * ¦
¦Удаление излишних ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ присваиваний ¦ ¦ * ¦ * ¦ ¦ ¦ * ¦ * ¦ ¦ * ¦
¦Использ. машинно- ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ зависимых команд ¦ ¦ * ¦ ¦ * ¦ ¦ * ¦ * ¦ * ¦ * ¦
¦Поддержка встроенных ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ функций ¦ ¦ ¦ ¦ ¦ ¦ ¦ * ¦ ¦ * ¦
¦Размещение переменных ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ в регистрах ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦
¦Непосредственные инструк-¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ции 80287 ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ * ¦ ¦ * ¦
¦Сжатие цепочки переходов ¦ * ¦ ¦ * ¦ * ¦ ¦ * ¦ * ¦ ¦ * ¦
¦Вынесение инвариантного ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ кода ¦ ¦ ¦ ¦ ¦ ¦ ¦ * ¦ ¦ ¦
¦Удаление переменных ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ индукции циклов ¦ ¦ ¦ ¦ ¦ ¦ ¦ * ¦ ¦ ¦
¦Удаление циклов ¦ ¦ ¦ ¦ ¦ ¦ ¦ * ¦ ¦ ¦
¦Удал. глуб. подвыражений ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦Разворачивание циклов ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦Слияние циклов ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+-------------------------+---+---+---+---+---+---+---+---+---+
¦ 1 - BORLAND Turbo C 1.5, 2 - COMPUTER INNOVATIONS ¦
¦ C86Plus 1.1, 3 - DATALIGHT Optimum-C 3.14, 4 - LATTICE ¦
¦ MS-DOS C 3.2, 5 - MANX Aztec C 4.0, 6 - METAWARE High C ¦
¦ 1.4, 7 - MICROSOFT C 5.0, 8 - MICROSOFT QuickC 1.0, 9 - ¦
¦ WATCOM C 6.0. ¦
¦ * - компилятор применяет этот метод оптимизации. ¦
+-------------------------------------------------------------+
¦ Большинство включенных в обзор компиляторов языка Си ¦
¦ поддерживают простые методы оптимизации, такие как ¦
¦ алгебраические упрощения, и только несколько компиляторов ¦
¦ применяют более сложные формы, такие как удаление общих ¦
¦ подвыражений. ¦
L--------------------------------------------------------------
Borland International.
Выход компилятора Turbo C представляет собой разумный, но не очень оптимизированный код. Кроме свертки констант, удаления лишних загрузок регистров и алгебраических упрощений, компилятор выполняет только снижение мощности, удаление недостижимого кода и размещение переменных в регистрах. Он не поддерживает другие общие методы оптимизации, такие как удаление лишних сохранений, общих подвыражений и переменных индукции цикла, а также вынесение инвариантного кода.
Turbo C разумно управляет прологом и эпилогом функций и использованием регистров, засылая в стек и извлекая только те регистры, которые явно используются внутри тела функции.
Computer Innovation Inc.
Компилятор C86Plus вырабатывает хороший код со средним уровнем оптимизации. Он выполняет базовые приемы оптимизации, такие как свертка констант и размножение копий. Однако он не выполняет размножение констант для удаления лишних сохранений.
Хотя компилятор успешно выполняет алгебраические упрощения, он порождает лишние инструкции из-за того, что размещает результаты в регистрах, вместо того, чтобы помещать их в переменные. Этот эффект проявляется в том, что при размещении переменных в регистрах предпринимаются попытки переразмещения, так как при выполнении нескольких операторов результаты в действительности должны быть присвоены соответствующим переменным.
Хотя C86Plus успешно справляется со сверткой явных дублирующихся присваиваний в одно присваивание, удаление лишних сохранений он выполняет неустойчиво. Единственное лишнее присваивание в функции dead_code остается единственной командой после того, как компилятор удаляет недостижимый код из функции.
C86Plus - один из нескольких компиляторов рассматриваемого набора, который преобразует инициализацию элементов массива из функции проверки разворачивания циклов в эквивалентную команду STOSW процессора 80x86 с префиксом REP. Однако, что касается разумного уровня оптимизации в других областях, то он не смог решить задачу преобразования цепочки переходов в функции jump_chain_compression в один переход. Он не выполняет существенную оптимизацию циклов.
Datalight Inc.
С появлением Optimum-C Datalight стала одним из первых поставщиков, предложивших оптимизирующий компилятор. Хотя набор тестов не подтвердил наглядно претензии Datalight на глобальную оптимизацию, Optimum-C сработал так хорошо в некоторых фрагментах теста, что он продемонстрировал слабые фрагменты набора, требующие изменений для усовершенствования желаемой проверки. Например, в первой версии функции jump_compression не возвращалось значение, что делало все вычисления и присваивания в функции лишними. Optimum-C выявил это и удалил большую часть кода функции, включая цепочку переходов.
В тесте размножения констант и копий Optimum-C определил, что присваивание i5 в обоих условных операторах является излишним по отношению к последующим присваиваниям. Компилятор удалил не только эти присваивания, но и условные операторы.
Неудовлетворительным оказалось удаление лишних сохранений значений регистров. Optimum-C удалил одно лишнее присваивание, i=k5, в тесте размножения констант и копий и лишнее присваивание в функции dead_code. Он не удалил второе лишнее присваивание, i=2, в тесте размножения констант и копий, и k=2, дублируемое присваивание.
Optimum-C - единственный компилятор, который пытался выполнить глубокое удаление общих выражений. Проверка сгенерированного кода показала, что общее выражение i5+i2 было перемещено выше первого базового блока условного оператора, но не было удалено из второго.
Вне ограничений на стандартное использование регистров, накладываемых семейством микропроцессоров 80x86, Optimum-C разумно использует регистры. В функции jump_compression каждый передаваемый параметр был помещен в регистр. Внутри тела функции не было ссылок в память, кроме начальной засылки в регистры.
Одной важной областью, в которой компилятор Optimum-C требует улучшений, является оптимизация циклов. Компилятор не пытается выполнять вынесение инвариантного кода и удаление переменных индукции цикла.
Тест выполнения показал, что компилятор Datalight очень эффективно управляет вводом/выводом getc/putc, а остальные тесты выполняются в приемлемое время.
Lattice Inc.
Имеющий большую историю компилятор Lattice MS-DOS C последовательно совершенствовался с каждой новой версией. Он известен как генератор стабильного, предсказуемого кода и выполняет умеренную оптимизацию. Lattice С выполняет снижение мощности, сжатие цепочки переходов и удаление общих подвыражений. Он не удаляет дублирующиеся присваивания после теста встроенных функций и лишние присваивания в функции dead_code. Хотя он не генерирует никакого кода для недостижимого printf в функции dead_code, компилятор Lattice C генерирует ненужный безусловный переход к LEAVE, которая является следующей инструкцией.
Единственными сгенерированными машинно-зависимыми инструкциями были ENTER и LEAVE, инструкции микропроцессоров 80x86 для прологов и эпилогов функций. Это сомнительное благо, поскольку выполнение ENTER требует больше циклов микропроцессора, чем установка адресации стекового фрейма отдельными инструкциями. Lattice C не выполняет оптимизацию циклов.
Manx Software Systems Inc.
Компилятор Aztec C86 сгенерировал хороший код с довольно хорошим уровнем оптимизации. Кроме свертки констант и алгебраических упрощений, Aztec C86 выполнил снижение мощности и удаление общих подвыражений. Однако, он не выполнил удаление лишних присваиваний и не удалял недостижимый код. Aztec C86 сгенерировал код для недостижимого оператора printf вместе с безусловным переходом через него.
Поскольку любая программа на Си имеет значительное количество вызовов функций, заголовок каждого вызова необходимо минимизировать. Aztec C86 использует необычный, но эффективный подход к решению этой проблемы. На выходе компилятора получается текст в языке ассемблера, который обрабатывается отдельным ассемблером. Компилятор вставляет в текст директивы условного ассемблирования вокруг кода, который устанавливает стековый фрейм и сохраняет регистры. После генерации кода функции компилятор определяет символы для управления установкой стекового фрейма и сохранения только тех регистров, которые используются в функции.
Aztec C86 не смог решить задачу преобразования цепочки переходов в один переход к конечной цели. Он также не выполнял оптимизацию циклов.
Metaware Inc.
High C вырабатывает хороший код со средним уровнем оптимизации. Компилятор выполняет все базовые виды оптимизации, включая свертку констант и алгебраические упрощения, удаление лишних операций загрузки регистров, снижение мощности и удаление общих подвыражений. Компилятор Metaware удаляет недостижимый код из функции dead_code, но не удаляет лишние присваивания.
High C разумно использует машинно-зависимые инструкции. Компилятор усовершенствует загрузку констант с плавающей точкой, используя команду копирования строк MOVS процессоров 80x86 для записи значений с плавающей точкой, вычисленных во время компиляции. Он также генерирует инструкцию LEAVE процессоров 80x86 для эпилога функций, но устанавливает адресацию стекового фрейма в прологе функции с помощью отдельных инструкций, а не используя более длительную инструкцию ENTER.
Компилятор High C не выполняет вынесение инвариантного кода, важный метод оптимизации циклов. Он также не смог применить успешно удаление переменных индукции циклов. Встроенные функции поддерживаются для нескольких целочисленных и строковых операций, таких как strlen.
Microsoft C.
В версии 5.0 своего компилятора Си корпорация Microsoft вывела высокий уровень оптимизации кода на рынок PC. Microsoft уделяет много внимания анализу циклов. C 5.0 – единственный из рассматриваемых компиляторов, который выполняет вынесение инвариантного кода и настоящее удаление переменных индукции циклов. Компилятор Microsoft C 5.0 превосходно использует регистры, стараясь минимизировать обращения к памяти в теле цикла (см. рис. 4 и 5).
Простой пример цикла в коде теста демонстрирует степень оптимизации циклов, выполняемой Microsoft C 5.0 (см. рис. 3). Компилятор применяет снижение мощности и полностью удаляет константное умножение, выявляет конечное состояние переменных j5 и k5, и помещает в регистры все переменные внутри цикла.
Другой хороший пример оптимизации циклов этим компилятором отражен в функции unnecessary_loop. C 5.0 удаляет цикл for и генерирует код только с целью установки конечного состояния переменной - индекса цикла и оператора, включенного в цикл. Компилятор также хорошо использует регистры.
Внимание фирмы Microsoft к оптимизации вознаграждается при работе теста выполнения. Он выполняется за время, которое является лучшим или близко к лучшему по каждой категории.
Microsoft QuickC.
Когда речь идет об оптимизации, QuickC становится настолько беспомощным, насколько C 5.0 изощренным. Код, сгенерированный QuickC, был в основном дословным переводом, насыщенным излишними загрузками и сохранениями регистров, переходами на переходы. Этот компилятор применяет лишь наиболее первичные методы оптимизации, свертку констант и некоторые алгебраические упрощения. Он сгенерировал недостижимый код, поместил переход через него и не смог выполнить сжатие цепочки переходов.
В пользу компилятора свидетельствует то, что что он разумно управляет прологами
и эпилогами функций, используя отдельные инструкции для установки адресации стекового фрейма при входе и инструкцию LEAVE при завершении функции. При входе сохраняются и при выходе восстанавливаются только те регистры, которые используются в теле функции.
QuickC был влючен в этот обзор, потому что он имеет ключ оптимизации в командной строке (-Ox). Генерируя код, который по своей природе - дословный перевод исходного текста, QuickC был разработан исключительно как быстрый прототип компилятора, но не как оптимизирующий компилятор.
WATCOM.
Новейший соперник, завоевывающий позиции на рынке компиляторов C - WATCOM C 6.0 (см. Product Watch, Philip N. Hisley, за этот месяц). C 6.0 вырабатывает компактный код, который прекрасно использует несколько ограниченный комплект регистров семейства 80x86. Кроме выполнения базовых приемов оптимизации, он поддерживает снижение мощности и удаление недостижимого кода и общих подвыражений. В то время, как Microsoft достигает улучшения кода благодаря оптимизации циклов, WATCOM увеличивает скорость путем уменьшения управляющих заголовков вызовов функций к их абсолютно минимальному размеру. Он достигает этого путем преимущественной передачи параметров через регистры, а не через стек.
WATCOM очень хорошо удаляет недостижимый код. C 6.0 не только удалил ненужные присваивания и недостижимый код внутри функции, но он также удалил пролог и эпилог функции и свернул всю функцию к простому возврату, приписав имя функции к инструкции возврата основной функции. В завершение всего, компилятор удалил локальный вызов функции.
Насколько C 6.0 изощрен в уничтожении бесполезной функции, настолько же он беспомощен при удалении бесполезного дублирующегося присваивания. Наиболее важная область, за которую WATCOM C 6.0, как и Optimum-C, не смог взяться, была оптимизация циклов. Он не поддерживает вынесение инвариантного кода и удаление переменных индукции циклов.
Хотя C 6.0 не выполняет разворачивание циклов в отдельные команды, он (также как Datalight Optimum-C и Computer Innovations C86Plus) использует команду REP/STOSW процессоров 80x86 для инициализации тестового массива, благодаря чему удаляет цикл.
Прекрасная генерация кода в WATCOM, в частности, разумное использование регистров, дает ему очень важное преимущество. В тесте выполнения он победил в большинстве тестов, интенсивно использующих процессор, и при этом выполнялся для большой модели в лучшее время, чем большинство других компиляторов для малой модели. К слабым сторонам WATCOM можно отнести ввод/вывод файлов, использование getc и putc. Здесь он близок к наихудшим компиляторам.
Выявленные лидеры
По существующему определению, любой компилятор, который выполняет не буквальное отображение исходного текста, выполняет некоторый вид оптимизации, даже если преобразование это такое низкоуровневое, как свертка констант. Минимальный приемлемый уровень оптимизации будет возрастать по мере того, как доступная на рынке технология генерации кода будет предоставлять более глубокие методы оптимизации. На сегодняшнем уровне технологии минимальным приемлемым уровнем оптимизации представляется удаление общих подвыражений. Этот уровень подразумевает, что компиляторы, которые выполняют удаление общих подвыражений, также выполняют основные приемы оптимизации, такие как свертка констант и алгебраические упрощения.
Даже с установленным минимальным уровнем оценка возможностей конкретных компиляторов усложняется существованием многих несоизмеримых форм оптимизации. Компилятор может хорошо использовать регистры, но не поддерживать удаление общих подвыражений. Поскольку оптимизированный код зависит не только от применяемых методов, но также и от структуры программы, которая оптимизировалась, в общем случае было бы заблуждением считать, что один компилятор лучше другого, опираясь исключительно на один отдельный тест.
Хотя все девять рассматриваемых компиляторов генерируют приемлемый код, три из них, - Datalight Optimum-C, Microsoft C 5.0 и WATCOM C 6.0, - выполняют оптимизацию кода более высокого уровня, чем остальные.
Компилятор Datalight Optimum-C - это быстрый и выразительный исполнитель. Он выполняет обширный анализ потоков данных и оптимизирует код, за который другие компиляторы не берутся.
Microsoft C 5.0 применяет оптимизацию циклов, которая является одной из областей с большими потенциальными возможностями улучшения кода. Применяя вынесение инвариантного кода, удаление переменных индукции циклов и очень качественное распределение переменных по регистрам, Microsoft C 5.0 вырабатывает прекрасный код.
Компилятор WATCOM C 6.0 соперничает с Microsoft C 5.0 по степени выполняемой оптимизации и генерирует наиболее быстрый код в тесте оптимизации. То, что WATCOM теряет на не самых оптимальных циклах, он более чем наверстывает в малых заголовках вызова функций. WATCOM C 6.0 хорошо использует регистры, минимизирует обращения к памяти и повышает эффективность выполнения программ.
Компиляторы Metaware High C и Computer Innovations C86Plus выполняют более-менее удовлетворительную степень оптимизации, но отступают на второй план при рассмотрении усовершенствований, сделанных в технологии компиляторов фирмами Datalight, Microsoft и WATCOM.
Нет единственного производителя, который захватил бы на рынке область технологии оптимизации для компиляторов Си. Конкуренция на рынке подталкивает производителей к развитию технологии и к обеспечению разработчиков лучшими и более мощными средствами языка Си. В будущем это может означать появление оптимизирующих компиляторов, которые будут вырабатывать более быстрый и компактный код.
ЛИСТИНГ 1: OPTBENCH.C
/* ---------------------------------------------------------- *
¦ ¦
¦ Серия тестов PC Tech Journal ¦
¦ Тест оптимизации кода Си ¦
¦ ¦
¦ Copyright (c) 1988 Ziff-Devis Publishing Company ¦
¦ ¦
¦ Эта программа-тест была разработана для проверки ¦
¦ методов оптимизации кода, применяемых компилятором ¦
¦ Си. Она не вырабатывает разумные результаты и не ¦
¦ представляет хороший стиль программирования. ¦
¦ ¦
* ---------------------------------------------------------- */
#include <stdio.h>
#include <string.h>
#define max_vector 2
#define constant5 5
typedef unsigned char uchar;
int i, j, k, l, m;
int i2, j2, k2;
int g3, h3, i3, k3, m3;
int i4, j4;
int i5, j5, k5;
double flt_1, flt_2, flt_3, flt_4, flt_5, flt_6;
int ivector[ 3 ];
uchar ivector2[ 3 ];
short ivector4[ 6 ];
int ivector5[ 100 ];
#ifndef NO_PROTOTYPES
void dead_code( int, char * );
void unnecessary_loop( void );
void loop_jamming( int );
void loop_unrolling( int );
int jump_compression( int, int, int, int, int );
#else
void dead_code();
void unnecessary_loop();
void loop_jamming();
void loop_unrolling();
int jump_compression();
#endif
int main( argc, argv ) /* optbench */
int argc;
char **argv;
{
/* ---------------------------- *
¦ Размножение констант и копий ¦
*------------------------------*/
j4 = 2;
if( i2 < j4 && i4 < j4 )
i2 = 2;
j4 = k5;
if( i2 < j4 && i4 < j4 )
i5 = 3;
/* ------------------------------------------ *
¦ Свертка констант, арифметические тождества ¦
¦ и излишние операции загрузки/сохранения ¦
* ------------------------------------------ */
i3 = 1 + 2;
flt_1 = 2.4 + 6.3;
i2 = 5;
j2 = i + 0;
k2 = i / 1;
i4 = i * 1;
i5 = i * 0;
#ifndef NO_ZERO_DIVIDE
/*
* Некоторые компиляторы распознают ошибку
* деления на нуль и не генерируют объектный код
*/
i2 = i / 0;
flt_2 = flt_1 / 0.0;
#else
printf( "This compiler handles divide-by-zero as \
an error\n");
#endif
flt_3 = 2.4 / 1.0;
flt_4 = 1.0 + 0.0000001;
flt_5 = flt_6 * 0.0;
flt_6 = flt_2 * flt_3;
/* -------------------- *
¦ Лишнее присваивание ¦
* -------------------- */
k3 = 1;
k3 = 1;
/* ------------------ *
¦ Снижение мощности ¦
* ------------------ */
k2 = 4 * j5;
for( i = 0; i <= 5; i++ )
ivector4[ i ] = i * 2;
/* ------------- *
¦ Простой цикл ¦
* ------------- */
j5 = 0;
k5 = 10000;
do {
k5 = k5 - 1;
j5 = j5 + 1;
i5 = (k5 * 3) / (j5 * constant5);
} while ( k5 > 0 );
/* -------------------------------------- *
¦ Управление переменной индукции цикла ¦
* -------------------------------------- */
for( i = 0; i < 100; i++ )
ivector5[ i * 2 + 3 ] = 5;
/* ----------------------- *
¦ Глубокие подвыражения ¦
* ----------------------- */
if( i < 10 )
j5 = i5 + i2;
else
k5 = i5 + i2;
/* ------------------------------------------------ *
¦ Проверка того, как компилятор генерирует адрес ¦
¦ переменной с константным индексом, размножает ¦
¦ копии и регистры ¦
* ------------------------------------------------ */
ivector[ 0 ] = 1; /* генерация константного адреса */
ivector[ i2 ] = 2; /* значение i2 должно быть скопировано*/
ivector[ i2 ] = 2; /* копирование регистров */
ivector[ 2 ] = 3; /* генарация константного адреса */
/* ----------------------------- *
¦ Удаление общих подвыражений ¦
* ----------------------------- */
if(( h3 + k3 ) < 0 || ( h3 + k3 ) > 5 )
printf("Common subexpression elimination\n");
else {
m3 = ( h3 + k3 ) / i3;
g3 = i3 + (h3 + k3);
/* -------------------------------------- *
¦ Вынесение инвариантного кода ¦
¦ (j * k) может быть вынесено из цикла ¦
* -------------------------------------- */
for( i4 = 0; i4 <= max_vector; i4++)
ivector2[ i4 ] = j * k;
/* ----------------------------- *
¦ Вызов функции с аргументами ¦
* ----------------------------- */
dead_code( 1, "This line should not be printed" );
/* ------------------------------ *
¦ Вызов функции без аргументов ¦
* ------------------------------ */
unnecessary_loop();
} /* Конец функции main */
/* ------------------------------------------------------ *
¦ Функция: dead_code ¦
¦ Проверка недостижимого кода и лишних ¦
¦ присваиваний. Не должен генерироваться код. ¦
* ------------------------------------------------------ */
void dead_code( a, b )
int a;
char *b;
{
int idead_store;
idead_store = a;
if( 0 )
printf( "%s\n", b );
} /* Конец dead_code */
/* ---------------------------------------------------- *
¦ Функция: unnecessary_loop ¦
¦ Цикл в следующей функции ненужен, так как ¦
¦ значение присваивания постоянно. В идеале ¦
¦ цикл должен быть удален. ¦
* ---------------------------------------------------- */
void unnecessary_loop()
{
int x;
x = 0;
for( i = 0; i < 5; i++ ) /* Цикл не должен генерироваться*/
k5 = x + j5;
} /* Конец unnecessary_loop */
/* ---------------------------------------------------- *
¦ Функция: loop_jamming ¦
¦ Два цикла в этой функции имеют одинаковые ¦
¦ заголовки и могут быть слиты в один. ¦
* ---------------------------------------------------- */
void loop_jamming( x )
int x;
{
for( i = 0; i < 5; i++ )
k5 = x + j5 * i;
for( i = 0; i < 5; i++ )
i5 = x * k5 * i;
} /* Конец loop_jamming */
/* ------------------------------------------------------ *
¦ Функция: loop_unrolling ¦
¦ Цикл в этой функции должен быть заменен ¦
¦ тремя присваиваниями с использованием ¦
¦ константной индексации массива или машинно- ¦
¦ зависимыми командами для инициализации ¦
¦ блока памяти. ¦
* ------------------------------------------------------ */
void loop_unrolling( x )
int x;
{
for( i = 0; i < 6; i++ )
ivector4[ i ] = 0;
} /* Конец loop_unrolling */
/* ----------------------------------------------------- *
¦ Функция: jump_compression ¦
¦ Эта программа полезна для демонстрации ¦
¦ сжатия цепочки переходов. goto end_1 может ¦
¦ быть заменен на прямой переход на beg_1. ¦
* ----------------------------------------------------- */
int jump_compression( i, j, k, l, m )
int i, j, k, l, m;
{
beg_1:
if( i < j )
if( j < k )
if( k < l )
if( l < m )
l += m;
else
goto end_1;
else
k += l;
else {
j += k;
end_1:
goto beg_1;
}
else
i += j;
return( i + j + k + l + m );
} /* Конец jump_compression */
Оглавление
Сфера применения оптимизации
Методы оптимизации
Оптимизировать или нет?
Тестирование компиляторов
Borland International.
Computer Innovation Inc.
Datalight Inc.
Lattice Inc.
Manx Software Systems Inc.
Metaware Inc.
Microsoft C.
Microsoft QuickC.
WATCOM.
Выявленные лидеры
