Генерація високоякісного коду для програм

Філіп М. Хіслей

Хоча всі компілятори з мови Сі призначені для
генерації найбільш швидких і компактних програм,
якість оптимізації коду у них може бути зовсім
різне.

Розробники компіляторів з мови Сі спочатку
прагнули до повної згоди зі стандартом Керніган і Річі. У
Надалі – до зменшення часу компіляції. Потім – до повної
підтримці моделей пам'яті сімейства мікропроцесорів 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;

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

            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 
        

Рис. 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
           

"Злиття циклів" мінімізує керуючі заголовки циклів шляхом зрощування коду з циклів, що мають однакові керуючі заголовки, в один цикл. Для того, щоб видалити керуючий заголовок другого циклу, два простих циклу

            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-fg |
| 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
#include
#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 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"

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*