Лабораторна робота № 4 Генерація і оптимізація об'єктнго кода

Мета роботи: вивчення основних принципів генерації компілятором об'єктного кода для лінійної ділянки програми, ознайомлення з методами оптимізації результуючого об'єктного кода з допомогою згортки і виключення зайвих операцій.

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

Програму рекомендується побудувати з трьох основних частин: перша частина – створення деревом синтаксичного розбору (за наслідками лабораторної роботи №3), друга частина - реалізація алгоритму створення об'єктного кода по дереву розбору, і третя частина - оптимізація створеного об'єктного кода. Результатом роботи повинна бути побудована на підставі заданої пропозиції граматики програма на об'єктній мові. Як об'єктна мова пропонується узяти мову асемблера для процесорів типу Intel 80x86 в реальному режимі (можливий вибір іншої об'єктної мови за узгодженням з викладачем). Ідентифікатори, що все зустрічаються в початковій програмі, вважати простими скалярними змінними, що не вимагають виконання перетворення типів. Обмеження на довжину ідентифікаторів і констант відповідають вимогам попередньої лабораторної роботи.

Короткі теоретичні відомості

Генерація об'єктного кода - це переклад компілятором внутрішнього представлення початкової програми в результуючу об'єктну програму на мові асемблера або безпосередньо на машинній мові (машинних кодах).

Генерація об'єктного кода виконується після того, як виконаний синтаксичний аналіз програми і всі необхідні дії з підготовки до генерації коду: розподілений адресний простір під функції і змінні, перевірена відповідність імен і типів змінних, констант і функцій в синтаксичних конструкціях початкової програми і так далі.

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

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

Всі ці переваги говорять на користь застосування оптимізації. Єдиним, але істотним недоліком оптимізації є необхідність ретельного її опрацьовування при створенні компілятора. Використовувані методи оптимізації ні за яких умов не повинні приводити до зміни “сенсу” початкової програми (тобто до таких ситуацій, коли результат виконання програми змінюється після її оптимізації). На жаль, не всі методи оптимізації, використовувані творцями компіляторів, можуть бути теоретично обгрунтовані і доведені для всіх можливих видів початкових програм. Тому більшість компіляторів передбачає можливість відключати ті або інші з можливих методів оптимізації. (Часто при оптимізації компілятори видають попередження розробникові програми, якщо та або інша її ділянка викликає підозри відносно правильності його “сенсу”). Застосування оптимізації також недоцільно в процесі відладки початкової програми.

Розрізняються дві основні категорії оптимізуючих перетворень:

• перетворення початкової програми (у формі її внутрішнього уявлення в компіляторі), не залежні від результуючої об'єктної мови;

• перетворення результуючої об'єктної програми.

Останній тип перетворень може залежати не тільки від властивостей об'єктної мови (що очевидно), але і від архітектури обчислювальної системи, на якій виконуватиметься результуюча програма. (Так, наприклад, при оптимізації може враховуватися об'єм кеш-пам'яті і методи організації конвеєрних операцій центрального процесора). Цей тип перетворень тут розглядатися не буде. Саме ці перетворення можуть вплинути на “сенс” початкової програми. В більшості випадків вони є “ноу-хау” виробників компіляторів і строго орієнтовані на певну архітектуру обчислювальних машин.

Методи перетворення програми залежать від типів синтаксичних конструкцій початкової мови. Теоретично розроблені методи оптимізації для багатьох типових конструкцій мов програмування. Далі будуть розглянуті тільки методи оптимізації лінійних ділянок - вони зустрічаються в будь-якій програмі і складають істотну частину програмного коду.

Лінійна ділянка програми - це виконувана по порядку послідовність операцій що має один вхід і один вихід. Найчастіше лінійну ділянку містить послідовність арифметичних операцій і операторів привласнення значень змінним.

Перш ніж перейти до питань оптимізації лінійних ділянок розглянемо їх внутрішньо уявлення в компіляторі.

Алгоритм генерації об'єктного кода по дереву виводу

Можливі різні форми внутрішнього представлення синтаксичних конструкцій початкової програми в компіляторі. На етапі синтаксичного розбору часто використовується форма, що іменується деревом виводу (методи його побудови розглядалися в попередніх лабораторних роботах). Але форми уявлення, використовувані на етапах синтаксичного аналізу, виявляються незручними в роботі при генерації і оптимізації об'єктного кода. Тому перед оптимізацією і безпосередньо генерацією об'єктної коди внутрішнє представлення програми перетвориться в одну з відповідних форм запису.

Прикладами таких форм запису є:

• зворотний польський запис операцій;

• тетради операцій;

• тріади операцій;

• власне команди асемблера.

Зворотній польський запис - це постфіксний запис операцій. Перевагою її є те, що всі операції записуються безпосередньо в порядку їх виконання. Вона надзвичайно ефективна в тих випадках, коли для обчислень використовується стек.

Тетради є записом операцій у формі з чотирьох складових: <операція>(<операнд1>,<операнд2>,<результат>). Тетради використовуються рідко, оскільки вимагають більше пам'яті для свого уявлення, чим тріади, не відображають взаємозв'язку операцій і, крім того, погано відображаються в команди асемблера і машинні коди, оскільки в наборах команд більшості сучасних машин не зустрічаються операції з трьома операндами.

Тріади є записом операцій у формі з трьох складових: <операція>(<операнд1>,<операнд2>), при цьому один або обидва операнди можуть бути посиланнями на іншу тріаду в тому випадку, якщо як операнд даної тріади виступає результат виконання іншої тріади. Тому тріади при записі послідовно номерують для зручності вказівки посилань одних тріад на інших. Наприклад, вираз A := B*c + D - B*10, записане у вигляді тріад матиме вигляд:

1) * ( B, C )

2) + ( ^1, D )

3) * ( B, 10 )

4) - ( ^2, ^3 )

5) := ( A, ^4 )

Тут операції позначені відповідним знаком (при цьому привласнення також є операцією), а знак ^ означає посилання операнда однієї тріади на результат іншої.

Команди асемблера зручні тим, що при їх використанні внутрішнє представлення програми повністю відповідає об'єктному коду і складні перетворення не потрібні. Проте використання команд асемблера вимагає додаткових структур для відображення їх взаємозв'язку. Крім того, внутрішнє представлення програми виходить залежним від результуючого кода, а це означає, що при орієнтації компілятора на інший результуючий код потрібно буде перебудовувати як само внутрішнє представлення програми, так і методи його обробки в алгоритмах оптимізації (при використанні тріад або тетрад цього не потрібно).

Для побудови внутрішнього представлення об'єктного коду (надалі - просто коди) по дереву виводу може використовуватися проста рекурсивна процедура. Ця процедура перш за все повинна визначити тип вузла дерева - він відповідає типу операції, символ якої знаходиться в листі дерева для поточного вузла. Цей лист є середнім листом вузла дерева для бінарних операцій і крайнім лівим листом - для унарних операцій. Після визначення типу процедура будує код для вузла дерева відповідно до типу операції. Якщо всі вузли наступного рівня для поточного вузла є листя дерева, то в код включаються операнди, відповідні цьому листю, і код, що вийшов, стає результатом виконання процедури. Інакше процедура повинна рекурсивно викликати сама себе для генерації коди вузлів дерева, що пролягають нижче, і результат виконання включити в свій створений код.

Тому для побудови внутрішнього представлення об'єктного коду по дереву виводу в першу чергу необхідно розробити форми представлення об'єктного коду для чотирьох випадків, відповідних видам поточного вузла дерева виводу:

• обидва вузли дерева, що пролягають нижче, - листя (термінальні символи граматики);

• тільки лівий вузол, що пролягає нижче, є листом дерева;

• тільки правий вузол, що пролягає нижче, є листом дерева:

• обидва вузли, що пролягають нижче, не є листям дерева.

• Розглянемо побудову двох видів внутрішнього уявлення по дереву виводу:

• побудова асемблерної коди по дереву виводу;

• побудова списку тріад по дереву виводу.