Вызовы хвостов WebAssembly
Мы внедряем вызовы хвостов WebAssembly в V8 v11.2! В этом посте мы кратко рассмотрим это предложение, покажем интересный пример использования копрограмм C++ с Emscripten и продемонстрируем, как V8 обрабатывает вызовы хвостов внутри.
Что такое оптимизация хвостовых вызовов?
Вызов считается находящимся в хвостовой позиции, если это последняя инструкция, выполняемая перед возвратом из текущей функции. Компиляторы могут оптимизировать такие вызовы, отбрасывая фрейм вызывающего и заменяя вызов на переход.
Это особенно полезно для рекурсивных функций. Например, рассмотрим эту 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 возвращает результат a непосредственно функции fib.
Одно из наблюдаемых следствий хвостовых вызовов заключается в том (помимо уменьшенного риска переполнения стека), что хвостовые вызовы не появляются в трассе стека. Они также не появляются в свойстве stack пойманного исключения или в трассировке стека 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 управляет этими манипуляциями со стеком и регистрами с помощью “gap resolver”, компонента, который принимает список перемещений, которые должны семантически выполняться параллельно, и генерирует соответствующую последовательность перемещений для разрешения потенциальных конфликтов между источниками и назначениями перемещений. Если конфликты являются ациклическими, это всего лишь вопрос упорядочивания перемещений таким образом, чтобы все источники были считаны до их перезаписи. Для циклических конфликтов (например, если мы меняем местами два параметра стека) это может включать перемещение одного из источников во временный регистр или временную ячейку стека для разрешения цикла.
Хвостовые вызовы также поддерживаются в Liftoff, нашем базовом компиляторе. На самом деле, они должны поддерживаться, иначе базовый код может исчерпать пространство стека. Тем не менее, они не оптимизированы на этом уровне: Liftoff добавляет параметры, адрес возврата и указатель на текущий кадр, чтобы завершить кадр так, как если бы это был обычный вызов, а затем сдвигает все вниз, чтобы удалить кадр вызывающего кода:
Перед переходом к целевой функции мы также извлекаем указатель кадра вызывающего кода (FP) в регистр FP, чтобы восстановить его предыдущее значение, и позволяем целевой функции снова сохранить его в прологе.
Эта стратегия не требует анализа и разрешения конфликтов перемещений, что ускоряет компиляцию. Сгенерированный код работает медленнее, но со временем повышается в уровне до TurboFan, если функция достаточно часто используется.