Генерація високоякісного коду для програм на СІ. Частина 1, Різне, Програмування, статті

Хоча всі компілятори з мови Сі призначені для генерації найбільш швидких і компактних програм, якість оптимізації коду у них може бути зовсім різне. Розробники компіляторів з мови Сі спочатку прагнули до повної згоди зі стандартом Керніган і Річі. У наслідку – до зменшення часу компіляції. Потім – до повної підтримки моделей пам’яті сімейства мікропроцесорів 80х86. Потім намагалися підтримувати переносимість вихідних текстів програм шляхом надання сумісних з UNIX бібліотек функцій. Після цього створювали спеціалізовані бібліотеки функцій для забезпечення низькорівневого доступу до характерних для персональних комп’ютерів (PC) можливостям. За цим слідували спроби дотримуватися розвивається стандарту ANSI C. Після чого слідував повернення до початку, але з розвиненим інтегрованим оточенням. І так далі.

Саме останній напрям у розвитку компіляторів Сі – оптимізація. Це можна продемонструвати такими сьогоднішніми заявами постачальників компіляторів: “Найбільш потужний оптимізуючий компілятор!” (Turbo C, Borland); “Нові методи оптимізації генерують найшвидший код!” (C 5.0, Microsoft); “Оптимізатор невтомно шукає шляхи прискорення виконання та мінімізації використовуваної пам’яті” (Optimum C, Datalight). Враховуючи цю моду, PC Tech Journal розробив тест для перевірки можливостей
оптимізації коду у Сі компіляторів, наявних на PC. Цей тест був виконаний на дев’яти компіляторах: Borland Turbo C 1.5, Computer Innovations C86Plus 1.10, Datalight Optimum-C 3.14, Lattice MS-DOS C 3.2, Manx Aztec C86 4.0, Metaware High C 1.4, Microsoft C 5.0 і QuickC 1.0, а також WATCOM C 6.0. Ці вироби представляють найкращі компілятори Сі, доступні на PC. Перевірка показала, що різні компілятори застосовують різні прийоми оптимізації з різним успіхом. Доступні й інші компілятори, але їх характеристики значно гірше, ніж у перерахованих. Більшість цих компіляторів описані в лютневому номері PC Tech Journal 1988 року в
статті “The State of C” (див. “C Contenders” і “Turbo and Quick Weigh In”, Marty Franz, стор 52 і 72 відповідно).

Оскільки сучасні компілятори Сі близькі по наданих можливостях, оптимізація залишається одним важливим відзнакою, за яким їх можна диференціювати. Робота компілятора полягає в тому, щоб странсліровать процедурне опис завдання і ефективно відобразити його в виділене безліч машинних команд цільового процесора. Ступінь ефективності генерації компілятором машинно-рівневого коду може мати суттєве вплив на швидкість виконання програми та її розмір.


Основна мета оптимізації – вироблення більш швидкого і меншого за розміром коду. У звичайному середовищі комп’ютера, де кількість доступної оперативної пам’яті є обмежений ресурс, що розділяється декількома користувачами, важлива оптимізація розміру коду. У середовищі PC оптимізація швидкості має більш високий пріоритет, оскільки PC звичайно використовується однією особою і доступний великий обсяг пам’яті (більшість PC мають принаймні 640KB основної пам’яті і багато хто має кілька мегабайт додаткової або
розширеної пам’яті). Отже, кращий спосіб оцінки можливостей оптимізації коду компілятора Сі, призначеного для PC, – оцінка швидкості.
 


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


Методи оптимізації


Існують різні методи машинно-залежною і машинно-незалежної
оптимізації коду. Вони можуть застосовуватися на всіх синтаксичних рівнях.
Одним з найпростіших методів є “розмноження констант”. При його
застосуванні будь-яке посилання на константне значення заміщається самим
значенням. У наступному прикладі підвищується ефективність завдяки видаленню
трьох адресних посилань і заміні їх константами:
  x = 2;
  if( a < x && b < x)
      c = x;

переводиться в
  x = 2;
  if(a < 2 && b < 2)
      c = 2;

Цілком пов’язано з розмноженням констант “розмноження копій”. В цьому методі
копіюються змінні замість константних значень. Наприклад,
    x = y;
  if(a < x && b < x)
      c = x;

переводиться в
  x = y;
  if(a < y && b < y)
      c = y;

Розмноження констант і копій також може видалити зайві присвоювання (x
= 2 і x = y в прикладах). Серед описуваних компіляторів тільки Microsoft C
5.0 і WATCOM C 6.0 застосовують розмноження констант.
Метод “згортки констант” (константних арифметика) зводить висловлювання,
які містять константні дані, до можливо простій формі.
Константні дані зазвичай використовуються в програмі або безпосередньо
(Як у випадку чисел або цифр), або опосередковано (як у випадку оголошених
маніфестних констант). Згортка констант зводить наступний оператор:
  #define TWO 2
  a = 1 + TWO;

до його еквівалентної формі,
  a = 3;

під час компіляції, завдяки чому видаляються непотрібні арифметичні
операції зі стадії виконання програми. У Сі згортання констант
застосовують як до цілих констант, так і до константам з плаваючою крапкою.
“Алгебраїчні спрощення” є вид згортки констант, який видаляє
аріфметічесіке тотожності. Код, сгенерірованиий для таких операторів, як
  x = y + 0;
  x = y * 0;
  x = y / 1.0;
  x = y / 0;

повинен бути простим константним привласненням та не повинен містити команд
для виконання арифметичних операцій. Пильний компілятор повинен
позначити останній оператор як помилковий і не генерувати код для нього.
“Витяг загальних подвираженій” – це процес видалення зайвих обчислень.
Замість того, щоб генерувати код для обчислення значення кожного разу,
коли воно використовується, оптимізуючий компілятор намагається виділити
вираз таким чином, щоб його значення обчислювалося тільки одного разу.
Там, де це можливо, наступні посилання на таке ж вираження використовують
раніше обчислена значення. Вирази y * 3 і a [y * 3] є загальними
подвираженіем в наступному тексті:
  if( a[y*3] < 0 // b[y*3] > 10)
      a[y*3] = 0;

Виділення цих виразів приводить до логічно еквівалентному тексту:
  T1 = y*3;
  A1 = &a[T1];
  A2 = &b[T1];
  if( *A1 < 0 // *A2 > 10)
      *A1 = 0;

Виділення загальних подвираженій зазвичай відбувається всередині оператора або блоку.
“Глибоке виділення загальних подвираженій” є більш складним і
перекриває базові блоки. Виділення загального подвираженія, y * 3, в операторі

  if(a == 0)
      a = y * 3;
  else
      b = y * 3;

призводить до логічного еквівалента:
  T1 = y * 3;
  if(a == 0)
      a = T1;
  else
      b = T1;

Малюнок 1 демонструє практичний виграш від виділення загальних
подвираженій в реальному коді.

  ————————————————————–¬
| МАЛЮНОК 1: Виділення загальних подвираженій |
  +————————————————————-+
| Оригінальний текст на Сі BORLAND LATTICE |
  ¦      Turbo C 1.5   MS-DOS C 3.2    ¦
  +————————————————————-+
  ¦if((h3 + k3) < 0 //  mov AX,h3     mov AX,h3  ¦
  ¦   (h3 + k3) > 5)    add AX,k3     add AX,k3  ¦
  ¦  printf(“Common    jl  @18  js L0187   ¦
  ¦   subexpression    mov AX,h3     cmp AX,5   ¦
  ¦   elimination”);    add AX,k3     jle L0193  ¦
  ¦      cmp AX,5 L0187:     ¦
  ¦      jle @17  mov AX,01.0000  ¦
  ¦       @18:    push AX    ¦
  ¦    mov AX,offset s@     call printf     ¦
  ¦      push AX  add SP,2   ¦
  ¦      call printf   L0193:     ¦
  ¦      mov SP,BP      ¦
  ¦       @17:          ¦
  +————————————————————-+
| Багаторазові входження обчислень замінюються значенням, |
| Яке є результатом єдиного входження |
| Обчислення. Borland Turbo C обчислює значення виділеного |
| Вираження h3 + k3 двічі, тоді як LATTICE MS-DOS C та інші |
| Застосовують виділення загальних подвираженій і обчислюють |
| Вираз тільки один раз. |
  L————————————————————–

Сфера застосування оптимізації


Термін “оптимізуючий компілятор” застосовується постачальниками компіляторів в загальному сенсі, для позначення компіляторів, які забезпечують певний рівень оптимізації – від найпростішого до найскладнішого. Щоб розрізняти ступінь оптимізації, що надається компіляторами, необхідно більш точне визначення термінів. Методи оптимізації коду можуть застосовуватися на різних рівнях синтаксичних конструкцій. Від самого первинного рівня до найбільш укрупненого, тобто на рівні оператора,
блоку, циклу, процедури та програми. Чим вище рівень оптимізації, тим більше можливості підвищення загальної ефективності програмного модуля. Однак витрати на застосування більшою мірою оптимізації можуть значно збільшити час компіляції.
Оператор – це первинна синтаксична одиниця в програмі. Більшість компіляторів виконують деяку оптимізацію на цьому рівні. Блок – це послідовність операторів, для якої існують єдина точка входу і єдина точка виходу. Лінійний вид блоку інструкцій дозволяє компілятору виконувати оптимізацію, що грунтується на проміжках життя різних даних і виразів, що використовуються всередині блоку. Оптимізуючий компілятор виділяє операційну структуру програм шляхом
конструювання орієнтованого потокового графа програм, в якому кожна вершина являє основний блок, а зв’язки між вершинами представляють потоки управління. Більшість компіляторів виробляють оптимізацію на рівні блоку.
Цикл містить виконувану багаторазово послідовність операторів. Оскільки багато програм проводять в циклах більшу частину часу свого виконання, оптимізація в цій області може дати суттєве поліпшення характеристик виконання програми. Будучи звичайної для компіляторів на великих комп’ютерах і мінікомп’ютерах, оптимізація на рівні циклу є новою для компіляторів Сі на PC.
Процедури – це оператори, які містять цілі підпрограми або функції. Оптимізація на цьому рівні взагалі не виконується компіляторами для PC.
Найбільш складний рівень оптимізації, рівень програми, в даний час розглядається суто теоретично і не включається ні одним доступним на PС, мінікомп’ютерах, і великих комп’ютерах компілятором Сі. Виробники, які стверджують, що їх компілятори виконують глобальну оптимізацію, мають на увазі рівень процедур, але не програми. Оптимізують перетворення можуть бути залежними або незалежними від архітектури комп’ютера. Процес компіляції комп’ютерної програми включає два основних дії: сінтаксічесікй / семантичний аналіз і генерацію коду. Синтаксичний / семантичний аналіз істотно залежить від
граматики і специфічний для мови. Генерація коду є загальною і прекрасно може бути використана для підтримки першої стадії для будь-якої кількості мов програмування.
Оригінальний текст конкретної мови насамперед транслюється в загальну проміжну форму, яка послідовно обробляється для вироблення на стадії генерації машинно-залежного коду. Машинно-незалежна оптимізація, така як виділення загальних подвираженій та винесення інваріантного коду, застосовується до проміжного коду. Машинно-залежна оптимізація застосовується до результату стадії генерації коду і використовує набір команд конкретного процесора. Ця оптимізація відома як “щілинна” оптимізація, тому що ці перетворення виконуються всередині маленького вікна (5 – 10 інструкцій машинного рівня). Типові приклади
щілинний оптимізації включають видалення зайвих операцій завантаження / збереження регістрів, видалення недосяжного коду, випрямлення
передач управління, алгебраїчні спрощення, зниження потужності (команд) і використання команд, специфічних для конкретного процесора.

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


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

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

Ваш отзыв

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

*

*