WebAssembly가 흔히 ‘구조화된 스택 머신’으로 설명되지만 실제로는 로컬(가변 변수) 때문에 SSA/라이브니스 분석 관점에서 스택 머신처럼 동작하지 않으며, 스트리밍 컴파일러와 최적화에 어떤 문제가 생기는지와 대안(블록 인자·멀티 값)을 다룬다.
URL: http://troubles.md/wasm-is-not-a-stack-machine/
머리말
WebAssembly의 문제점과 이를 고치기 위한 제안들을 다루는 4부작 미니시리즈의 1편이다. 2편은 여기, 3편은 여기, 4편은 여기에 있다. 이 글은 가상 머신, 컴파일러, WebAssembly에 대한 어느 정도의 친숙함을 전제로 하지만, 필요할 때마다 관련 정보를 링크해 익숙하지 않더라도 따라올 수 있게 하겠다. 또한 이 시리즈는 내가 WebAssembly를 싫어하는 것처럼 보일 수 있다. 하지만 나는 WebAssembly를 정말 좋아한다! 얼마나 대단한지에 대한 글도 따로 썼다! 사실 나는 WebAssembly가 가능한 한 최고의 형태가 되길 바란다. 그래서 명세의 잉크가 아직 완전히 마르지 않은 지금, 이 설계상의 불만들을 짚어 보며 이 문제들 중 일부 또는 전부가 조만간 해결되기를 바라면서 이 시리즈를 쓴다.
여러분도 이제 WebAssembly에 익숙할 것이다. 플러그인부터 블록체인 스마트 컨트랙트, 그리고 물론 웹까지, 곳곳에서 사용되고 있다. 지금 당장 WebAssembly의 위키피디아 문서를 보면 기술에 대한 훌륭한 개요를 얻을 수 있다. 다만 한 가지 문제가 있다. “Design(설계)” 섹션에 이렇게 적혀 있다:
WebAssembly code is intended to be run on a portable abstract structured stack machine
아니다.
스택 머신과 레지스터 머신의 차이는 본질적으로 다음과 같다. 스택 머신은 값을 스택에서 pop하고 스택에 push한다. 예를 들어 + 연산은 스택의 마지막 두 값을 pop해서 더한 다음, 결과를 다시 스택에 push한다. 레지스터 머신은 값을 저장할 수 있는 “자리”가 몇 개 있고, 연산은 그 레지스터들을 읽고 쓴다. 그래서 +는 3개의 인자를 받는다. 2개는 피연산자를 읽을 레지스터를 나타내고, 1개는 결과를 쓸 레지스터를 나타낸다1.
레지스터의 문제는 라이브니스(liveness) 분석이 없다는 점이다. 다음과 같은 코드가 있을 때:
text%0 = 1 %1 = 2 %2 = add %0, %1 ...
%0와 %1이 덧셈 이후에도 사용되는가? 미리 보기(lookahead) 없이 알 방법이 없다. SSA2 기반 레지스터 머신(각 레지스터가 정확히 한 번만 쓰이는 LLVM IR 같은 것)에서도 각 레지스터의 라이브니스는 계속 재계산해야 한다. 이는 컴파일에 오버헤드가 생긴다는 뜻이다. 변수의 라이브니스를 아는 것은 효율적인 어셈블리를 생성하는 데 매우 중요하지만, IR을 만들 때 라이브니스를 계산해 IR의 일부로 저장하는 대신, 매번 이 데이터를 다시 계산해야 한다.
IR이 전부 메모리 내에 있고, 특히 코드가 SSA 형태라면 그리 나쁘진 않다. 하지만 같은 품질의 코드를 위해 추가 작업을 해야 하며, 스트리밍 컴파일러(예: FireFox의 Wasm 베이스라인 컴파일러)는 좋은 코드를 만들어 내지 못한다.
물론 머신에 라이브니스 분석 메타데이터를 추가할 수는 있다. 하지만 그 라이브니스 분석은 코드가 SSA 형태일 때만 유용하다. SSA가 아니라면 라이브니스는 극도로 거칠어진다.
그런데 여기서 WebAssembly가 등장한다. WebAssembly에는 로컬(locals)이라는 것이 있다. 로컬은 함수의 생명주기 동안 존재하는 가변 변수다. WebAssembly 블록은 인자를 받을 수 없기 때문에, 블록이 바깥에서 데이터를 받는 유일한 방법이 로컬이다. 여기에는 SSA를 무력화시키는 전형적인 예인 루프 카운터 같은 것도 포함되지만, 일반 블록도 포함된다. 예를 들어:
wasm(func (result i32) (add (i32.const 1) (i32.const 2)) (block (result i32) ; 위 add의 결과를 읽을 수 없다 ))
그래서 이렇게 해야 한다:
wasm(func (result i32) (local i32) (local.set 0 (add (i32.const 1) (i32.const 2))) (block (result i32) (local.get 0) ))
이건 문제다. 보통 스택 머신은 SSA 형태로(그리고 라이브니스 분석과 함께) 아주 쉽게 변환할 수 있다. 스택의 아이템은 연산자의 인자로 사용되는 순간 죽는다(dead). 예외도, 단서도 없다. pick 연산자3조차 pick의 인자가 컴파일 타임 상수인 한 이런 관점에서 생각할 수 있다. 다만 일반적으로 pick 명령을 포함하는 스택 머신의 SSA 변환은 참조 카운팅(refcounting)으로 구현될 것이다. 즉 변수를 읽을 때 불필요하게 새 변수를 만들지 않게 한다. 하지만 로컬은 문제다. 로컬은 가변이므로 SSA로 간단히 변환할 수 없고, 항상 함수의 생명주기 전체에 걸쳐 살아 있다.
이는 최적화에 문제를 일으킨다. SSA 형태는 가장 강력한 최적화 도구 중 하나다. 로컬이 가변이라는 사실이 이를 무력화하고, 로컬이 함수 전체 범위(global to the function)라는 사실이 라이브니스 분석을 무력화한다. 왜 문제가 되는지 예를 들어 보자. WebAssembly를 어떤 네이티브 아키텍처로 컴파일하려 한다고 하자. 코드를 “레지스터에 몇 개의 인자를 두는” 형태로 컴파일할 것이다. 그런데 그 함수에 대해 직접 라이브니스 분석을 하지 않는 한, 그 레지스터들은 인자들에 의해 영구적으로 “사용 중”으로 표시된다. 추가 분석 없이는 그 인자가 마지막으로 사용되는 지점을 알 수 없고, 그래서 그 인자가 차지하던 레지스터를 다른 용도로 재사용할 수 없다. 인자를 전혀 사용하지 않는 함수라 해도, 그 인자들이 차지한 공간을 다른 것에 쓸 수 없다.
이는 본질적으로 WebAssembly를 “라이브니스 분석이 없는 레지스터 머신”으로 만든다. 그뿐 아니라, SSA 형태조차 아닌 레지스터 머신이 된다. 최적화에 사용할 수 있는 두 가지 도구 모두를 사용할 수 없게 되는 것이다. 진짜 최적화 컴파일러에서는 그 정보를 다시 만들어낼 수 있다. 하지만 WebAssembly는 이미 한 번 그 정보를 생성한 컴파일러에 의해 방출(emitted)된 결과다. 그 작업을 다시 해야 할 기술적 이유는 없다. 그저 언어의 결함일 뿐이다. WebAssembly 스트림에 대해 동작해야 하는 컴파일러는 이 정보를 재구성할 능력이 더 떨어지고, 그 결과 본질적으로 아무 이유 없이 훨씬 나쁜 코드를 생성하게 된다.
WebAssembly 명세 개발자들이 멍청한 것은 아니다. 대부분은 매우 잘 설계된 명세다. 하지만 WebAssembly의 레거시에 발목이 잡혀 있다. WebAssembly는 바이트코드로 시작한 것이 아니라, asm.js를 위한 단순화된 바이너리 표현에 가까웠다. 본질적으로 처음에는 JavaScript처럼 소스 코드에 가까운 형태로 설계되었다. 더 효율적인 표현이긴 하지만, 제대로 된 가상 머신 명령어 집합은 아니었다. 그러다가 레지스터 머신이 되었고4, 마지막 순간에 연산자들을 스택 기반 인코딩으로 바꿨다. 그 시점에는 로컬 같은 개념이 명세에 꽤 깊게 자리 잡고 있었다.
그뿐 아니라, WebAssembly 명세 팀은 대부분의 기간 동안 사실상 눈을 가린 채로 진행했다. 스트리밍 컴파일러는 아직 만들어진 적이 없었고, 아니, 컴파일러 자체가 아직 만들어진 적이 없었다. 로컬이 문제가 될 거라고는 분명하지 않았다. 결국 C도 로컬 변수를 사용하면서 컴파일러가 SSA 그래프를 구성해 잘 굴러가니까.
내가 이러한 문제들(그리고 이 시리즈의 다음 글들에서 다룰 다른 문제들)을 깨달은 것은 Wasmtime 통합을 위한 스트리밍 WebAssembly 컴파일러를 작업하면서였다. 그 전까지는 WebAssembly 설계가 완전히 견고하다고 생각했고, 사실 지금도 대부분의 결정이 옳았다고 강하게 믿는다. 문제가 있긴 하지만, 명세가 쓰이던 당시가 비교적 미지의 영역이었음을 생각하면 WebAssembly 워킹 그룹이 얼마나 많은 것을 제대로 해냈는지 놀라울 정도다.
현재 로컬은 함수 인자와 로컬 변수를 모두 나타낸다. 블록이 인자를 받을 수 있게 하고, 함수와 블록 모두 여러 값을 반환할 수 있게 하는 제안이 있다. 이를 통해 로컬을 완전히 없애는 것이 가능해진다.
루프 카운터는 카운터를 인자로 주고, 루프 헤더로 점프할 때 스택 위에 새 카운터 값을 올려두는 방식으로 구현한다. 이는 phi 함수처럼 동작하지만 개념적으로 훨씬 단순하다. WebAssembly에서는 로컬의 주소를 얻는 것이 불가능하므로 어떤 형태의 alloca도 필요 없다. LLVM과 달리 로컬이 아예 필요하지 않은 것이다. 남는 것은 함수 인자를 “함수 시작 시 스택 위에 인자가 놓여 있다”는 방식으로 구현하는 것뿐이며, 그러면 로컬이 전혀 필요 없어진다.
이렇게 하면 표현력을 줄이지 않으면서 WebAssembly 명세와 그 컴파일러의 복잡도를 크게 낮출 수 있고, WebAssembly를 생성하는 컴파일러가 원본 소스에 대한 더 많은 지식을 WebAssembly 자체에 인코딩할 수 있게 된다. 최적화 컴파일러가 여기서 더 좋은 코드를 뽑아내지는 못할 수도 있지만, 훨씬 단순해지고 유지보수도 쉬워질 것이다. 그리고 스트리밍 컴파일러는 훨씬 단순해지며 훨씬 더 좋은 코드를 만들어 낼 것이다.
마지막으로, 이런 스택 머신은 자동으로 SSA 형태일 뿐 아니라 자동으로 엄격한(strict) SSA 형태가 된다. 즉 정의되지 않은 변수를 접근하는 것이 정적으로 불가능해진다. 현재의 WebAssembly에서는, 로컬이 접근되기 전에 항상 설정된다는 것을 정적으로 증명할 수 없는 한 함수에 진입할 때 로컬을 0으로 초기화해야 한다. 다시 말해, 컴파일러는 거의 항상 이 정보를 이미 갖고 있는데도 불구하고 말이다. 로컬을 제거하면 정의되지 않은 메모리 접근 자체가 정적으로 불가능해진다.
다음 글에서는 WebAssembly의 문제 많은 제어 흐름(control flow)을 다룬다.
