Wasm — не совсем стековая машина

Принято считать, что WebAssembly — стековая машина: так пишут в Википедии, в официальной спецификации и в популярных руководствах. На практике, как обнаружила Alisa (purplesyringa), начавшая писать байт-код Wasm руками, это не совсем стековая машина: у неё нет ни dup, ни swap, ни прочих операций перестановки стека. Перевод её разбора того, чем Wasm на самом деле отличается от JVM и Forth, и почему это меняет интуицию для всех, кто пришёл туда из стековых VM.

Регистровая машина и стековая машина

Шаг назад. Что такое стековая машина? Допустим, вы пишете на каком-нибудь языке высокого уровня и вам нужно посчитать 2 * 3 + 5 * 7. У низкоуровневых языков нет понятия составных выражений: они умеют выполнять только одну операцию за раз. То есть вам нужно сделать два умножения, сохранить промежуточные результаты, потом сложить.

Многие низкоуровневые языки — например, ассемблер x86 — представят эти шаги примерно так:

			a = 2
b = 3
c = a * b
d = 5
e = 7
f = d * e
g = c + f
		

Это регистровая машина. У вас есть переменные (их называют регистрами), в которых можно держать и постоянные значения, и временные результаты. Каждая инструкция — формы var1 = var2 op var3.

Другие языки — например, Forth или Hex Casting — используют для тех же целей стек. Стек хранит последовательность значений в порядке поступления; уже посчитанные подвыражения «лежат» на нём, пока вы работаете с другими частями. На стековом языке тот же самый расчёт выглядит так:

			push(2)
push(3)
mul()    -- снимает два верхних значения и кладёт их произведение
push(5)
push(7)
mul()
add()
		

Обратите внимание на сходство: в обеих программах столько же шагов, и шаги делают то же самое. Главное различие — в стековой машине операнды неявно закодированы в порядке инструкций, а регистровая машина каждый раз указывает индексы явно.

Перестановки на стеке

Сжатия без потерь, которое всегда уменьшает данные, не существует — поэтому, делая индексы неявными, мы что-то теряем в выразительной силе. Что именно?

Для простых выражений — почти ничего. А вот когда значения переиспользуются, разница становится очевидной. Представьте, что вы — компилятор и вам надо скомпилировать такой кусок:

			x = 1 + 2 + 3 + 4
y = x * x * x
		

На регистровой машине всё прямолинейно:

			(посчитали x как обычно)
tmp = x * x
y = tmp * x
		

А вот стековая машина «как описано выше» не умеет ссылаться на одно и то же значение дважды: mul всегда умножает два значения, лежащих на разных позициях стека. Чтобы такая программа стала возможной, в реальные стековые машины добавляют операции работы со стеком — помимо чисто вычислительных. Нужный нам инструмент называется dup — он дублирует верхнее значение стека:

			(посчитали x как обычно)
dup()    -- стек: x, x
dup()    -- стек: x, x, x
mul()    -- стек: x, x*x
mul()    -- стек: x*(x*x)
		

Вы заметите, что регистровая машина посчитала (x*x)*x, а стековая — x*(x*x). Для умножения это одно и то же, но для других операций может быть нет. Чтобы починить — добавляют swap, который меняет местами два верхних значения:

			(посчитали x как обычно)
dup()    -- стек: x, x
dup()    -- стек: x, x, x
mul()    -- стек: x, x*x
swap()   -- стек: x*x, x
mul()    -- стек: (x*x)*x
		

На практике используют ещё больше операций: over (копирует предпоследнее значение наверх), 2dup (дублирует два верхних), drop (выбрасывает верхнее), rot (переносит третье сверху наверх) и так далее.

С этой точки зрения стековые машины можно рассматривать как разделение операций и индексов, на которые они действуют. Регистровые машины всегда явно указывают индексы и платят за это лишним размером, когда индексы избыточны. Стековые машины кодируют индексы только когда нужно — но платят за это ростом числа инструкций. Если хочется красиво — стековые машины реализуют «энтропийное сжатие» регистровой записи: средний код получается компактнее, потому что неявный индекс операнда дешевле в битах, чем явное имя регистра.

А что у Wasm?

Если посмотреть на JVM — известную стековую машину, с которой Wikipedia сравнивает WebAssembly — найдёте примерно тот же набор байт-кода:

• Доступ к памяти и константам: iaload, iastore, iconst.
• Унарные и бинарные операции: d2f, iadd.
• Манипуляции со стеком: dup, dup_x1 (он же over), pop (он же drop), swap.

JVM — не чистая стековая машина: у неё есть инструкции для доступа к локальным переменным (iload, istore). Но без них тоже можно писать вполне рабочие JVM-программы — javac обычно использует их только для переменных, которые программист на Java явно завёл.

А теперь посмотрите на набор инструкций Wasm:

• Доступ к памяти и константам: i32.load, i32.store, i32.const.
• Унарные и бинарные операции: f32.demote_f64, i32.add.
• Манипуляции со стеком: drop, э-э… и всё?

Любопытно, не правда ли? У Wasm полно инструкций, которые принимают аргументы и кладут возвращаемые значения на стек, но почти нет инструкций, которые могут стек переставить. Насколько я могу судить, drop существует только потому, что иначе нельзя было бы проигнорировать результат функции.

По сути, чистый Wasm умеет вычислять выражения ровно так, как они записаны в исходнике. Оптимизирующий компилятор не может сделать вынесение общих подвыражений (CSE) или превратить expr^2 в expr * expr без введения новых переменных. Как только нужно что-то нетривиальное — приходится тянуться к локальным переменным, и иллюзия «стековой машины» рассыпается: получается обычная регистровая.

Семантика

На мой взгляд, правильно смотреть на Wasm как на регистровую машину с операциями, обобщёнными до составных выражений. В бинарном Wasm выражения закодированы в обратной польской записи, которую удобно вычислять стеком — но это просто формат кодирования. В текстовом Wasm выражения, наоборот, записываются в LISP-подобной нотации — и она ничуть не менее эффективна.

Вообразите бинарный Wasm с префиксной нотацией — принципиально это бы ничего не поменяло. Если гадать почему всё-таки выбрали постфиксную — вероятно, чтобы упростить неоптимизирующие интерпретаторы, или потому что у разработчиков был опыт со стек-ориентированными VM, и это стало решающим аргументом.

Эту перспективу подкрепляет ещё один факт: пока Wasm не получил расширение multi-value, управляющие конструкции практически не могли взаимодействовать со стеком. Значения, положенные на стек до if, не были видны внутри его тела; тело if могло вернуть только одно значение, поэтому if по сути был тернарным оператором, и даже значения с одним потребителем приходилось гонять через локальные переменные.

Заключение

Имеет ли это значение на практике? Не очень: почти любую машину можно перевести в SSA-форму (static single assignment — внутреннее представление, в котором каждой переменной значение присваивается ровно один раз; большинство оптимизирующих компиляторов работают именно с ней), и тогда формат входа становится не важен. Простоту реализации стекового интерпретатора тоже надо признать плюсом — это, наверное, помогло Wasm быстрее стать стандартом.

Но я думаю, стоит честно сказать: опыт работы со стек-ориентированными VM плохо переносится на Wasm — потому что Wasm не совсем стековая машина.

Уже после публикации этого поста я нашла ещё один отличный разбор того же вопроса — но с точки зрения оптимизаций. Рекомендую почитать.

Перевод: оригинал — purplesyringa.moe/blog/wasm-is-not-quite-a-stack-machine/. Публикуется с разрешения автора в адаптации редакции tproger.