Модель виконання: фрейми й продовження

Рішення плану 11, крок 17 (2026-10-05). Воно визначає, як згенеровані функції Erlang викликають, повертають керування, призупиняються й зазнають збою, коли з'являються рекурсія, хвостові виклики й процеси. Крок 19 реалізував виклики, повернення, хвостові виклики й фрейми (Реалізація перелічує, що ще відкрито); кроки 23, 24, 26 і 43 будуються на ньому.

Рішення

Кожен процес Erlang виконується на власному пласкому стеку явних фреймів, а згенерований код переходить між функціями лише через гарантовані хвостові передачі (LLVM musttail). Нехвостовий виклик зберігає продовження (continuation) того, хто викликає, у його фреймі й переходить до функції, яку викликають; повернення переходить назад до цього продовження. Тому нативний стек лишається завглибшки в один виклик над планувальником, хоч якою глибокою була б рекурсія Erlang, а процес може зупинитися на будь-якій передачі й пізніше відновитися на будь-якому потоці.

• Один плаский стек на процес замінює сегментований стек коренів 8F. Він містить заголовки фреймів і слоти, зростає переміщенням і адресується як база плюс зсув.
• Кожна функція, якій потрібен фрейм, знижується (lowering) до входу (entry) і тіла (body). Тіло починається з switch за індексом продовження фрейму, тож одна функція LLVM зберігає всі блоки, точки злиття й обробники функції.
• Аргументи й результати передаються в регістрах процесу x[0..n) (X-регістри BEAM); кожен вказівник на код має єдину сигнатуру void code(Process *).
• Винятки розмотують фрейми до найглибшого фрейму, чий заголовок називає продовження-обробник.

Стан процесу

Фрейми

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

Дескриптор розширює нинішній abi::v1::FrameDescriptor (дескриптор модуля, слоти атомів модуля й функції, арність) вказівниками на код входу й тіла та кількістю слотів. Слова заголовка не є термами; обхідник іде за previous і читає кількість слотів із дескрипторів. Нижній фрейм (bottom frame), що належить runtime, лежить під першим викликом кожного процесу: продовження 1 — це нормальний вихід (результат у x[0]), продовження 2 — обробник неперехопленого винятку.

Операції

• Виклик (нехвостовий). Живі значення вже лежать у слотах (нинішнє правило коренів). Той, хто викликає, встановлює свій resume на наступний індекс продовження, пише аргументи в x[0..n) і передає керування на вхід функції, яку викликають. Віддалений виклик передає керування на експортований символ входу.
• Вхід. Рахує одну редукцію (див. поступання), заштовхує обнулений фрейм (переміщуючи стек, коли він повний), копіює x[0..n) у слоти, встановлює resume = 0 і передає керування тілу.
• Повернення. Функція, яку викликали, пише результат у x[0], виштовхує свій фрейм (top = frame, frame = previous) і передає керування тілу того, хто викликав, яке перемикається за його resume.
• Хвостовий виклик. Аргументи йдуть у x[0..n), той, хто викликає, виштовхує свій фрейм без передачі, потім передає керування на вхід функції, яку викликають. Метою повернення лишається той, хто викликав того, хто викликає, тож хвостова рекурсія виконується в сталому стеку Erlang і нативному стеку. Локальні, взаємні й віддалені хвостові виклики — це той самий перехід.
• Поступання (yield). Кожен вхід витрачає одну редукцію. На нулі він записує себе в resume_at і повертається до планувальника замість заштовхування фрейму; аргументи лишаються в x[0..arity), які тоді є єдиними регістрами процесу, що є коренями. Відновлення поповнює бюджет і передає керування на resume_at, що повторює вхід. Пізніші очікування (receive, крок 46) зберігають замість входу індекс продовження тіла.
• Вихід. Повернення в нижній фрейм записує нормальний вихід; розмотування до нього записує неперехоплений виняток. В обох випадках код повертається до планувальника.
• Поширення винятків. Породження винятку чи невдала перевірка служби записує помилку в канал, як нині, і називає для трасування 8 найглибших фреймів із ланцюга фреймів. Потім розмотувач виштовхує фрейми, чий handler дорівнює 0, встановлює resume = handler у першому фреймі, що його має, і передає керування його тілу. Обробники catch, try і after — це індекси продовжень; вхід у захищену ділянку встановлює handler, а вихід із неї відновлює охопний індекс, обидва відомі статично в межах однієї функції. Halt і збої інфраструктури пропускають кожен обробник і розмотуються прямо до нижнього фрейму, як вони пропускають обробники нині. Обробник забирає виняток нинішніми службами (CLAUSE_catch_v1, CLAUSE_exception_v2) і повторно породжує його через розмотувач.
• Виклик із боку хоста. Runtime заштовхує нижній фрейм, завантажує x[] і виконує цикл планувальника, доки не досягне цього фрейму. Служби runtime лишаються звичайними нативними викликами й ніколи не входять повторно в згенерований код; запускає його лише цей цикл хоста.

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

Видимість коренів

На кожній передачі й кожній точці безпеки корені процесу такі: усі слоти всіх фреймів на його стеку, x[0..live) і корисне навантаження, список аргументів і терм стека каналу збоїв (уже корені процесу). Слова передачі результату нинішнього стеку коренів зникають; їхню роль бере x[0].

Значення ніколи не переживають передачу в нативних регістрах чи значеннях SSA. Кожне тіло перезавантажує адресу свого фрейму з stack + frame після входу й читає живі значення зі слотів. У межах одного продовження служба, що може заштовхнути фрейм чи перемістити купу, робить недійсними всі вказівники на слоти й на купу, що зберігаються в значеннях SSA; правило перезавантаження для збирань визначено в розділі збирання в згенерованому коді.

Наступник стеку коренів 8F

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

• заголовки фреймів живуть у стеку, слоти адресуються як stack + frame + header + index;
• блок зростає подвоєнням і переміщенням (realloc), ніколи не зменшується під час виконання й відокремлений від блоку купи;
• межу в 4 096 фреймів прибрано; слова стека враховуються в бюджеті пам'яті процесу, а його перевищення — це задокументований збій кроку 20.

Цільові платформи

musttail з уніфікованою сигнатурою void (Process *) приймається кожною потрібною цільовою платформою на O0 і O2 (прототип нижче, clang 23.1.2):

Бекенд повідомляє про помилку, коли не може виконати виклик musttail, тож успішна компіляція і є гарантією. Запасний варіант для майбутньої цілі, що його відхилить: трамплін. Кожен код повертає наступний вказівник на код до циклу планувальника замість переходу (null призупиняє); фрейми, корені й індекси продовжень не змінюються. Жодна потрібна ціль цього не потребує.

Реалізація

Крок 19 (2026-10-05) реалізує модель із такими рішеннями й прогалинами:

• Два етапи. Зниження все ще видає нативну форму: одну функцію TermWord(context, arguments) на функцію Erlang, звичайні виклики між ними, заповнювач — виклик clause.frame, що називає слоти термів, і ret результату виклику в хвостовій позиції. Потім lower_frames (compiler/src/codegen/frames.cpp) переносить кожне тіло в <symbol>.body, додає пролог (заголовок фрейму, регістри, перемикач відновлення), розбиває блоки після нехвостових викликів і точок безпеки в головах циклів, вивантажує значення, що використовуються після них (терми — у слоти термів, інші слова — в сирі слоти), виносить сталі адреси слотів у пролог і перетворює виклики, хвостові виклики й повернення на передачі musttail. Спеціалізація типів і тестові шви працюють із нативною формою; бекенд виконує lower_frames перед інспекцією IR, а optimize виконує його, якщо це ще потрібно.
• Вхід і тіло. Окремої функції входу немає: той, хто викликає, викликає CLAUSE_enter_v1(context, callee.frame), що заштовхує фрейм, копіює аргументи й повертає тіло функції, яку викликають. Хвостовий виклик використовує CLAUSE_tail_v1, що спершу звільняє фрейм того, хто викликає.
• Хвостові позиції — це останній вираз тіла клаузи, якщо йти крізь блоки, дужки й тіла клауз case та if. Виклики в операндах catch, try, maybe і andalso/orelse не є хвостовими.
• Винятки повертаються через кожного, хто викликав, і той перевіряє канал після виклику, як і раніше; індекси обробників і пряме розмотування лишаються оптимізацією. Трасування стека читають ланцюг фреймів у момент породження винятку.
• Цикли. Генератори comprehension — це цикли всередині одного тіла. Їхні курсори й акумулятор живуть у слотах термів, тож жодне значення SSA не переноситься через цикл, а точка відновлення всередині нього не потребує нічого, окрім звичайних вивантажень.
• Поступання (крок 43, процеси). CLAUSE_enter_v1 і CLAUSE_tail_v1 витрачають одну з редукцій процесу; коли їх не лишилося, вони записують функцію, в яку входять (ProcessStack::resume_, resume_at моделі), тримають її аргументи як корені-регістри й повертають код, що завершує квант часу, тож нативний стек розмотується до виконавця, який згодом повторює вхід. Голови циклів не поступаються. Збирач обходить слоти термів фреймів, регістри, які призупинення тримає живими (ProcessStack::keep_registers), і канал збоїв (крок 23, корені). Входи у функції й голови циклів comprehension — це точки безпеки, що збирають сміття, коли купа цього просить (крок 26, збирання в згенерованому коді); сирі слоти вивантаження ніколи не містять термів.
• Без обмеження. Стек зростає, доки хост не відмовить у пам'яті, що завершується збоєм out_of_memory (код виходу 70, виконувані файли), як зростає процес OTP. Необов'язкове обмеження на процес StackOptions::limit_words (окреме від необов'язкового бюджету купи) завершує заштовхування понад нього збоєм resource_limit. Фрейми нині займають 4 слова заголовка плюс 1-40 слотів.
• Вхід із боку хоста. Експортований символ зберігає нативну сигнатуру й виконує свою функцію над нижнім фреймом runtime через CLAUSE_invoke_v1; нативні винятки, кинуті службами, стримуються там.

Порівняння альтернатив

Прототип у tests/prototypes/execution_model: ті самі функції Erlang (sum/1 — рекурсія в тілі, loop/2 — хвостова рекурсія, fail/1, що породжує boom на глибині N, catcher/1, що його перехоплює), знижені вручну трьома способами. Хост: Windows x64, clang 23.1.2; час — одиничні запуски на O2. Запуск: python tests/prototypes/execution_model/run.py.

Варіант обраної моделі з трампліном проходить ті самі запуски (20 мс на рекурсію, 16 мс на 10M хвостових викликів на O2). Відхилено:

• Нативні виклики з явними кореневими фреймами. Глибока рекурсія потребує нативного стека на процес, розрахованого на найглибший виклик; призупинення потребує перемикання стеків, специфічного для кожної цілі; 32-бітні цілі не можуть резервувати великі стеки для багатьох процесів.
• Корутини LLVM. Одне виділення на виклик, немає хвостових викликів, непрозорі для збирача фрейми, проходи корутин навіть на O0, а симетрична передача однаково залежить від musttail.
• Одна функція LLVM на продовження (класичний CPS). Ті самі передачі, але точки злиття й обробники, досяжні з кількох продовжень, довелося б розбивати на додаткові функції; перемикач відновлення зберігає нинішній обхідник однієї функції.

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

Свідчення прототипу

run.py збирає обрану модель (musttail і трамплін), нативну базову лінію й модель корутин для хоста на O0 і O2, запускає їх і компілює вручну знижені функції (generated.cpp, freestanding) для кожної цілі вище на O0 і O2, рахуючи виклики musttail в IR і хвостові переходи в асемблері. Результат 2026-10-05: PASS. Для обраної моделі на обох рівнях: повернення (42), рекурсія в тілі завглибшки 1 000 000, 10 000 000 хвостових викликів, помилка, породжена на глибині 100 000 і перехоплена фреймом обробника, та сама помилка без перехоплення (нижній фрейм, трасування з 8 фреймів fail) і два процеси, що чергуються квантами по 4 000 редукцій (1 002 кванти). Усі 15 місць передачі є musttail на O0 на кожній цілі (14 на O2 після вбудовування).

Тіло sum/1 для i686-pc-windows-msvc (IR на O2, імена скорочено). IR для x86_64-pc-windows-msvc такий самий, зі словами i64 і подвоєними зсувами.

%2 = load ptr, ptr %0, align 4                      ; stack base
%3 = getelementptr inbounds nuw i8, ptr %0, i32 8
%4 = load i32, ptr %3, align 4                      ; current frame offset
%5 = getelementptr inbounds nuw [4 x i8], ptr %2, i32 %4
%6 = getelementptr inbounds nuw i8, ptr %5, i32 16  ; slot 0 (N)
%7 = getelementptr inbounds nuw i8, ptr %5, i32 8   ; header: resume index
%8 = load i32, ptr %7, align 4
%9 = icmp eq i32 %8, 0                              ; switch on resume
...
16:                                                 ; N > 0: call sum(N - 1)
  store i32 1, ptr %7, align 4                      ; resume = 1
  ...                                               ; x0 = N - 1
  %19 = tail call ptr @call(ptr %0, ptr @SUM)       ; push frame or park
  musttail call void %19(ptr nonnull %0)
  ret void
20:                                                 ; resume 1: x0 += N
  ...
  %24 = tail call ptr @leave(ptr %0)                ; pop, caller body
  musttail call void %24(ptr nonnull %0)
  ret void