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

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

Рішення

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

• Один плаский стек на процес (ProcessStack, process/stack) містить заголовки фреймів і слоти, зростає переміщенням і адресується як база плюс зсув.
• Кожна функція — це одна функція LLVM, її тіло (body), що починається з switch за індексом відновлення фрейму, тож вона зберігає всі блоки, точки злиття й обробники функції.
• Аргументи й результати передаються в регістрах процесу x[] (X-регістри BEAM). Кожен вказівник на код має єдину сигнатуру abi::v1::Code, void(void *context, TermWord x0, ..., TermWord x5): перші abi::v1::register_arguments (6) регістрів передаються також як параметри, тож початкові аргументи виклику й результат повернення лишаються в машинних регістрах.
• Збій повертається через кожного, хто викликав, і той перевіряє канал збоїв після виклику (канал збоїв).

Стан процесу

abi::v1::FrameState стоїть на початку кожного контексту, тож згенерований код читає й оновлює його вбудовано:

heap_top/heap_limit, runtime і self обслуговують вбудоване виділення, завантаження атомів і self/0 (фрейми й передачі). Призупинений процес записує вхід, з якого він продовжує, у ProcessStack::resume_.

Фрейми

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

Дескриптор <symbol>.frame називає модуль, функцію й арність і містить вказівник на код тіла та кількість слотів (abi). Слова заголовка не є термами; обхідник іде за previous і читає кількість слотів із дескрипторів. Нижній фрейм (bottom frame), що належить runtime, лежить під першим викликом кожного процесу й кожного виклику з боку хоста: повернення в нього зберігає результат у першому регістрі й завершує нативний виклик.

Операції

• Виклик (нехвостовий). Значення, живі після виклику, вивантажуються в слоти. Той, хто викликає, встановлює свій resume на наступний індекс продовження, кладе аргументи в регістри й передає керування функції, яку викликають. Локальні, віддалені, fun- і динамічні виклики — це та сама передача; виклик fun чи динамічний виклик спершу запитує в служби підготовки FrameDescriptor функції, яку викликають (fun).
• Вхід. Витрачає одну редукцію, заштовхує обнулений фрейм (нарощуючи стек, коли він повний), копіює аргументи понад параметри в слоти, встановлює resume = 0 і передає керування тілу функції, яку викликають.
• Повернення. Функція, яку викликали, передає результат як x0, виштовхує свій фрейм (top = frame, frame = previous) і передає керування тілу того, хто викликав, яке перемикається за його resume.
• Хвостовий виклик. Той, хто викликає, виштовхує свій фрейм без передачі, потім входить у функцію, яку викликають, на своєму місці. Метою повернення лишається той, хто викликав того, хто викликає, тож хвостова рекурсія виконується в сталому стеку Erlang і нативному стеку. Хвостовий виклик самого себе лишає фрейм на місці: він витрачає редукцію, скидає слова відновлення й обробника фрейму та лічильник живих значень і копіює аргументи понад параметри, не переписуючи заголовок і не обнуляючи слоти; LLVM перетворює його на цикл. Хвостовий виклик іншого члена циклу хвостових викликів того, хто викликає (функцій одного модуля, які досягають одна одної через хвостові виклики), зберігає зв'язок із тим, хто викликав, і слоти термів, що є в обох фреймах: він записує дескриптор функції, яку викликають, обнуляє лише ті її слоти термів, що виходять за слоти того, хто викликає, і пропускає перевірку межі стека, коли фрейм функції, яку викликають, не більший. Як і при хвостовому виклику самого себе, збережений слот може містити терм попереднього члена, доки функція, яку викликають, його не запише, тож збирання можуть тримати такий терм живим трохи довше. Члени циклу мають одну спільну нативну функцію: дескриптор кожного члена вказує її як тіло, індекси відновлення нумеруються наскрізно для всіх членів, а старт (resume 0) вибирає члена за дескриптором фрейму, тож хвостовий виклик між членами є розгалуженням замість передачі. Налагоджувачі бачать членів як вбудовані в цю функцію.
• Поступання (yield). Коли редукцій не лишилося, вхід не заштовхує фрейм: він записує себе в ProcessStack::resume_, тримає свої аргументи як корені-регістри (ProcessStack::keep_registers) і повертає код, що завершує квант часу, тож нативний стек розмотується до виконавця, який згодом поповнює бюджет і повторює вхід. Голови циклів comprehension теж витрачають редукцію й поступаються через вхід, коли редукцій не лишилося. receive чекає через вбудовану функцію CLAUSE_wait_frame_v1, у яку входять як у виклик (receive).
• Вихід. Повернення в нижній фрейм завершує процес із його результатом; збій, що повертається в нього, завершує процес зі збоєм.
• Винятки. Породження винятку чи невдала перевірка служби записує помилку в канал і копіює 8 найглибших фреймів ланцюга для трасування стека (трасування стека). Кожен, хто викликав, перевіряє канал після виклику й одразу повертається або переходить до блоку обробника охопного catch, try чи after у тому самому тілі (канал збоїв). Halt і збої інфраструктури пропускають кожен обробник і повертаються до нижнього фрейму.
• Виклик із боку хоста. Експортований символ зберігає нативну сигнатуру й виконує свою функцію над нижнім фреймом через CLAUSE_invoke_v1, відновлюючи її після кожного поступання; нативні винятки, кинуті службами, стримуються там. Служби runtime лишаються звичайними нативними викликами й ніколи не входять повторно в згенерований код.

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

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

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

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

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

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

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

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

Реалізація

• Два етапи. Зниження (lowering) видає нативну форму: одну функцію TermWord(context, arguments) на функцію Erlang, звичайні виклики між ними, заповнювач — виклик clause.frame, що називає слоти термів, і ret результату виклику в хвостовій позиції. Потім lower_frames (compiler/src/codegen/frames.cpp) переносить кожне тіло в <symbol>.body, додає пролог (заголовок фрейму, регістри, перемикач відновлення), розбиває блоки після нехвостових викликів і точок безпеки в головах циклів, вивантажує значення, що використовуються після них (терми — у слоти термів, інші слова — в сирі слоти), виносить сталі адреси слотів у пролог і перетворює виклики, хвостові виклики й повернення на передачі musttail. Спеціалізація типів і тестові шви працюють із нативною формою; бекенд виконує lower_frames перед інспекцією IR, а optimize виконує його, якщо це ще потрібно.
• Вбудовані передачі. Входи, хвостові входи й повернення виконуються вбудовано над FrameState. Кожен із них переходить до CLAUSE_enter_v1, CLAUSE_tail_v1 або CLAUSE_return_v1, коли купа потребує збирання, процес профілюється, редукцій не лишилося, стек має зрости чи досягти межі або функція, яку викликають, є вбудованою. Перевірка збою після виклику читає слово failed стану. Сервісні шляхи зберігають параметри в масив регістрів перед сервісом і перезавантажують їх після нього.
• Параметри. Тіло читає свої початкові аргументи з параметрів на старті, а результат виклику — з x0 під час відновлення; lower_frames вивантажує будь-яке з них у слот, лише коли воно живе через виклик або точку безпеки. Варіант циклу для чисел із рухомою комою (abi) приймає деякі параметри як біти чисел подвійної точності: їх передають лише його вбудовані передачі, а сервісні шляхи натомість входять у функцію з комірками, тож регістри, які читає служба, містять терми.
• Хвостові позиції — це останній вираз тіла клаузи, якщо йти крізь блоки, дужки й тіла клауз case, if та receive. Виклики в операндах catch, try, maybe і andalso/orelse не є хвостовими.
• Цикли. Генератори comprehension — це цикли всередині одного тіла. Їхні курсори й акумулятор живуть у слотах термів, тож жодне значення SSA не переноситься через цикл, а точка відновлення всередині нього не потребує нічого, окрім звичайних вивантажень.
• Точки безпеки. Входи у функції й голови циклів comprehension збирають сміття, коли купа цього просить (збирання в згенерованому коді); сирі слоти вивантаження ніколи не містять термів.
• Без обмеження. Стек зростає, доки хост не відмовить у пам'яті, що завершується збоєм out_of_memory (код виходу 70, виконувані файли), як зростає процес OTP. Необов'язкове обмеження на процес StackOptions::limit_words (окреме від необов'язкового бюджету купи) завершує заштовхування понад нього збоєм resource_limit.

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

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

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

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