Хвостовые вызовы WebAssembly
Мы отправляем хвостовые вызовы WebAssembly в версии V8 v11.2! В этом посте мы даем краткий обзор этого предложения, продемонстрируем интересный вариант использования сопрограмм C++ с Emscripten и покажем, как V8 обрабатывает внутренние вызовы tail.
Что такое оптимизация хвостового вызова?
Считается, что вызов находится в хвостовой позиции, если это последняя команда, выполняемая перед возвратом из текущей функции. Компиляторы могут оптимизировать такие вызовы, отбрасывая фрейм вызывающего абонента и заменяя вызов переходом.
Это особенно полезно для рекурсивных функций. Например, возьмем эту функцию C, которая суммирует элементы связанного списка:
int sum(List* list, int acc) {
if (list == nullptr) return acc;
return sum(list->next, acc + list->val);
}При обычном вызове это занимает 𝒪(n) пространства стека: каждый элемент списка добавляет новый фрейм в стек вызовов. При достаточно длинном списке это может очень быстро переполнить стек. Заменив вызов переходом, оптимизация хвостового вызова эффективно превращает эту рекурсивную функцию в цикл, который использует 𝒪(1) стекового пространства:
int sum(List* list, int acc) {
while (list != nullptr) {
acc = acc + list->val;
list = list->next;
}
return acc;
}Эта оптимизация особенно важна для функциональных языков. Они в значительной степени полагаются на рекурсивные функции, а чистые, такие как Haskell, даже не предоставляют структуры управления циклом. Любая пользовательская итерация обычно так или иначе использует рекурсию. Без оптимизации хвостовых вызовов это очень быстро привело бы к переполнению стека для любой нетривиальной программы.
Предложение хвостового вызова WebAssembly
Есть два способа вызвать функцию в Wasm MVP: call и call_indirect. Предложение хвостового вызова WebAssembly добавляет свои аналоги хвостового вызова: return_call и return_call_indirect. Это означает, что цепочка инструментов несет ответственность за фактическую оптимизацию хвостовых вызовов и создание соответствующего типа вызова, что дает ему больший контроль над производительностью и использованием пространства стека.
Давайте посмотрим на рекурсивную функцию Фибоначчи. Байт-код Wasm включен сюда в текстовом формате для полноты картины, но вы можете найти его в C++ в следующем разделе:
(func $fib_rec (param $n i32) (param $a i32) (param $b i32) (result i32)
(if (i32.eqz (local.get $n))
(then (return (local.get $a)))
(else
(return_call $fib_rec
(i32.sub (local.get $n) (i32.const 1))
(local.get $b)
(i32.add (local.get $a) (local.get $b))
)
)
)
)
(func $fib (param $n i32) (result i32)
(call $fib_rec (local.get $n) (i32.const 0) (i32.const 1))
)В любой момент времени существует только один фрейм fib_rec, который раскручивается перед выполнением следующего рекурсивного вызова. Когда мы достигаем базового случая, fib_rec возвращает результат непосредственно в fib.
Одним из наблюдаемых последствий хвостовых вызовов (помимо снижения риска переполнения стека) является то, что хвостовые вызовы не отображаются в трассировке стека. Они не отображаются ни в свойстве стека перехваченного исключения, ни в трассировке стека DevTools. К моменту возникновения исключения или приостановки выполнения кадры хвостового вызывающего объекта исчезают, и V8 не может их восстановить.
Использование хвостовых вызовов с Emscripten
Функциональные языки часто зависят от хвостовых вызовов, но их также можно использовать в качестве программиста на C или C++. Emscripten (и Clang, который использует Emscripten) поддерживает атрибут musttail, который сообщает компилятору, что вызов должен быть скомпилирован в хвостовой вызов. В качестве примера рассмотрим эту рекурсивную реализацию функции Фибоначчи, которая вычисляет n-е число Фибоначчи по модулю 2^32 (поскольку целые числа переполняются при больших n):
#include <stdio.h>
unsigned fib_rec(unsigned n, unsigned a, unsigned b) {
if (n == 0) {
return a;
}
return fib_rec(n - 1, b, a + b);
}
unsigned fib(unsigned n) {
return fib_rec(n, 0, 1);
}
int main() {
for (unsigned i = 0; i < 10; i++) {
printf("fib(%d): %d\n", i, fib(i));
}
printf("fib(1000000): %d\n", fib(1000000));
}После компиляции с помощью emcc test.c -o test.js запуск этой программы в Node.js приводит к ошибке переполнения стека. Мы можем исправить это, добавив __attribute__((__musttail__)) к возврату в fib_rec и добавив -mtail-call к аргументам компиляции. Теперь созданные модули Wasm содержат новые инструкции хвостового вызова, поэтому мы должны передать --experimental-wasm-return_call в Node.js, но стек больше не переполняется.
Вот пример использования взаимной рекурсии:
#include <stdio.h>
#include <stdbool.h>
bool is_odd(unsigned n);
bool is_even(unsigned n);
bool is_odd(unsigned n) {
if (n == 0) {
return false;
}
__attribute__((__musttail__))
return is_even(n - 1);
}
bool is_even(unsigned n) {
if (n == 0) {
return true;
}
__attribute__((__musttail__))
return is_odd(n - 1);
}
int main() {
printf("is_even(1000000): %d\n", is_even(1000000));
}Обратите внимание, что оба эти примера достаточно просты, так что если мы компилируем с -O2, компилятор может предварительно вычислить ответ и избежать исчерпания стека даже без хвостовых вызовов, но это не относится к более сложному коду. В реальном коде атрибут musttail может быть полезен для написания высокопроизводительных циклов интерпретатора.
Помимо атрибута musttail, C++ зависит от хвостовых вызовов для еще одной функции: сопрограмм C++20. Взаимосвязь между хвостовыми вызовами и сопрограммами C++20 очень подробно описана, но, подытоживая, можно использовать сопрограммы в шаблоне, который незаметно вызовет переполнение стека, даже если исходный код этого не делает. чтобы не выглядело так, как будто есть проблема. Чтобы решить эту проблему, комитет C++ добавил требование, чтобы компиляторы реализовывали «симметричную передачу», чтобы избежать переполнения стека, что на практике означает скрытое использование хвостовых вызовов.
Когда хвостовые вызовы WebAssembly включены, Clang реализует симметричную передачу, как описано в этом сообщении в блоге, но когда хвостовые вызовы не включены, Clang молча компилирует код без симметричной передачи, что может привести к переполнению стека и технически не является правильной реализацией C +20!
Чтобы увидеть разницу в действии, используйте Emscripten для компиляции последнего примера, и обратите внимание, что он избегает переполнения стека только в том случае, если включены хвостовые вызовы. Обратите внимание, что из-за недавно исправленной ошибки это правильно работает только в Emscripten 3.1.35 или более поздних версиях.
Хвостовые вызовы в V8
Как мы видели ранее, движок не отвечает за обнаружение вызовов в хвостовой позиции. Это должно быть сделано выше по течению с помощью цепочки инструментов. Таким образом, единственное, что осталось сделать для TurboFan (оптимизирующего компилятора V8), — это выдать соответствующую последовательность инструкций, основанную на типе вызова и сигнатуре целевой функции. Для нашего предыдущего примера с Фибоначчи стек будет выглядеть так:
Слева мы находимся внутри fib_rec (зеленый), вызванный fib (синий) и готовый к рекурсивному хвостовому вызову fib_rec. Сначала мы раскручиваем текущий фрейм, сбрасывая указатель фрейма и стека. Указатель фрейма просто восстанавливает свое предыдущее значение, читая его из слота «Caller FP». Указатель стека перемещается в верхнюю часть родительского фрейма, плюс достаточно места для любых потенциальных параметров стека и возвращаемых значений стека для вызываемого объекта (0 в этом случае, все передается регистрами). Параметры перемещаются в ожидаемые регистры в соответствии с привязкой fib_rec (не показано на диаграмме). И, наконец, мы запускаем fib_rec, который начинается с создания нового фрейма.
fib_rec раскручивается и перематывается таким образом до тех пор, пока n == 0, после чего он возвращает a регистру fib.
Это простой случай, когда все параметры и возвращаемые значения помещаются в регистры, а вызываемый объект имеет ту же подпись, что и вызывающий. В общем случае нам может понадобиться выполнить сложные манипуляции со стеком:
- Чтение исходящих параметров из старого фрейма
- Переместить параметры в новый фрейм
- Отрегулируйте размер фрейма, перемещая адрес возврата вверх или вниз, в зависимости от количества параметров стека в вызываемом объекте.
Все эти чтения и записи могут конфликтовать друг с другом, потому что мы повторно используем одно и то же пространство стека. Это принципиальное отличие от не-хвостового вызова, который просто помещал бы все параметры стека и адрес возврата на вершину стека.
TurboFan обрабатывает эти манипуляции со стеком и регистрами с помощью «преобразователя промежутков», компонента, который берет список ходов, которые семантически должны выполняться параллельно, и генерирует соответствующую последовательность ходов для устранения возможных помех между источниками и пунктами назначения ходов. Если конфликты ацикличны, это просто вопрос переупорядочения ходов таким образом, чтобы все источники читались до того, как они будут перезаписаны. Для циклических конфликтов (например, если мы меняем местами два параметра стека) это может включать перемещение одного из источников во временный регистр или во временный слот стека, чтобы разорвать цикл.
Вызовы Tail также поддерживаются в Liftoff, нашем базовом компиляторе. На самом деле они должны поддерживаться, иначе базовому коду может не хватить места в стеке. Однако они не оптимизированы на этом уровне: Liftoff подталкивает параметры, адрес возврата и указатель фрейма, чтобы завершить кадр, как если бы это был обычный вызов, а затем сдвигает все вниз, чтобы отбросить кадр вызывающего абонента:
Прежде чем перейти к целевой функции, мы также помещаем вызывающий FP в регистр FP, чтобы восстановить его предыдущее значение и позволить целевой функции снова поместить его в пролог.
Эта стратегия не требует анализа и разрешения конфликтов перемещения, что ускоряет компиляцию. Сгенерированный код работает медленнее, но в конечном итоге достигает уровня TurboFan, если функция достаточно горячая.
