Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

21장: LLVM 코드 생성

새 파일

  • src/llvm/mod.rs
  • src/llvm/control.rs
  • src/llvm/values.rs
  • src/llvm/primitives.rs
  • src/native.rs

변경된 파일

  • src/flat.rs
  • build.rs
  • src/flat_lint.rs
  • src/lib.rs
  • src/main.rs

동기

이제 우리는 Fun 프로그램을 실행할 수 있지만, 실제 작업은 여전히 우리의 인터프리터가 맡아야 합니다. 이 장에서는 셸에서 바로 실행할 수 있는 실행 파일을 만들어 보겠습니다. 계산기에서 출발한 프로젝트로서는 꽤 만족스러운 도착점입니다!

준비 작업의 상당 부분은 이미 끝났습니다. 패턴 매칭은 분기가 되었고, 클로저는 명시적인 환경을 갖게 되었으며, Flat IR은 호출과 꼬리 전달이 어디에 위치해야 하는지 알려 줍니다. 명령어 선택, 레지스터 할당, 기계어 수준 최적화는 LLVM이 처리할 것입니다.

그래도 우리 값이 메모리에 어떻게 배치되는지, 우리 함수들이 서로를 어떻게 호출하는지는 여전히 우리가 LLVM에 알려 주어야 합니다. 이러한 결정이 런타임과 어긋나면, LLVM은 잘못된 프로그램을 효율적으로 컴파일해 버릴 수 있습니다. 우리는 이미 이해하고 있는 표현들을 활용해 새로운 작업을 감당할 만한 수준으로 유지하면서, 그 경계를 신중하게 짚어 나가겠습니다.

현재의 언어

언어 자체는 바뀌지 않았습니다. fun-ch21 build FILE -o OUT은 실행 파일을 만듭니다. run은 여전히 인터프리터를 선택합니다. -O0부터 -O3까지가 최적화를 제어하며, 기본값은 -O2입니다. --dump=llvm은 최적화 전의 모듈을, --dump=llvm-opt는 최적화 후의 모듈을 보여 줍니다.

인수 테스트 프로그램은 레코드, 사전, 고차 함수, IO, 그리고 엄격한 누산기 루프를 한데 모읍니다:

-- engines: native
data Shape = Circle Double | Rect Double Double
  deriving (Show)

data Point = Point { x :: Double, y :: Double }
  deriving (Eq, Show)

class Area a where
  area :: a -> Double

instance Area Shape where
  area (Circle r) = 3.0 * r * r
  area (Rect w h) = w * h

norm :: Point -> Double
norm p = sqrt (p.x * p.x + p.y * p.y)

sumTo :: Int -> Int
sumTo n = go 0 n
  where
    go acc 0 = acc
    go acc k = go (acc + k) (k - 1)

main :: IO ()
main = do
  let p = Point { x = 3.0, y = 4.0 }
  print (norm p)
  mapM_ (print . area) [Circle 1.0, Rect 2.0 3.0]
  print (map (.x) [p, p { x = 10.0 }])
  print (p == p { y = 4.0 })
  print (sumTo 10000000)

마지막 호출은 천만 번 반복을 수행합니다. 올바른 수를 얻는 것은 과제의 일부일 뿐입니다. 우리의 명시적 기계에서 꼬리 호출이 그러하듯이, 네이티브 스택 역시 유계(bounded)로 유지되어야 합니다.

이론

LLVM은 정적 단일 대입(static single assignment), 곧 SSA를 사용합니다. 각 명령어 결과에는 정의가 하나뿐이므로, 이름은 언제나 같은 계산된 값을 가리킵니다. 우리의 고유한 Flat 바인더는 이미 이 개념에 잘 들어맞습니다. Let은 바인더를 LLVM 값에 연결하고, Join은 여러 경로가 들어올 수 있는 기본 블록이 됩니다.

흥미로운 질문은 그 경로들이 블록에 값을 어떻게 전달하느냐입니다. LLVM은 phi 노드를 사용합니다. 각 조인 매개변수는 phi가 되고, Jump는 블록으로 분기하기 전에 자신의 유입 값을 제공합니다. 우리가 이미 만들어 둔 조인 포인트 덕분에 이 변환은 자연스러운 형태를 갖게 됩니다 (Maurer et al. 2017).

하나의 조인에서 만나는 두 경로를 생각해 봅시다. 한 경로는 10을, 다른 경로는 20을 제공합니다. phi는 우리가 어느 경로로 도착했는지에 따라 그 경로에 연결된 값을 취합니다. 원래의 조건을 다시 검사하지는 않습니다.

여기에는 코드 생성에서 저지르기 쉬운 실수가 하나 있습니다. Flat 연산 하나를 방출하면 LLVM 블록이 여러 개 생길 수 있습니다. 예를 들어 나눗셈은 0 검사를 추가합니다. phi의 유입 간선은 식을 방출하기 시작한 블록이 아니라, 그 검사 후에 실제로 떠나는 블록을 가리켜야 합니다. 점프 인자를 내보낸 뒤에는 빌더의 현재 블록을 기록하십시오.

Flat 구성 요소LLVM 변환
Let명령어와 이름-값 항목
Case태그 검사와 switch
Joinphi 매개변수를 갖는 블록
Jumpphi 유입 값과 br
알려진 꼬리 호출tail call tailcc, 바로 뒤에 ret
알려지지 않은 호출C 호출 규약 런타임 apply

꼬리 위치만으로는 네이티브 스택 사용량을 유계로 유지하기에 충분하지 않습니다. LLVM은 호환되는 호출 규약과 적절한 반환 시퀀스를 요구합니다. 우리는 모든 빠른 진입점에 tailcc를 부여하고, 알려진 꼬리 호출에 표시를 하며, 호출 결과를 즉시 반환합니다. 내부 링크(internal linkage)는 x86-64 위치 독립 코드의 가시성 요구 사항도 충족합니다. 이러한 선택은 LLVM의 꼬리 호출 규칙을 따릅니다. 이 보장은 상호 재귀를 포함하여 알려진 포화 호출에 적용됩니다. 이 보장은 런타임의 C eval/apply 경계를 넘어서까지 확장되지는 않습니다.

구현

먼저 타깃을 확정하기

llvm/mod.rs는 모듈, 빌더, 타깃 머신, 심볼 테이블을 소유합니다. 이 모듈의 LLVM 값들은 호출자가 소유한 Context를 빌려 씁니다. 이렇게 하면 수명 경계가 명시적으로 드러나고 자기 참조적인 Rust 구조체를 피할 수 있습니다. 모든 함수 진입점과 전역 슬롯은 본문보다 먼저 선언되므로, 전방 호출과 상호 재귀 호출에 특별한 처리가 필요하지 않습니다.

이 장은 Inkwell 0.10.0을 llvm22-1-prefer-dynamic과 함께 LLVM 22로 고정합니다. 타깃 초기화는 한 번만 실행됩니다. 타깃 머신은 호스트 트리플, 범용(generic) CPU, 위치 독립 재배치를 사용합니다. 이 타깃 머신의 트리플과 데이터 레이아웃은 방출 이전에 모듈에 설정됩니다. 32비트 포인터 타깃은 거부됩니다. 바인딩을 더 간단히 소개하는 자료로는 컴파일러 크레이트의 예제를 참고하십시오.

빌더 연산은 오류를 반환합니다. Flat 린트는 입력을 검사하고, LLVM의 검증기는 --lint와 관계없이 완성된 모든 모듈을 검사합니다. 최적화는 새 패스 관리자를 사용하며 다시 한 번 검증합니다:

#![allow(unused)]
fn main() {
/// Run the new pass manager only after constructing a complete, valid module.
pub fn optimize(&self, level: u8) -> Result<()> {
    if level > 3 {
        return Err(Error("optimization level must be 0..3".into()));
    }
    self.module
        .run_passes(
            &format!("default<O{level}>"),
            &self.machine,
            PassBuilderOptions::create(),
        )
        .map_err(|e| Error(e.to_string()))?;
    self.verify()
}
}

검증기는 누락된 종결자, 잘못된 phi, 타입이 맞지 않는 호출을 잡아낼 수 있습니다. 이는 훌륭한 1차 방어선입니다. 하지만 완벽하게 유효한 LLVM이라도 Fun을 잘못 번역한 결과일 수 있습니다. 예를 들어 인자를 잘못된 순서로 평가하거나 정수 오버플로를 잘못 처리할 수 있습니다. 우리는 같은 프로그램을 인터프리터와 네이티브 코드 양쪽으로 실행하여 이러한 실수를 잡아냅니다.

작업 목록으로 순회하기

방출기는 Flat 트리를 결코 재귀적으로 내려가지 않습니다. 대기 중인 블록은 벡터에 저장되며, 루프가 직선형 Let 척추를 하나씩 소비합니다. 종결 처리기는 반환이나 제어 이전을 방출하거나, 조인과 대안의 본문을 큐에 넣습니다.

환경은 고유한 SSA 정의들의 테이블입니다. 렉시컬 스코프는 Flat 린트에서 이미 검사했으므로, 방출 단계에서는 분기마다 스코프 맵을 복제하지 않습니다. 조인의 phi는 그 호출자들을 방문하기 전에 생성됩니다. 들어오는 간선은 그 호출자들이 방출될 때 추가할 수 있습니다. 완성된 각 블록에는 종결자가 정확히 하나 있습니다.

작업 목록 방식은 린트, 출력, 정리에도 적용됩니다. 이 중 마지막 것은 잊기 쉽습니다. Rust가 생성하는 소멸자는 컴파일이 겉보기에 성공한 뒤에도 깊은 Rc 트리를 재귀적으로 해제할 수 있습니다. 우리는 이 간선들도 작업 목록으로 비워 냅니다. 깊은 Flat 트리는 작은 Rust 스택 위에서 검사되고, 출력되고, 방출되고, 검증되고, 해제됩니다. 이렇게 하면 코드 생성 루프가 성공했다고 해서 다른 모든 패스가 안전하다고 가정하는 대신, 우리의 Flat 순회를 직접 검사하게 됩니다.

#![allow(unused)]
fn main() {
pub(super) fn body(
    &mut self,
    b: &Body,
    mut env: Env<'ctx>,
    mut joins: Joins<'ctx>,
) -> Result<()> {
    // Unique binders index SSA values; lint already checked scopes.
    // Branches share this table without cloning lexical environments.
    let block = self.builder.get_insert_block().unwrap();
    let mut work = vec![Block {
        body: b.clone(),
        block,
    }];
    while let Some(Block { body, block }) = work.pop() {
        self.builder.position_at_end(block);
        let mut cursor = body.as_ref();
        while let Flat::Let(v, r, rest) = cursor {
            let value = self.rhs(r, &env)?;
            env.insert(v.clone(), value);
            cursor = rest;
        }
        self.terminal(cursor, &mut env, &mut joins, &mut work)?;
    }
    Ok(())
}
}

워드 표현 유지하기

모든 Fun 값은 20장의 공유 runtime_layout을 사용하는 LLVM i64입니다. 로드는 워드를 포인터로 변환하고 워드 배열을 인덱싱합니다. Inkwell의 불투명 포인터는 접근하는 원소 타입을 명시적으로 요구합니다:

#![allow(unused)]
fn main() {
pub(super) fn slot(
    &self,
    pointer: PointerValue<'ctx>,
    index: u64,
) -> Result<PointerValue<'ctx>> {
    // SAFETY: GEP indexes i64 words using the checked ABI layout.
    Ok(unsafe {
        self.builder.build_gep(
            self.word,
            pointer,
            &[self.n(index)],
            "slot",
        )?
    })
}
}

unsafe 경계는 LLVM을 구성합니다. 이 경계는 Rust 포인터를 역참조하지 않습니다. 그래도 생성된 접근 코드는 검사를 거친 생성자 항수와 런타임 레이아웃에 의존합니다. 우리는 추가적인 inbounds 보장을 주장하지 않고 일반 GEP를 사용합니다. 생성자 필드는 헤더에서 한 워드 뒤에 있습니다. 클로저 캡처는 여기에 더해 느린 진입점 주소와 항수도 건너뜁니다.

인자 없는 생성자는 즉칫값입니다. 그 밖의 생성자는 rt_alloc으로 할당한 다음 슬롯 순서대로 초기화합니다. 두 형태를 모두 포함하는 타입에 대한 case는 헤더를 로드하기 전에 최하위 비트를 검사합니다. 한 형태만 포함하는 타입에는 그런 분기가 필요하지 않습니다. 정수 및 문자 리터럴 case는 태그가 붙은 워드에 대해 곧바로 switch합니다. 문자열 동등성은 매치 컴파일 단계에서 이미 기본 검사로 바뀌었습니다.

문자열 리터럴은 헤더, 바이트 길이, 패딩된 UTF-8 바이트를 담은 정렬된 읽기 전용 객체입니다. 유지되는 데이터 테이블이 이들의 루트 워드를 기록합니다. llvm.used는 최적화와 링킹을 거치는 동안 그 테이블을 유지합니다. 이 정적 객체들은 결코 이동되거나 해제되지 않습니다. 힙 문자열과 double은 포인터를 담지 않으므로 아토믹 할당을 사용합니다. 생성된 전역 변수와 살아 있는 기계 레지스터/스택 슬롯은 Boehm에게 계속 보입니다 (Boehm and Weiser 1988).

정수 연산은 산술 시프트로 디코딩하고, i64로 계산한 뒤, 다시 태그를 붙입니다. 랩어라운드는 정의된 동작이므로 우리는 nsw도 nuw도 붙이지 않습니다. 제수가 0이면 나눗셈 전에 rt_div_zero로 분기합니다. 가장 작은 Fun 정수를 -1로 나눈 결과는 더 넓은 중간 i64에 들어갑니다. 다시 태그를 붙이는 과정이 필요한 63비트 랩어라운드를 제공합니다. div와 mod는 부호 때문에 내림(flooring)이 필요할 때 버림 방식의 몫과 나머지를 보정합니다.

Double 연산은 박스를 풀고, fast-math 플래그 없이 IEEE 명령어를 사용한 뒤, 다시 박싱합니다. 순서 있는(ordered) 비교는 NaN 동작을 보존합니다. 초월 함수, 포화 변환, 텍스트, 서식화, IO는 인터프리터가 사용하는 것과 같은 런타임을 호출합니다. LLVM 최적화가 이러한 언어 수준의 선택을 대체해서는 안 됩니다.

빠른 호출과 클로저 적용 분리하기

끌어올려진 함수마다 진입점이 두 개 있습니다. 빠른 진입점은 tailcc로 환경 워드 하나와 그 뒤에 오는 일반 워드 인자들을 받습니다. 최상위 함수는 사용하지 않는 환경 자리에 0을 받습니다. 알려진 호출은 피호출자뿐 아니라 호출 명령어에도 호출 규약을 지정합니다:

#![allow(unused)]
fn main() {
pub(super) fn known(
    &self,
    f: FuncId,
    env: Option<IntValue<'ctx>>,
    args: &[IntValue<'ctx>],
    tail: bool,
) -> Result<IntValue<'ctx>> {
    let mut actual: Vec<BasicMetadataValueEnum> =
        vec![env.unwrap_or(self.n(0)).into()];
    actual
        .extend(args.iter().map(|v| BasicMetadataValueEnum::from(*v)));
    let call = self.builder.build_call(
        self.fast[f.0 as usize],
        &actual,
        "known",
    )?;
    call.set_call_convention(TAIL_CC);
    call.set_tail_call(tail);
    if self
        .builder
        .get_insert_block()
        .unwrap()
        .get_parent()
        .unwrap()
        .get_call_conventions()
        != TAIL_CC
    {
        call.set_tail_call_kind(
            inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
        );
    }
    Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}
}

느린 진입점은 C ABI를 사용하며, 클로저 워드와 인자 배열 포인터를 받습니다. 이 진입점은 함수의 구문적 항수만큼 정확히 인자를 풀어낸 뒤 빠른 코드로 진입합니다. 클로저는 이 느린 진입점의 주소를 저장합니다. 알려지지 않은 호출은 rt_apply1부터 rt_apply4까지를 사용하며, 더 넓은 묶음에는 범용 rt_apply를 사용합니다. 일반 인자 배열은 제어 흐름 지점에서 반복적으로 할당하지 않고 함수의 진입 블록에서 할당합니다. 런타임은 기존의 eval/apply 프로토콜을 사용하여 부분 적용과 과포화 적용을 처리합니다(Marlow and Peyton Jones 2004).

C 어댑터는 보장된 꼬리 전달이 아니며, rt_apply를 거치는 알 수 없는 꼬리 호출도 마찬가지입니다. 따라서 고차 재귀는 네이티브 스택을 키울 수 있습니다. 이 보장을 확장하려면 호환되는 호출 규약을 갖춘, LLVM이 생성하는 apply 경로가 필요합니다. 선택적인 최적화기 변환을 언어 차원의 보장처럼 취급하기보다는 이 경계를 명시적으로 유지하는 편이 더 유용합니다.

초기화, 생성, 링크

fun_init은 먼저 전역 함수 클로저를 설치한 다음, 엄격한 값 초기화식을 의존성 순서대로 평가합니다. 생성된 C main은 런타임을 초기화하고, fun_init을 호출하고, 소스의 main을 unit에 적용한 뒤, 출력을 플러시하기 위해 rt_exit을 통해 종료합니다. 이 순서는 어떤 최상위 오류가 먼저 발생하는지를 보존하며, IO 동작을 단지 구성하는 것만으로는 어떤 효과도 일어나지 않도록 보장합니다.

native.rs는 타깃 머신으로 오브젝트 파일을 쓴 다음 시스템 cc를 직접 호출합니다. 이때 libfun_rt_21.a, Boehm, 그리고 rustc가 알려 주는 네이티브 라이브러리 플래그를 함께 링크합니다. FUN_RT로 설치된 아카이브를 지정할 수 있습니다. 지정하지 않으면 컴파일러 옆에서 아카이브를 찾습니다. just build는 런타임과 플래그를 먼저 준비합니다. 링크는 출력 위치 옆의 임시 디렉터리에서 이루어지며, 성공했을 때만 실행 파일을 설치합니다. 셸 보간은 쓰지 않으며, 링크가 실패해도 기존 출력물은 그대로 남습니다.

tailcc와 C 런타임 사이를 오가는 호출에는 명시적으로 notail을 붙입니다. 그렇게 하지 않으면 LLVM이 서로 다른 두 호출 규약에 걸쳐 꼬리 전달을 추론하여, 인자가 많은 호출에서 스택 정리를 잘못할 수 있습니다. IR이 검증을 통과할 수도 있기 때문에 이것은 특히 고약한 버그입니다. 이 경계를 표시해도 이미 알려진 Fun 함수 사이에서 우리가 보장하는 꼬리 호출에는 영향이 없습니다.

실행해 보기

저장소 README의 설명대로 LLVM 22와 Boehm을 설치하십시오. LLVM_SYS_221_PREFIX를 LLVM 설치 경로(prefix)로 설정한 다음 루트에서 빌드하십시오:

$ just build
$ target/debug/fun-ch21 build crates/ch21_llvm/tests/programs/native/acceptance.fun -o build/acceptance --lint
$ build/acceptance
5.0
3.0
6.0
[3.0,10.0]
True
50000005000000
$ target/debug/fun-ch21 dump --pass=llvm crates/ch21_llvm/tests/programs/native/acceptance.fun > build/acceptance.ll
$ target/debug/fun-ch21 dump --pass=llvm-opt crates/ch21_llvm/tests/programs/native/acceptance.fun > build/acceptance-opt.ll

예제를 네이티브 코드와 인터프리터 양쪽으로 실행해 보십시오. 평가 순서 버그는 어떤 오류가 먼저 나타나는지에서 드러나는 경우가 많으므로, 성공한 결과뿐 아니라 오류도 비교하십시오. 모든 최적화 수준을 시험해 보는 것도 좋습니다. 호출 규약 실수는 LLVM이 특정 변환을 하기로 결정할 때까지 숨어 있을 수 있습니다.

별도의 스트레스 테스트는 네이티브 재귀 프로그램을 512 KiB 스택으로 실행합니다. 또 다른 루프는 64 MiB의 Boehm 힙 한도 아래에서 최소 1억 워드를 할당합니다. 이 테스트들은 함께 서로 다른 두 가지 의무를 검사합니다. 꼬리 전달은 호출 프레임을 해제해야 하고, 죽은 힙 객체는 계속 회수 가능해야 합니다. LLVM 검증을 통과했다는 것만으로는 둘 중 어느 것도 입증되지 않습니다.

연습 문제

  1. 몸풀기. 태그가 붙은 워드에서 시작해 inttoptr, GEP, load를 거치는 필드 로드를 추적하십시오. 앞선 어떤 검사가 그 필드 인덱스를 정당화하는지 밝히십시오.
  2. 중급. 호출자가 둘인 조인의 블록을 그리십시오. 한쪽 호출자에 나눗셈을 추가한 뒤, 올바른 phi 선행자가 무엇인지 찾아보십시오.
  3. 중급. 정수 곱셈에 nsw를 붙이면 대부분의 예제가 여전히 통과하더라도 Fun의 의미론이 바뀌는 이유를 설명하십시오.
  4. 고급. sumTo의 최적화 전 IR과 최적화된 IR을 비교하십시오. 재귀 전달의 양쪽 끝에서 호출 규약을 확인하십시오.
  5. 고급. C apply 경계를 드러내는 미지 호출(unknown call) 스트레스 테스트를 설계하십시오. 이를 보장된 꼬리 호출로 만들려면 ABI를 어떻게 바꿔야 하는지 설명하십시오.

더 읽을거리

원문 © Stephen Diehl · Write You a Haskell · 산문 CC BY-SA 4.0 · 코드 MIT
yeokja 한국어 번역 · Anthropic 사의 claude-opus-5-5 모델을 활용하여 번역되었으며 학습을 모두 비허용한 상태로 작업하였습니다 · 이 문서는 원문을 수정한 비공식 번역본이며 산문은 같은 CC BY-SA 4.0으로 제공합니다.