Страница:
Microsoft QuickC.
Когда речь идет об оптимизации, QuickC становится настолько беспомощным, насколько C 5.0 изощренным. Код, сгенерированный QuickC, был в основном дословным переводом, насыщенным излишними загрузками и сохранениями регистров, переходами на переходы. Этот компилятор применяет лишь наиболее первичные методы оптимизации, свертку констант и некоторые алгебраические упрощения. Он сгенерировал недостижимый код, поместил переход через него и не смог выполнить сжатие цепочки переходов.
В пользу компилятора свидетельствует то, что что он разумно управляет прологами и эпилогами функций, используя отдельные инструкции для установки адресации стекового фрейма при входе и инструкцию LEAVE при завершении функции. При входе сохраняются и при выходе восстанавливаются только те регистры, которые используются в теле функции.
QuickC был влючен в этот обзор, потому что он имеет ключ оптимизации в командной строке (-Ox). Генерируя код, который по своей природе - дословный перевод исходного текста, 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. Здесь он близок к наихудшим компиляторам.
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.
Нет единственного производителя, который захватил бы на рынке область технологии оптимизации для компиляторов Си. Конкуренция на рынке подталкивает производителей к развитию технологии и к обеспечению разработчиков лучшими и более мощными средствами языка Си. В будущем это может означать появление оптимизирующих компиляторов, которые будут вырабатывать более быстрый и компактный код.
¦ ¦
¦ Серия тестов 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 */
Даже с установленным минимальным уровнем оценка возможностей конкретных компиляторов усложняется существованием многих несоизмеримых форм оптимизации. Компилятор может хорошо использовать регистры, но не поддерживать удаление общих подвыражений. Поскольку оптимизированный код зависит не только от применяемых методов, но также и от структуры программы, которая оптимизировалась, в общем случае было бы заблуждением считать, что один компилятор лучше другого, опираясь исключительно на один отдельный тест.
Хотя все девять рассматриваемых компиляторов генерируют приемлемый код, три из них, - 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 */