Mugo, 스스로를 컴파일할 수 있는 Go 부분 집합용 토이 컴파일러
원문은 Ben Hoyt님이 에 게재했습니다. 이 블로그 구독하기
요약: 이 글에서는 Go 프로그래밍 언어의 아주 작은 부분 집합을 위한 단일 패스 컴파일러인 Mugo를 소개한다. (매우 단순한) x86-64 어셈블리를 출력하며, Mugo 컴파일러 자체를 구현할 수 있을 만큼의 언어 기능만을 지원한다:
int와string타입, 슬라이스, 함수, 지역 변수, 전역 변수, 그리고 기본적인 표현식과 문장.
코딩을 시작한 이래로 컴파일러에 매료되어 왔다. 내가 만든 첫 프로그래밍 프로젝트 중 하나는 8086 DOS용 셀프 호스팅 Forth 컴파일러인 “Third”였다. Forth는 컴파일하기가 믿을 수 없을 만큼 쉽다: 표현식이나 문장이 없고, 공백으로 구분된 각 토큰이 직접 call 명령어로 컴파일된다 — 종종 direct threading 같은 기법을 통해서다.
C나 Go 같은 일반적인 언어는 표현식과 문장을 포함한 더 복잡한 문법을 가지고 있어 제대로 된 파서와 코드 생성기가 필요하다. 이런 언어들의 컴파일러는 보통 복잡하고 강력하지만, 앞으로 살펴보겠지만 기본적인 타입과 최적화되지 않은 출력에만 충실한다면 충분히 간단하게 만들 수도 있다.
Mugo는 Fabrice Bellard가 만든 Obfuscated Tiny C Compiler의 정신을 어느 정도 따르고 있다. 물론 내 것은 훨씬 더 평범하며, 당장 IOCCC에서 수상할 일은 없을 것이다. Bellard의 컴파일러는 네이티브 i386 Linux 실행 파일로 자기 자신을 컴파일할 수 있을 만큼의 C만을 구현한다.
나는 Go로도 난독화만 빼고 비슷한 것을 해보고 싶었다. 이 아이디어는 샤워 중에 떠오른 생각에서 시작했다: “Go에서 자기 자신을 컴파일할 수 있는 가장 작은 부분 집합은 뭘까?” Fabrice의 C 컴파일러는 난독화된 C 2048바이트로 구현되어 있는 반면, 내 것은 포맷팅된 Go 1600줄이다.
긴 주말 동안 해본 재미있는 연습이었지만, 어디까지나 토이 프로젝트다 — Go의 훌륭한 기능들을 모두 빼놓았다: 사용자 정의 타입, 인터페이스, 고루틴, 채널, 맵, 가비지 컬렉션, 심지어 범위 검사조차 없다! Mugo의 목표는 교육적인 것이었다: 나 자신을 위해서, 그리고 바라건대 독자를 위해서도. 이런 연습을 하다 보면 우리가 쓰는 도구가 어떻게 동작하는지 그 베일을 벗길 수 있다.
어느 부분 집합을 선택할 것인가?
Mugo는 Go의 부분 집합이므로, 소스 코드를 Go로도, Mugo로도 컴파일할 수 있다. 내 생각에 이 점이 훨씬 더 흥미롭게 만든다. 테스트도 더 쉬워졌다: Go로 빌드된 버전의 어셈블리 출력이 Mugo로 빌드된 버전의 출력과 동일하면 제대로 동작한다는 것을 알 수 있었다 — diff mugo2.asm mugo3.asm이 아무 출력도 보이지 않았을 때는 정말 근사한 순간이었다!
시작하기 전에 어떤 기능들을 포함할지 곰곰이 고민했다. 컴파일러 상태를 저장하려면 어떤 종류의 컨테이너 타입이 필요할 것 같았다: 예를 들어 변수 이름과 타입, 함수 시그니처와 반환 타입 같은 것들이다. 그런데 어떤 컨테이너를 써야 할까?
Go에는 포인터가 있지만, 포인터 연산이 불가능하기 때문에 C의 포인터만큼 강력하지는 않고 더 안전하다. Bellard의 컴파일러는 C 포인터를 많이 활용하지만, Go에서는 그 방식을 쓸 수 없었다.
구조체나 맵은 어떨까? 그것들은 구현하기가 더 복잡할 뿐 아니라, 무언가의 목록을 저장한다는 가장 흔한 문제를 제대로 해결해 주지도 않는다. 그래서 나는 그런 것들 없이도 충분하다고 판단하고, 슬라이스만 있으면 된다고 결정했다.
Mugo가 지원하는 기능은 다음과 같다:
int타입, 10진수 정수 리터럴, 문자 상수, 그리고int에 대해 동작하는 대부분의 표현식:+,-,*,/,%,==,!=,<,<=,>,>=연산자를 지원하며, 연산자 우선순위는 Go와 동일하게 처리한다. 컴파일러는bool이라는 타입 이름도 인식하지만int와 동일하게 취급한다(&&,||,!는 이런 유사 bool 값에 대해 동작한다).string타입.\이스케이프가 포함된 문자열 상수,==나!=를 이용한 문자열 동등성 검사,+를 이용한 문자열 연결, 그리고len()을 지원한다.- 슬라이스. 단
[]int와[]string만 지원한다. 슬라이스 리터럴과make()는 지원하지 않으므로, 슬라이스를 만들려면 빈 슬라이스를 생성한 뒤append로 추가해야 한다. 슬라이스 원소에 대한 조회와 할당,slice[:n]표현식, 그리고len()을 지원한다. - 타입 검사는 존재하지만 완전하지 않다. 말이 된다고 생각되는 곳이나 디버깅에 도움이 되는 곳에서는 타입을 검사하지만, 결코 완전하다고 할 수는 없다.
- 문장:
if와else,for condition { ... },return, 그리고 Go의:=짧은 변수 선언을 지원한다. - 변수와 상수. 다만
var와const는 최상위 레벨에서만 지원되며, 지역 변수에는:=를 사용해야 한다(어차피 Go에서 더 흔한 방식이다). 타입이 지정된 정수 상수만 지원된다. - 최상위 함수(재귀 포함). 다만 함수 값과 익명 함수는 지원하지 않는다. 함수는 하나의 반환 값만 가질 수 있으며, 가변 인자 함수는 포함되지 않는다.
- 입출력. 미리 정의된 세 개의 함수를 사용한다:
getc는 stdin에서 문자 하나를 읽고,print와log는 각각 stdout과 stderr에 문자열을 쓴다. - Go 문법. 단 여기서 필요한 만큼으로 축소되었다. 많은 구문이 지원되지 않는다. 예를 들어
++와--,for range루프 등이다.//를 이용한 한 줄 주석은 지원된다.
대략 이 정도가 전부다! 위 목록에 없다면 아마도 지원하지 않는다고 보면 된다. 말했듯이, 정말 작은 부분 집합이다.
이것을 만들면서 간결하고 잘 정리된 Go 언어 명세를 여러 번 참고했지만, 거의 확실히 뭔가 틀린 부분이 있을 것이다. 다만 구현된 기능들은 내 “diff 테스트”가 보여주듯 Go처럼 동작하는 것 같다.
코드 생성
Mugo는 파싱을 진행하면서 바로 x86-64 어셈블리를 출력하는 단일 패스 컴파일러다. (Linux용으로 작성되었지만 macOS나 Windows에서 동작하도록 만드는 것도 어렵지 않을 것이다.) 메모리에 추상 구문 트리가 없다 — 어차피 슬라이스만으로 트리를 만드는 것도 까다로울 것이다.
또한 매우 단순하다(naive). 최적화가 전혀 없다 — 나는 기본적으로 강력한 레지스터 기반 CPU를 멍청한 스택 머신으로 만들어 버리고, 중간 값들을 스택에 push하고 pop한다. 실제 컴파일러 복잡도의 절반 정도는 코드 생성에, 나머지 절반은 타입 검사에 있다고 할 수 있는데, Mugo에서는 두 가지 모두 엄청나게 단순화되어 있다.
꼼수를 써야 했던 부분 중 하나는 지역 변수 선언(Go의 := 문법)이었다. 단일 패스 방식이라 함수 파싱이 끝날 때까지 지역 변수가 몇 개인지, 타입이 무엇인지 알 수 없다. 그래서 함수 프롤로그에서는 관례적인 rbp 프레임 포인터 처리 외에도, 스택 포인터에서 64바이트를 빼서 최대 8개 셀 분량의 지역 변수 공간을 확보한다(Mugo에서 가장 많이 쓰는 함수는 7개 셀을 사용한다).
업데이트: Hacker News의 “a1369209993” 님이 지적해 주었다시피 크기를 알게 된 함수 끝에서 정의된 어셈블러 상수를 참조할 수도 있었다. 이미 if와 else의 순방향 점프에서는 어셈블러가 그 일을 처리하도록 하고 있다. 고맙다!
정수 add 함수에 대한 전체 출력은 다음과 같다:
; func add(x int, y int) int {
; return x + y
; }
; function prologue
add:
push rbp ; rbp is the frame pointer
mov rbp, rsp
sub rsp, 64 ; make space for any more locals
; (not used by this function)
; fetch and push local variable x, then y
push qword [rbp+24]
push qword [rbp+16]
; the + operation
pop rbx
pop rax
add rax, rbx
push rax
; pop result back into rax for "return"
pop rax
; function epilogue (restore stack and frame pointer)
mov rsp, rbp
pop rbp
ret 16 ; return, and free space due to
; caller pushing x and ygcc의 최적화되지 않은 출력과 비교하면, 그렇게 나쁘지 않다:
push rbp
mov rbp, rsp
mov qword [rbp-8], rdi
mov qword [rbp-16], rsi
mov rdx, qword [rbp-8]
mov rax, qword [rbp-16]
add rax, rdx
pop rbp
ret하지만 gcc의 최적화된 출력은 레지스터 기반의 단일 명령어를 생성한다:
lea rax, [rdi+rsi]
ret호출자 측에서 add 호출을 생성하기 위해 Mugo는 다음과 같은 코드를 만든다:
; add(1, 2)
push qword 1 ; push first arg
push qword 2 ; push second arg
call add ; call the function
push rax ; push return value back to stack보다시피 Mugo는 ABI와는 전혀 다른, 매우 비효율적인 자체 ABI를 사용한다 — 표준 x86-64 ABI는 처음 6개의 “셀”(64비트 값)을 레지스터에 넣는다.
단순함을 위해 Mugo의 ABI는 인자를 스택에 push한다. 순서대로 push되므로 메모리상에서는 스택에 역순으로 쌓이게 된다. 다만 반환 값에는 레지스터를 사용한다: rax, 그리고 셀이 더 있으면 rbx와 rcx를 사용한다. Go에서와 마찬가지로 int는 한 셀, string은 두 셀(주소와 길이), 슬라이스는 세 셀(주소, 길이, 용량)이다.
문자열 연결과 슬라이스 append를 위한 메모리 할당에는 Mugo는 아주 단순한 “bump 할당기”를 사용한다. 즉, 고정된 1MB 메모리 청크 안에서 포인터를 앞으로 밀어 나가다가 다 쓰면 메모리 부족 메시지를 내고 종료한다. 메모리를 해제하지 않으며, 가비지 컬렉터도 없다. 짧게 실행되는 프로그램에는 안성맞춤이다!
어셈블리를 생성하기 위해 Mugo는 단순히 print를 호출해 표준 출력에 쓴다:
func genFuncStart(name string) {
print("\n")
print(name + ":\n")
print("push rbp\n")
print("mov rbp, rsp\n")
print("sub rsp, " + itoa(localSpace) + "\n") // space for locals
}Mugo를 실행한 뒤에는 NASM으로 출력을 어셈블하고 ld 링커로 실행 파일을 만든다. 컴파일러의 세 가지 버전을 빌드하는 Makefile 예시는 다음과 같다:
# Build the compiler with Go
mugo:
go build -o build/mugo
# Build the compiler with the Go-built Mugo
mugo2:
build/mugo <mugo.go >build/mugo2.asm
nasm -felf64 -o build/mugo2.o build/mugo2.asm
ld -o build/mugo2 build/mugo2.o
# Build the compiler with the Mugo-built Mugo
mugo3:
build/mugo2 <mugo.go >build/mugo3.asm
nasm -felf64 -o build/mugo3.o build/mugo3.asm
ld -o build/mugo3 build/mugo3.o
diff build/mugo2.asm build/mugo3.asm # ensure output matches!컴파일러 자체를 실행하는 간단한 테스트로부터 커버리지 리포트를 만드는 make 타깃도 있다. 이 테스트는 단순히 Mugo의 main()을 호출하므로, 커버리지 프로파일을 켠 채 테스트 바이너리를 실행하고 mugo.go를 프로세스의 표준 입력으로 보낸다. “테스트”는 컴파일러의 전체 소스 코드를 컴파일하고 어떤 커버리지가 나오는지 기록하는 것이다:
coverage:
go test -c -o build/mugo_test -cover
build/mugo_test -test.coverprofile build/coverage.out \
<mugo.go >/dev/null
go tool cover -html build/coverage.out -o build/coverage.html처음에는 컴파일러가 사용하지 않는 기능 몇 가지를 포함했었는데, 테스트되지 않아 커버리지 리포트에 빨간색으로 표시되었다. 몇 가지를 제외하고는 — ! not 연산자나 문자열 슬라이스 할당처럼 일관성을 위해 있는 편이 자연스러워 보이는 것들이다 — 사용하지 않는 기능들은 제거했다. 이제 오류 처리를 제외하고는 모든 기능에 대해 완전한 커버리지를 확보했다.
한두 번은 디버깅을 위해 gdb를 꺼내야 했다. 내 x86 어셈블리 실력은 확실히 녹슬어 있고, 제대로 된 64비트 어셈블리를 작성해 본 적도 없다. 단일 패스라는 제약 안에서도 출력을 개선할 방법은 분명 많을 것이다 — 하지만 그런 개선은 독자를 위한 연습 문제로 남겨 두었다. :-)
렉서와 파서
Go는 토큰화하고 파싱하기 쉬운 깔끔하고 단순한 문법을 가지고 있다. Mugo는 렉서에서 한 문자 선행(lookahead)을 사용하고, 전형적인 재귀 하강 파서를 사용한다.
렉서는 기본적으로 다음 문자에 대한 거대한 if문 집합이며, 다음 문자는 전역 정수 c에 저장된다. 다음은 그 모습의 일부다:
func next() {
// Skip whitespace and comments, and look for / operator
for c == '/' || c == ' ' || c == '\t' || c == '\r' || c == '\n' {
if c == '/' {
nextChar()
if c != '/' {
token = tDivide
return
}
nextChar()
// Comment, skip till end of line
for c >= 0 && c != '\n' {
nextChar()
}
} else if c == '\n' {
nextChar()
// Semicolon insertion: golang.org/ref/spec#Semicolons
if token == tIdent || token == tIntLit || token == tStrLit ||
token == tReturn || token == tRParen ||
token == tRBracket || token == tRBrace {
token = tSemicolon
return
}
} else {
nextChar()
}
}
if c < 0 {
// End of file
token = tEOF
return
}
// Integer literal
if isDigit(c) {
tokenInt = c - '0'
nextChar()
for isDigit(c) {
tokenInt = tokenInt*10 + c - '0'
nextChar()
}
token = tIntLit
return
}
// ... handle other tokens (snipped) ...
}파서에서는 Go 명세의 문법에 나오는 생성 규칙 이름을 그대로 사용하려 했다. 예를 들어 Expression, VarSpec, Operand 같은 이름이다. 물론 언어의 부분 집합을 다루고 있으므로 많은 규칙이 Go 명세보다 축소된 형태다. 다음은 파싱 함수의 예시 몇 가지다 — 코드 생성 함수 호출이 어떻게 섞여 있는지에 주목해 보자:
func Literal() int {
if token == tIntLit {
genIntLit(tokenInt)
next()
return typeInt
} else if token == tStrLit {
genStrLit(tokenStr)
next()
return typeString
} else {
error("expected integer or string literal")
return 0
}
}
func SimpleStmt() {
// Funky parsing here to handle assignments
identName := tokenStr
expect(tIdent, "assignment or call statement")
if token == tAssign {
next()
lhsType := varType(identName)
rhsType := Expression()
if lhsType != rhsType {
error("can't assign " + typeName(rhsType) + " to " +
typeName(lhsType))
}
genAssign(identName)
} else if token == tDeclAssign {
next()
typ := Expression()
defineLocal(typ, identName)
genAssign(identName)
} else if token == tLParen {
genIdentifier(identName)
typ := Arguments()
genDiscard(typ) // discard return value
} else if token == tLBracket {
next()
indexExpr()
expect(tRBracket, "]")
expect(tAssign, "=")
Expression()
genSliceAssign(identName)
} else {
error("expected assignment or call not " + tokenName(token))
}
}
func Statement() {
if token == tIf {
IfStmt()
} else if token == tFor {
ForStmt()
} else if token == tReturn {
ReturnStmt()
} else {
SimpleStmt()
}
}위 “단순 문장(simple statement)”은 약간 지저분한 부분 중 하나다 — 구문 트리를 생성하는 파서라면 아마 Expression을 호출해 좌변을 파싱한 뒤, =나 :=가 있는지 확인하고 우변을 파싱할 것이다. 하지만 우리는 Expression을 호출할 수 없다. 그렇게 하면 그 표현식을 가져오는 코드를 컴파일해 버리기 때문이다. 그래서 식별자를 파싱한 뒤, 다음에 오는 것이 할당인지, 함수 호출인지, 아니면 슬라이스 표현식인지 판별해야 한다. 위 코드가 모든 엣지 케이스를 올바르게 처리한다고 확신할 수는 없지만, 충분히 쓸 만하다.
연산자 우선순위는 재귀 하강 방식으로 처리되며, 다음의 &&와 || 연산자처럼 동작한다(orExpr와 andExpr라는 이름은 Go 명세에는 나오지 않는다):
func andExpr() int {
typ := comparisonExpr()
for token == tAnd {
op := token
next()
typRight := comparisonExpr()
typ = genBinary(op, typ, typRight)
}
return typ
}
func orExpr() int {
typ := andExpr()
for token == tOr {
op := token
next()
typRight := andExpr()
typ = genBinary(op, typ, typRight)
}
return typ
}
func Expression() int {
return orExpr()
}재귀 하강 파서에는 두 개의 재귀적 전방 참조가 있다: Expression(표현식 파싱 내부의 여러 함수가 Expression을 호출해야 한다)과 Block(블록 요소들이 결국 Block 안으로 중첩된다). Go는 전방 참조가 필요하지도 않고 허용하지도 않으므로, Mugo는 시작할 때 이 두 함수를 올바른 시그니처로 미리 정의해 둔다.
컴파일러는 전역 슬라이스 집합에 변수 이름과 타입 정보를 추적해 둔다:
var (
globals []string // global names and types
globalTypes []int
locals []string // local names and types
localTypes []int
funcs []string // function names
funcSigIndexes []int // indexes into funcSigs
funcSigs []int // each func: retType N arg1Type ... argNType
)앞의 네 개는 설명이 거의 필요 없지만, funcSigs 슬라이스는 좀, 뭐랄까, 독특하다. 사실 이건 구조체들의 슬라이스다. 실제 Go 코드라면 아마 funcSig 구조체를 정의하고 이 “func” 슬라이스 세 개를 함수 이름에서 구조체로의 맵 하나로 합쳤을 것이다:
var funcSigs map[string]funcSig
type funcSig struct {
retType int
argTypes []int
}하지만 Mugo는 구조체나 맵을 지원하지 않으므로, 이 필드들을 int의 평면 슬라이스에 쑤셔 넣어야 했고, funcSigIndexes[i]가 funcSigs 슬라이스 안에서 해당 의사(pseudo) 구조체의 시작을 가리키도록 했다(인덱스 i에 있는 함수에 대해).
성능
최적화를 전혀 하지 않으므로 Mugo가 Go보다 훨씬 느릴 것은 당연하고, 그래서 광범위한 성능 테스트를 하지는 않을 것이다. 하지만 재미 삼아 정수 연산이 들어간 기본 루프의 성능을 테스트하는 작은 프로그램을 작성했다 — 1부터 10억까지의 숫자를 합산하는 프로그램이다:
var (
result int
)
func main() {
sum := 0
i := 1
for i <= 1000000000 {
sum = sum + i
i = i + 1
}
result = sum // so Go doesn't optimize it out
}내 머신에서 이 코드의 Go 버전은 0.34초 만에 실행된다. Mugo 버전은 5.7초가 걸린다 — 약 17배 더 오래 걸리는 셈이다. 역대 최악의 어셈블리 코드 중 하나 치고는 나쁘지 않은 것 같다. 참고로 동일한 루프의 Python 버전은 1분 38초가 걸린다 … 동적 타입 바이트코드 인터프리터는 무거운 정수 연산에 적합한 선택이 아니다.
흥미롭게도 sum 자체를 지역 변수가 아니라 전역 변수로 만들면 Mugo 버전은 그대로이지만 Go 버전은 0.34초 대신 1.7초가 걸린다. Mugo가 훨씬 느린 큰 이유 중 하나는 모든 것을 스택상의 메모리에서 처리하기 때문이라고 짐작한다 — 스택이 CPU 캐시에 있더라도 레지스터가 언제나 더 빠르다.
성능의 또 다른 측면은 코드 크기다: Mugo가 빌드한 실행 파일은 Go로 빌드한 것보다 훨씬 작다. Go로 빌드한 Mugo 바이너리는 1.6MB다. Mugo로 빌드한 Mugo는 불과 56KB — 약 1/29 크기다! 사실 공정한 비교는 아니다 — Mugo에는 고루틴 스케줄러나 가비지 컬렉터, 런타임 타입 정보가 포함되어 있지 않다(이 Go FAQ 질문을 참고하라). 하지만 이는 흥미로운 질문을 던진다: Go로 작성된 간단한 CLI 도구의 경우, 아주 단순한 스케줄러와 GC로 바이너리 크기를 줄일 수 있지 않을까?
관련 프로젝트
앞서 언급했듯이 나는 오랫동안 인터프리터와 컴파일러에 관심을 가져 왔다. 이 글이 마음에 들었다면, 나의 관련 프로젝트 몇 가지를 소개한다:
- Third: 수년 전에 내가 작성한 8086 DOS용 Forth 컴파일러. Forth 컴파일러를 만드는 방법에 대한 튜토리얼은 Richard Jones의
jonesforth.S도 참고해 보라. - pyast64:
ast모듈을 이용해 Python 구문을 x86-64 어셈블리로 변환한다. - LoxLox: Crafting Interpreters의 Lox 프로그래밍 언어를 Lox 자체로 작성한 인터프리터(뭔가 패턴이 보이기 시작하는가?).
- GoAWK: Go로 작성된 POSIX 호환 AWK 인터프리터.
- ZZT in Go: Adrian Siekierka의 Reconstruction of ZZT를 Go로 포팅하기 위해 내가 작성한 Pascal-to-Go 변환기를 설명한다.
이 글이 즐거웠기를 바란다 — 나는 Mugo를 만들면서 확실히 재미있었다. 언제든 피드백을 보내 달라! Hacker News에서의 토론도 읽어 볼 수 있다.
댓글
로그인하고 댓글 남기기