클로저 변환 IR을 WebAssembly 실행 코드로 변환하는 코드 생성 패스와 Wasm 모듈/타입/명령어 방출 과정을 살펴본다.
URL: https://thunderseethe.dev/posts/emit-base/
이 글은 언어 만들기 시리즈의 일부다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈다.
오늘 글의 바로 이전 단계는 베이스 클로저 변환 패스다. 코드 방출(code emission)은 클로저 변환 IR을 실행 가능한 타깃, 즉 WebAssembly로 바꾼다.
오늘은 정말 좋은 날이다. 우리는 실행의 문턱 앞에 함께 서 있다. 지금까지 해온 모든 작업이 마침내 마지막 컴파일 패스—코드 생성(Code Generation)—으로 수렴한다. 클로저 변환된 IR을 받아 실행 가능한 코드로 바꿔, 석양을 향해 달려간다.
경험 많은 컴파일러 작성자라면 의아할 수도 있다. 클로저 변환은 전통적으로 컴파일러의 마지막 패스와는 거리가 멀고, 보통 백엔드보다는 미들엔드 쪽에 놓인다. 걱정하지 말자. 여기에서도 그 말은 맞다. 우리는 클로저 변환을 백엔드 쪽으로 옮긴 게 아니라, 백엔드 자체를 통째로 뛰어넘었다. 컴파일러 미들엔드에서 곧바로 코드를 생성하는 비결은 우리의 코드 생성 타깃인 WebAssembly(Wasm)에 있다.
Wasm은 컴파일러 타깃으로서 꽤 높은 수준이다. 덕분에 아래와 같은 더 낮은 수준의 백엔드 패스를 생략할 수 있다.
Wasm이 이런 패스들을 건너뛸 수 있는 이유는, 이름이 WebAssembly라 주는 인상과 달리 Wasm이 바이트코드 형식이기 때문이다. 바이트코드는 CPU가 직접 실행하지 않는다. 대신 바이트코드를 어셈블리로 번역해 실행하는 가상 머신(VM)이 실행한다. Wasm은 x86-64보다는 JVM과 더 많은 DNA를 공유한다.
바이트코드를 택한 건 실용적인 이유도 있지만, 더 큰 이유는 개인 취향이다. 내가 언어에 관심을 갖는 지점은 주로 의미 분석(semantic analysis)이라서 타입체커부터 시작했다. 백엔드에도 흥미로운 설계 여지가 많지만 내 흥미를 끌진 않는다. 바이트코드는 거인의 어깨 위에 올라, 처음부터 끝까지 돌아가는 무언가를 빠르게 갖출 수 있게 해준다. 클라우드가 결국 남의 컴퓨터라면, 가상 머신은 결국 남의 백엔드 패스다.
바이트코드는 본질적으로 어셈블리보다 높은 수준이라서 존재하지만, 그렇다고 우리가 클로저 변환으로 만들어내는 IR보다 높은 수준은 아니다. 우리의 IR은 트리 구조로, 각 표현식이 임의의 부분 표현식을 포함할 수 있다. 반면 바이트코드는 수행할 연산들의 리스트다. 따라서 IR을 리스트에 들어맞도록 평평하게 펴야 한다. 또한 바이트코드 연산은 IR이 제공하는 것보다 단순하다. 불행히도 Wasm 바이트코드에는 “클로저를 구성하는” 단일 구성 요소가 없다. 더 복잡한 표현식을 여러 연산으로 분해해야 한다.
바이트코드 연산은 어셈블리와 닮았다. 대부분 산술과 메모리 셔플로 구성된다. 예를 들어 두 정수를 더하는 Wasm은 다음과 같다.
wasm(local.get $1) (local.get $2) (i32.add) (local.set $3)
자세한 내용은 잠시 후 다루겠지만, 우선 이게 IR보다 어셈블리에 더 가깝게 보인다는 점을 보자. 레지스터 $1, $2에서 정수를 꺼내 i32.add로 더한 뒤 결과를 $3에 쓴다. 하지만 중요한 차이도 있다. 진짜 어셈블리라면 $1, $2, $3 같은 추상 레지스터가 아니라 CPU가 제공하는 구체 레지스터를 알아야 한다. 더한 뒤 결과를 어디에 둘지도 알아야 한다. 예컨대 반환 값을 어디 레지스터에 써야 하는지도 알아야 한다. 또한 어셈블리에선 스택을 직접 관리해야 한다. 스택 포인터가 든 레지스터가 무엇인지 알고, 함수에서 돌아올 때 갱신해야 한다.
바이트코드는 이런 걱정을 가상 머신에게 맡긴다. 개념적 부담이 줄고 이식성이 좋아진다. 타깃 CPU별 어셈블리를 어떻게 방출할지 알 필요가 없다. 누군가 그 CPU용 가상 머신을 써두기만 하면 된다.
컴파일러 베테랑들은 또 이렇게 말할지도 모른다. “잠깐, LLVM도 네가 말한 장점들을 제공하면서 네이티브 코드를 만들어 주지 않나?” 이에 대해 나는 이렇게 말하겠다. “야! 그만 말해!” 앞서 말했듯 개인 취향이다. 이 블로그 시리즈는 내 것이다. 그래서 나는 Wasm을 방출한다. 왜냐하면 멋지니까.
Wasm이 바이트코드라는 건 안다. 어떤 VM이 이를 실행하며 실제 머신에서 돌려준다. 좋은 시작이다. 하지만 IR에서 Wasm을 방출하려면 Wasm을 더 알아야 한다. 바이트코드인 Wasm의 주요 형식은 바이너리다. 각 연산은 VM이 디코딩하기 쉬운 바이트(혹은 몇 바이트)로 인코딩되지만, 사람이 읽기는 거의 불가능하다. 다행히 Wasm은 바이너리 형식과 함께 사람이 읽을 수 있는 텍스트 형식도 제공한다. 예시에서는 텍스트 형식을 쓰되, 실제 코드는 바이너리를 생성한다.
텍스트 형식은 S-표현식을 사용하며 리스프처럼 보인다. S-표현식 덕분에 편리한 문법 설탕을 쓸 수 있다. 앞선 예시는 중첩 S-표현식으로 트리처럼 다시 쓸 수 있다.
wasm(local.set $3 (i32.add (local.get $1) (local.get $2)))
이는 순전히 문법적 편의일 뿐이다. 내부적으로 Wasm은 언제나 평평한 연산 리스트다.
Wasm 코드는 .wasm 파일(텍스트면 .wat)에 담긴다. 각 .wasm 파일은 하나의 Wasm 모듈을 포함한다. 다른 언어의 모듈 개념과 마찬가지로, 이는 여러 함수의 모음이며 다른 Wasm 모듈과의 import/export를 포함한다. 함수는 Wasm의 주요 계산 단위다. 각 함수는 예상대로 여러 인자를 받지만, 놀랍게도 여러 값을 반환할 수도 있다. (우린 쓰지 않지만 Wasm은 둘 이상의 값을 반환할 수 있다.)
모듈 내부에는 모듈이 담을 수 있는 각 요소에 대한 섹션(section)이 있다. 섹션은 엔티티의 순서 있는 리스트이며, 바이너리 형식에서는 새 섹션의 시작을 알리는 ID로 표시된다. 이 순서 있는 리스트는 컨테이너일 뿐 아니라 식별자 역할도 한다. 예를 들어 함수 섹션은 함수 시그니처의 순서 리스트다. 어떤 함수를 참조할 때는 함수 섹션에서의 인덱스로 참조한다.
이처럼 엔티티를 섹션으로 나누는 이유는 Wasm의 원래 동기가 브라우저를 위한 이식 가능한 바이트코드였기 때문이다. 서버에서 클라이언트로 전송되는 것을 상정하여, 네트워크 스트리밍과 압축을 고려한 인코딩 선택이 많다. 모듈은 다양한 섹션을 지원하고, 그중 다수는 옵션이지만, 여기서는 우리가 사용할 것만 다룬다.
첫 번째 섹션은 Wasm 모듈이 필요로 하는 모든 타입을 선언한다. Wasm 코드는 타입이 있으며, VM은 실행 전에 타입을 검증한다. 모든 타입이 인덱스를 필요로 하는 것은 아니다. Wasm은 즉시 사용 가능한 값 타입(value type) 집합을 정의한다. 우리는 그중 두 가지를 사용한다.
(더 많은 값 타입이 여기에 있다.)
I32는 32비트 정수다. Ref는 합성 타입(compound type)에 대한 참조다. 합성 타입은 여러 값 타입을 묶어 만든 더 큰 타입이며, 여기서는 함수나 구조체가 된다. 합성 타입은 인덱스를 필요로 하므로 타입 섹션에 선언해야 한다. Ref는 자신이 참조하는 타입을 그 인덱스로 지정한다.
함수 타입을 참조하고 싶다면(함수형 언어에서 흔하다) 먼저 함수 타입을 선언해야 한다.
wasm(type (func (param i32 i32) (result i32)))
함수 타입은 param, result로 매개변수와 반환 타입을 정의한다. 위 타입은 두 정수를 받아 정수를 반환한다. 매개변수와 반환 타입은 값 타입이어야 한다. Wasm은 값 타입만 전달할 수 있다.
이 함수를 다른 함수에 넘기고 싶다면 참조로 감싸야 한다.
wasm(type (func (param (ref 0)) (result i32)))
앞의 함수는 섹션 인덱스 0이므로 (ref 0)로 참조한다. 이를 이용해 인덱스 1의 두 번째 타입을 “앞의 함수를 받아 정수를 반환하는 함수”로 정의한다.
방출 중에 사용할 또 다른 합성 타입은 구조체(struct)다. 구조체는 필드 리스트로 이루어지며 필드는 사실상 값 타입이다. 필드는 i8, i16 같은 추가 타입도 지원하지만 필요 없다. 구조체 안에 함수를 저장하려면 여전히 참조 타입이 필요하다.
wasm(type (struct (field (ref 0)) (field i32)))
위는 두 필드를 가진 구조체를 정의한다.
마지막으로 필요한 타입 기능은 서브타이핑(subtyping)이다. 어떤 타입이 다른 타입의 서브타입임을 선언해 타입 간 캐스팅을 가능케 한다. 이는 클로저 구현에 필수적이다. 앞의 구조체에 sub를 붙이면 서브타이핑 가능한 타입이 된다.
wasm(type (sub (struct (field (ref 0)) (field i32))))
이는 실제 서브타입을 만들지는 않지만 “이 구조체 타입의 서브타입을 허용한다”는 뜻이다. Wasm은 기본적으로 타입 서브타이핑이 활성화되지 않으므로, 필요함을 명시해야 한다. 활성화 후에는 그 구조체의 인덱스를 사용해 서브타입을 정의할 수 있다.
wasm(type (sub final 2 (struct (field (ref 0)) (field i32) (field i32))))
이 구조체는 이전 구조체의 모든 필드를 같은 순서/타입으로 갖고, 새 정수 필드를 추가했으므로 서브타입이다. 또한 final로 표시했기 때문에 더 이상 서브타입을 만들 수 없다. 이제 인덱스 2와 3 사이에서 캐스팅할 수 있다.
하지만 어떤 타입이든 서브타입이 될 수 있는 건 아니다. 함수가 구조체의 서브타입이 될 수는 없다. 또한 임의의 구조체를 다른 구조체의 서브타입으로 만들 수 없다. 서브타입이 되려면 슈퍼 구조체의 필드를 올바른 순서와 타입으로 공유해야 한다. 예를 들어 아래는 필드 순서를 바꿨기 때문에 유효하지 않다.
wasm(type (sub final 2 (struct (field i32) (field (ref 0)) (field i32))))
모든 것을 합치면 최종 타입 섹션은 다음처럼 보인다.
wasm(type (func (param i32 i32) (result i32))) (type (func (param (ref 0)) (result i32))) (type (sub (struct (field (ref 0)) (field i32)))) (type (sub final 2 (struct (field (ref 0)) (field i32) (field i32))))
타입 섹션이 타입을 선언하듯, 함수 섹션은 함수를 선언한다. 보통은 함수 본문이 들어갈 것 같지만, 바이너리 형식에서는 함수 정의를 함수 섹션과 코드 섹션으로 나눈다.
이렇게 나누면 VM이 함수를 스트리밍하며 병렬 컴파일할 수 있다. 우리에겐 구현 디테일이지만, 함수 섹션에는 Wasm 연산이 없다. 대신 이 모듈이 정의하는 함수들의 시그니처만 담는다. C의 헤더 파일과 비슷하다.
함수 시그니처 자체도 단순하다.
wasm(func (type 0))
함수 시그니처는 자신의 타입이지만, 타입은 타입 섹션에 이미 정의되어 있다. 함수 섹션에는 함수 타입을 가리키는 인덱스만 필요하다. 이는 참조 타입이 아니라 함수 타입 자체를 쓰는 드문 자리 중 하나다. 함수 섹션이 너무 사소해서 텍스트 형식에는 잘 드러나지 않는 이유이기도 하다.
내보내기(export) 섹션은 모듈의 공개 API를 선언한다. 함수들의 묶음인 모듈은 혼자서는 별 일을 하지 않는다. VM에 로드해도 즉시 아무것도 실행하지 않는다. 로드시 코드를 실행하게 하는 방법도 있지만(스크립트처럼), 여기서는 쓰지 않고 다루지도 않는다.
우리에게 모듈은 비활성(inert)이다. 무언가가 함수를 호출해야 동작이 시작된다. 모듈 밖에서 모듈 안의 함수를 호출하는 유일한 방법은 그 함수가 export되어 있는 경우다. export는 단순 인덱스만 쓰지 않고 텍스트 이름을 부여한다. 예를 들어 첫 함수를 export하려면:
wasm(export "main" (func 0))
이름 “main”으로 export를 선언하고 함수 인덱스 0을 가리킨다. 함수임을 명시해야 하는데, Wasm은 다른 것들도 export할 수 있기 때문이다. (우린 필요 없지만) 메모리, 글로벌, 테이블도 함수와 함께 export할 수 있다. 지금은 우리에겐 과분하다. export에 준 이름은 모듈 내부에서의 사용에는 영향이 없고, 외부에서 import될 때만 의미가 있다.
코드 섹션에서 마법이 일어난다. 함수 본문과, 머신을 움직이는 명령어들이 여기에 있다. 코드 섹션은 자체 인덱스를 갖지 않고, 함수 본문을 담는 용도이므로 함수 인덱스를 재사용한다.
코드 섹션에 무엇이 들어가는지 말하기 전에 Wasm의 실행 모델을 더 이해해야 한다. Wasm은 스택 머신이다. 모든 계산을 스택으로 수행한다. 2 + 3을 계산하려면:
wasm(i32.const 2) (i32.const 3) (i32.add)
i32.const는 알려진 정수를 스택에 올린다. 첫 두 명령을 실행하면 스택엔 값이 쌓인다.
스택이므로 i32.const 3은 2 위에 놓여 스택의 맨 위 값이 된다. i32.add는 스택에서 두 값을 소비해 그 합으로 대체한다.
모든 연산은 인자를 스택에서 가져오고 결과를 스택에 돌려놓는다. 하지만 스택 꼭대기만으로 작업하는 것이 늘 편하진 않다. 값을 계산해두고 다른 계산을 한 뒤 다시 그 값으로 돌아오고 싶을 때가 많다. 스택에 어디에 무엇을 남겼는지 꼼꼼히 추적해 되찾을 수도 있지만, 복잡한 표현식에서는 금방 번거롭고 오류가 나기 쉽다.
그래서 Wasm은 스택 값들을 저장할 수 있는 로컬 변수(local)를 제공한다. 함수는 원하는 만큼 로컬을 쓸 수 있지만, 미리 몇 개가 필요한지 선언해야 한다. 로컬은 함수 내부에서만 유효하고 함수가 리턴하면 사라진다. 로컬은 값을 기억할 뿐 아니라 같은 값을 여러 번 써야 할 때도 유용하다.
wasm(i32.const 2) (i32.const 3) (i32.add) (local.set 0) (local.get 0) (local.get 0) (i32.mul)
스택에서 5를 계산한 뒤 로컬 0에 저장한다. 그런 다음 i32.mul로 제곱(25)을 계산하기 위해 5를 두 번 꺼낸다. Wasm은 스택의 값을 직접 복제하는 명령이 없어서, 여러 번 쓰려면 로컬에 저장해야 한다.
이제 코드 섹션으로 돌아가자. 함수 섹션의 각 함수 인덱스에 대해, 코드 섹션에는 두 가지를 제공한다.
로컬은 미리 선언해야 한다. 방출하는 우리에겐 약간의 부담이지만, VM이 함수에 필요한 로컬 수를 미리 알고 더 좋은 코드를 만들 수 있게 해준다. 로컬은 값 타입이어야 한다. local.set은 스택의 최상단 값을 로컬에 넣는데, 그 최상단 값은 항상 값 타입이어야 한다. 따라서 로컬에는 값 타입만 들어간다.
그 다음은 명령어 리스트다. 모든 명령어를 다루진 않는다(정말 많다). 여기선 큰 그림만 보고, 실제로 쓰는 명령어는 등장할 때 자세히 본다.
명령어는 카테고리로 나뉜다.
이것도 전부는 아니지만 우리가 사용할 것들이다. 숫자 명령어는 산술/불리언/비트 연산을 다루지만, 우리 언어에는 덧셈조차 없으므로 거의 쓰지 않는다. (함수형 언어를 만드는 게 아니라 “함수형 언어”를 만들고 있다.) 우리가 필요한 숫자 명령어는 상수를 스택에 올리는 i32.const뿐이다.
참조 명령어는 참조의 생성, 비교, 캐스팅을 다룬다. null 참조도 지원하지만 필요 없다. 하이라이트는 두 가지다.
ref.func: 함수 인덱스로부터 함수 참조를 생성한다.ref.cast: 한 타입의 참조를 서브타입 참조로 다운캐스트한다.슈퍼타입으로의 업캐스트는 암묵적이므로, 다운캐스트에만 명령어가 필요하다.
구조체 참조에 대한 명령이 없는 것이 눈에 띄는데, 구조체는 집합 명령어로 처리되기 때문이다. 집합 명령어는 Wasm의 GC 기능 일부다. 기본 Wasm을 확장해, 가비지 컬렉션되는 관리 힙 타입을 지원한다. 일반 Wasm 값은 스택에 살지만, GC 타입은 힙에 살며 더 이상 참조되지 않으면 GC가 해제한다. Wasm GC는 아직 표준의 일부는 아니고 플래그로 활성화해야 하지만, 주요 런타임이 모두 지원하므로 표준에 들어가지 않을 가능성은 매우 낮다.
집합 명령어는 GC 객체를 다루며, 구조체와 배열 두 종류가 있다. 우리는 구조체만 필요하다. 구조체는 struct.new로 만들며, 타입 인덱스와 스택의 값들을 받아 새 구조체의 참조를 만든다. 타입 섹션의 (struct (field (ref 0)) (field i32))를 예로 들어, 정수 두 개를 받아 정수를 반환하는 함수 0이 있다고 하자. 아래처럼 인스턴스를 만들 수 있다.
wasm(ref.func 0) (i32.const 435) (struct.new 2)
struct.new는 생성할 구조체 타입을 정적으로 받지만, 필드 값은 스택에서 받는다. 필드는 스택에 올바른 순서로 있어야 하며, 아래처럼 순서를 바꾸면 타입 오류가 된다.
wasm(i32.const 435) (ref.func 0) (struct.new 2)
구조체가 있으면 struct.get은 타입 인덱스와 필드 인덱스를 받아, 스택에서 구조체 참조를 소비하고 그 필드 값을 생산한다. 구조체는 집합으로 분류되지만 여전히 일반 참조를 만든다. 따라서 struct.cast 같은 별도 명령은 필요 없고, ref.cast가 구조체에도 그대로 동작한다.
변수 명령어는 로컬을 다룬다. local.get, local.set은 이미 봤다. 우리가 쓸 또 하나는 local.tee다. local.tee는 get+set을 합친 것처럼, 스택에서 값을 꺼내 로컬에 저장하면서 스택에 복사본을 남긴다. 예를 들어:
textlet x = ...; let y = x + 1; x + y
x를 로컬 0에 저장하되 곧바로 y를 계산하기 위해 x가 필요하다. local.set 0 후 즉시 local.get 0을 하기보다 local.tee 0을 사용하면 x를 저장하면서 스택에 x를 남겨 y 계산에 쓸 수 있다. 이후 x + y를 계산할 때도 local.get 0으로 x를 다시 가져올 수 있다.
제어 명령어는 제어 흐름을 다룬다. 함수형 언어인 우리에겐 주로 함수 호출이다. Wasm은 if/else, 루프, 스위치도 지원하지만 여기서는 call_ref가 핵심이다. struct.new처럼 정적인 함수 참조 타입과 스택의 인자들을 받아 해당 함수를 호출한다. 우리가 방출할 클로저를 호출할 수 있게 해준다.
여기까지는 정보가 많았지만, Wasm 전체로 보면 애피타이저 수준이다. 이제 IR에서 Wasm을 만들어내는 과정으로 넘어가자. 텍스트 형식에 맞춰 문자열을 이어붙일 수도 있지만, 목적에 비해 너무 취약하다.
텍스트 형식을 방출하면 실행 전에 바이너리로 변환하는 추가 단계가 생긴다. 실행되는 건 결국 바이너리 형식이므로, 애초에 바이너리를 직접 방출하는 게 더 단순하다. 필요하면 부가 워크플로로 텍스트 형식을 제공하면 된다.
그렇다고 바이트를 손으로 하나씩 찍는 건 문자열 이어붙이기보다 나을 게 없다. 다행히 Rust에는 wasm-encoder 크레이트가 있어 Wasm 바이너리 모듈을 구성하는 래퍼 타입을 제공한다. Wasm 같은 표준 바이트코드를 선택하면 표준 생태계 도구를 활용할 수 있다는 장점이 있다. wasm-encoder는 Wasm이 기대하는 바이트를 뱉어주지만, 그 바이트가 Wasm의 불변식(invariant)을 만족하는지 검증해주진 않는다.
의존성에 모든 일을 떠넘긴다면 컴파일러 장인이라 부르기 어렵다. 타입이 맞는지, 사용 전에 정의되는지 등은 여전히 우리가 보장해야 한다. 다만 여기까지의 컴파일 과정에서 이미 많은 것을 암묵적으로 처리했다. 타입체킹을 했으니 타입이 맞을 거라 믿는다. 이름 해석이 성공했으니 정의 전에 사용되지 않을 거라 믿는다. 그렇지 않았다면 코드 생성에 도달하기 전에 컴파일 오류를 냈을 것이다.
그러면 방출에서 정확히 뭘 하냐? 클로저 변환 후 우리는 아이템(item)들의 모음을 갖는다. 메인 표현식에 대한 아이템 하나와, 메인 표현식에서 변환된 각 클로저마다 하나씩의 아이템이다. 우리는 이 아이템들을 Wasm 모듈로 조립하고, 각 아이템을 Wasm 함수로 만든다.
아이템을 Wasm 함수로 바꾸는 과정에서:
IR을 표현식 결과를 생산하는 명령어 리스트로 변환해야 한다.이를 위해 세 도우미 구조체를 쓴다.
EmitWasm은 아이템을 함수로 변환하는 총괄 구조체이고, 변환 중에 EmitTypes, EmitLocals를 호출해 Wasm 타입과 로컬을 만든다. 먼저 EmitTypes를 설명하고 EmitWasm으로 올라간다.
EmitTypes는 IR 타입을 Wasm 타입으로 바꾼다. AST 타입을 IR 타입으로 내리던 과정과 비슷하다. 이를 위해 메타데이터가 필요하다.
ruststruct EmitType { types: Vec<PartialTy>, supertypes: HashMap<u32, u32>, }
동일한 Wasm 타입은 같은 인덱스를 가져야 하므로, 변환한 타입을 types에 인터닝(intern)한다. 이를 생략할 수도 있지만(wasm-encoder는 바이트를 출력해 준다), 그러면 같아 보이는 타입들이 타입체크에 실패해 당황스러운 오류 메시지를 낳는다. 또한 각 타입의 서브타입/슈퍼타입 관계도 추적하지만, 구조체만 서브타입으로 엮는다.
가장 복잡한 타이핑은 클로저에서 나온다. 클로저 변환에서 보았듯 클로저는 이미 두 타입 Closure, ClosureEnv로 존재한다. 이 둘은 Wasm 타입이 필요하며, 서로 서브타입 관계도 필요하다. 그리고 Wasm에서는 클로저가 세 번째 모습으로 나타난다: struct.
struct는 모든 구조체의 슈퍼타입이다. 값 타입처럼 인덱스가 필요 없다(필드가 없기 때문). 어떤 선언된 구조체 타입도 암묵적으로 struct로 업캐스트되고, struct는 어떤 선언된 구조체로든 다운캐스트될 수 있다. 이는 동적 타이핑에 위험할 정도로 가깝고, 잘못 다운캐스트하면 런타임에 크래시 난다.
예를 들어, 정수 인자를 받아 정수를 반환하고 환경에 정수를 하나 캡처하는 클로저를 생각해 보자. 코드 생성 동안 우리는 이 클로저를 세 가지 타입으로 참조한다.
struct - 추상 슈퍼타입(struct (field (ref $fun))) - 클로저의 함수 필드 하나만 가진 구조체(추상 타입)(struct (field (ref $fun)) (field i32)) - 함수+환경을 모두 담은 구체 타입뒤의 두 타입을 각각 클로저의 추상 타입(abstract type), 구체 타입(concrete type)이라 부르자.
EmitTypes는 타입의 최종 형태가 아니므로, 방출 중에 필요한 부분만 담는 PartialTy를 쓴다.
rustenum PartialTy { Func(FuncType), Struct(Vec<FieldType>, bool), }
함수 타입은 wasm_encoder의 FuncType(인자/반환 타입 포함)로 저장한다. 구조체 타입은 FieldType 리스트로 저장한다. 모든 ValueType은 FieldType이 될 수 있다(추가 타입도 있지만 여기선 필요 없다).
구조체의 bool은 서브타이핑에 대한 final 여부를 추적한다. 확실히 서브타입이 없으면 true, 서브타입이 있을 수 있으면 false다.
EmitType의 주요 진입점은 emit_val_ty다. IR 타입에서 Wasm 타입이 필요할 때 기본으로 쓰는 함수다.
rustfn emit_val_ty(&mut self, ty: &Type) -> ValType { todo!() }
emit_val_ty는 Type을 Wasm 값 타입으로 바꾼다.
rustmatch ty { Type::Int => ValType::I32, Type::ClosureEnv(closure, _) => self.emit_val_ty(closure), Type::Closure(arg, ret) => self.emit_closure_index(arg, ret) .struct_index .as_val_ty(), }
Int는 I32가 된다. 지금까지 i32를 썼기 때문에 암묵적으로 32비트라 가정했지만, 여기서 명시된다. ClosureEnv는 그 안의 closure 타입이 반환하는 타입을 그대로 반환한다. Closure는 emit_closure_index를 호출해 struct_index를 값 타입으로 만든다. 이게 무엇을 의미하는지 더 파고들어야 한다.
emit_closure_index는 클로저 타입을 Wasm 타입 하나가 아니라 둘로 만든다. 하나는 클로저의 실제 함수 타입, 다른 하나는 클로저의 추상 타입이다.
rustfn emit_closure_index( &mut self, arg: &Type, ret: &Type ) -> ClosureTypeIndex { todo!() }
ClosureTypeIndex는 인덱스를 정리해주는 보조 구조체다.
ruststruct ClosureTypeIndex { func_index: u32, struct_index: u32, }
먼저 클로저의 인자/반환 타입을 값 타입으로 변환한다.
rustlet arg_valty = self.emit_val_ty(arg); let ret_valty = self.emit_val_ty(ret);
그 다음 함수 타입을 만든다.
rustlet func_index = self.emit_ref_ty(PartialTy::Func(FuncType::new( [abstract_struct_ty(), arg_valty], [ret_valty], )));
IR에선 인자가 하나지만 Wasm 함수 타입은 인자가 둘이다. 첫 번째는 abstract_struct_ty()가 반환하는 Wasm의 struct이고, 두 번째가 실제 클로저 인자다. 첫 번째 인자는 클로저 환경이며 struct로 타이핑한다. 기술적으로는 잘못된 구조체를 넘길 수 있지만, IR이 타입체크되었으므로 그런 일은 없다고 믿는다.
그렇다면 왜 위험을 감수하고 struct를 쓰는가? 정확한 클로저 구체 타입은 클로저 본문 안에서만 알 수 있다. 환경 파라미터로 클로저 자신을 넘길 때, 우리는 클로저의 함수 타입만 안다. 그럼 최소한 그걸 쓰면 유닛 구조체 같은 걸 환경으로 넘기는 걸 막을 수 있지 않나?
안전성은 늘지만, 그 대신 재귀 타입이 필요해 방출이 까다로워진다. 클로저의 추상 타입은 본문의 함수 타입을 포함하고, 그 함수 타입이 다시 클로저의 추상 타입을 인자로 쓰면, 추상 타입이 자기 자신을 포함하는 꼴이 된다.
Wasm은 재귀 타입을 지원한다. 각 클로저별 재귀 그룹을 추적해 방출할 수도 있다. 하지만 그 복잡도가 가져오는 이득(안전/성능)은 크지 않다. 어차피 클로저 본문에서는 추상 타입에서 구체 타입으로 캐스팅해야 한다. 그래서 약간의 타입 치팅으로 단순함을 택한다.
여기서 또 등장한 emit_ref_ty는 합성 타입을 인터닝하는 함수다.
rustfn emit_ref_ty(&mut self, key: PartialTy) -> u32 { self .types .iter() .position(|x| x == &key) .unwrap_or_else(|| { let indx = self.types.len(); self.types.push(key); indx }) .try_into() .unwrap() }
타입 리스트에서 동일한 타입을 찾고, 없으면 끝에 추가해서 그 인덱스를 사용한다.
emit_closure_index로 돌아가서, 구조체 타입도 emit_ref_ty로 인덱싱한다.
rustlet struct_index = self.emit_ref_ty(PartialTy::Struct( vec![FieldType { element_type: StorageType::Val(func_index.as_val_ty()), mutable: false, }], false ));
타입 인덱스를 Wasm 값 타입으로 감싸는 일이 너무 흔해서, u32 인덱스를 값 타입으로 바꾸는 as_val_ty 헬퍼를 만든다.
rustimpl AsValTy for u32 { fn as_val_ty(&self) -> ValType { ValType::Ref(RefType { nullable: false, heap_type: HeapType::Concrete(*self), }) } }
인덱스를 참조 타입으로 만들기만 하면 된다. 우리 언어에는 null이 없으니 nullable: false로 둔다.
마지막으로 결과를 조립한다.
rustClosureTypeIndex { func_index, struct_index }
이로써 끝이다.
아이템을 위한 또 다른 타입 방출 메서드 emit_item_ty가 필요하다.
rustfn emit_item_ty( &mut self, item: &Item ) -> u32 { todo!() }
emit_item_ty는 우리가 생성할 Wasm 함수들의 함수 타입을 만든다. 함수 타입은 값 타입이 아니라 “함수 타입 인덱스(u32)”로 다뤄진다. emit_ref_ty가 함수 타입도 처리할 수 있지만, 최상위 아이템에서만 필요한 클로저 환경 처리의 특수 케이스가 있어 여기서 다룬다.
먼저 반환 타입을 만든다.
rustlet ret_ty = self.emit_val_ty(&item.ret_ty);
그 다음 매개변수와 반환 타입으로 Wasm 함수 타입을 만든다.
rustlet func_ty = FuncType::new( item.params.iter().map(|var| match &var.ty { Type::ClosureEnv(_, _) => abstract_struct_ty(), ty => self.emit_val_ty(ty), }), [ret_ty], );
파라미터 목록에서 ClosureEnv를 만나면 struct로 취급한다. 앞서 논의했듯, 클로저 본문의 구현 함수에 환경을 넘길 때는 struct로 타이핑하고 싶기 때문이다. 마지막으로 인덱스를 만든다.
rustself.emit_ref_ty(PartialTy::Func(func_ty))
여기까지가 EmitTypes의 핵심이다. 몇몇 헬퍼는 문맥에서 등장할 때 다룬다.
이제 본론인 Wasm 명령어 방출로 가자. 타입 방출은 이를 위한 빌드업이었다. 우선 EmitWasm은 함수 간에 필요한 상태를 추적한다.
ruststruct EmitWasm { types: EmitType, functions: HashMap<ItemId, u32>, }
types는 방금 다룬 타입 방출기다. functions는 ItemId별 함수 인덱스로 미리 채워진 맵으로, 아이템을 해당 Wasm 함수로 매핑한다. EmitWasm의 유일한 진입점은 emit_item이다.
rustfn emit_item( &mut self, item: Item ) -> Function { todo!() }
아이템을 받아 Wasm Function을 만든다. Function은 명령어 리스트인데, 정의를 보면:
rustpub struct Function { bytes: Vec<u8>, }
…바이트 벡터다. 하지만 그 바이트가 명령어의 바이너리 인코딩이라 믿자.
Function 생성 API를 보면 로컬 타입이 필요하다.
rustimpl Function { pub fn new<L>(locals: L) -> Self where L: IntoIterator<Item = (u32, ValType)>, { ... } pub fn new_with_locals_types<L>(locals: L) -> Self where L: IntoIterator<Item = ValType>, { ... } }
어쨌든 ValType 이터레이터가 필요하다. 즉, 함수 본문이 사용할 로컬 변수 타입 목록이다. 로컬은 인덱스로만 참조하므로 이름은 필요 없다.
문제는 IR에서 쓰이는 로컬을 미리 계산하지 않았다는 점이다. 하지만 해결은 간단하다. 먼저 명령어를 방출하며 로컬을 추적하고, 그 뒤에 Function을 만든다.
rustlet (inss, local_tys) = self.emit_body(&item.params, item.body); let mut function = Function::new_with_locals_types(local_tys); for ins in inss { function.instruction(&ins); } function.instruction(&Instruction::Return); function.instruction(&Instruction::End); function
emit_body에서 로컬 개수를 추적한 뒤 Function을 만들고 명령어를 채운다. 모든 함수는 return과 end로 끝나므로 무조건 붙인다.
return은 스택 최상단 값을 반환하고, 스택의 다른 값들은 모두 제거한다. end는 현재 스코프를 끝낸다. Wasm의 구조화된 제어 흐름(if/loop 등)에서 쓰이지만, 함수도 스코프를 도입하므로 종료가 필요하다. 스트리밍과 관련이 있다고 믿지만 확실치는 않다.
이제 본문을 어떻게 명령어로 만드는지 보자.
rustfn emit_body( &mut self, params: &[Var], body: IR ) -> (Vec<Instruction<'static>>, Vec<ValType>) { let mut locals = EmitLocals { next_local: 0, locals: HashMap::default(), local_tys: vec![], }; todo!() }
Wasm에서 함수 파라미터도 로컬처럼 접근한다. 즉, 파라미터 수를 알아야 로컬 인덱스를 올바르게 배정할 수 있다. 파라미터가 2개면 로컬 0, 1은 파라미터를 가리키고 실제 로컬은 2부터 시작한다. 파라미터는 본문에서 로컬로 선언할 필요는 없고, 타입은 시그니처에 이미 있다.
로컬 관리가 중요하므로 별도 타입 EmitLocals를 둔다.
ruststruct EmitLocals { next_local: u32, local_tys: Vec<ValType>, locals: HashMap<VarId, u32>, }
next_local로 로컬 개수를 추적하고, local_tys로 로컬 타입을 추적하며, locals로 변수→로컬 인덱스 매핑을 유지한다. 이를 위해 세 메서드를 제공한다.
rustimpl EmitLocals { fn param_for( &mut self, id: VarId ) -> u32; fn anon_local( &mut self ) -> u32; fn local_for( &mut self, id: VarId ) -> u32; }
구현은 VarSupply와 비슷한 루틴이어서 생략한다. 전체 코드는 레포에 있다.
param_for: 파라미터에 대한 로컬을 반환한다. 파라미터는 local_tys에 넣지 않는다.anon_local: IR에 나타나지 않는 익명 로컬을 만든다. 변수 매핑 없이 로컬 타입만 추적한다.local_for: 가장 흔한 경우로, 로컬 타입을 추적하면서 변수→로컬 매핑도 한다.emit_body로 돌아가면, 먼저 파라미터들을 로컬로 시드한다.
rustfor param in params { locals.param_for(param.id); }
그 다음 본문이 클로저 본문인 경우를 처리한다.
rustlet mut inss: Vec<Instruction> = vec![]; if let Type::ClosureEnv(closure, env) = ¶ms[0].ty { let closure_env_index = self.types.emit_closure_env_index(closure, env); let casted_env_local = locals.anon_local(closure_env_index.as_val_ty()); inss.extend([ Instruction::LocalGet(locals[¶ms[0].id]), Instruction::RefCastNonNull(HeapType::Concrete(closure_env_index)), Instruction::LocalSet(casted_env_local), ]); locals.locals.insert( params[0].id, casted_env_local, ); }
첫 파라미터가 ClosureEnv면 클로저 본문이다. 이때 환경(추상 타입)을 구체 타입으로 캐스팅해야 한다.
rustInstruction::LocalGet(locals[¶ms[0].id]), Instruction::RefCastNonNull(HeapType::Concrete(closure_env_index)), Instruction::LocalSet(casted_env_local),
첫 번째로 환경 파라미터 로컬에서 값을 꺼낸다. 그 구조체 참조를 closure_env_index로 표현되는 구체 타입으로 다운캐스트한다. 마지막으로 캐스팅된 참조를 새로운 익명 로컬 casted_env_local에 저장한다.
타입이 바뀌었으므로 새 로컬이 필요하다. 이후 본문에서는 추상 struct가 아니라 캐스팅된 환경을 쓰고 싶다. 그래서 첫 파라미터가 가리키는 로컬을 몰래 casted_env_local로 바꿔치기한다. 이제 본문에서 환경 파라미터를 참조하면 params[0] 대신 casted_env_local을 쓰게 된다.
환경의 Wasm 타입은 EmitTypes의 emit_closure_env_index가 결정한다.
rustimpl EmiTypes { fn emit_closure_env_index( &mut self, closure: &Type, env: &[Type] ) -> u32 { todo!() } }
클로저 환경 구성요소 closure, env가 주어지면 각 타입마다 필드를 가진 Wasm 구조체 타입을 방출한다. 먼저 closure에서 함수 타입 인덱스를 얻는다.
rustlet Type::Closure(arg, ret) = closure else { panic!("ICE: Non-closure type appeared in ClosureEnv type"); }; let closure_indices = self.emit_closure_index(arg, ret);
그 인덱스로 환경 구조체의 첫 필드(코드 필드)를 만든다.
rustlet code_field = FieldType { element_type: StorageType::Val( closure_indices.func_index.as_val_ty()), mutable: false, };
이후 환경 나머지 필드를 만든다.
rustlet fields = std::iter::once(code_field) .chain(env.iter().map(|ty| FieldType { element_type: StorageType::Val(self.emit_val_ty(ty)), mutable: false, })) .collect();
구체 타입을 방출하면서 추상 타입도 방출한다. 추상/구체 타입 사이의 슈퍼타입 관계를 추적해야 하기 때문이다.
rustlet abstract_indx = self.emit_ref_ty(PartialTy::Struct(vec![code_field], false)); let concrete_indx = self.emit_ref_ty(PartialTy::Struct(fields, true)); self.supertypes.insert(concrete_indx, abstract_indx); concrete_indx
마지막으로 emit_body는 IR 방출로 넘어간다.
rustself.emit_ir(body, &mut locals, &mut inss); (inss, locals.local_tys)
많이 돌아왔지만, emit_ir은 익숙한 모양이다.
rustfn emit_ir( &mut self, body: IR, locals: &mut EmitLocals, inss: &mut Vec<Instruction> ) { match body { // 이제부터 난장판이다 } }
트리 타입에 대한 match는 이제 따뜻한 집 같다. 재귀 호출이 있다면 기쁨의 눈물을 흘릴지도 모른다.
emit_ir의 목표는 IR을 명령어 리스트로 바꾸는 것이다. 케이스별로 보자. 그 전에 중요한 불변식 하나가 있다.
명령어 중간에 무엇을 하든 상관없지만, 끝에는 하나만 남아야 한다.
rustIR::Var(var) => inss.push(Instruction::LocalGet(locals[&var.id])),
변수가 바인딩될 때 로컬을 만들었으니, 그 로컬에서 값을 꺼내면 된다. 로컬은 값 하나만 담으므로 불변식이 유지된다.
rustIR::Int(i) => inss.push(Instruction::I32Const(i)),
정수 리터럴은 i32.const로 스택에 올린다.
클로저는 여러 명령어가 필요하다. 먼저 인덱스를 정리한다.
rustIR::Closure(ty, item_id, vars) => { let func_index = self.functions[&item_id]; let struct_index = self .types .emit_closure_env_index(&ty, &vars.iter().map(|v| v.ty.clone()).collect::<Vec<_>>()); let ValType::Ref(RefType { heap_type, .. }) = self.types.emit_val_ty(&ty) else { panic!("ICE: Closure assigned to variable with non closure type"); }; todo!() }
item_id에 해당하는 함수 인덱스를 조회해 클로저 함수 참조를 만드는 데 쓴다. 다음으로 클로저 구체 타입 인덱스를 방출한다. 클로저는 추상 타입으로 전달되지만, 구조체를 만들 때는 구체 타입이 필요하다.
또한 구조체를 생성한 뒤 추상 타입으로 캐스팅해야 하므로, ty를 값 타입으로 방출해 heap_type(추상 타입의 힙 타입)을 꺼낸다. HeapType은 타입 인덱스를 감싼 것이며, 여기서는 클로저의 추상 구조체 타입 인덱스를 가리킨다.
이제 명령어를 방출한다.
rustinss.push(Instruction::RefFunc(func_index)); inss.extend( vars .into_iter() .map(|var| Instruction::LocalGet(locals[&var.id])), ); inss.push(Instruction::StructNew(struct_index)); inss.push(Instruction::RefCastNonNull(heap_type));
RefFunc는 함수 인덱스로 함수 참조를 만든다. LocalGet로 캡처 변수를 스택에 올린다. StructNew 전에 스택에는 (위에서 아래로) 함수 참조와 캡처 값들이 있다.
StructNew는 구체 타입을 사용해 구조체를 만들고 구조체 참조 하나를 스택에 남긴다. 마지막으로 그 구조체를 heap_type(추상 타입)으로 다운캐스트가 아니라 업캐스트에 해당하는 “기억 지우기” 캐스팅을 한다. 결과적으로 캡처 필드들은 잊고 함수 필드만 남는 셈이다.
Apply는 클로저를 풀어 자기 자신을 환경으로 넘기는 부분이다. 다시 인덱스를 모은다.
rustIR::Apply(fun, arg) => { let local_ty = fun.type_of(); let Type::Closure(arg_ty, ret_ty) = local_ty else { panic!("ICE: Expected closure type for function of apply"); }; let closure_indices = self.types.emit_closure_index(&arg_ty, &ret_ty); todo!() }
여기서 필요한 건 클로저 추상 타입 인덱스와 함수 타입 인덱스뿐이다. 구체 타입은 여기서 알 수 없다(정보가 없다). 이게 서로 다른 환경을 가진 클로저들을 같은 함수 타입처럼 취급할 수 있게 해준다.
이제 방출을 시작한다.
rustself.emit_ir(*fun, locals, inss); let fun_locals = locals.anon_local( closure_indices.struct_index.as_val_ty()); inss.push(Instruction::LocalTee(fun_local)); self.emit_ir(*arg, locals, inss);
재귀 호출이 등장했다. 감격스럽다. fun을 방출하면 스택에 클로저 참조 값 하나가 있어야 한다(불변식). 이를 여러 번 써야 하므로 익명 로컬을 만들고 LocalTee로 저장하면서 스택에도 남긴다.
인자를 방출하면 스택(위→아래)에 인자 값, 그 아래에 클로저 참조가 놓인다. 이 순서는 다음 단계에서 중요하다.
rustinss.extend([ Instruction::LocalGet(fun_local), Instruction::StructGet { struct_type_index: closure_indices.struct_index, field_index: 0, // code 필드는 항상 0 }, Instruction::CallRef(closure_indices.func_index), ]);
로컬에서 클로저 참조를 다시 가져온 뒤, 그 참조의 0번 필드(함수 참조)를 꺼낸다. CallRef로 들어가기 직전 스택 최상단은 호출할 함수가 된다.
CallRef는 스택 최상단에 호출할 함수가 있고, 그 아래에 함수 인자가 N개(N은 인자 개수)가 있어야 한다. 우리 클로저 함수는 항상 두 인자(환경 + 실제 인자)를 받으므로, CallRef는 (함수 참조 + 두 인자) 총 3개를 소비하고 결과를 스택에 남긴다.
IR의 Local(Wasm 로컬과 혼동 주의)은 아래처럼 방출한다.
rustself.emit_ir(*defn, locals, inss); let val_ty = self.types.emit_val_ty(&var.ty); let local = locals.local_for(var.id, val_ty); inss.push(Instruction::LocalSet(local)); self.emit_ir(*body, locals, inss);
정의식을 방출해 값 하나를 스택에 남기고(불변식), 새 로컬에 저장한다. 그 후 본문을 방출한다.
Access는 클로저 환경에서 캡처 값을 꺼낸다(필드 접근). 입력은 반드시 ClosureEnv 타입이므로 이를 언랩하고 인덱스를 만든다.
rustlet ty = strukt.type_of(); let Type::ClosureEnv(closure, env) = ty else { panic!("ICE: Expected closure env type for struct access"); }; let struct_type_index = self.types.emit_closure_env_index(&closure, &env);
그 타입 인덱스로 구조체를 접근한다.
rustself.emit_ir(*strukt, locals, inss); inss.push(Instruction::StructGet { struct_type_index, field_index: field.try_into().unwrap(), });
strukt를 방출하면 스택에 구조체 참조가 하나 남고, StructGet이 이를 소비해 해당 필드 값을 남긴다. usize→u32 변환을 하는데, 캡처 변수가 400만 개 이상이면 크래시 난다. 하지만 그 전에 다른 곳에서 터질 것이다.
이로써 IR에서 Wasm을 방출하는 데 필요한 모든 것을 갖췄다.
이제 이 패스의 최상위 함수 emit_wasm에서 모든 것을 접착한다.
rustfn emit_wasm( items: Vec<(ItemId, Item)>, ) -> Vec<u8> { todo!() }
입력은 아이템 리스트다. 현재 언어는 최상위 함수가 없어서 “아이템”이 하나뿐이지만, 클로저 변환이 클로저마다 아이템을 만들기 때문에 이 시점에는 여러 아이템이 있을 수 있다. 출력 Vec<u8>는 Wasm 모듈의 바이너리 인코딩이다.
모듈은 섹션들의 묶음이므로 섹션들을 준비한다.
rustlet mut types = EmitType::default(); let mut func = FunctionSection::new(); let mut export = ExportSection::new();
여기서 types는 섹션이 아니지만 곧 섹션이 된다. func와 export는 각 아이템에 함수 인덱스를 부여하는 데 쓰인다.
rustlet functions: HashMap<ItemId, u32> = items .iter() .map(|(item_id, item)| { let func_index = func.len(); let type_index = types.emit_item_ty(item); func.function(type_index); export.export(&format!("func{}", item_id.0), ExportKind::Func, func_index); (*item_id, func_index) }) .collect();
아이템마다 함수 섹션/내보내기 섹션을 채우면서 아이템 타입도 방출하고, 아이템 ID→함수 인덱스 맵을 만든다. 지금은 방출한 모든 아이템을 export해 공개한다. 캡슐화는 언어가 단일 표현식 이상을 지원할 때 고민하자.
이 functions로 EmitWasm을 만들고, 곧바로 코드 섹션을 채운다.
rustlet mut emitter = EmitWasm { types, functions, }; let mut code = CodeSection::default(); for (_, item) in items { code.function(&emitter.emit_item(item)); }
emit_item은 Function을 만들고 이를 코드 섹션에 추가한다. 순서가 중요하다. 코드 섹션의 함수 본문 순서는 함수 섹션의 시그니처 순서와 일치해야 한다. 아이템 순서를 그대로 사용해 동기화한다.
모든 섹션을 만든 뒤 모듈을 조립한다.
rustlet mut module = Module::default(); module .section(&emitter.types.into_type_section()) .section(&func) .section(&export) .section(&code); module.finish()
여기서도 순서가 중요하다. 섹션 순서를 잘못 두면 Wasm 모듈이 조용히 망가지며(검증 실패) 제대로 동작하지 않는다. 나중에 섹션을 추가하면 이 코드에서 올바른 위치에 삽입해야 한다.
이제 into_type_section이 EmitTypes를 타입 섹션으로 바꾸는 걸 보자.
rustimpl EmitTypes { fn into_type_section(self) -> TypeSection { todo!() } }
EmitTypes는 방출 동안 요청된 모든 타입을 추적했다. 이제 이를 이용해 모듈의 TypeSection을 만든다. 기본 구조는 types를 순회하는 것이다.
rustlet mut sect = TypeSection::new(); for (i, ty) in self.types.into_iter().enumerate() { todo!() } sect
각 PartialTy를 완전한 Wasm 타입으로 승격해 섹션에 쓴다.
rustlet (inner, is_final) = match ty { PartialTy::Func(func_type) => ( CompositeInnerType::Func(func_type), true, ), PartialTy::Struct(fields, is_final) => ( CompositeInnerType::Struct(StructType { fields: fields.into_boxed_slice(), }), is_final, ), };
CompositeInnerType은 wasm_encoder가 제공하는 인코딩 도우미 타입이다. 두 번째 값 is_final은 타입의 final 여부다. 함수는 서브타입이 될 일이 없으니 항상 final이다. 구조체는 서브타이핑이 가능하므로, 우리가 추적한 is_final을 그대로 전달한다.
이제 SubType을 방출한다.
rustlet indx: u32 = i.try_into().unwrap(); let supertype_idx = self.supertypes.get(&indx).copied(); sect.ty().subtype(&SubType { is_final, supertype_idx, composite_type: CompositeType { shared: false, inner, }, })
이상해 보일 수 있다. 함수 타입은 서로 서브타입이 될 일이 없는데 왜 SubType로 방출하나? supertype_idx가 없으면 None이고, Wasm 인코딩에서 슈퍼타입이 없고 final이면 “그냥 타입”과 구분되지 않는다. 실제 인코딩을 보면, 슈퍼타입이 있거나 final이 아니면 접두 바이트를 내보내는데, 함수 타입은 둘 다 아니므로 접두 없이 encode_function으로 내려간다. 항상 SubType로 내보내면 분기 조금을 줄일 수 있고 인코딩엔 영향이 없다.
이렇게 PartialTy를 Wasm 서브타입으로 바꾸어 타입 섹션을 만든다.
이로써 Wasm 방출 전체가 끝났다. module.finish()가 Wasm 바이트를 생성한다.
지금까지의 작업은 AST를 실행 가능한 Wasm으로 바꾸는 능력으로 결실을 맺는다. 이것이야말로 컴파일의 정수다. 축하 겸 간단한 AST에 대한 코드 방출을 해 보자.
rustlet add = Var(...); let f = Var(...); let x = Var(...); Ast::fun(add, Ast::app( Ast::fun(f, Ast::app( Ast::app( Ast::Var(add), Ast::app(Ast::Var(f), Ast::Int(400)) ), Ast::app(Ast::Var(f), Ast::Int(1234)) )), Ast::app(Ast::Var(add), Ast::Int(1))) )
읽기 쉽도록 NodeId는 생략했다. 머릿속으로 채워 넣어도 된다. 이 AST는 미지의 add 함수를 받아 1로 부분 적용해 f를 만든 뒤, f 400과 f 1234를 더한다. 커링이 있는 하스켈로 더 간단히 쓰면:
haskell\add -> let f = add 1 in add (f 400) (f 1234)
우리 언어에는 덧셈 같은 원시 숫자 연산이 없지만, add라는 이름의 함수를 받아서 “가짜로” 할 수 있다. Wasm을 실행할 때 그런 함수를 찾아 하드코딩 구현을 제공하면 된다. 레포의 테스트는 실제로 이를 이용해 실행 결과를 확인한다.
이 AST를 지금까지의 패스들에 통과시키면 Wasm이 나온다. 바이너리는 읽기 어려우니 텍스트 형식으로 보여준다.
wasm(module (type (func (param (ref struct) i32) (result i32))) (type (sub (struct (field (ref 0))))) (type (func (param (ref struct) i32) (result (ref 1)))) (type (sub (struct (field (ref 2))))) (type (func (param (ref 3)) (result i32))) (export "func0" (func 0)) (func (type 4) (param (ref 3)) (result i32) (local (ref 3) (ref 1) (ref 3) (ref 1) (ref 1) (ref 1)) (local.set 2 (call_ref 2 (local.tee 1 (local.get 0)) (i32.const 1) (struct.get 3 0 (local.get 1)))) (return (call_ref 0 (local.tee 5 (call_ref 2 (local.tee 3 (local.get 0)) (call_ref 0 (local.tee 4 (local.get 2)) (i32.const 400) (struct.get 1 0 (local.get 4))) (struct.get 3 0 (local.get 3)))) (call_ref 0 (local.tee 6 (local.get 2)) (i32.const 1234) (struct.get 1 0 (local.get 6))) (struct.get 1 0 (local.get 5))))))
(400 + 1) + (1234 + 1)을 계산하는 것치고 코드가 많아 보이는데, 맞다. 아직 최적화를 하지 않았기 때문이다. Wasm의 매력 중 하나는, 우리가 직접 만들었어야 할 도구들이 이미 많이 있다는 점이다. Wasm을 최적화하는 CLI wasm-opt에 돌리면 더 나은 버전이 나온다.
wasm(module (type $0 (func (param (ref struct) i32) (result i32))) (type $1 (sub (struct (field (ref $0))))) (type $2 (func (param (ref struct) i32) (result (ref $1)))) (type $3 (sub (struct (field (ref $2))))) (type $4 (func (param (ref $3)) (result i32))) (export "func0" (func $0)) (func $0 (type $4) (param $0 (ref $3)) (result i32) (local $1 (ref $1)) (local $2 (ref $2)) (local $3 (ref $0)) (local $4 (ref $1)) (call_ref $0 (local.tee $4 (call_ref $2 (local.get $0) (call_ref $0 (local.tee $1 (call_ref $2 (local.get $0) (i32.const 1) (local.tee $2 (struct.get $3 0 (local.get $0))))) (i32.const 400) (local.tee $3 (struct.get $1 0 (local.get $1)))) (local.get $2) )) (call_ref $0 (local.get $1) (i32.const 1234) (local.get $3)) (struct.get $1 0 (local.get $4)))))
음… 로컬 수는 줄었으니 낫긴 한데, 크게 낫진 않다. 우리가 기대하는 형태:
wasm(i32.add (i32.add (i32.const 400) (i32.const 1)) (i32.add (i32.const 1234) (i32.const 1)))
와는 거리가 멀다. 게다가 전부 상수라면 진짜 최적 출력은:
wasm(i32.const 1636)
이어야 한다. 모듈 부분을 제외하더라도, 우리의 코드는 둘 다보다 훨씬 많은 명령어를 쓴다. 이는 두 가지 요인 때문이다.
add 함수를 블랙박스로 인자로 받는다.add가 파라미터로 전달되므로 소스를 이용한 단순화가 불가능하다. 게다가 add는 “두 정수를 받아 정수를 반환”하는 단순 함수가 아니라, 정수 하나를 받아 새 클로저를 반환하고, 그 클로저가 또 정수를 받아 최종적으로 정수를 반환하는 형태다.
결국 우리의 Wasm 출력 대부분은 정수 덧셈이 아니라 클로저를 구성하고 적용하는 데 소비된다. 아직 최적화 정원에 따기 쉬운 열매가 많다. 그럼에도 이 코드는 동작한다.
이 코드를 실행하면 함수가 1636을 반환하는 것을 볼 수 있다. 실제로 레포의 test_example가 그걸 한다. 함수형 언어에서 최적화된 코드를 만드는 방법을 사람들이 알아내는 데는 수십 년이 걸렸다. 블로그 글 몇 년으로 그걸 따라잡으려는 건 미친 짓이다. 하지만 그럴 필요도 없다. 우리의 코드 생성은 최적은 아니어도 정확하다. 시작하기엔 그것으로 충분하다. 앞으로 글에서 개선해 나가면 된다.
이제 해냈다. 컴파일러를 만들었다. 어제만 해도 컴파일의 단계들을 바라보고 있었던 것 같은데, 이제 전부 해버렸다.
잠깐. 실행에 들떠서 큰 실수를 한 것 같다. 컴파일러 프론트엔드에 파서 모양의 거대한 구멍이 남아 있다. 사용자가 손으로 만든 AST를 먹여야 한다면 과연 컴파일러 장인이라 할 수 있을까? 아니다. 컴파일에서 가장 큰 타르피트(tarpit)인 파서를 건너야 한다.