7.3: Компіляція

Last updated
Save as PDF

Page ID: 34512

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

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

З кодом C насправді є крок, перш ніж розбирати вихідний код, який називається препроцесором. Препроцесор - це за своєю суттю програма для заміни тексту. Наприклад, будь-яка змінна, оголошена як текст змінної #define, буде замінена на text. Цей попередньо оброблений код потім передається в компілятор.

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

Синтаксис найчастіше описується в Backus-Naur Form (BNF) ^[21] який є мовою, за допомогою якої ви можете описати мови!

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

Процесори, як правило, можуть завантажувати лише значення в регістри з пам'яті на конкретних вирівнюваннях. Невирівняні навантаження призводять, в кращому випадку, до погіршення продуктивності. — Малюнок 7.1. Вирівнювання

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

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

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

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

Програмісти повинні враховувати вирівнювання, особливо при створенні структури s Хоча компілятор знає правила вирівнювання для архітектури, для якої він будує, іноді програмісти можуть викликати неоптимальну поведінку.

Стандарт C99 говорить лише про те, що структури будуть впорядковані в пам'яті в тому ж порядку, в якому вони вказані в оголошенні, і що в масиві структур всі елементи будуть однакового розміру.

Приклад 7.1. Приклад оббивки структури

  1 $ cat struct.c
    #include <stdio.h>
    
    struct a_struct {
  5         char char_one;
            char char_two;
            int int_one;
    };
    
 10 int main(void)
    {
    
            struct a_struct s;
    
 15         printf("%p : s.char_one\n" \
                   "%p : s.char_two\n" \
                   "%p : s.int_one\n", &s.char_one,
                   &s.char_two, &s.int_one);
    
 20         return 0;
    
    }
    
    $ gcc -o struct struct.c
 25 
    $ gcc -fpack-struct -o struct-packed struct.c
    
    $ ./struct
    0x7fdf6798 : s.char_one
 30 0x7fdf6799 : s.char_two
    0x7fdf679c : s.int_one
    
    $ ./struct-packed
    0x7fcd2778 : s.char_one
 35 0x7fcd2779 : s.char_two
    0x7fcd277a : s.int_one

У наведеному вище прикладі ми придумуємо структуру, яка має два байти (символи), за якими слідує 4-байтове ціле число. Компілятор накладає структуру, як показано нижче.

Компілятор накладає структуру, щоб вирівняти ціле число на 4-байтовій межі. — Малюнок 7.2. Вирівнювання

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

Раніше ми говорили про згладжування в кеші, і про те, як кілька адрес можуть зіставлятися в один і той же рядок кешу. Програмістам потрібно бути впевненим, що коли вони пишуть свої програми, вони не викликають відскакування рядків кешу.

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

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

Одним з можливих способів виявлення такого роду ситуації є профілювання. Коли ви профілюєте свій код, ви «дивитеся» його, щоб проаналізувати, які шляхи коду взяті і скільки часу вони займають для виконання. За допомогою оптимізації під керуванням профілем (PGO) компілятор може поставити спеціальні додаткові біти коду в перший бінарний файл, який він будує, який запускає і робить запис про взяті гілки тощо Потім ви можете перекомпілювати двійковий файл з додатковою інформацією, щоб можливо створити більш ефективний двійковий файл. В іншому випадку програміст може подивитися на вихід профілю і, можливо, виявити такі ситуації, як стрибок рядка кешу. (ХХХ десь ще?)

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

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

Таким чином, як програміст на C ви повинні бути знайомі з тим, що можна припустити про те, що буде робити компілятор і що може бути змінною. Що саме ви можете припустити і не можете припустити, детально описано в стандарті C99; якщо ви програмуєте на C, це, безумовно, варто інвестувати в ознайомлення з правилами, щоб уникнути написання непортативного або глючного коду.

Приклад 7.2. Приклад вирівнювання стека

  1 $ cat stack.c
    #include <stdio.h>
    
    struct a_struct {
  5         int a;
            int b;
    };
    
    int main(void)
 10 {
            int i;
            struct a_struct s;
            printf("%p\n%p\ndiff %ld\n", &i, &s, (unsigned long)&s - (unsigned long)&i);
            return 0;
 15 }
    $ gcc-3.3 -Wall -o stack-3.3 ./stack.c
    $ gcc-4.0 -o stack-4.0 stack.c
    
    $ ./stack-3.3
 20 0x60000fffffc2b510
    0x60000fffffc2b520
    diff 16
    
    $ ./stack-4.0
 25 0x60000fffff89b520
    0x60000fffff89b524
    diff 4

У наведеному вище прикладі, взятому з машини Itanium, ми бачимо, що прокладка та вирівнювання стеку значно змінилися між версіями gcc. Цей тип речей слід очікувати і повинен розглядати програміст.

Як правило, ви повинні переконатися, що ви не робите припущень щодо розміру типів або правил вирівнювання.

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

Можна взяти кілька прикладів з ядра Linux, якому часто доводиться мати справу з вирівнюванням сторінок пам'яті всередині системи.

Приклад 7.3. Маніпуляції з вирівнюванням сторінки

  1 [ include/asm-ia64/page.h ]
    
    /*
     * PAGE_SHIFT determines the actual kernel page size.
  5  */
    #if defined(CONFIG_IA64_PAGE_SIZE_4KB)
    # define PAGE_SHIFT     12
    #elif defined(CONFIG_IA64_PAGE_SIZE_8KB)
    # define PAGE_SHIFT     13
 10 #elif defined(CONFIG_IA64_PAGE_SIZE_16KB)
    # define PAGE_SHIFT     14
    #elif defined(CONFIG_IA64_PAGE_SIZE_64KB)
    # define PAGE_SHIFT     16
    #else
 15 # error Unsupported page size!
    #endif
    
    #define PAGE_SIZE               (__IA64_UL_CONST(1) << PAGE_SHIFT)
    #define PAGE_MASK               (~(PAGE_SIZE - 1))
 20 #define PAGE_ALIGN(addr)        (((addr) + PAGE_SIZE - 1) & PAGE_MASK)

Вище ми бачимо, що існує ряд різних варіантів розмірів сторінок всередині ядра, починаючи від 4 КБ до 64 КБ.

Макрос PAGE_SIZE є досить пояснювальним, даючи поточний розмір сторінки, обраний у системі, зміщуючи значення 1 на заданий номер зсуву (пам'ятайте, це еквівалент сказати 2 ^{n, де n} - PAGE_SHIFT).

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

XXX продовжити коротке обговорення

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

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

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

Якщо код містить цикл, наприклад цикл for або while, і компілятор має деяке уявлення про те, скільки разів він буде виконуватися, можливо, ефективніше розгорнути цикл, щоб він виконувався послідовно. Це означає, що замість того, щоб робити внутрішню частину циклу, а потім розгалужуватися назад до початку, щоб повторити процес, внутрішній код циклу дублюється для виконання знову.

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

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

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

Таким чином компілятор може зробити прогноз про те, яким шляхом швидше за все піде тест. Є кілька простих правил, які компілятор може використовувати, щоб вгадати такі речі, наприклад, якщо (val == -1), ймовірно, не буде істинним, оскільки -1 зазвичай вказує на код помилки і, сподіваємось, що не буде спрацьовувати занадто часто.

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

^[21] Насправді найпоширенішою формою є Розширена форма Backus-Naur, або EBNF, оскільки вона дозволяє деякі додаткові правила, які більше підходять для сучасних мов.