Некоторое время назад я добавил в свой язык программирования Ü такой функционал, как генераторы. В этой статье я хочу поведать, как это было сделано и зачем.
Данная статья будет полезна как интересующимся компиляторостроением, так и тем, кому интересно внутреннее устройство генераторов в частности и корутин вообще.
Что есть такое генератор
Прежде всего стоит отметить, что генераторы есть частный случай корутин.
А что же такое есть корутина? Это такая функция, которая может приостанавливать и возобновлять своё выполнение. При этом она сама решает, когда это делать — посредством специальных операторов, например. Это отличает корутины от любого другого кода, который может быть остановлен только планировщиком ОС, но зато в произвольном месте.
Так вот, генератор — это такая корутина, которая после приостановки своего выполнения порождает некоторое значение — результат. Генератор при этом может завершиться (как и любая другая функция), тогда результат уже не будет порождён.
Что нужно для корутин
Корутина отличается от обычной функции тем, что во время, когда она остановлена, ей нужно где-то особым образом сохранять своё состояние — аргументы, локальные переменные и ссылки, временные значения, адрес остановки и т. д. Использовать стек данных, как обычные функции, корутина не может, т. к. после приостановки работы стек переходит под контроль вызывающего кода и может быть перезаписан. Поэтому корутина должна использовать некий отдельный участок памяти для хранения своего состояния.
Существуют разные подходы для выделения памяти под состояние корутин. Первый подход — выделять необходимое количество памяти из кучи, или вообще, запрашивать целый отдельный стек у ОС. Второй подход — переложить выделение памяти на вызывающий код, например, выделив память из стека (с сохранением гарантии неизменности этой области памяти), или использовать память части некого объекта (поле структуры).
Также для корутины надо где-то хранить её статус — завершена ли она, или ещё нет. Для корутин, возвращающих результат (в т. ч. генераторов) нужно где-то хранить этот результат. Кроме того, в языках с исключениями надо ещё хранить опциональное исключение, которое могло возникнуть при выполнении корутины. Для всех этих целей можно использовать тот же блок памяти, что и для остального состояния корутины.
Корутины с точки зрения языка высокого уровня
В ЯП высокого уровня корутины — это функции, возвращающие объект специального типа-корутины. Данный объект инкапсулирует управление памятью состояния корутины, ответственен за её разрушение. К объекту корутины применимы операции запроса статуса (корутина завершилась/ещё нет), попытки возобновления выполнения и получения результата этого выполнения.
Корутины в библиотеке LLVM
Уже несколько лет в библиотеке LLVM (на которой основан компилятор Ü) существует инфраструктура для поддержки корутин. В своё время Gor Nishanov сделал презентацию, раскрывающую, в общем, как эта инфраструктура работает. Интересующимся рекомендую её посмотреть.
Суть поддержки корутин в LLVM следующая: фронтенд компилятора строит функцию-корутину почти так же, как и обычную функцию. Разница заключается лишь в том, что функцию-корутину фронтенд помечает специальным образом и добавляет специальный код для инициализации корутины. Это код включает в себя также выделение памяти под состояние корутины из кучи.
Для работы с корутинами существуют специальные встроенные функции — вроде llvm.coro.done, llvm.coro.resume, llvm.coro.destroy, llvm.coro.promise, которые соответственно позволяют узнать состояние объекта-корутины, возобновить её исполнение, разрушить объект-корутину, получить адрес результата.
Существуют специальные проходы LLVM, которые раскрывают вызовы llvm.coro функций, определяют необходимый размер блока памяти под состояние корутины, осуществляют сохранение/восстановление состояния при возобновлении/приостановке исполнения.
В Ü используется вариант корутин, работающих по схеме switch-resume. В этой схеме исходная функция-корутина разбивается на три части. Первая часть собственно создаёт объект корутины — выделяет под него память и инициализирует его. Вторая часть — функция возобновления исполнения корутины. Эта функция содержит внутри switch по номеру точки приостановки корутины, который передаёт исполнение в ту точку, с которой управление приостановилось в прошлый раз. Поэтому то данная схема и называется switch-resume. Третья часть — функция разрушения корутины. Она аналогично содержит внутри себя switch и вызывает код разрушения, соответствующий состоянию, в котором корутина была приостановлена. Указатели на две последних функции первая функция записывает в блок памяти состояния корутины. Функции llvm.coro.resume и llvm.coro.destroy соответственно раскрываются в вызовы этих функций через указатели, хранящиеся в блоке памяти состояния корутины.
Точки останова в функции-корутине помечаются через вызов llvm.coro.suspend. Эта функция возвращает результат операции. Возможны три варианта результата. Первый — выполнена приостановка, тогда функция-корутина должна тут же вызвать llvm.coro.end и завершиться. Второй — выполнено возобновление, в этом случае функция-корутина должна продолжить работу. Третий — запрошено разрушение корутины и должен отработать код разрушения.
Стоит ещё отметить, что корутины в библиотеке LLVM легковесны в том плане, что память в них выделяется строго под состояние текущей функции-корутины. Для вызовов обычных функций из этой корутины используется стек вызывающего корутину кода. Так можно делать, т. к. приостановка работы корутины происходит непосредственно из неё, а значит состояние тех функций, что она вызывает, сохранять не надо.
О выделении памяти под корутины
Как было отмечено выше, память под состояние корутины выделяется из кучи. Данный подход имеет как достоинства, так и недостатки.
Достоинство такого подхода заключается в том, что размер блока памяти, необходимого для хранения состояния корутины, определяется бекендом компилятора и основывается уже на оптимизированной версии функции. Это позволяет выделять памяти по-минимуму, только под те части состояния корутины, которые реально нужно сохранять. Если бы тот же самый анализ того, что нужно сохранять, выполнял бы фронтенд компилятора, то объём памяти получался бы в общем случае большим, т. к. фронтенд не в состоянии, например, выбросить некоторые временные переменные, сократить время жизни именованных переменных, провести регистровые оптимизации и т. д.
Ещё одно достоинство — все объекты корутин имеют один фиксированный размер, равный размеру указателя. Это позволяет в языке использовать один и тот же тип для хранения объектов-корутин, полученных из разных функций-корутин. Главное, чтобы тип возвращаемого значения был одним и тем же. При этом даже можно одну и ту же переменную типа корутины использовать для хранения объектов-корутин, полученных вызовом функций-корутин с разной сигнатурой.
Главный и очевиднейший недостаток данного подхода — выделение памяти из кучи накладно. Но данный недостаток нивелируется, в некоторых случаях. Бекенд LLVM может заменить аллокацию памяти из кучи под состояние корутины стековой аллокацией. Обычно это происходит для корутин, которые создаются, используются и разрушаются в рамках одной функции. При этом даже возможно полное устранение аллокаций из кучи для корутин, которые сами внутри себя создают корутины. Но оптимизация эта в общем случае не гарантирована, а значит это нужно при использовании корутин иметь в виду — быть готовым к аллокации из кучи, или просматривать скомпилированный код, чтобы удостовериться, что аллокация из кучи была устранена.
Как генераторы реализованы в Ü
С теорией всё теперь более-менее понятно. Итак, как же конкретно в Ü работать с генераторами?
Прежде всего нужно объявить функцию-генератор с использованием ключевого слова generator:
fn generator SomeGen() : i32
{
//
}Теперь нужно, чтобы этот генератор мог порождать какие-либо значения. Для этого в язык добавлен оператор yield. Этот оператор можно использовать в генераторах (и только в них). Он отчасти похож на оператор return, но в отличие от него не завершает исполнения функции, а только приостанавливает его.
fn generator SomeGen() : i32
{
// Данный генератор породит три значения, после чего завершится
yield 1;
yield 2;
yield 3;
}Внутри оператор yield работает следующим образом: он инициализирует возвращаемое значение, сохраняет состояние генератора и передаёт управление вызывающему корутину коду. При возобновлении выполнения генератора управление передастся коду, следующему за оператором yield.
Кроме оператора yield в генераторах можно использовать и оператор return. Оператор return без значения просто завершит генератор. Генератор также завершится, если поток управления достиг конца функции. Оператор return со значением аналогичен комбинации операторов yield и пустого return.
Теперь вопрос — как работать с генераторами? Для возобновления работы корутин (в т. ч. и генераторов) в языке реализован оператор if_coro_advance. Данный оператор проверяет, не завершилась ли корутина, если ещё нет — возобновляет её работу. В случае, если корутина — генератор и после его возобновления и приостановки он ещё не завершён, происходит извлечение результата и управление передаётся блоку кода, который с этим результатом будет работать.
fn generator SomeGen() : i32;
fn PrintInt(i32 x);
fn Foo()
{
auto mut gen= SomeGen(); // Создаём объект генератора
if_coro_advance( x : gen )
{
// Генератор отработал и вернул значение.
PrintInt(x);
}
else
{
// Генератор завершился.
}
}Типы генераторов в Ü
Функция-генератор на самом деле является функцией, возвращающей объект-генератор. Тип этого объекта — специальный класс, генерируемый компилятором. В тип генератора входит тип возвращаемого значения (с модификаторами ссылочности/изменяемости), а также ряд вспомогательных флагов (для обозначения наличия внутренней ссылки и потоконебезопасной внутренней изменяемости).
Можно явно объявить переменную (параметр функции, поле структуры и т. д.) типа генератора, используя для этого специальный синтаксис.
fn generator IntGen() : i32;
fn generator FloatRefGen() : f32&;
fn Foo()
{
var (generator : i32) gen0= IntGen();
var (generator : f32&) gen1= FloatRefGen();
}Типы генераторов имеют деструктор. Имеется также оператор сравнения на равенство, при этом равенство истинно, только если объект сравнивается сам с собою. Само собою разумеется, тип генератора некопируем — отсутствуют конструктор копий и оператор копирующего присваивания.
Тип генератора включает в себя вид внутренней логической ссылки. Это необходимо для механизма проверки ссылок. Генератор или не содержит в себе ссылок вовсе, или содержит неизменяемые ссылки, или содержит изменяемые ссылки. Для функций-генераторов этот вид определяется автоматически — исходя из её сигнатуры. Если отсутствуют ссылочные параметры, то и внутренние ссылки у объекта-генератора отсутствуют. Если есть параметры-неизменяемые ссылки (только неизменяемые), то считается, что объект генератор содержит в себе неизменяемые ссылки. Ну а если же есть параметры-изменяемые ссылки, то вид внутренней ссылки будет изменяемым. Также на вид внутренней ссылки влияют параметры-значения (если они могут содержать внутри ссылки).
При явном обозначении типа генератора можно указать вид внутренней ссылки, причём с тегом (хоть он пока и не используется).
fn generator IntGen(i32& x) : i32; // Функция-генератор захватывает ссылку на свой параметр
fn Foo()
{
var i32 x = 66;
var (generator'imut some_tag' : i32) gen= IntGen(x);
}Если какая-то переменная имеет ссылку внутри объекта-генератора, эту переменную менять нельзя и компилятор породит ошибку при попытке изменения. Это аналогично тому, как если бы на эту переменную существовала ссылка в обычном объекте типа класса (например, в каком-нибудь optional_ref).
fn generator IntGen(i32& x) : i32;
fn Foo()
{
var i32 mut x = 66;
auto gen= IntGen(x);
++x; // Компилятор породит ошибку, т. к. "gen" содержит внутри себя ссылку на "x"
}Ещё тип генератора может иметь тег non_sync. Этот тег используется для пометки типов, которые содержат внутри себя потоконебезопасную внутреннюю изменяемость. Подробнее о том, зачем оно нужно, можно прочесть в документации. Также у функций-генераторов, имеющих non_sync параметры или возвращаемые значения, необходимо указывать явно non_sync тег. Необходимо это затем, чтобы не требовать в месте объявления функции-генератора полноты типов параметров, которая нужна была бы для автоматического вывода non_sync тега.
struct A non_sync{}
fn generator non_sync SomeGen(A a) : f64;
fn Foo()
{
var (generator non_sync : f64) gen= SomeGen(A());
}Разрушение корутин
Как было упомянуто выше, у объектов-корутин (в т. ч. генераторов) существует деструктор. Нужен он для того, чтобы можно было разрушить объект типа корутины, не дожидаясь его завершения. Более того, некоторые корутины (особенно генераторы) могут вообще никогда не завершиться — иметь внутри бесконечный цикл, так что ждать их завершения не имеет смысла.
Деструктор корутины вызывает как положено деструкторы всех локальных переменных и аргументов-значений. Каждая точка приостановки корутины имеет свой код разрушения — для тех переменных, что существуют в этой точке. Деструкторы для этой точки вызываются, как если бы в обычной функции там стоял return.
Важной особенностью корутин, на которую стоит обратить внимание, является тот факт, что любая точка приостановки (yield и т. д.) является также и неявной точкой возврата — из-за потенциальной возможности разрушить корутину после её приостановки. Практически это означает, что парный код инициализации-деинициализации может быть потенциально разбит, если между инициаилизацией и деинициализацией есть точки приостановки корутины. А это может привезти к неприятным ошибкам — например, когда мьютекс захватили, но не освободили, т. к. корутина разрушилась. Чтобы избежать такого, надо или избегать кода приостановки состояния между кодом инициализации и кодом деинициализации, или же использовать RAII — когда код деинициализации отрабатывает в деструкторе соответствующего объекта, который будет вызван даже в случае разрушения корутины.
Некоторые детали реализации
Компилятор для каждой корутины создаёт как минимум две точки останова — начальную и конечную. Начальная точка остановки создаётся почти сразу, ей предшествует разве что только код перемещения аргументов-значений в память корутины. Сделано это затем, чтобы при создании объекта-корутины (начальном вызове функции-корутины) не выполнялось никаких тяжёлых действий. Конечная точка останова создаётся для состояния, когда корутина завершилась. При этом при достижении этой точки вызываются все деструкторы локальных переменных и аргументов, вместо того, чтобы дожидаться, кода отработает деструктор объекта-корутины.
Интересной особенностью генерации кода корутин является условность выделения памяти под её состояние. Перед тем, как позвать функцию аллокации (malloc) следует для начала через вызов llvm.coro.alloc проверить необходимость в этом. Аналогично с вызовом функции деаллокации (free) — необходимость проверяется через результат вызова llvm.coro.free. Сделано это для того, чтобы работала оптимизация удаления аллокации из кучи. Если бекенд LLVM заоптимизировал аллокацию, llvm.coro.alloc вернёт false и код аллокации, созданный фронтендом, вызываться не будет. В проходах LLVM для корутин эта оптимизация реализована специальным образом. Другие проходы оптимизации не всегда могут заоптимизировать вызовы malloc и free, т. к. они могут потенциально содержать сторонние эффекты.
В процессе реализации я наткнулся на неочевидную с первого взгляда проблему. В функциях некоторые аргументы-значения (композитные типы больших размеров) могут передаваться через скрытую ссылку, указывающую на блок памяти, выделяемый вызывающей стороной и который живёт только до конца вызова. Для корутин, как оказалось, это не допустимо, ибо происходит неявный захват ссылки на блок памяти, не живущий достаточно долго. Решена эта проблема была относительно просто — функции-корутины копируют во внутренний блок памяти аргументы-значения, передаваемые по скрытой ссылке.
Механизм передачи результата генераторов через yield работает в Ü весьма эффективно. Оператор yield конструирует значение-результат в специальной области структуры состояния корутины. Вызывающая сторона ответственна за то, чтобы извлечь этот результат и где-то его сохранить и разрушить. Встроенный оператор if_coro_advance именно так и делает. Такой подход позволяет избежать лишних копирований результата а также не беспокоиться о том, что результат может быть забыт и не разрушен. Это отличает генераторы в Ü от таковых в C++, где результат хранится в структуре генератора как обычное поле, для которого в конечном итоге нужно всегда вызывать деструктор.
Примеры внутреннего представления
Предположим, что есть такой код с использованием генератора:
fn generator SimpleGen() : i32
{
yield 12345;
}
fn PrintInt(i32 x);
fn Foo()
{
auto mut gen= SimpleGen();
if_coro_advance( x : gen )
{
PrintInt(x);
}
else
{
halt; // Ожидается, что генератор отработает хотя бы один раз
}
}Фронтенд компилятора генерирует следующий IR-код:
; Function Attrs: nounwind
define void @_Z3Foov() unnamed_addr #2 comdat {
allocations:
%0 = alloca %"9generatorIiLj0EE", align 8
br label %func_code
func_code: ; preds = %allocations
call void @llvm.lifetime.start.p0(i64 8, ptr %0)
%1 = call ptr @_Z9SimpleGenv()
store ptr %1, ptr %0, align 8
%coro_handle = load ptr, ptr %0, align 8
%coro_done = call i1 @llvm.coro.done(ptr %coro_handle)
br i1 %coro_done, label %if_coro_advance_else, label %coro_not_done
coro_not_done: ; preds = %func_code
call void @llvm.coro.resume(ptr %coro_handle)
%coro_done_after_resume = call i1 @llvm.coro.done(ptr %coro_handle)
br i1 %coro_done_after_resume, label %if_coro_advance_else, label %not_done_after_resume
not_done_after_resume: ; preds = %coro_not_done
%x = call ptr @llvm.coro.promise(ptr %coro_handle, i32 4, i1 false)
%2 = load i32, ptr %x, align 4
call void @_Z8PrintInti(i32 %2)
br label %after_if_coro_advance
if_coro_advance_else: ; preds = %coro_not_done, %func_code
call void @__U_halt()
unreachable
after_if_coro_advance: ; preds = %not_done_after_resume
call void @_ZN9generatorIiLj0EE10destructorERS0_(ptr %0)
call void @llvm.lifetime.end.p0(i64 8, ptr %0)
ret void
}
; Function Attrs: nounwind
define private void @_ZN9generatorIiLj0EE10destructorERS0_(ptr noalias nonnull %0) unnamed_addr #2 {
func_code:
%1 = load ptr, ptr %0, align 8
call void @llvm.coro.destroy(ptr %1)
ret void
}
; Function Attrs: nounwind presplitcoroutine
define ptr @_Z9SimpleGenv() unnamed_addr #5 comdat {
allocations:
br label %func_code
func_code: ; preds = %allocations
%coro_promise = alloca i32, align 4
%coro_id = call token @llvm.coro.id(i32 0, ptr %coro_promise, ptr null, ptr null)
%coro_need_to_alloc = call i1 @llvm.coro.alloc(token %coro_id)
br i1 %coro_need_to_alloc, label %need_to_alloc, label %block_coro_begin
need_to_alloc: ; preds = %func_code
%coro_frame_size = call i64 @llvm.coro.size.i64()
%coro_frame_memory_allocated = call ptr @ust_memory_allocate_impl(i64 %coro_frame_size)
br label %block_coro_begin
block_coro_begin: ; preds = %need_to_alloc, %func_code
%coro_frame_memory = phi ptr [ null, %func_code ], [ %coro_frame_memory_allocated, %need_to_alloc ]
%coro_handle = call ptr @llvm.coro.begin(token %coro_id, ptr %coro_frame_memory)
br label %func_code1
coro_cleanup: ; preds = %suspend_destroy3, %suspend_destroy, %coro_suspend_final
%coro_frame_memory_for_free = call ptr @llvm.coro.free(token %coro_id, ptr %coro_handle)
%coro_need_to_free = icmp ne ptr %coro_frame_memory_for_free, null
br i1 %coro_need_to_free, label %need_to_free, label %coro_suspend
need_to_free: ; preds = %coro_cleanup
call void @ust_memory_free_impl(ptr %coro_frame_memory_for_free)
br label %coro_suspend
coro_suspend: ; preds = %suspend_normal, %func_code1, %coro_suspend_final, %need_to_free, %coro_cleanup
%0 = call i1 @llvm.coro.end(ptr %coro_handle, i1 false)
ret ptr %coro_handle
coro_suspend_final: ; preds = %suspend_normal4
%final_suspend_value = call i8 @llvm.coro.suspend(token none, i1 true)
switch i8 %final_suspend_value, label %coro_suspend [
i8 0, label %coro_final_suspend_unreachable
i8 1, label %coro_cleanup
]
coro_final_suspend_unreachable: ; preds = %coro_suspend_final
unreachable
func_code1: ; preds = %block_coro_begin
%suspend_value = call i8 @llvm.coro.suspend(token none, i1 false)
switch i8 %suspend_value, label %coro_suspend [
i8 0, label %suspend_normal
i8 1, label %suspend_destroy
]
suspend_destroy: ; preds = %func_code1
br label %coro_cleanup
suspend_normal: ; preds = %func_code1
store i32 12345, ptr %coro_promise, align 4
%suspend_value2 = call i8 @llvm.coro.suspend(token none, i1 false)
switch i8 %suspend_value2, label %coro_suspend [
i8 0, label %suspend_normal4
i8 1, label %suspend_destroy3
]
suspend_destroy3: ; preds = %suspend_normal
br label %coro_cleanup
suspend_normal4: ; preds = %suspend_normal
br label %coro_suspend_final
}Видно, какие LLVM-функции используются для задания функции-корутины и работы с объектом-корутиной. Обратите внимание, что функция-генератор содержит три точки приостановки (вызовы suspend) — начальную точку, на которой корутина останавливается после создания, точку, соответствующую оператору yield и конечную точку.
После проходов обработки корутин бекенд компилятора превращает код следующим образом:
%_Z9SimpleGenv.Frame = type { ptr, ptr, i32, i2 }
; Function Attrs: nounwind
define void @_Z3Foov() unnamed_addr #1 comdat {
allocations:
%0 = alloca %"9generatorIiLj0EE", align 8
call void @llvm.lifetime.start.p0(i64 8, ptr %0)
%1 = call ptr @_Z9SimpleGenv()
store ptr %1, ptr %0, align 8
%coro_handle = load ptr, ptr %0, align 8
%2 = load ptr, ptr %coro_handle, align 8
%3 = icmp eq ptr %2, null
br i1 %3, label %if_coro_advance_else, label %coro_not_done
coro_not_done: ; preds = %allocations
%4 = getelementptr inbounds { ptr, ptr }, ptr %coro_handle, i32 0, i32 0
%5 = load ptr, ptr %4, align 8
%6 = bitcast ptr %5 to ptr
call fastcc void %6(ptr %coro_handle)
%7 = load ptr, ptr %coro_handle, align 8
%8 = icmp eq ptr %7, null
br i1 %8, label %if_coro_advance_else, label %not_done_after_resume
not_done_after_resume: ; preds = %coro_not_done
%9 = getelementptr inbounds i8, ptr %coro_handle, i32 16
%10 = load i32, ptr %9, align 4
call void @_Z8PrintInti(i32 %10)
call void @_ZN9generatorIiLj0EE10destructorERS0_(ptr %0)
call void @llvm.lifetime.end.p0(i64 8, ptr %0)
ret void
if_coro_advance_else: ; preds = %coro_not_done, %allocations
call void @__U_halt()
unreachable
}
; Function Attrs: nounwind
define private void @_ZN9generatorIiLj0EE10destructorERS0_(ptr noalias nonnull %0) unnamed_addr #1 {
func_code:
%1 = load ptr, ptr %0, align 8
%2 = getelementptr inbounds { ptr, ptr }, ptr %1, i32 0, i32 1
%3 = load ptr, ptr %2, align 8
%4 = bitcast ptr %3 to ptr
call fastcc void %4(ptr %1)
ret void
}
; Function Attrs: nounwind
define ptr @_Z9SimpleGenv() unnamed_addr #1 comdat {
allocations:
%coro_promise = alloca i32, align 4
%coro_frame_memory_allocated = call ptr @ust_memory_allocate_impl(i64 24)
%resume.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_frame_memory_allocated, i32 0, i32 0
store ptr @_Z9SimpleGenv.resume, ptr %resume.addr, align 8
%0 = select i1 true, ptr @_Z9SimpleGenv.destroy, ptr @_Z9SimpleGenv.cleanup
%destroy.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_frame_memory_allocated, i32 0, i32 1
store ptr %0, ptr %destroy.addr, align 8
%coro_promise.reload.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_frame_memory_allocated, i32 0, i32 2
%index.addr12 = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_frame_memory_allocated, i32 0, i32 3
store i2 1, ptr %index.addr12, align 1
ret ptr %coro_frame_memory_allocated
}
; Function Attrs: nounwind
define internal fastcc void @_Z9SimpleGenv.resume(ptr noalias nonnull align 8 dereferenceable(24) %coro_handle) #1 {
entry.resume:
%coro_promise.reload.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 2
br label %resume.entry
coro_cleanup: ; preds = %suspend_destroy3, %suspend_destroy, %AfterCoroSuspend10
%coro_need_to_free = icmp ne ptr %coro_handle, null
br i1 %coro_need_to_free, label %need_to_free, label %coro_suspend
need_to_free: ; preds = %coro_cleanup
call void @ust_memory_free_impl(ptr %coro_handle)
br label %coro_suspend
coro_suspend: ; preds = %AfterCoroSuspend, %AfterCoroSuspend7, %AfterCoroSuspend10, %need_to_free, %coro_cleanup
br label %CoroEnd
CoroEnd: ; preds = %coro_suspend
ret void
CoroSave8: ; preds = %suspend_normal4
%ResumeFn.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 0
store ptr null, ptr %ResumeFn.addr, align 8
br label %CoroSuspend9
CoroSuspend9: ; preds = %CoroSave8
br label %resume.2.landing
resume.2.landing: ; preds = %CoroSuspend9
br label %AfterCoroSuspend10
AfterCoroSuspend10: ; preds = %resume.2.landing
switch i8 -1, label %coro_suspend [
i8 0, label %coro_final_suspend_unreachable
i8 1, label %coro_cleanup
]
coro_final_suspend_unreachable: ; preds = %AfterCoroSuspend10
unreachable
resume.1: ; preds = %resume.entry
br label %resume.1.landing
resume.1.landing: ; preds = %resume.1
br label %AfterCoroSuspend7
AfterCoroSuspend7: ; preds = %resume.1.landing
switch i8 0, label %coro_suspend [
i8 0, label %suspend_normal
i8 1, label %suspend_destroy
]
suspend_destroy: ; preds = %AfterCoroSuspend7
br label %coro_cleanup
suspend_normal: ; preds = %AfterCoroSuspend7
store i32 12345, ptr %coro_promise.reload.addr, align 4
br label %CoroSave
CoroSave: ; preds = %suspend_normal
%index.addr11 = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 3
store i2 0, ptr %index.addr11, align 1
br label %CoroSuspend
CoroSuspend: ; preds = %CoroSave
br label %resume.0.landing
resume.0: ; preds = %resume.entry
br label %resume.0.landing
resume.0.landing: ; preds = %resume.0, %CoroSuspend
%0 = phi i8 [ -1, %CoroSuspend ], [ 0, %resume.0 ]
br label %AfterCoroSuspend
AfterCoroSuspend: ; preds = %resume.0.landing
switch i8 %0, label %coro_suspend [
i8 0, label %suspend_normal4
i8 1, label %suspend_destroy3
]
suspend_destroy3: ; preds = %AfterCoroSuspend
br label %coro_cleanup
suspend_normal4: ; preds = %AfterCoroSuspend
br label %CoroSave8
resume.entry: ; preds = %entry.resume
%index.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 3
%index = load i2, ptr %index.addr, align 1
switch i2 %index, label %unreachable [
i2 0, label %resume.0
i2 1, label %resume.1
]
unreachable: ; preds = %resume.entry
unreachable
}
; Function Attrs: nounwind
define internal fastcc void @_Z9SimpleGenv.destroy(ptr noalias nonnull align 8 dereferenceable(24) %coro_handle) #1 {
entry.destroy:
%coro_promise.reload.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 2
br label %resume.entry
coro_cleanup: ; preds = %suspend_destroy3, %suspend_destroy, %AfterCoroSuspend10
%coro_need_to_free = icmp ne ptr %coro_handle, null
br i1 %coro_need_to_free, label %need_to_free, label %coro_suspend
need_to_free: ; preds = %coro_cleanup
call void @ust_memory_free_impl(ptr %coro_handle)
br label %coro_suspend
coro_suspend: ; preds = %AfterCoroSuspend, %AfterCoroSuspend7, %AfterCoroSuspend10, %need_to_free, %coro_cleanup
br label %CoroEnd
CoroEnd: ; preds = %coro_suspend
ret void
CoroSave8: ; preds = %suspend_normal4
%ResumeFn.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 0
store ptr null, ptr %ResumeFn.addr, align 8
br label %CoroSuspend9
CoroSuspend9: ; preds = %CoroSave8
br label %resume.2.landing
resume.2: ; preds = %resume.entry
br label %resume.2.landing
resume.2.landing: ; preds = %resume.2, %CoroSuspend9
%0 = phi i8 [ -1, %CoroSuspend9 ], [ 1, %resume.2 ]
br label %AfterCoroSuspend10
AfterCoroSuspend10: ; preds = %resume.2.landing
switch i8 %0, label %coro_suspend [
i8 0, label %coro_final_suspend_unreachable
i8 1, label %coro_cleanup
]
coro_final_suspend_unreachable: ; preds = %AfterCoroSuspend10
unreachable
resume.1: ; preds = %Switch
br label %resume.1.landing
resume.1.landing: ; preds = %resume.1
br label %AfterCoroSuspend7
AfterCoroSuspend7: ; preds = %resume.1.landing
switch i8 1, label %coro_suspend [
i8 0, label %suspend_normal
i8 1, label %suspend_destroy
]
suspend_destroy: ; preds = %AfterCoroSuspend7
br label %coro_cleanup
suspend_normal: ; preds = %AfterCoroSuspend7
store i32 12345, ptr %coro_promise.reload.addr, align 4
br label %CoroSave
CoroSave: ; preds = %suspend_normal
%index.addr11 = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 3
store i2 0, ptr %index.addr11, align 1
br label %CoroSuspend
CoroSuspend: ; preds = %CoroSave
br label %resume.0.landing
resume.0: ; preds = %Switch
br label %resume.0.landing
resume.0.landing: ; preds = %resume.0, %CoroSuspend
%1 = phi i8 [ -1, %CoroSuspend ], [ 1, %resume.0 ]
br label %AfterCoroSuspend
AfterCoroSuspend: ; preds = %resume.0.landing
switch i8 %1, label %coro_suspend [
i8 0, label %suspend_normal4
i8 1, label %suspend_destroy3
]
suspend_destroy3: ; preds = %AfterCoroSuspend
br label %coro_cleanup
suspend_normal4: ; preds = %AfterCoroSuspend
br label %CoroSave8
resume.entry: ; preds = %entry.destroy
%index.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 3
%index = load i2, ptr %index.addr, align 1
%ResumeFn.addr1 = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i32 0, i32 0
%2 = load ptr, ptr %ResumeFn.addr1, align 8
%3 = icmp eq ptr %2, null
br i1 %3, label %resume.2, label %Switch
Switch: ; preds = %resume.entry
switch i2 %index, label %unreachable [
i2 0, label %resume.0
i2 1, label %resume.1
]
unreachable: ; preds = %Switch
unreachable
}Как видно выше, и как уже было упомянуто, бекенд создал дополнительные функции с постфиксами .resume и .destroy. В них присутствует тот самый упомянутый switch. Также стоит обратить внимание на созданный тип структуры состояния корутины (_Z9SimpleGenv.Frame). Видно, что он включает в себя два указателя (для созданных функций), место под результат и номер точки останова. В данном конкретном случае это всё, но в более сложных корутинах эта структура будет содержать дополнительные поля. Также стоит обратить внимание, как определяется, что корутина завершена. Для этого не используется отдельное поле структуры состояния, вместо этого конечное состояние обозначается через зануление указателя на resume функцию.
После проходов оптимизации (-O2) код выше становится сильно проще:
%_Z9SimpleGenv.Frame = type { ptr, ptr, i32, i2 }
; Function Attrs: nounwind
define void @_Z3Foov() unnamed_addr #0 comdat {
not_done_after_resume:
tail call void @_Z8PrintInti(i32 12345)
ret void
}
; Function Attrs: nounwind
define noalias nonnull ptr @_Z9SimpleGenv() unnamed_addr #0 comdat {
allocations:
%res.i = tail call dereferenceable_or_null(24) ptr @malloc(i64 24)
store ptr @_Z9SimpleGenv.resume, ptr %res.i, align 8
%destroy.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %res.i, i64 0, i32 1
store ptr @_Z9SimpleGenv.destroy, ptr %destroy.addr, align 8
%index.addr11 = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %res.i, i64 0, i32 3
store i2 0, ptr %index.addr11, align 1
ret ptr %res.i
}
; Function Attrs: mustprogress nounwind willreturn
define internal fastcc void @_Z9SimpleGenv.resume(ptr noalias nocapture nonnull align 8 dereferenceable(24) %coro_handle) #3 {
resume.entry:
%index.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i64 0, i32 3
%index = load i2, ptr %index.addr, align 4
%switch = icmp eq i2 %index, 0
br i1 %switch, label %AfterCoroSuspend7.thread, label %AfterCoroSuspend10
CoroEnd: ; preds = %AfterCoroSuspend10, %AfterCoroSuspend7.thread
ret void
AfterCoroSuspend7.thread: ; preds = %resume.entry
%coro_promise.reload.addr = getelementptr inbounds %_Z9SimpleGenv.Frame, ptr %coro_handle, i64 0, i32 2
store i32 12345, ptr %coro_promise.reload.addr, align 8, !tbaa !2
store i2 1, ptr %index.addr, align 4
br label %CoroEnd
AfterCoroSuspend10: ; preds = %resume.entry
store ptr null, ptr %coro_handle, align 8
br label %CoroEnd
}
; Function Attrs: mustprogress nounwind willreturn
define internal fastcc void @_Z9SimpleGenv.destroy(ptr noalias nocapture nonnull align 8 dereferenceable(24) %coro_handle) #3 {
resume.entry:
tail call void @free(ptr nonnull %coro_handle)
ret void
}Видно, что сама функция-генератор и её части предельно упростились. А вызов этой функции из функции Foo вообще встроился и всё лишнее убралось.
Конкретно генераторы имеет смысл применять для порождения последовательности значений. Поэтому приведу ещё один пример, на сей раз с последовательностью.
fn generator GenSequence(u32 num) : f32
{
for( auto mut i = 0u; i < num; ++i )
{
yield f32(i);
}
}
fn PrintFloat(f32 x);
fn Foo(u32 num)
{
auto mut gen= GenSequence(num);
while( true )
{
if_coro_advance( x : gen )
{
PrintFloat(x);
}
else
{
break;
}
}
}LLVM код после раскрытия и оптимизации:
; Function Attrs: nounwind
define void @_Z3Fooj(i32 %num) unnamed_addr #0 comdat {
allocations:
%"<8.not.i" = icmp eq i32 %num, 0
br label %coro_not_done
coro_not_donethread-pre-split: ; preds = %suspend_normal.preheader.i, %suspend_normal5.i
%i.09.i = phi i32 [ 0, %suspend_normal.preheader.i ], [ %"++.i", %suspend_normal5.i ]
%0 = uitofp i32 %i.09.i to float
tail call void @_Z10PrintFloatf(float %0)
br label %coro_not_done
coro_not_done: ; preds = %coro_not_donethread-pre-split, %allocations
%switch.i = phi i1 [ false, %coro_not_donethread-pre-split ], [ true, %allocations ]
%.sroa.10.0 = phi i32 [ %i.09.i, %coro_not_donethread-pre-split ], [ undef, %allocations ]
br i1 %switch.i, label %suspend_normal.preheader.i, label %suspend_normal5.i
suspend_normal.preheader.i: ; preds = %coro_not_done
br i1 %"<8.not.i", label %if_coro_advance_else, label %coro_not_donethread-pre-split
suspend_normal5.i: ; preds = %coro_not_done
%"++.i" = add nuw i32 %.sroa.10.0, 1
%exitcond.not.i = icmp eq i32 %"++.i", %num
br i1 %exitcond.not.i, label %if_coro_advance_else, label %coro_not_donethread-pre-split
if_coro_advance_else: ; preds = %suspend_normal5.i, %suspend_normal.preheader.i
ret void
}Как видно выше, вызов корутины встроился (аллокации из кучи убрались). Правда код всё ещё немного переусложнён излишними ветвлениями и phi узлами. Я долго выяснял, почему так может быть, и так и не нашёл однозначного ответа. Есть только предположение, что всему виною тут как раз пресловутый switch внутри resume функции. Насколько показали мои исследования, проходы оптимизации LLVM не умеют удалять лишние ветвления из циклов. Тем не менее код близок к оптимальному, хоть и не идеален.
Ограничения генераторов в Ü
Существует ряд ограничений функций-генераторов. Часть из них вполне логична, а часть существует только потому, что реализовать что-то было слишком сложно.
- Вывод типа возвращаемого значения (через
auto) для функций-генераторов не работает. Тип надо указывать явно. - Не поддерживаются виртуальные методы-генераторы, хотя обычные методы могут быть генераторами.
- Соглашение о вызове у функций-генераторов может быть только
default. - Само собою, генератором нельзя сделать конструкторы, операторы присваивания, деструкторы и т. д.
Ряд вышеописанных ограничений при этом всё же можно обойти, например так — через функции-обёртки:
class A polymorph
{
public:
fn virtual SomeGen(this) : ( generator'imut this_tag' : i32)'this'
{
return SomeGenImpl();
}
private:
fn generator SomeGenImpl(this) : i32;
}Сравнение с другими языками
Ü — не первый и не последний язык, где есть корутины. Ниже изложено краткое описание того, как они реализованы в некоторых других популярных языках.
С++
В стандарт C++20 были добавлены корутины — как генераторы, так и асинхронные функции. Советую почитать перевод статьи про корутины в C++. Так же, как и в Ü, память под корутины выделяется из кучи (при помощи оператора new).
В отличие от Ü, корутины в C++ просто так не работают, для них нужно писать некий вспомогательный пользовательский код (типы-обёртки, promise-типы). Также в C++ наличествуют исключения, что тоже осложняет работу с корутинами. Ну и не добавляет простоты модель перемещения C++ (не разрушающая, как в Ü или Rust), вынуждающая звать конструкторы/деструкторы при yield.
Компилятор Clang реализует корутины через тот же функционал, что компилятор Ü. Точнее наоборот — в Clang корутины были реализованы раньше, чем в Ü.
Rust
В Rust генераторов (в стабильной ветке на момент написания данной статьи) всё ещё нету. Зато есть асинхронные функции. Работают они при этом существенно иначе, чем в Ü. Под каждую асинхронную функцию компилятор создаёт свой тип, реализующий типаж Future. Состояние асинхронной функции (локальные переменные и т. д.) хранятся в этом типе.
Данный подход сильно усложняет фронтенд компилятора, т. к. в нём нужно вести анализ того, что нужно сохранять в структуре состояния и реализовывать сохранение состояния. Также данный подход затрудняет создание рекурсивных корутин. Для их реализации приходится заворачивать объект-корутину в Box<dyn Future>.
Ещё одна особенность — поскольку объект корутины не имеет контроля над памятью, в которой он расположен, возможно изменение адресов локальных переменных между возобновлениями работы корутины из-за перемещения объекта в другую область памяти. Это недопустимо, т. к. может поломать локальные ссылки, хранящиеся в структуре корутины. Поэтому Rust требует для работы с корутиной жёстко определить её адрес через std::Pin.
Плюс подхода Rust — отсутствие выделений памяти из кучи гарантировано. Выделение памяти из кучи будет присутствовать, только если явно выделять память под объект-корутину из кучи (через Box или что-то подобное).
Swift
Компилятор Swift использует для асинхронных функций тот же функционал библиотеки LLVM, что и Clang или компилятор Ü, но несколько иную его разновидность. В нём используется несколько более сложный async lowering. Насколько я понял, память нём тоже выделяется из кучи, ибо рекурсивные асинхронные функции компилируются без проблем (в отличие от Rust).
Python, JavaScript, C#, Java и другие подобные языки
В скриптовых языках и языках с виртуальной машиной не составляет особых проблем реализовать корутины. Это даже проще, чем в компилируемых языках с наличием ссылок — не надо беспокоиться о том, что структура состояния при перемещении инвалидируется. А можно и вообще всегда выделять состояние из кучи — в подобных языках и так всё не слишком быстро работает, ещё одна аллокация погоды не сделает.
Зачем нужны генераторы
По-правде говоря, генераторы не так чтобы уж сильно необходимы. Схожий генераторам функционал можно относительно легко реализовать через класс со специальным методом (next, operator() и т. д.). К примеру, в С++ генераторы только относительно-недавно появились и без них до этого прекрасно жили.
Немногое, что приходит в голову — это реализация логики некоторых игр через генераторы. Сложную машину состояний игровых юнитов можно реализовать как функцию-генератор, а обмен состояний с остальным игровым кодом — через yield. Хотя, не понятно, насколько такой подход сейчас распространён, сейчас больше используют всякие ECS.
А вот что реально нужно и полезно, так это асинхронные функции. Мотивацией добавления генераторов в Ü была подготовка к внедрению подобных функций. Внутренне ведь они работают почти что одинаково, что означает, что добавить в язык асинхронные функции после реализации генераторов будет относительно просто.
Но на данный момент пока что в Ü асинхронные функции не реализованы. Мешают этому пока что некоторые несовершенства текущего механизма контроля ссылок в языке. Как они будут устранены, так можно будет и асинхронными функциями заняться.
Выводы
Инфраструктура LLVM по поддержке корутин оказалась весьма удобной для реализации генераторов. Если бы её не было, реализовать их было бы существенно сложнее. Если кто-то использует библиотеку LLVM для своего языка, настоятельно рекомендую использовать функционал этой библиотеки для своих корутин.
Основной сложностью при реализации генераторов было подружить их с другими концепциями языка и обработать (в т. ч. написать тесты) на хитрые краевые случаи. Это и заняло большую часть времени работы над генераторами.
Благодаря наличию генераторов есть теперь задел для реализации асинхронных функций, коими я надеюсь в обозримой перспективе заняться.
Ссылки
Исходный код. Там же через Actions доступна сборка компилятора (пока только под Ubuntu 20.04).