Кодогенерація

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

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

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

Подальші етапи компіляції можуть і не належати до «генерації коду», в залежності від того, наскільки значними будуть зміни, що вносяться ними. Так, локальна оптимізація навряд чи може називатися «генерацією коду», проте сам генератор коду може включати в себе етап локальної оптимізації.

Завдання генератора коду

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

Деякі завдання, які, зазвичай, вирішують складні генератори коду:

• Вибір інструкцій: які саме інструкції використати;
• Планування інструкцій: у якому порядку розміщувати ці інструкції. Планування — це оптимізація, котра може значно впливати на швидкість виконання програми на конвеєрних процесорах;
• Розміщення у регістрах: розміщення змінних програми у регістрах процесора;
• Дані про налагодження покоління, якщо потрібно, так що код може бути налагоджений.

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

W:=ADD(X,MUL(Y,Z))

може бути перетворене в лінійну послідовність інструкцій рекурсивну генерації послідовностей

t1:=X і t2:=MUL(Y,Z) ,

а потім в інструкцію

ADD W,t1,t2 .

В компіляторах, які використовують проміжну мову, може бути дві стадії вибору інструкцій — одна для перетворення дерева розбору в проміжний код, а друга (виконується значно пізніше) — для перетворення проміжного коду в інструкції цільової системи команд. Друга стадія не вимагає обходу дерева : вона може виконуватися послідовно і зазвичай складається з простої заміни операцій проміжної мови відповідними їм кодами операцій. Насправді, якщо компілятор фактично є транслятором (наприклад, один переводить Eiffel в C), то друга стадія генерації коду може включати побудову дерева з лінійного проміжного коду.

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

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

Підсумки

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

Див. також

• Компіляція

Примітки

1. (PDF). Архів оригіналу (PDF) за 18 листопада 2018. Процитовано 18 листопада 2018.
2. . Архів оригіналу за 24 листопада 2018. Процитовано 24 листопада 2018.
3. . Архів оригіналу за 24 листопада 2018. Процитовано 24 листопада 2018.

Література

• Дональд Кнут. Мистецтво програмування.
• Альфред  Ст.  Агв, Моніка  С.  Лам, Рави Мережі, Джеффрі  Д.  Ульман. Компілятори: принципи, технології та інструментарій = Компілятори: Principles, Techniques, and Tools. — 2-е вид. — М.: Вільямс, 2008. — .
• Робін Хантер. Основні концепції компіляторів = The Essence of Компілятори. — М.: «Вільямс», 2002. — С. 256. — .

Посилання

• Семантичний аналізатор [ 24 листопада 2018 у Wayback Machine.](укр.)
• Семантичний аналіз тексту [ 20 грудня 2018 у Wayback Machine.](укр.)
• Синтаксичний аналіз [ 20 грудня 2018 у Wayback Machine.](укр.)
• Корнійко Ілля. Створення компілятора [ 24 листопада 2018 у Wayback Machine.] (рос.)
• Архитектура набора команд (ISA) [ 28 листопада 2018 у Wayback Machine.] (рос.)
• Code Generation: The Real Lesson of Rails ^{[недоступне посилання з липня 2019]}(англ.)