k-young-passionate
commented
2 weeks ago 예전에 프로그래밍 언어론을 들을 때 배웠던 컴파일러 부분을 다시 들은 느낌입니다 ㅎㅎ
(해당 강의가 너무 어려워서 컴파일러 강의는 수강하지 않았습니다)
내용이 조금 어렵기는 하지만 대략적으로 rust 가 어떻게 컴파일 되며, 현재 가지고 있는 개선점들에 대해서 알게 되었습니다! 잘 읽었습니다 ㅎㅎ
날씨가 너무 좋아졌죠! 그런데 글 쓰기는 또 늦어버렸네요. GUI 알아보기 2는 준비가 좀 걸릴 것 같아서 다른 주제를 가져와 봤습니다. 뭘 할 지 고민해봤는데, 제가 주로 쓰는 언어인 rust의 컴파일 과정을 가져와 봤습니다.
Rust는 비교적 최근에 나온 언어로, C/C++과 비슷한 수준의 속도를 유지하면서 안정성, 동시성을 향상 시키는 것을 목표로 설계 됐다. 메모리 실수가 일어날만한 부분은 컴파일러가 미리 유효하지 않음을 알려서 (오류를 뱉어서) 잘못 코드를 구현했을 시 컴파일 자체가 불가능하다.
이렇듯 안정성을 보장하기 위해 Rust 컴파일러 두 가지 측면에서 다른 컴파일러와 다르게 동작한다.
위 내용만 보면 무슨 말인지 전혀 모르겠다. 이에 대해 차례로 서술할 것이다.
실행 파일 생성 과정
Invocation: 컴파일러 호출
컴파일은 사용자가 텍스트로 Rust 소스 프로그램을 작성하고 rustc 컴파일러를 호출할 때 시작된다. 컴파일러가 수행해야 하는 작업은 command line 옵션에 의해 정의된다. 예를 들어,
nightly features(-Z flags: Rust의 pre-release 버전)을 활성화하거나,check 전용 빌드(빌드가 되는지 확인하기만 하는 기능)를 수행하거나, 실행 가능한 코드 대신LLVM Intermediate Representation(LLVM-IR)을 내보낼 수 있다.Command line 인수 구문 분석은
rustc_driver에서 수행한다. 해당crate(라이브러리)는 사용자가 요청한 컴파일 구성을 정의하고 이를rustc_interface::Config로 컴파일 프로세스의 나머지 부분에 전달한다.정리하면, Command line에 작성한 옵션은 Rust를 실행할 때 사용하는
rustc프로그램의main()함수에서 읽힌다.위처럼 main.rs의 실행 파일을 만들고, 실행하는 과정에서
rustc란 Rust 자체의 컴파일러를 사용하는데, 해당 프로그램의 옵션이 Rust의 argument를 처리하듯이rustc_interface::Config를 쓴다.Lexing and Parsing
렉싱(lexer)는 소스코드를 토큰 스트림으로 바꾸는 것을 의미한다. Raw Rust 소스 텍스트는
rustc_lexer에 있는 저수준의 렉서(lexer: 어휘 분석기)에 의해 분석된다. 이 단계에서 소스 텍스트는 토큰이라고 알려진 원자 소스 코드 단위의 스트림으로 변환된다. 렉서는 유니코드 문자 인코딩을 지원한다.토큰 스트림은
rustc_parse에 있는 고수준의 렉서를 통과하여 컴파일 프로세스의 다음 단계를 준비한다.StringReader구조체는 이 단계에서 일련의 검증을 수행하고 문자열을interned symbol로 변환하는 데 사용된다(intern은 나중에 설명). String interning은 각 고유 문자열 값의 변경 불가능한 사본을 하나만 저장하는 방법이다.렉서는 인터페이스가 작고 rustc의 진단 인프라(diagnostic infrastructure) 직접 의존하지 않는다. 대신 진단 정보를 일반 데이터로 제공하며, 이는 rustc_parse::lexer에서 실제 진단 정보로 방출됩니다. 렉서는 IDE와 절차적 매크로(
proc-macros라고도 함)에 대한 완전한 정보 충실도를 유지한다.파서(parser)는 렉서의 토큰 스트림을 추상 구문 트리(AST: Abstract Syntax Tree)로 변환한다. 구문 분석은 재귀적 하향식(top-down) 접근 방식을 사용한다. 파서의 crate 진입점은
rustc_parse::parser::Parser에서 찾을 수 있는Parser::parse_crate_mod()및Parser::parse_mod()메서드이다. 외부 모듈 파싱 진입점은rustc_expand::module::parse_external_mod이다. 그리고 매크로 파서 진입점은Parser::parse_nonterminal()이다.파싱은
bump,check,eat,expect,look_ahead와 같은 일련의 parser utility methods를 사용하여 수행된다.매크로 확장(macro-expansion), AST 유효성 검사(AST-validation), 이름 해석(name-resolution), 그리고 초기 린팅(early linting)도 렉싱과 파싱 단계에서 수행된다.
rustc_ast::ast::{Crate, Expr, Pat, ...}와 같은 AST 노드들이 파서로부터 반환 되며, 표준Diag API가 오류 처리에 사용한다. 일반적으로 Rust 컴파일러는 Rust의 문법 상위 집합을 구문 분석하여 오류로부터 복구하려고 하며, 동시에 오류 유형을 출력한다.AST Lowering: AST의 수준을 낮추는 과정
High-Level Intermediate Representation(HIR, 고수준 중간 표현)은 AST보다 컴파일러에 더 적합한 표현 방식으로, 다음 단계에서 AST는 HIR으로 변환된다. 이 과정을lowering이라고 하며,loop나async fn(비동기 함수)와 같은 축약되거나 간략화 된 구문 구조를 확장하고 형식화하는 작업(이를 desugaring이라고 함)이 많이 포함된다.그 후 HIR을 사용하여 타입 추론(type inference), trait 해결(trait solving), 그리고 타입 검사(type checking)를 수행한다.
let만을 사용해서 타입 지정 없이 변수를 선언하는 경우가 있다. 타입 검사는 표현식의 타입을 자동으로 감지하는 과정이다.hir::Ty를 컴파일러가 내부적으로 사용하는 타입 표현(Ty<'tcx>)으로 변환하는 과정이다. 이를 타입 검사라고 하는 이유는, 이 정보를 사용하여 프로그램에서 사용된 타입의 타입 안정성, 정확성, 그리고 일관성을 검증하기 때문이다.MIR Lowering: HIR -> MIR
HIR은 THIR(Typed High-Level Intermediate Representation)이라는 형태로 더 많이 desugaring(구문을 확장하고 형식화)된 후, 다시 MIR로 변환된다. THIR는 패턴 및 완전성 검사(패턴 매칭이 모든 경우를 다루고 있는지 확인하기 위한 검사)에 사용된다. 이후 THIR를 이용해 MIR을 생성한다.
MIR은 차용 검사(borrow checking)에 사용되며, 이 단계에서 많은 최적화 작업이 이루어진다. MIR은 일반적이기 때문에 이 단계에서 최적화를 수행하면 이후 코드 생성과 컴파일 속도가 개선된다. 예를 들어, LLVM 레벨에서는
simplify_try MIR최적화가 찾아내는 패턴을 최적화 할 수 없기 때문에, 일부 최적화는 MIR 레벨에서 수행하는 것이 더 쉽다.Rust 코드의 코드 생성 단계에서는
monomorphization(단형화) 과정이 이루어진다. 이는 제네릭 코드(템플릿과 유사함)를 각 타입 매개변수가 구체적인 타입으로 대체된 코드로 복사하는 것을 의미한다. 이를 위해 어떤 구체적인 타입에 대해 코드를 생성할지 목록을 수집해야 하며, 이 과정은monomorphization collection(단형화 수집)이라고 부르며, MIR 단계에서 수행된다.Code Generation: 코드 생성
코드 생성(code generation, 혹은 codegen) 단계에서는 고수준 표현(예: HIR, MIR)을 실행 가능한 이진 파일로 변환한다.
rustc는 코드 생성을 위해LLVM을 사용하므로, 첫 번째 단계로 MIR을LLVM-IR로 변환한다. 이 과정에서 MIR은 실제로monomorphized(단형화)된다. 이후,LLVM-IR은LLVM에 전달되어 추가적인 최적화가 수행된다.LLVM은 이LLVM-IR을 사용하여 machine code(어셈블리 코드와 유사하지만 추가적인 저수준 타입 및 주석이 포함된 코드, 예: ELF 오브젝트나 WASM)를 생성한다. 이후, 생성된 라이브러리나 이진 파일들이 함께 링크되어 최종적인 실행 파일이 만들어진다.컴파일러의 작업 방식
컴파일러가 코드에 대해 어떤 작업을 수행하는지 고수준 개요를 확인했으므로, 이러한 작업들이 어떻게 이루어지는지에 대해 알아볼 것이다. 컴파일러는 많은 제약 조건들과 상충하는 목표들을 최적화 해야하는데, 이러한 목표에는 다음 항목들이 있다.
Intermediate Representations: 중간 표현
대부분의 컴파일러와 마찬가지로
rustc도 계산을 용이하게 하기 위해 중간 표현(IR, Intermediate Representations)을 사용한다. 일반적으로 소스 코드 자체를 직접 다루는 것은 매우 불편하고 오류를 유발하기 쉽다. 소스 코드는 인간이 읽기 좋고 모호하지 않도록 설계되었지만, 타입 검사와 같은 작업을 수행하기에는 덜 편리하다.대신,
rustc를 포함한 대부분의 컴파일러는 소스 코드로부터 분석하기 더 쉬운 형태의 IR을 생성합니다.rustc는 각기 다른 목적에 최적화된 몇 가지 IR을 사용한다. 위의실행 파일 생성 과정에서 만들었던 중간 매개체를 의미한다.컴파일러에서는 많은 값이 내부적으로 저장된다(interned). 이는 성능 및 메모리 최적화로, 특수한 할당자(arena)라고 불리는 메모리 공간에 값을 할당하고, 이후 이 값들에 대한 참조를 전달하는 방식이다. 이를 통해 동일한 값(예: 프로그램 내의 타입)이 한 번만 할당되며, 포인터를 비교하는 방식으로 빠르게 비교할 수 있다. 많은 중간 표현들이 이 방식으로 관리된다.
Queries: 쿼리
Rust 컴파일러의 첫 번째 주요 구현 선택(implementation choice)은 쿼리 시스템을 사용하는 것이다. Rust 컴파일러는 코드 위에서 순차적으로 실행되도록 구현되어 있지 않도록 구성되어 있다. 이를 통해 증분 컴파일(incremental compilation)을 가능하게 한다. 즉, 사용자가 프로그램을 변경하고 다시 컴파일할 때, 새로 생성된 이진 파일을 출력하기 위해 불필요한 작업을 최소화하려는 목적이다.
rustc에서, 앞서 설명한 주요 단계들은 서로 호출하는 여러 개의 쿼리로 구성되어 있다. 예를 들어, 어떤 항목의 '타입을 묻는 쿼리'가 있고, 또 다른 쿼리는 '함수의 최적화된 MIR(중간 표현)을 요청'한다. 이러한 쿼리들은 서로 호출할 수 있으며, 쿼리 시스템(query system)을 통해 추적 된다. 각 쿼리의 결과는 디스크에 캐시 되어, 컴파일러가 이전 컴파일 결과와 비교해 어떤 쿼리의 결과가 변경되었는지 확인하고, 변경된 쿼리들만 다시 처리하게 된다.원칙적으로는 쿼리 단계마다 각 항목에 대해 이러한 과정을 개별적으로 수행한다. 예를 들어, 함수에 대한 HIR(고수준 중간 표현)을 가져온 다음, 쿼리를 통해 해당 HIR의 LLVM-IR을 요청한다. 이 과정은 최적화된 MIR 생성을 유도하고, 이 MIR은 차용 검사기(borrow checker)를 구동하며, 다시 MIR 생성을 촉진한다.
하지만, 실제로는 일부 쿼리는 디스크에 캐시 되지 않으며, 컴파일러의 일부는 프로그램의 사용되지 않는 코드(죽은 코드)도 포함하여 모든 코드를 실행해야만 한다(예: borrow checker는 실행에서 사용되지 않으나 이를 포함해서 실행한다).
예를 들어, 현재
mir_borrowck쿼리는 crate의 모든 함수에서 먼저 실행된다. 그 다음, 코드 생성 백엔드는collect_and_partition_mono_items쿼리를 호출하는데, 이는 먼저 모든 접근 가능한 함수의optimized_mir를 재귀적으로 요청한다. 이 과정에서 해당 함수에 대해mir_borrowck를 실행한 후, 코드 생성 유닛이 생성된다. 이처럼 접근할 수 없는 함수도 오류를 발생함을 보장하기 위해 이러한 작업 분할이 유지된다. => 간단하게, 컴파일 과정에서 실행에 쓰이지 않더라도 borrow-check를 하고, 문제가 있는 코드에 오류를 보장하도록 만든다.컴파일러는 원래부터 쿼리 시스템을 염두에 두고 설계된 것이 아니었으며, 쿼리 시스템이 후에 추가되었다. 따라서 아직 쿼리화 되지 않은 컴파일러 부분이 존재한다.
LLVM은 Rust 팀에서 작성한 코드가 아니므로 쿼리 시스템에 포함되지 않았다. 계획은 결국 이전에 언급한 모든 단계가 쿼리화 되도록 하는 것이지만, 2022년 11월 기준으로는HIR에서LLVM-IR까지의 단계만 쿼리화 되었다. 즉, 렉싱(lexing), 파싱(parsing), 이름 해석(name resolution), 매크로 확장(macro expansion) 등은 프로그램 전체에 대해 한 번에 수행된다.마지막으로 중요한 개념 중 하나는
타이핑 컨텍스트(typing context), 즉TyCtxt이다. 이는 모든 쿼리의 중심에 있는 거대한 구조체(struct: rust의 타입 중 하나)이다. 모든 쿼리는TyCtxt타입의 메서드로 정의되며, 메모리에 저장된 쿼리 캐시도 여기 저장된다. 코드에서는 일반적으로tcx라는 변수가 타이핑 컨텍스트를 가리키는 핸들로 사용된다. 또한,tcx라는lifetime을 볼 수 있는데, 이는 어떤 것(변수, 값 등)이TyCtxt의 lifetime에 연관되어 있음을 의미한다(주로 저장되거나 내부적으로 참조된 값을 나타낸다).ty::Ty: 타입
타입은 컴파일러 분석의 핵심 중 하나이다. 사용자 프로그램에서 타입을 나타내는 주된 타입(컴파일러에서)은
rustc_middle::ty::Ty이다. 매우 중요해서 ty::Ty에 대한 전체 장이 있지만, 지금은 그것이 존재하고rustc가 유형을 나타내는 방식이라는 것만 언급하고 넘어간다. 또한rustc_middle::ty모듈은 쿼리에서 언급한TyCtxt구조체를 정의한다는 점에 유의해야 한다.Parallelism: 병렬 처리
Rust 프로젝트가 좀 커지면 컴파일과 링크가 느린 것을 체감할 수 있다. 이 점은 컴파일러 개발진도 인지하고 있는지, 컴파일러 성능은 개발진이 개선하고자 하는 문제이며, 지속적으로 작업 중인 부분이라고 한다. 그 중 한 가지는
rustc자체를 병렬화하는 것이다. 현재rustc에서 기본적으로 병렬화 된 유일한 부분은 코드 생성이다.나머지 부분은 아직 병렬화되지 않았으며, 해당 문제를 해결하기 위해 많은 노력이 기울여졌지만, 일반적으로 어려운 문제라고 한다. 현재의 접근 방식은
RefCell을Mutex로 변환하는 것이다. 즉, 스레드 안전한 내부 가변성으로 전환하는 것이다. 하지만 여전히lock contention, 쿼리 시스템 불변성을 유지하는 문제, 그리고 코드베이스의 복잡성 등 여러 도전 과제가 존재한다.config.toml에서 병렬 컴파일을 활성화하여 현재 작업 중인 기능을 시도해볼 수 있고, 아직 초기 단계이지만 이미 유망한 성능 향상이 나타나고 있다.Bootstrapping: 부트스트래핑
rustc는 Rust로 작성되어있다. 그렇다면 컴파일러는 어떻게 컴파일할까? 간단하다. 이전 버전의 컴파일러를 사용하여 새로운 컴파일러를 컴파일한다. 이를 부트스트래핑(bootstrapping)이라고 한다.부트스트래핑은 여러 함축적인 의미를 가진다. 예를 들어, 이는 Rust의 주요 사용자 중 하나가 Rust 컴파일러 자체임을 의미하므로, 우리는 항상 self testing하고 있다는 뜻이다. 이는 "dogfooding"(자기 제품을 직접 사용하는 것)이라고도 한다.
참고 자료
Rust Compiler Development Guide
이 많은 내용이... overview인 것이 믿기지 않습니다... 다 하고 보니 개요였고, 상세한 내용이 따로 있더라고요...? 시리즈로 이어갑니다.