LLVM backend: 컴파일러를 위한 IR로 낮추기

C backend는 Mere를, 사람을 위한 다른 언어로 번역했다 —— 식이 있고, 중첩된 구조가 있고, 지역 변수가 있고, 기대대로 동작하는 if가 있는 언어로. 다음 backend는 그것을, 아주 다른 독자를 위해 만들어진 무언가로 번역한다: LLVM의 중간 표현, 컴파일러가 소비하고 싶어 하는 형식이다. 지원할 feature는, C backend가 이미 덮은 것과 같은 것이다. 바뀌는 것은, 낮추는 작업의 얼마만큼을 스스로 해야 하는가다. 타깃이, C가 조용히 해 주던 거의 모든 것을 벗겨냈기 때문이다.

편의가 없는 타깃

C에서 LLVM IR로의 이행을 정하는 세 차이가 있고, 그 저마다가, 작업을 타깃에서 컴파일러로 옮긴다.

첫째는 **정적 단일 대입(SSA)**이다. LLVM IR에서는 모든 값이, 가상 레지스터에 꼭 한 번만 쓰인다 —— %1, %2, 그렇게, 다함이 없는 공급으로, 실제 머신 레지스터로의 대응은 나중에 LLVM이 정하도록 맡겨진다. 변수를 재대입하지 않고, 새 레지스터를 낳는다. 그 하나의 규칙이 하류의 모든 것을 다시 빚고, 그 가장 날카로운 귀결이 제어 흐름이다.

둘째는, 구조화된 if가 없다는 것이다. C는 backend에 cond ? a : b라고 쓰게 하고 넘어가게 했다. LLVM IR에 있는 것은 기본 블록과 분기뿐이다: if를 컴파일하려면, 조건을 i1로 계산하고, 두 라벨 붙은 블록으로 조건 분기하고, 각 블록에 자기 값을 계산하게 하고, 그리고 —— SSA가 하나의 변수에 두 다른 값을 가지는 것을 금하므로 —— 합류점에서 두 결과를 phi 노드로 화해시킨다. phi는 “이 값은, 어느 블록에서 왔는가에 따라, 닿은 쪽이다”라고 말하는 명령이다. 겸손한 if/then/else가, 네 블록과 하나의 phi가 된다. 언어의 모든 분기, match의 모든 팔이, 이 방식으로 낮아진다: 태그를 꺼내고, 각 생성자와 icmp하고, 조건 분기의 연쇄, 그리고 팔을 다시 merge하는 phi.

셋째는, 타입이 명시적이고 기계에 가깝다는 것이다. bool은 i1이고, 표시될 수 있기 전에 i32로 제로 확장된다; 포인터는 ptr; 튜플은 이름 붙은 구조체 타입 %tuple_int_str = type { i32, ptr } 로, 리터럴로 채우는 것이 아니라 insertvalue로 한 명령씩 조립하고, extractvalue로 읽어 되돌린다. heap 구조체로의 주소 지정은 getelementptr다. C라면 #include할 수 있던 런타임 헬퍼는, 대신 IR 안에서 인라인 정의된다 —— 문자열 연결이 malloc과 strlen과 memcpy로 써 내려진다 —— 그리고 puts나 strcmp 같은 함수는 선언되고 직접 불린다. 몇몇은 어려워지는 대신 쉬워진다: LLVM은 모듈 안의 전방 참조를 허용하므로, C가 상호 재귀에 요한 전방 선언은, 그저 필요 없다.

같은 사다리를, 두 번째로 오르기

LLVM backend를 세우는 것의 두드러진 점은, 그것이 얼마나 정확히 C backend의 발자취를 되짚었는가다. 같은 feature가 같은 순서로 왔다 —— 정수, 문자열, 튜플, 레코드, match를 동반한 variant, 일급 함수, 포획을 동반한 클로저, 단형화된 다형 타입, 재귀 variant, 완전한 패턴 언어, show, 그리고 region과 with와 view의 메모리 모델 통째 —— 그 저마다가 작은 슬라이스이고, C backend가 이미 번역한 구문을, 하지만 이번에는 C의 식이 아니라 SSA와 기본 블록으로 번역한다. 클로저는 여전히 함수 포인터와 환경 포인터의 두 워드 쌍이다; 그저 그것이 이제, 컴파운드 리터럴의 C 구조체가 아니라, insertvalue 로 조립되는 %closure_T1_T2 = type { ptr, ptr }일 뿐이다. 마지막 슬라이스까지, LLVM backend는 C backend가 한 전 feature를, 병렬로 덮었다.

같은 사다리를 두 번 오르는 것은 낭비가 아니다; 그것은 두 번째 종류의 검사다. C backend는, 언어가 사람용 타깃으로 낮춰질 수 있음을 증명했다; LLVM backend는, 그것이 컴파일러용 타깃으로도 낮춰질 수 있음을 증명한다 —— C의 구조를 일절 갖지 않고, 기본 블록과 phi 노드와 명시적 타입을 스스로 공급하는 타깃으로. 그 양쪽의, 아주 다른 형태로 깔끔하게 낮아지는 feature는, 번역을 살아남을 만큼 명확히 정의된 feature이고, 그것은 조용한 형태의 설계 검증이다. 그리고 양쪽 lowering이 같은 인터프리터에 유지되므로, 이제 세 구현이 바이트 단위로 일치해야 한다 —— 인터프리터, C 출력, LLVM 출력 —— 그리고 새로운 하나하나가, 두 회 전의 차분 테스트를 더 엄하게 한다.

C가 이미 어디서나 도는데, 왜

C backend가 이미 이식 가능한 네이티브 코드를 낳는다면, LLVM IR을 손으로 뱉는 것 —— C가 공짜로 한 낮춤을 모두 하는 것 —— 에는 이유가 필요하다. 이유는, IR의 건너편에 있는 것이다. LLVM의 최적화기와 네이티브 코드 생성기는 존재하는 것 중 최상의 부류이고, Clang, Rust, Swift의 배후에 있는 같은 기구다: 레지스터 할당, 명령 선택, 인라인화, 적극적 최적화, 그리고 LLVM이 타깃하는 모든 플랫폼용 codegen. IR을 뱉음으로써, Mere는 프로그램을 그 기반에 건네고, 그 전부를 상속한다. 거래는 명시적이고 의도적이다 —— 낮추는 작업의 더 많은 부분을 미리 하고, 그 대신, 프로 수준의 최적화와, 프로젝트의 누구도 쓰지 않아도 되는 네이티브 코드를 얻는다.

그것이 이 Part 전체를 관통하는 선택의 형태다: 도달 범위와 단순함을 위한 C, 최적화를 위한 LLVM, 기준을 위한 인터프리터, 모두를 동일한 출력으로 유지한다. 두 코드 생성기가 이제 존재하고, feature 마다 일치하며, 서로와 인터프리터에 대해 바이트 단위로 검증되었다. 자연스러운 물음은, 그 일치가, 작지 않은 프로그램 —— 열 줄의 데모가 아니라 천 줄의 파서 —— 과의 접촉을 살아남는가다. 다음 회: 스케일에서 동일하게 유지하기 —— 천 줄을 넘는 현실적인 프로그램이, 모든 backend에서 꼭 같은 바이트를 낳는, 그리고 그것을 유지하는 데 무엇이 드는가.