WebAssembly가 왜 진정한 스택 머신이 아닌지, locals와 라이브니스 분석, SSA 형식, 스트리밍 컴파일러 관점에서의 문제를 살펴본다.
머리말
이것은 WebAssembly의 문제점과 이를 해결하기 위한 제안에 관한 4부작 미니시리즈의 1부입니다. 2부는 여기, 3부는 여기, 4부는 여기. 이 글은 가상 머신, 컴파일러, WebAssembly에 대한 어느 정도의 친숙함을 전제로 하지만, 필요할 때는 관련 정보를 링크하려고 하니 익숙하지 않더라도 따라올 수 있을 것입니다. 또, 이 시리즈는 제가 WebAssembly를 싫어하는 것처럼 보일 수도 있습니다. 저는 WebAssembly를 정말 좋아합니다! 저는 그것이 얼마나 훌륭한지에 대한 글 전체를 쓰기도 했습니다! 사실 저는 그것을 너무나 좋아하기 때문에, 그것이 될 수 있는 한 최고의 것이 되기를 바랍니다. 그리고 이 시리즈는 사양의 잉크가 아직 어느 정도 마르지 않았을 때, 이런 문제들 중 일부 혹은 전부가 곧 해결되기를 바라는 마음으로 설계에 대한 제 불만을 정리해 보는 과정입니다.
이제 여러분은 분명 WebAssembly에 익숙할 것입니다. 플러그인부터 블록체인 스마트 컨트랙트, 그리고 물론 웹에 이르기까지, 어디에서나 사용되고 있습니다. 지금 WebAssembly의 Wikipedia 문서에 가 보면 기술에 대한 훌륭한 개요를 볼 수 있습니다. 다만 한 가지 문제가 있습니다. “Design” 섹션에는 이렇게 적혀 있습니다:
WebAssembly code is intended to be run on a portable abstract structured stack machine
아닙니다.
스택 머신과 레지스터 머신의 차이는 본질적으로 이것입니다. 스택 머신은 스택에서 값을 pop하고 스택에 값을 push합니다. 그래서 예를 들어 + 연산은 스택의 마지막 두 값을 꺼내 더한 다음, 그 결과를 다시 스택에 넣습니다. 레지스터 머신은 값을 저장할 수 있는 여러 장소를 가지고 있고, 연산은 그 레지스터들을 읽고 씁니다. 그래서 +는 3개의 인수를 받게 됩니다. 2개는 피연산자를 읽어올 레지스터를 나타내고, 1개는 결과를 써 넣을 레지스터를 나타냅니다1.
레지스터의 문제는 라이브니스 분석이 없다는 점입니다. 다음과 같은 코드가 있다고 합시다:
%0 = 1
%1 = 2
%2 = add %0, %1
...
%0와 %1은 덧셈 이후에도 사용될까요? 미리 내다보지 않으면 알 방법이 없습니다. LLVM IR 같은 SSA2 레지스터 머신(각 레지스터가 정확히 한 번만 써지는 형태)에서도 각 레지스터의 라이브니스는 계속해서 다시 계산되어야 합니다. 이는 컴파일에 오버헤드가 따른다는 뜻입니다. 변수의 라이브니스를 아는 것은 효율적인 어셈블리를 생성하는 데 매우 중요하지만, IR을 만들 때 라이브니스를 계산해 그 일부로 저장하는 대신 매번 이 데이터를 다시 계산해야 하기 때문입니다.
IR이 전적으로 메모리 안에만 있다면, 특히 코드가 SSA 형태라면, 이것은 그렇게까지 나쁘지 않습니다. 하지만 같은 품질의 코드를 위해 추가 작업을 해야 한다는 뜻이고, 스트리밍 컴파일러(FireFox의 Wasm 베이스라인 컴파일러 같은)는 좋은 코드를 생성할 수 없다는 뜻이기도 합니다.
물론 머신에 라이브니스 분석 메타데이터를 추가할 수는 있습니다. 하지만 그 라이브니스 분석은 코드가 SSA 형태일 때에만 유용합니다. SSA 형태가 아니라면 라이브니스는 극도로 거칠어집니다.
바로 여기에서 WebAssembly가 등장합니다. WebAssembly에는 locals라고 불리는 것이 있습니다. locals는 함수의 생애 동안 살아 있는 가변 변수입니다. WebAssembly 블록은 인수를 받을 수 없기 때문에, 블록이 바깥으로부터 데이터를 받는 유일한 방법이 바로 이것입니다. 여기에는 SSA를 무너뜨리는 가변 변수의 전형적인 예인 루프 카운터 같은 것도 포함되지만, 일반적인 블록도 포함됩니다. 예를 들면 다음과 같습니다:
(func (result i32)
(add (i32.const 1) (i32.const 2))
(block (result i32)
; 위 add의 결과를 읽을 수 없음
))
이렇게 해야 합니다:
(func (result i32)
(local i32)
(local.set 0 (add (i32.const 1) (i32.const 2)))
(block (result i32)
(local.get 0)
))
이것은 문제입니다. 보통 스택 머신은 SSA 형태로 손쉽게 변환할 수 있으며, 라이브니스 분석도 간단합니다. 스택 위의 항목은 연산자의 인수로 사용되는 순간 죽습니다. 다른 경우는 없습니다. pick 연산자3조차도 pick의 인수가 컴파일 시점 상수인 한 이런 관점에서 생각할 수 있습니다. 다만 일반적으로 pick 명령을 포함하는 스택 머신의 SSA 변환은 refcounting을 사용해 구현될 것입니다. 즉, 변수를 읽는다고 해서 불필요한 새 변수를 만들 필요가 없다는 뜻입니다. 그러나 locals는 문제입니다. 가변이기 때문에 SSA로 쉽게 변환할 수 없고, 언제나 함수의 생애 전체 동안 살아 있기 때문입니다.
이것은 최적화에 문제를 일으킵니다. SSA 형태는 가장 강력한 최적화 도구 중 하나입니다. locals가 가변이라는 사실은 그것을 무력화하고, 함수 전체에 걸쳐 전역적이라는 사실은 라이브니스 분석을 무력화합니다. 왜 이것이 문제인지 예를 들어 봅시다. WebAssembly를 어떤 네이티브 아키텍처로 컴파일하려 한다고 합시다. 코드는 여러 개의 인수를 레지스터에 두는 형태로 컴파일될 것입니다. 그런데 그 함수에 대해 여러분 스스로 라이브니스 분석을 하지 않는 한, 그 레지스터들은 그 인수들 때문에 영구적으로 “사용 중”으로 표시됩니다. 그 인수가 마지막으로 사용되는 시점을 추가 분석 없이는 알 수 없기 때문에, 그 인수가 사용하던 레지스터를 다른 용도로 재사용할 수 없습니다. 심지어 인수를 전혀 사용하지 않는 함수조차도, 그 인수들이 차지한 공간을 다른 어떤 것에도 재사용할 수 없습니다.
이것은 본질적으로 WebAssembly를 라이브니스 분석이 없는 레지스터 머신으로 만듭니다. 그런데 그뿐만이 아닙니다. SSA 형태조차 아닌 레지스터 머신입니다. 즉, 최적화를 위해 우리가 사용할 수 있는 두 가지 도구가 모두 쓸 수 없게 됩니다. 진정한 최적화 컴파일러에서는 그 정보를 다시 만들어낼 수 있지만, WebAssembly는 이미 한 번 그 정보를 생성한 컴파일러에 의해 배출된 결과물입니다. 우리가 그 작업을 다시 해야만 하는 기술적 이유는 없습니다. 그것은 단지 언어의 결함일 뿐입니다. WebAssembly의 스트림을 대상으로 동작해야 하는 컴파일러는 이 정보를 재구성할 능력이 더 제한적이며, 본질적으로 아무 좋은 이유 없이 훨씬 더 나쁜 코드를 생성하게 됩니다.
WebAssembly 사양의 개발자들이 어리석은 것은 아닙니다. 전반적으로 그것은 매우 잘 설계된 사양입니다. 그러나 그들은 WebAssembly의 유산에 발목이 잡혀 있습니다. WebAssembly는 처음부터 바이트코드로 시작한 것이 아니라, asm.js를 위한 단순화된 바이너리 표현에 더 가까운 것으로 시작했습니다. 본질적으로 그것은 원래 JavaScript 같은 소스 코드로 설계되었습니다. 더 효율적인 표현이기는 하겠지만, 여전히 제대로 된 가상 머신 명령어 집합은 아니었습니다. 그다음에는 레지스터 머신이 되었고4, 연산자에 대해 스택 기반 인코딩으로 바뀐 것은 정말 마지막 순간이었습니다. 그 시점에는 locals 같은 개념이 이미 사양에 깊이 자리 잡고 있었습니다. 그뿐만이 아닙니다. 대부분의 경우 WebAssembly 사양 팀은 거의 눈을 가린 채로 날고 있었습니다. 스트리밍 컴파일러는 아직 하나도 만들어지지 않았고, 아니, 컴파일러 자체도 아직 만들어지지 않았습니다. locals를 갖는 것이 문제가 될지 분명하지 않았습니다. 결국 C도 컴파일러가 SSA 그래프를 구축하는 지역 변수를 사용하면서 잘 버티고 있으니까요.
제가 이런 문제들, 그리고 이 시리즈의 이후 글에서 다룰 더 많은 문제들을 깨닫게 된 것은 Wasmtime와의 통합을 위한 스트리밍 WebAssembly 컴파일러를 작업하면서였습니다. 그 전까지 저는 WebAssembly의 설계가 완전히 견고하다고 생각했고, 사실 지금도 대부분의 결정은 옳았다고 강하게 믿습니다. 문제가 있기는 하지만, 사양이 작성되던 당시 그것이 비교적 미지의 영역이었다는 점을 생각하면 WebAssembly 작업 그룹이 그렇게 많은 것을 올바르게 해냈다는 사실은 놀라울 정도입니다.
현재 locals는 함수 인수와 지역 변수 둘 다를 나타냅니다. 블록이 인수를 받을 수 있고 함수와 블록 모두 하나보다 많은 값을 반환할 수 있도록 하는 제안이 있습니다. 이렇게 되면 locals를 완전히 없앨 수 있게 됩니다. 루프 카운터는 카운터를 인수로 전달하는 방식으로 구현되고, 루프의 헤더로 점프할 때는 카운터의 새 값이 스택 위에 있어야 합니다. 이것은 phi 함수처럼 동작하지만 개념적으로는 훨씬 단순합니다. WebAssembly에서는 locals의 주소를 얻는 것이 불가능하기 때문에 어떤 형태로든 alloca가 필요하지 않습니다. LLVM과는 달리, 애초에 locals가 전혀 필요하지 않습니다. 마지막으로 남는 것은 함수 인수를 함수 시작 시 스택 위에 놓인 상태로 구현하는 것뿐이며, 그러면 더 이상 locals가 전혀 필요하지 않게 됩니다.
이것은 표현력을 줄이지 않으면서 WebAssembly 사양과 그 컴파일러의 복잡성을 크게 줄여 주고, WebAssembly를 생성하는 컴파일러가 원본 소스에 대해 알고 있는 더 많은 정보를 WebAssembly 자체에 인코딩할 수 있게 해 줍니다. 최적화 컴파일러가 이것으로부터 더 나은 코드를 생성하지는 않을 가능성이 크지만, 훨씬 더 단순해지고 유지보수하기 쉬워질 것이며, 스트리밍 컴파일러는 훨씬 더 단순해지고 훨씬 더 나은 코드를 생성하게 될 것입니다.
마지막으로, 이런 스택 머신은 자동으로 SSA 형태일 뿐 아니라 자동으로 엄격한 SSA 형태이기도 합니다. 이는 정의되지 않은 변수에 접근하는 것이 정적으로 불가능하다는 뜻입니다. 현재의 WebAssembly에서는 함수에 진입할 때, 그 local이 접근되기 전에 항상 설정된다는 것을 정적으로 증명할 수 없는 한 locals를 0으로 초기화해야 합니다. 다시 말해, 컴파일러는 거의 항상 이 정보를 가지고 있으며, locals를 제거하면 정의되지 않은 메모리에 접근하는 일이 정적으로 불가능해집니다.
다음 글에서는 WebAssembly의 문제가 많은 제어 흐름을 다루겠습니다.
예, x86 같은 많은 레지스터 머신은 입력 레지스터 중 하나에 결과를 출력한다는 것을 알고 있습니다. 하지만 그것도 개념적으로는 입력과 출력을 위한 별도의 인수를 받는 것과 같고, 단지 더 제한적일 뿐입니다. ↩︎
SSA 형태가 무엇인지 모른다면 Wikipedia의 관련 문서를 볼 수 있습니다.↩︎
pick 연산자는 스택의 n번째 항목을 스택 맨 위로 복제합니다. 아쉽게도 이것은 WebAssembly에서는 사용할 수 없습니다. ↩︎
제 기억으로는 무한한 레지스터를 가지고 있었기 때문에 SSA 형태로 생성하는 것이 가능했지만, 라이브니스 분석은 없었습니다. ↩︎