Суперскалярный стековий процесор: продовжуємо схрещувати вужа і їжака


Продовження статті, де вдалося продемонструвати, що фронтенд стекової машини цілком дозволяє заховати за ним суперскалярный процесор з OoO.
Тема даної статті — виклик функцій.

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

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

Але перш зробимо ліричний відступ на тему стека як такого.
Саме поняття стек здатне вводити в оману.

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

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

AMD29K, SPARC і Itanium належать до так званого Berkeley Risc сімейства архітектур, у них стек виконує ще одну важливу функцію: пул регістрів є верхівкою стека (register windows), що, як передбачається, прискорює передачу параметрів при виклику функцій.
SPARC V7 з'явився на пару років раніше AMD29K, але він бачиться (автору) менше архітектурно струнким.
RSE блок Itanium'а в цілому аналогічний такому від AMD29K, але з'явився значно пізніше.

AMD29K заслуговує окремих добрих слів

У ньому два апаратних стека. Кілька стеків в архітектурі не нові, це було ще на Burroughs B5000, радянських (і нинішніх) Эльбрусах. Але там другий стек призначений для зберігання адреси повернення з процедур. Тут же вони обидва використовуються для зберігання даних:
  • memory stack — використовується для зберігання великих локальних змінних (структури і масиви) також як і хвоста параметрів, якщо їх більше 16. Регістр gr125(msp) є покажчиком на вершину цього стека.
  • register stack — в наявності 128 локальних реєстрів, які утворюють вершину стека
    • регістровий стек служить для швидкого доступу до вершини стека в пам'яті (відмінного від вищеописаного memory stack, звичайно)
    • глобальні регістри gr126(rab) і gr127(rfb) визначають верх і низ стека, gr1(rsp) зберігає покажчик на його вершину

    • вміє робити в одному циклі два читання і одну запис
    • у ньому немає явних стекових операцій таких як push&pop, замість них при виклику функції для неї звільняється певна компілятором кількість регістрів (activation record, так тут називається call frame)
    • доступ до даних з activation record йде через регістри, які для кожної функції нумеруються від lr0
    • lr0 і lr1 зарезервовані, в першому адресу повернення, у другому — activation record викликає функції
    • регістрові вікна викликає і викликається функцій перетинаються параметрами аналогічно SPARC
    • якщо для виклику нової функції не вистачає вільних регістрів, відбувається trap SPILL, обробник якого виштовхує частину значень регістрів в пам'ять, звільняючи їх
    • навпаки, коли вільних регістрів стає занадто багато, спрацьовує FILL
    • щоб це відбувалося, компілятор вставляє інструкції
      sub gr1,gr1,16 ;function prologue, lr0+lr1+2 local variables
      asgeu SPILL,gr1,rab ;compare with top of window
      ... ;function body
      jmpi lr0 ;return
      asleu FILL,lr1,rfb ;compare with bottom of window gr127
Які цікаві ідеї варто тут відзначити?
  1. Нумерація регістрів для кожної функції своя, це особливість Berkeley RISC
  2. А ось розщеплення стека — особливість саме цієї архітектури. У SPARC'е регістрові вікна зберігаються в той же стек, де лежать і звичайні (не швидкі) змінні. І fill/spill робляться з розривами — кожне вікно зі свого кадру.
Ось це поділ стека на «великий, але повільний» і «маленький, але швидкий» вельми важливо. Розберемося з мотивами.

Передача параметрів, виклик функцій

Ідея стека як сховища локальних змінних (параметрів) прекрасна в своїй логічності і завершеності. Слабке місце — продуктивність системи впирається в затримки і продуктивність пам'яті. У часи PDP-11 з цим нічого не можна було вдіяти, але з тих пір ситуація змінилася.

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

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

У даний момент поширеними є два методи передачі параметрів через регістри:
  1. Закріплення за певними регістрами спеціальної ролі. Наприклад, в MSVC(x86-64) прийнято перші чотири цілочисельних аргументів передавати через регістри RCX, RDX, R8, R9. З цього випливає єдина нумерація регістрів для всіх функцій. До архітектур, які використовують цю техніку, можна віднести також MIPS, PPC, ARM, DEC Alpha… Зрозуміло, що в ланцюжку викликів зберігати параметри все одно більше ніде, крім як на стеку. Тут вся надія на кеш. Або на оптимізатор, який може вирішити, що конкретний параметр у цій функції більше не використовується і зберігати його зовсім не потрібно.
  2. Техніка регістрових вікон. Ця гілка архітектур зростає з проекту Berkeley Risc. Сюди відноситься вже розібраний нами AMD29K, а також i960, Itanium, SPARC. Суть в тому, що обмежені кількості параметрів і локальних даних викликаної функції розташовуються в регистровом вікні, при виклику наступної функції вікно зсувається, таким чином ці дані утворюють стек. У кожній функції своя нумерація регістрів. Все, що не влізло в вікно, потрапляє у звичайний стек, глобальні регістри під тимчасові дані також можуть бути використані. Так от у випадку i960 і SPARC, регістровий стек вкраплен у звичайний, а для AMD29K & Itanium — це різні стеки. Фактично, AMD29K & Itanium пропонують компілятору вибрати дані, які він вважає гідними опинитися в «швидкому стеку», все інше відбудеться саме собою. Це нагадує застаріле нині ключеве слово «register», рішення приймає компілятор, мова високого рівня.
З точки зору потенційної продуктивності обидва підходи приблизно рівносильні. У першому підході вся тяжкість оптимізації лягає на компілятор, а не на процесор (ймовірно) полегшує і здешевлює розробку кінцевої системи.

Але ми дещо захопилися, пора повернутися до збереження контексту поточної функції в проектованої архітектурі.

Збереження контексту функції

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

Є нюанс, який варто відзначити — до початку виклику функції повинні відпрацювати всі мопи, з допомогою яких обчислювалися її аргументи. Тому з точки зору процесора, виклик функції — узагальнена інструкція з довільною кількістю аргументів.

Тепер варто визначитися з нумерацією регістрів.
Нехай загальна нумерація, тобто ми пішли по шляху MIPS, а не SPARC.
  • Якщо ланцюжок викликів досить довга, очевидно, що всі регістри зайняті. І мова йде про те, які з них ми будемо вивантажувати в пам'ять (SPILL). Тобто порядок захоплення все ж важливий.
  • порядок захоплення залежить від передісторії викликів
  • всередині функції він визначається динамічно
  • немає ніяких гарантій, що повернувши результат роботи функції в деякій регістрі, ми не отримаємо (під час зворотного виконання FILL) конфлікт з цим регістром
  • автор не бачить шляхів уникнути подібних конфліктів, що, звичайно, не означає, що їх (шляхів) дійсно немає
Спробуємо регістрові вікна.
  • нумерація регістрів кожної функції починається заново і це просто чудово оскільки позбавляє нас від обліку передісторії
  • звичайна техніка — кільцевої буфер регістрів, FILL&SPILL
  • будемо використовувати два фізичних стека — для регістрових вікон і всього іншого
  • потрібно запам'ятати які регістри використані на момент виклику дочірньої функції. І така інформація у нас є. Припустимо, зайняті регістри r0, r5 і r11. Фактично, використовується тільки чверть від використаного діапазону регістрів і є спокуса як-то «упакувати» їх. Але тоді при поверненні з дочірньою функції доведеться «розпаковувати» їх назад. Так що пул регістрів поточної функції (в даному випадку) залишиться розміром 12 регістрів (+службова інформація: адреса повернення, попередній frame). Тим більше, що сама по собі кількість регістрів не так вже й критично, набагато дорожче обходиться кількість одночасних операцій читання/запису, а воно не зміниться
  • а ось із збереженням регістрів на згадку, мабуть, щось можна зробити, спробуємо не зберігати пам'ять завідомо непотрібні дані з незайнятих регістрів
  • для цього після запису зайнятих регістрів функції, збережемо маску їх зайнятості
  • а для цього, у свою чергу, доведеться FILL&SPILL робити не за кількістю необхідних регістрів, а по-фреймно: все, що стосується одного виклику за раз
  • тоді в поточному початку кільцевого буфера регістрів завжди буде описувач кадру (наступного кандидата на SPILL)
  • перший регістр, який ми дістаємо при FILL'е буде містити маску (або її частина) використаних регістрів, з використанням якої ми дістанемо з пам'яті потрібну кількість регістрів, що і вимагалося
Однак, зосередившись на зовнішній стороні виклику функцій ми упустили з виду те, як все це буде виконуватися всередині. Автор не вважає себе спеціалістом по «залізу», але проблеми все ж передбачає.
На щастя, розбиратися з ними ми будемо в наступній статті.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.