컴파일러는 어렵다? 1988년 한 튜토리얼이 깨뜨린 신화

TL;DR 컴파일러 작성의 난해함을 깨기 위해 1988년 Jack Crenshaw의 단일 패스 튜토리얼과 2005년 Nanopass 논문이 제시됐다. Crenshaw는 500줄 미만 Pascal 코드로 작동하는 컴파일러를 보여줬고, Nanopass는 컴파일러를 수십수백 개의 극도로 작은 패스로 보는 관점을 제안했다. LLVM 17은 1,100개 이상의 패스를, Chez Scheme은 5060개 패스로 이 철학을 실전에서 증명했다.

1986년 『Dragon Book』 초판이 나오면서 컴파일러 수업은 정규표현식에서 DFA, LR 파싱 테이블, 속성 문법까지 방대한 이론으로 가득 찼다. 학생들은 책을 다 읽고도 실제로 작동하는 컴파일러 하나를 완성하지 못하는 경우가 많았다. 1988년 Jack Crenshaw는 이에 반발해 “Let’s Build a Compiler!“를 연재하기 시작했다. 그의 시리즈는 Pascal로 단일 패스 컴파일러를 500줄도 안 되는 코드로 구현하며, 컴파일러가 결코 어렵지 않다는 사실을 증명했다. 이후 2005년 Nanopass 논문은 한 걸음 더 나아가 “컴파일러란 내부 표현을 수없이 작은 단계로 변환하는 과정일 뿐"이라는 사고방식을 제시했다.

Crenshaw의 500줄 vs Nanopass의 23개 패스

Crenshaw의 튜토리얼은 AST조차 없이 재귀 하강 파서가 코드 생성을 동시에 수행하는 극단적으로 단순한 구조였다. 파스칼로 작성된 원본은 물론 C 버전과 Forth 버전까지 나왔고, 지금도 GitHub 저장소 400개 이상에서 참조된다. 이에 앞서 Dragon Book 중심 교육이 2016년 기준 CS 프로그램의 38%를 차지하고 있었다. Nanopass 논문은 이 단순함을 유지하면서도 유연성을 더했다. 2005년 논문에서 제시된 초기 컴파일러는 Scheme의 비-trivial 부분집합을 x86 어셈블리로 변환하는 데 정확히 23개의 패스를 사용했다. 각 패스는 입력 언어와 출력 언어를 명확히 정의하고, 프레임워크가 트리 순회 코드를 7090% 자동 생성해준다. Kent Dybvig 팀은 20152016년 Chez Scheme 전체 컴파일러를 Nanopass로 다시 썼는데, 최적화 레벨에 따라 50~60개 패스가 된다. 이렇듯 접근법은 교육에서 실전으로 빠르게 확대됐다.

한 페이지 넘는 패스는 잘못된 패스다

전통적인 컴파일러는 5~15개의 큰 패스와 복잡한 IR(Three-Address Code, SSA)을 사용한다. 반면 Nanopass는 의도적으로 패스를 쪼개 “한 패스가 한 페이지를 넘으면 너무 많은 일을 하는 것"이라는 원칙을 세웠다. 결과적으로 보일러플레이트 코드가 극적으로 줄고, 각 패스 뒤에 IR을 출력해 디버깅이 쉬워진다. 다만 트리 순회가 많아지면 컴파일 시간이 늘어날 수 있는데, LLVM은 이를 " pragmatic nanopass” 방식으로 해결했다. LLVM 17 기준으로 llvm/lib/Transforms와 Analysis 디렉토리에는 1,100개가 넘는 패스가 존재하며, 새로운 PassManager는 합법적인 경우 패스를 병렬로 실행하기도 한다. MLIR은 이 철학을 더욱 발전시켜 여러 dialect(중간 언어)를 명확히 정의하고 조합한다. Crenshaw 방식은 빠르고 코드 크기가 작지만 최적화를 추가하기 어렵다는 한계를, Nanopass는 IR 설계 자체가 어렵다는 새로운 과제를 남겼다.

교육에서 LLVM, Rust, Swift까지 번진 작은 변환 철학

Indiana University와 University of Utah를 비롯한 여러 대학이 2023~2024년 컴파일러 수업에 Nanopass 프레임워크를 도입했다. 산업계에서도 Rust의 MIR, Swift의 SIL, LLVM의 MLIR이 모두 “잘 정의된 여러 IR과 작은 변환"이라는 동일한 사상을 공유한다. Chez Scheme 팀은 Nanopass로 재작성한 후 유지보수성과 확장성이 크게 개선됐다고 보고했다. 다만 세계 최고 수준의 최적화(예: SPEC CPU 벤치마크)를 목표로 할 때는 전역 레지스터 할당이나 다면체 최적화 같은 복잡한 교차 분석이 필요해 “완벽한 한 페이지 패스” 모델만으로는 부족하다는 지적도 나온다. 학생들이 가장 어려워하는 부분은 오히려 패스 개수를 늘리는 것이 아니라, 적절한 IR을 설계하고 불변 조건을 유지하는 일이다. 결국 Nanopass는 불필요한 복잡함을 제거해주지만, 언어 설계와 호출 규약, 최적화에 대한 본질적인 이해는 여전히 요구한다.

오늘날 컴파일러를 만들거나 수정해야 하는 상황에서 당신은 패스를 몇 개로 쪼갤 수 있을까. Crenshaw의 단순함과 Nanopass의 세밀함 사이에서 각자의 프로젝트에 맞는 균형을 찾는 것이 진짜 과제다. 그 균형을 찾는 과정 자체가 컴파일러를 어렵게 만드는 마지막 벽인지도 모른다.

참고문헌

[1] Want to Write a Compiler? Just Read These Two Papers - https://prog21.dadgum.com/30.html

[2] A Nanopass Framework for Compiler Education (2005) - https://www.cs.indiana.edu/~dyb/pubs/nanopass.pdf

[3] Let’s Build a Compiler! by Jack Crenshaw - http://compilers.iecc.com/crenshaw/

[4] Chez Scheme Source Code (Nanopass implementation) - https://github.com/cisco/ChezScheme

[5] LLVM 17.0.1 Release Notes - https://releases.llvm.org/17.0.1/docs/ReleaseNotes.html