Cranelift의 백엔드 프레임워크를 개편하며 명령어 선택(Instruction Selection) 문제와 새로운 머신 백엔드 설계를 설명한다.
URL: https://cfallin.org/blog/2020/09/18/cranelift-isel-1/
Title: Cranelift를 위한 새로운 백엔드, 1부: 명령어 선택
이 글은 Mozilla에서 본업의 일환으로 최근 Cranelift에서 진행한 작업에 대한 3부작 시리즈의 첫 번째 글이다. 이 첫 글에서는 맥락을 잡고 명령어 선택(instruction selection) 문제를 설명한다. 특히 지난 9개월 정도 동안 함께 작업해온 명령어 선택기와 백엔드 프레임워크 전반의 개편에 대해 이야기하겠다. 이 작업은 뛰어난 동료 Julian Seward와 Benjamin Bouvier와 함께 공동 개발했으며, 초기에는 Dan Gohman에게서도 중요한 의견을 받았고, 많은 훌륭한 Cranelift 해커들의 도움을 받았다.
그렇다면 Cranelift란 무엇일까? Cranelift는 Rust로 작성된 컴파일러 프레임워크로, 특히(하지만 그것만을 위해서가 아니라) JIT 컴파일을 염두에 두고 설계되었다. 범용 컴파일러이며, 가장 널리 쓰이는 용도는 WebAssembly 컴파일이다. 하지만 다른 프론트엔드도 여럿 존재한다. 예를 들어 cg_clif는 Rust 컴파일러 자체가 Cranelift를 백엔드로 사용하도록 어댑트한다. Mozilla와 여러 곳의 사람들이 수년간 이 컴파일러를 개발해왔다. Cranelift는 브라우저 밖에서 WebAssembly를 실행하는 런타임인 wasmtime의 기본 컴파일러 백엔드이며, 여러 다른 곳에서도 프로덕션에서 사용된다. 최근에는 대부분의 스마트폰을 포함한 ARM64(AArch64) 머신에서 nightly Firefox에 Cranelift 기반 WebAssembly 지원을 켜는 스위치를 뒤집었고, 잘 진행된다면 결국 안정(stable) Firefox 릴리스에도 들어갈 것이다. Cranelift는 Bytecode Alliance 산하에서 개발된다.
지난 9개월 동안 우리는 Cranelift의 “머신 백엔드”, 즉 특정 CPU 명령어 집합(ISA)을 지원하는 컴파일러 부분을 위한 새로운 프레임워크를 만들었다. 또한 위에서 언급한 AArch64를 위한 새로운 백엔드도 추가했고, Firefox에서 프로덕션으로 사용 가능할 때까지 필요한 기능을 채워 넣었다. 이 글은 백엔드 프레임워크 개편에 들어간 설계 과정을 설명하기 위한 맥락을 제공한다.
움직이는 부품이 많아서 전체를 한 번에 이해하기는 조금 헷갈릴 수 있다. 아래는 Cranelift가 여러 구성 요소들 사이에서 어디에 위치하는지 보여주는 시각적 개요다. 특히 두 개의 주요 Rust 크레이트(와asm 프론트엔드와 codegen 백엔드)와 Cranelift를 사용하는 여러 프로그램을 중심으로 나타냈다.
최근 우리가 Cranelift에서 수행한 작업을 이해하려면 위의 cranelift_codegen 크레이트로 확대해, 이것이 예전에는 어떻게 동작했는지 이야기해야 한다. “CLIF” 입력이란 무엇이고, 컴파일러는 이를 CPU가 실행할 수 있는 머신 코드로 어떻게 변환하는가?
Cranelift는 컴파일 중인 코드를 표현하기 위해 CLIF, 즉 Cranelift IR(중간 표현) 형식을 사용한다. 프로그램 최적화를 수행하는 모든 컴파일러는 어떤 형태로든 IR(Intermediate Representation)을 사용한다. 이는 프로그램이 수행할 수 있는 모든 연산을 표현할 수 있는 가상 명령어 집합 같은 것으로 생각할 수 있다. IR은 보통 실제 ISA보다 단순하며, 작은 수의 잘 정의된 명령어로 구성되어 컴파일러가 프로그램 의미를 쉽게 추론할 수 있도록 설계된다. 또한 IR은 컴파일러가 최종적으로 타깃하는 CPU 아키텍처와 독립적이다. 덕분에 컴파일러의 많은 부분(입력 언어로부터 IR을 생성하는 부분과 IR을 최적화하는 부분 등)을 새로운 CPU 아키텍처로 이식할 때도 재사용할 수 있다. CLIF는 SSA(Static Single Assignment) 형태이며, 기본 블록을 갖는 전통적인 제어 흐름 그래프를 사용한다(이전에는 확장 기본 블록을 허용했으나 지금은 단계적으로 제거되었다). 많은 SSA IR과 달리, CLIF는 명시적인 φ 명령어 대신 블록 파라미터로 φ 노드를 표현한다.
cranelift_codegen 내부에서, 우리가 백엔드 설계를 개편하기 전에는 컴파일 내내 그리고 컴파일러가 최종 머신 코드를 출력할 때까지 프로그램이 CLIF로 유지되었다. 이는 앞서 말한 내용과 모순처럼 보일 수 있다. IR이 머신 독립적이라면, 어떻게 머신 코드를 출력하는 최종 형태가 될 수 있을까?
답은 기존 백엔드가 “합법화(legalization)”와 “인코딩(encodings)” 개념을 중심으로 구축되어 있었다는 점이다. 높은 수준에서의 아이디어는, 모든 Cranelift 명령어는 하나의 머신 명령어에 대응하거나, 혹은 다른 Cranelift 명령어들의 시퀀스로 대체될 수 있다는 것이다. 이런 매핑이 주어지면, 초기 컴파일 단계에서 나온 임의의 머신 독립 명령어들로 시작해, CLIF를 단계적으로 정제(refine)하면서 편집을 수행해 결국 CLIF가 머신 코드와 1:1로 대응하도록 만들 수 있다. 이 과정을 시각화하면 다음과 같다.
매우 단순한 예로, 직접적인 “인코딩”이 머신 명령어에 대응되는 CLIF 명령어로 iadd가 있다. 이는 두 정수를 더한다. 사실상 모든 현대 아키텍처에서 이는 레지스터 두 개를 더하는 간단한 ALU 명령어로 매핑된다.
반면 많은 CLIF 명령어는 깔끔하게 매핑되지 않는다. 일부 산술 명령어가 그 예다. 예를 들어 정수의 이진 표현에서 1로 설정된 비트 수를 세는 CLIF 명령어(popcount)가 있다. 모든 CPU가 이를 위한 단일 명령어를 제공하는 것은 아니므로, 더 긴 비트 조작 시퀀스로 확장될 수 있다. 더 높은 의미 수준에서 정의된 연산도 확장으로 내려갈 수밖에 없다. 예를 들어 Wasm 메모리 접근은 선형 메모리 베이스와 크기를 가져오고, Wasm 주소를 한계와 비교해 바운드 체크를 수행하고, 실제 주소를 계산한 다음 접근을 수행하는 일련의 연산으로 낮춰진다.
따라서 함수 하나를 컴파일할 때, 우리는 CLIF를 순회하며 직접적인 머신 인코딩이 없는 명령어를 찾는다. 각 명령어에 대해 합법화된 시퀀스로 확장하고, 그 시퀀스 안의 명령어들에 대해서도 재귀적으로 같은 작업을 고려한다. 모든 명령어가 머신 인코딩을 가질 때까지 반복한다. 그 시점이 되면 각 명령어의 인코딩에 해당하는 바이트를 출력할 수 있다1.
레거시 Cranelift 백엔드 설계(단일 IR을 유지하며 확장 기반 합법화를 수행)는 장점이 적지 않다. 하지만 예상할 수 있듯 단점도 많다. 각각 몇 가지를 살펴보자.
머신 코드 방출까지 단일 IR 위에서 동작하므로, 동일한 최적화를 여러 단계에 적용할 수 있다. 예를 들어 “Wasm 메모리 접근” 같은 고수준 명령어가 로드, 덧셈, 바운드 체크 시퀀스로 확장된다고 하자. 한 함수에 이런 시퀀스가 많이 나타난다면, 공통 부분(예: Wasm 메모리의 베이스 계산)을 끌어올려 공유할 수도 있다. 즉 합법화 방식은 가능한 많은 코드가 가능한 많은 단계에서 최적화 기회를 갖도록 노출한다. 실제로 레거시 파이프라인은 이 방식으로 동작했다. 합법화 전후로 각각 “pre-opt”와 “post-opt” 최적화 패스를 실행한다.
만약 대부분 의 Cranelift 명령어가 하나의 머신 명령어가 되고, 합법화가 거의 필요 없다면, 이 방식은 매우 빠를 수 있다. 작은 테이블 인덱스로 표현된 “인코딩”을 채우는 단일 순회로 끝나기 때문이다.
확장 기반 합법화가 항상 최적의 코드를 만들지는 않는다. 지금까지는 CLIF→머신의 1:1 또는 1:다 매핑을 봤다. 하지만 어떤 경우에는 여러 CLIF 명령어의 동작을 하나 의 머신 명령어가 구현하기도 한다(다:1 매핑). 효율적인 코드를 생성하려면 이런 명령어를 활용할 수 있어야 한다.
예를 들어 x86에서는 메모리 참조 명령어가 base + scale * index 형태의 주소를 계산할 수 있는데, 여기서 base와 index는 레지스터이고 scale은 1, 2, 4, 8 중 하나다. CLIF에는 이런 주소 모드 개념이 없기 때문에, 주소 계산에서 나타나는 순수한 iadd(덧셈)와 ishl(시프트) 또는 imul(곱셈) 조합을 패턴 매칭하고 싶다. 그리고 load 명령어의 입력이 특정한 덧셈/시프트/곱셈 조합이라는 사실에 기반해 load의 인코딩을 선택해야 한다. 이는 인코딩이 오직 그 명령어의 동작만을 표현한다는 추상화를 깨는 듯 보인다.
원칙적으로는 합법화 규칙에 더 일반적인 패턴 매칭을 구현해 다:1 매핑을 허용할 수도 있다. 그러나 이는 상당한 리팩터링이 될 것이고, 설계를 전체적으로 재고하는 김에 다른 이유들 때문에 이런 식의 땜질을 피하고 싶었다.
단일 IR 접근에는 개념적 어려움이 있다. 어떤 명령어가 어떤 다른 명령어들로 확장되는지에 대한 정적 표현이 없고, 합법화 전체의 정확성과 종료(termination) 속성을 추론하기가 어렵다.
구체적으로, 확장 기반 합법화 규칙은 명령어들 사이에 부분 순서를 따라야 한다. A가 B를 포함하는 시퀀스로 확장된다면, B는 나중에 A로 확장될 수 없다. 실제로 매핑은 대부분 1:1이었고, 1:1이 아닌 경우에도 “입력” 고수준 명령어와 “머신 수준” 명령어 사이에 명확한 영역 분리가 있었다. 하지만 더 복잡한 머신, 또는 타깃 ISA를 더 잘 활용하려는 더 복잡한 매칭 스킴에서는, 백엔드 작성자가 이런 관계를 머릿속으로 정리하기가 큰 어려움이 될 수 있다.
확장 기반 합법화에는 효율성 우려도 있다. 알고리즘 관점에서 우리는 가능하면 고정점(fixpoint) 루프(여기서는 “더 이상 확장이 없을 때까지 계속 확장”)를 피하고 싶다. 실행 시간은 상한이 있긴 하지만, 체인 형태로 이어지는 확장의 최대 깊이에 의존하므로 상한을 추론하기가 다소 어렵다.
또한 제자리 편집(in-place editing)을 가능하게 하는 데이터 구조는 생각보다 느리다. 보통 컴파일러는 IR 명령어를 연결 리스트에 저장해 제자리 편집을 가능하게 한다. 이는 점근적으로는 배열 기반과 비슷한 속도일 수 있지만(랜덤 접근이 필요 없으므로), 현대 CPU에서는 캐시 친화성이나 ILP 친화성이 훨씬 떨어진다. 우리는 대신 명령어 배열을 저장하고 가능하면 단일 패스로 순회하는 것을 선호한다.
우리 구현의 합법화 스킴은 시간이 지나며 다소 다루기 어렵게 커졌다. 내 동료 Benjamin Bouvier가 왜 이 설계를 고치고 싶은지 모든 이유를 매우 설득력 있게 적어둔 GitHub 이슈가 있다: #1141: Kill Recipes With Fire. 이는 이를 만든 엔지니어들을 폄하하는 것이 아니다. 고수준 규칙 명세로부터 합법화기를 생성하는 훌륭한 DSL 기반 코드 생성 단계로 복잡성을 가능한 한 잘 관리해왔다. 그러나 합법화와 인코딩을 추론하는 일이 우리가 바라는 것보다 번거로웠고, 컴파일러 백엔드는 기여자들에게 그다지 접근성이 높지 않았다. 새로운 명령어 하나를 추가하려면 단순히 명령어와 오프코드뿐 아니라 “recipe”, “encoding”, “legalization”까지 학습해야 했고, DSL 안에서 각 조각을 올바르게 맞추는 길을 찾아야 했다. 보다 전통적인 코드 하향 변환 방식은 이런 복잡성의 상당 부분을 피할 수 있다.
단일 레벨 IR에는 근본적인 긴장이 있다. 분석과 최적화가 잘 동작하려면, IR은 특정 연산을 표현하는 방식이 하나뿐이어야 한다. 즉, 작은 수의 정규화된(canonical) 명령어 집합이어야 한다. 반면 머신 수준 표현은 타깃 ISA의 관련 세부 사항을 모두 표현해야 한다. 예를 들어 주소 계산은 머신에서 다양한 방식(서로 다른 주소 지정 모드)으로 나타날 수 있지만, 우리는 모든 분석에서 특별한 주소 계산 오프코드를 처리하고 싶지는 않다. 또한 방출 시점의 암묵적 규칙(“입력이 add인 load는 항상 이 주소 지정 모드가 된다”)도 이상적이지 않다.
단일 IR은 이 스펙트럼의 양 끝을 모두 제대로 만족시킬 수 없고, CLIF가 어느 한쪽에서 멀어질수록 문제가 생겼다. 이 충돌을 해결하려면, 명시적인 명령어 선택기로 연결된 2단계 표현을 갖는 것이 최선이다. CLIF 자체는 가능한 한 단순하고 정규화된 형태로 유지할 수 있고, 동시에 머신 전용 명령어에는 필요한 모든 세부 사항을 담을 수 있다.
이 모든 이유로, Cranelift 개편의 일부이자 새로운 AArch64 백엔드의 전제 조건으로, 우리는 머신 백엔드와 명령어 선택을 위한 새로운 프레임워크를 만들었다. 이 프레임워크에서 머신 백엔드는 CLIF와 분리된 자체 명령어를 정의할 수 있다. 고정점에 도달할 때까지 확장하는 합법화 대신 단일 하향 변환(lowering) 패스를 정의하며, 모든 것은 더 효율적인 데이터 구조 위에서 구축되어 데이터 패스를 신중하게 최적화하고 연결 리스트를 완전히 제거했다. 이제 이 새로운 설계를 설명하겠다.
새 Cranelift 백엔드의 핵심 아이디어는 머신 전용 IR 을 추가하는 것이다. 이는 머신 코드를 잘 표현하도록(즉 IR이 머신 코드에 매우 가깝도록) 특별히 선택된 여러 속성을 가진다. 우리는 이를 VCode라고 부르는데, “virtual-register code(가상 레지스터 코드)”에서 왔다. VCode는 MachInst(머신 명령어)를 담는다. 우리가 선택한 핵심 설계 결정은 다음과 같다.
VCode는 선형(linear) 명령어 시퀀스다. 기본 블록을 순회할 수 있는 제어 흐름 정보는 있지만, 명령어를 쉽게 삽입/삭제하거나 코드 순서를 재배열하기에 적합한 데이터 구조는 아니다. 대신 단일 패스로 VCode로 하향 변환하며, 명령어를 최종(또는 거의 최종) 순서대로 생성한다. 이를 효율적으로 만드는 방법은 후속 글에서 더 다루겠다.
이 설계는 연결 리스트 데이터 구조의 비효율을 피하며, 대신 명령어 배열 위에서 빠른 패스를 가능하게 한다. 또한 MachInst 크기를 비교적 작게 유지했다(AArch64에서 명령어당 16바이트). 이는 코드 생성과 반복 속도에도 도움이 된다.
VCode는 SSA 기반이 아니다. 대신 명령어는 레지스터를 대상으로 동작한다. 하향 변환 중에 우리는 가상 레지스터를 할당한다. VCode가 생성된 후 레지스터 할당기가 적절한 레지스터 배치를 계산하고, 명령어를 제자리에서 편집하여 가상 레지스터를 실제 레지스터로 바꾼다. (둘 다 32비트 표현 공간에 패킹하며, 최상위 비트로 가상/실 레지스터를 구분한다.)
이 레벨에서 SSA를 버리면 SSA 불변식을 유지하는 오버헤드를 피할 수 있고 실제 머신에 더 가깝다. 명령어의 하향 변환은 예를 들어, 목적지 레지스터를 임시로 사용한 뒤 최종적으로 그 레지스터에 값을 쓰는 형태도 허용된다. SSA 형태가 요구되었다면 이 경우 임시값을 할당하고 레지스터 할당기가 이를 다시 같은 레지스터로 병합(coalesce)하기를 기대해야 하는데, 이는 컴파일 시간 오버헤드를 늘린다.
VCode는 MachInst의 컨테이너지만, 머신 백엔드마다 별도의 MachInst 타입이 있다. 머신 독립 부분은 MachInst(Rust의 trait)에 대해 매개변수화되어 있으며, 컴파일러가 빌드되는 특정 타깃에 대해 정적으로 모노모픽(monormorphize)된다.
Rust의 강력한 타입 시스템(예: enum)을 이용해 머신 명령어를 모델링하면, 명령어 도메인이 뒤섞이는 문제(어떤 CLIF 명령어가 머신 독립/의존/둘 다인지?)를 피할 수 있고, 각 백엔드가 인코딩에 필요한 정보를 적절히 저장할 수 있다.
VCode 함수 본문은 대략 다음 정보로 구성된다고 볼 수 있다(단순화한 것이며, 실제 예는 아래에서 더 보인다).
명령어는 단순히 배열에 저장되고, 기본 블록은 배열(명령어) 인덱스 범위로 별도로 기록된다. 앞서 말했듯 이 데이터 구조는 빠른 순회를 위한 것이지 편집을 위한 것이 아니다. 우리는 첫 번째 블록(b0)이 엔트리 블록이 되도록 보장하고, 연속된 블록 인덱스가 연속된 명령어 인덱스 범위를 갖도록(즉 서로 인접하게 배치되도록) 보장한다.
각 명령어는 VCode 컨테이너 관점에서는 거의 불투명(opaque)하지만 몇 가지 예외가 있다. 모든 명령어는 (i) 레지스터 참조, (ii) 분기라면 기본 블록 타깃을 노출한다. 레지스터 참조는 일반적인 “use”와 “def”(읽기와 쓰기)로 분류된다.2
또한 명령어는 가상 레지스터(여기서는 v0..vN) 또는 실 머신 레지스터(여기서는 r0..rN)를 참조할 수 있다. 이 선택은 머신 백엔드가 특정 명령어 또는 ABI(인자 전달 규약) 때문에 특정 레지스터를 사용해야 하는 경우를 가능하게 한다. VCode의 의미론은 레지스터 할당기가 실 레지스터의 라이브 레인지 (def에서 use까지)를 인식하고, 그 라이브 레인지 동안 가상 레지스터를 해당 실 레지스터에 할당하지 않도록 하는 것이다. 할당 후 모든 머신 명령어는 제자리에서 편집되어 실 레지스터만 참조하게 된다.
레지스터와 분기 타깃 외에, VCode에 담긴 명령어는 머신 코드를 방출하기 위해 필요한 다른 어떤 정보든 담을 수 있다. 각 머신 백엔드는 이 정보를 저장하기 위한 고유 타입을 정의한다. 예를 들어 AArch64에서는 다음과 같은(단순화된) 명령어 형식들이 있다.
pub enum Inst {
두 개의 레지스터 소스와 하나의 레지스터 목적지를 갖는 ALU 연산.
AluRRR {
alu_op: ALUOp,
rd: Writable<Reg>,
rn: Reg,
rm: Reg,
},
레지스터 소스와 immediate-12 소스를 갖고 레지스터 목적지로 쓰는 ALU 연산.
AluRRImm12 {
alu_op: ALUOp,
rd: Writable<Reg>,
rn: Reg,
imm12: Imm12,
},
16비트 immediate를 갖는 MOVZ.
MovZ {
rd: Writable<Reg>,
imm: MoveWideConst,
size: OperandSize,
},
2-way 조건 분기. 두 개의 타깃을 포함한다. 방출 시에는 조건 분기 명령어
뒤에 무조건 분기 명령어가 나오지만, 방출 버퍼는 보통 이를 하나의 분기로
접어(collapse)준다. 자세한 내용은 후속 글에서 더 다룬다!
CondBr {
taken: BranchTarget,
not_taken: BranchTarget,
kind: CondBrKind,
},
...
}
이 enum의 각 arm은 예전 백엔드의 “인코딩”과 비슷하다고 볼 수 있지만, 훨씬 더 직관적인 방식으로 정의되어 있다. 예전 Cranelift 백엔드는 DSL로 명령어 인코딩을 정의해야 했고, 인코딩은 숫자 인덱스를 부여받았으며 추가 파라미터는 특수 비트 패킹 인코딩으로 넣었다. 반면 여기서는 명령어를 타입 안전하고 사용하기 쉬운 Rust 데이터 구조로 그대로 저장한다.
VCode 데이터 구조 설계나 명령어 인터페이스에 대해 더 자세히 다루지는 않겠다. 다만 새로운 머신 백엔드에 필요한 명령어 방출 기능은 자신의 명령어 타입에 대해 MachInst trait 구현을 제공하고(그리고 아래에서 설명할 방식으로 하향 변환하면) 구현할 수 있다. 우리는 이것이 예전 DSL 기반 프레임워크에서 백엔드를 개발하는 것보다 훨씬 쉬운 작업이라고 믿고 있으며, 초기 경험도 그 방향을 지지한다.
이제 가장 흥미로운 설계 질문에 도달했다. 머신 독립적인 CLIF 명령어에서 적절한 CPU 명령어 타입을 갖는 VCode로 어떻게 하향 변환하는가? 즉, 확장 기반 합법화와 인코딩 스킴을 무엇으로 대체했는가?
요약하면, CLIF 명령어에 대해 단일 패스 를 수행하며 각 명령어에서 머신 백엔드가 제공하는 함수를 호출해 그 CLIF 명령어를 VCode 명령어(들)로 하향 변환한다. 백엔드는 명령어와 그로 들어오는 값들을 살펴볼 수 있는 “lowering context”를 받으며, 원하는 만큼 “트리 매칭(tree matching)”을 수행할 수 있다(아래 참고). 이는 자연스럽게 1:1, 1:다, 다:1 번역을 허용한다. 다:1 매치가 발생할 때 데드 코드를 제거하기 위해, 실제로 사용되는 값에 대해서만 명령어를 생성하도록 이 패스에 참조 카운팅을 통합했다.
예전 설계는 CLIF→머신에서 1:1 및 1:다 매핑은 가능했지만 다:1은 불가능했다. 이는 주소 지정 모드처럼 특정 연산 조합을 인식해 그 모든 연산을 한 번에 커버하는 특정 명령어를 선택하고 싶을 때 특히 문제가 된다.
먼저 어떤 CLIF 명령어를 루트로 하는 “트리”를 정의해보자. 명령어의 각 인자(argument)에 대해 프로그램을 “위로” 올라가 그 값을 생산한(produce) 정의(def)를 찾을 수 있다. CLIF는 SSA이므로, 명령어 인자는 일반 값(정확히 하나의 정의를 갖는다)이거나 블록 파라미터(전통적인 SSA의 φ 노드)로서 여러 가능한 정의를 나타낸다. 블록 파라미터(φ 노드)에 도달하면 그 지점에서 트리의 리프로 끝난다고 하자. 실제 데이터플로우의 부분집합 인 트리에 대해 패턴 매칭해도 전혀 문제없다(최적이 아닐 수는 있지만 여전히 정당하다). 예를 들어 다음 CLIF 코드가 있다고 하자.
block0(v0: i64, v1: i64, v2: b1):
brnz v2, block1(v0)
jump block1(v1)
block1(v2: i64):
v3 = iconst.i64 64
v4 = iadd.i64 v2, v3
v5 = iadd.i64 v4, v0
v6 = load.i64 v5
return v6
v6 = load.i64 v5라는 load 명령어를 보자. 단순한 코드 생성기는 이를 CPU의 일반적인 load 명령어로 1:1 매핑하고, 주소로 v5를 담고 있는 레지스터를 사용하면 된다. 이는 분명 올바르다. 하지만 더 잘할 수 있다. 예를 들어 AArch64에서는 ldr x0, [x1, x2]처럼 두 레지스터 합 또는 ldr x0, [x1, #64]처럼 레지스터 + 상수 오프셋 주소 지정 모드가 가능하다.
“피연산자 트리(operand tree)”는 다음처럼 그릴 수 있다.
v2와 v0에서 멈추는 이유는 이들이 블록 파라미터이기 때문이다. 어떤 명령어가 이 값을 생산하는지 확정할 수 없다. v3는 상수 64로 대체할 수 있다. 이런 관점에서 load 명령어의 하향 변환은 주소 지정 모드를 비교적 쉽게 선택할 수 있다. (AArch64에서 이 선택을 하는 코드는 여기 있다. 이 경우 레지스터 + 상수 즉시값 형태를 선택하고, v0 + v2를 위한 add를 별도로 생성한다.)
하향 변환 과정에서 실제로 피연산자 트리를 명시적으로 구성하지는 않는다. 대신 머신 백엔드는 각 명령어 입력을 질의할 수 있고, 하향 변환 프레임워크는 구조체를 제공하여 (가능하다면) 생산자 명령어, (가능하다면) 상수 값, 그리고 필요할 때 값을 담게 될 레지스터를 알려준다. 백엔드는 “생산자 명령어”를 통해 트리를 필요한 만큼 위로 탐색할 수 있다. 트리 위쪽의 어떤 명령어 동작을 루트 명령어에 더 이상 결합할 수 없다면, 그 시점부터는 그 값을 레지스터에서 그냥 사용하면 된다. 루트 명령어만을 위한 머신 명령어를 생성하는 것은 언제나 안전하다(다만 최적이 아닐 수 있다).
이 매칭 전략을 사용해 실제 번역은 어떻게 할까? 기본적으로 백엔드는 CLIF 명령어마다 한 번 호출되는 함수를 제공한다. 이 함수는 피연산자 트리의 “루트”에서 실행되며, 원하는 만큼의 머신 명령어를 생성할 수 있다. 이 함수는 사실상 루트 CLIF 명령어의 오프코드에 대한 큰 match 문이며, 각 arm은 필요하면 더 깊이 살펴본다.
다음은 AArch64로 내리는 정수 덧셈의 match-arm을 단순화한 버전이다(전체 버전은 여기).
match op {
// ...
Opcode::Iadd => {
let rd = get_output_reg(ctx, outputs[0]);
let rn = put_input_in_reg(ctx, inputs[0]);
let rm = put_input_in_rse_imm12(ctx, inputs[1]);
let alu_op = choose_32_64(ty, ALUOp::Add32, ALUOp::Add64);
ctx.emit(alu_inst_imm12(alu_op, rd, rn, rm));
}
// ...
}
여기서 여러 헬퍼 함수들에서 약간의 “마법”이 일어난다. put_input_in_reg()는 ctx의 적절한 메서드를 호출해 입력 값이 들어 있는 레지스터를 찾는다. put_input_in_rse_imm12()는 더 흥미롭다. 이는 ResultRSEImm12를 반환하는데, 이는 “레지스터, 시프트된 레지스터, 확장된 레지스터, 또는 12비트 즉시값”이다. 이 선택지는 AArch64에서 add 명령어의 두 번째 인자에 대해 가능한 모든 옵션을 포착한다. 이 헬퍼는 피연산자 트리의 노드를 보고, add에 직접 포함될 수 있는 시프트 또는 0/부호 확장 연산자를 매치하려고 시도한다. 또한 피연산자가 상수인지 확인하고, 그렇다면 12비트 즉시 필드에 들어갈 수 있는지도 본다. 그 어떤 것도 아니면 단순히 레지스터 입력을 사용하도록 폴백한다. alu_inst_imm12()는 이 enum을 분해하고 그에 맞는 Inst arm(AluRRR, AluRRRShift, AluRRRExtend, AluRRImm12)을 선택한다.
끝이다. 여러 연산을 매치하고 머신 명령어를 만들기 위해 합법화와 반복적인 코드 편집이 필요 없다. 우리는 이런 방식으로 하향 변환 로직을 작성하는 것이 꽤 직관적이고 이해하기 쉽다는 것을 확인했다.
이제 명령어 하나는 내릴 수 있다. 그렇다면 명령어가 많은 함수 본문은 어떻게 내릴까? 단순히 명령어를 순회하며 위에서 말한 match-over-opcode 함수를 호출하는 것만으로도 동작은 한다. 하지만 다:1 케이스를 더 효율적으로 처리하고 싶다. 위의 add 로직이 예를 들어 좌측 시프트 연산을 add 명령어에 통합할 수 있다고 하자. 그러면 add 머신 명령어는 시프트의 입력 레지스터를 사용하고 시프트의 출력은 완전히 무시한다. 시프트 연산자의 다른 사용처가 없다면, 그 계산 자체를 아예 하지 않는 것이 맞다. 그렇지 않다면, add에 연산을 합친 의미가 없어진다.
이 문제를 해결하기 위해 일종의 참조 카운팅을 구현한다. 구체적으로는, 어떤 SSA 값이 실제로 사용되는지 추적하고, 그 값의 결과가 사용되거나(또는 반드시 수행되어야 하는 부작용이 있거나) 할 때만 CLIF 명령어에 대한 코드를 생성한다. 이는 데드 코드 제거의 한 형태지만, 단일 하향 변환 패스에 통합되어 있다.
값이 사용되는지 알기 위해, 값마다 카운터를 하나 두고 0으로 초기화한다. 머신 백엔드가 어떤 입력을 레지스터로 사용한다면(상수로 직접 사용하거나 생산자 명령어의 연산을 흡수하는 것이 아니라), 하향 변환 드라이버에 해당 레지스터가 사용되었다고 알린다.
이 방식이 동작하려면 def보다 use를 먼저 봐야 한다. 그래서 함수 본문을 “뒤에서부터” 순회한다. 구체적으로는 포스트오더(postorder)로 순회한다. 이렇게 하면 SSA에서 어떤 명령어를 지배(dominate)하는 명령어보다 먼저 그 명령어를 보게 되므로, use를 def보다 먼저 보게 된다.
마지막으로 부작용(side-effect)을 조심해야 한다. 이는 두 가지 방식으로 중요하다. 첫째, 명령어가 부작용을 갖는다면 그 결과가 사용되지 않더라도 VCode로 내려야 한다. 둘째, 어떤 연산을 다른 연산에 병합할 때, 그로 인해 부작용이 있는 연산이 다른 연산을 넘어 이동하거나 실행 여부가 바뀌어서는 안 된다. 우리는 “색칠(coloring)” 스킴으로 부작용의 정당성을 보장한다(정방향 패스에서 모든 명령어에 색을 부여하고, 각 부작용과 각 새 기본 블록에서 색을 갱신). 생산자 명령어는 (항상 이동 가능하도록) 부작용이 없거나, 또는 소비자 명령어와 같은 색(따라서 다른 부작용을 넘어 이동하지 않음)일 때만 병합 후보로 고려된다.
하향 변환 절차는 다음과 같다(전체 버전은 여기).
쉽다!
실제로 어떻게 동작하는지 보자. 다음 CLIF 코드를 고려해보자.
function %f25(i32, i32) -> i32 {
block0(v0: i32, v1: i32):
v2 = iconst.i32 21
v3 = ishl.i32 v0, v2
v4 = isub.i32 v1, v3
return v4
}
AArch64에서는 좌측 시프트(ishl) 연산이 subtract 연산에 병합되어, ALU 명령어의 레지스터-레지스터-시프트 형태를 사용하길 기대한다. 실제로 그렇게 된다(여기서는 clif-util compile -d --target aarch64 실행 시 RUST_LOG=debug로 볼 수 있는 디버그 덤프 포맷을 보여준다).
VCode {
Entry block: 0
Block 0:
(original IR block: block0)
(instruction range: 0 .. 6)
Inst 0: mov %v0J, x0
Inst 1: mov %v1J, x1
Inst 2: sub %v4Jw, %v1Jw, %v0Jw, LSL 21
Inst 3: mov %v5J, %v4J
Inst 4: mov x0, %v5J
Inst 5: ret
}
이후 레지스터 할당기를 거치고, 프롤로그/에필로그가 붙는다(어떤 레지스터가 파괴(clobber)되는지 알기 전에는 생성할 수 없다). 불필요한 move도 제거되며, 최종적으로는 다음과 같은 코드가 된다.
stp fp, lr, [sp, #-16]!
mov fp, sp
sub w0, w1, w0, LSL 21
mov sp, fp
ldp fp, lr, [sp], #16
ret
이는 AArch64에서 C로부터 호출 가능한, 완전히 유효한 함수다. (만약 이것이 리프 함수임을 알 수 있었다면 스택 프레임 설정과 해제를 피하면서 더 개선할 수도 있었을 텐데! 아쉽게도 최적화 기회는 아직 많이 남아 있다.)
흥미로운 명령어 선택 사례의 다른 예시는 우리의 filetests에 많이 있다. 최근 우리의 즐겨 하는 일 중 하나는 디스어셈블리를 뚫어져라 쳐다보며 비효율적인 번역을 찾아 필요한 패턴 매칭을 개선하는 것이다. 그래서 점점 더 좋아지고 있다(내 뛰어난 동료 Julian Seward는 특정 JIT 실행에서 가장 뜨거운 기본 블록을 덤프하는 커스텀 도구를 만들었고, AArch64 및 x86-64 백엔드에서 상당수의 개선점을 찾아냈다).
이 글에서 많은 내용을 다뤘지만, 새로운 Cranelift 백엔드 프레임워크에 대해 더 이야기할 것이 많다.
두 번째 글에서는 VCode 하향 변환 이후 의 패스들을 가능한 한 효율적으로 설계한 방법을 이야기하고 싶다. 특히 분기 단순화를 수행하는 방식이 핵심인데, 빈 기본 블록을 제거하고 분기 조건을 뒤집고 폴스루 경로를 활용하는 전통적인 단계별 프로세스를 피하고, 대신 바이너리 코드가 방출되는 마지막 순간에 편집을 수행한다(자세한 내용은 MachBuffer 구현을 참고하라).
세 번째 글에서는 추상 해석(abstract interpretation)을 이용해 레지스터 할당기를 위한 심볼릭 체커를 만든 이야기를 하겠다. 이는 퍼징 중 여러 흥미로운 버그를 찾는 데 효과적이었다.
계속 지켜봐 달라!
그동안 Cranelift에 관한 어떤 논의든, 우리의 Bytecode Alliance Zulip 채팅에 자유롭게 참여해주기 바란다(이 글을 위한 토픽도 있다)!
Julian Seward와 Benjamin Bouvier에게 이 글을 리뷰하고 여러 추가 및 수정 사항을 제안해준 것에 감사한다.
1
이 설명은 인코딩이 정해진 뒤에 이어지는 몇몇 매우 중요한 단계를 생략하고 있다는 점에 유의하라. 가장 중요한 것은 레지스터 할당 이다. 이는 IR의 각 값을 어떤 머신 레지스터에 둘지 선택한다. 이 과정에서 값이 스택으로 스필(spill)되거나 스택에서 다시 로드되거나, 혹은 단순히 레지스터 간 이동이 필요할 때 명령어를 삽입해야 할 수도 있다. 그 다음 몇 가지 정리 작업(예: 분기 해석 및 실제 머신 코드 오프셋에 맞춘 분기 형태 최적화)을 거친 뒤, 비로소 인코딩을 사용해 머신 코드를 방출할 수 있다.
2
우리는 또한 use와 def가 동시에 있는 “mod”(modify) 타입의 레지스터 참조를 지원하며, use 지점과 def 지점에 같은 레지스터가 할당되도록 보장한다. 이는 레지스터 할당기에 임시적인 제약을 추가하는 “tied operands”라는 이전 메커니즘을 대체한다. mod는 대신 명령어를 통해 라이브 레인지를 연장함으로써 처리된다.
3
뒤집기(reversal) 스킴은 실제로는 이것보다 조금 더 미묘하다. 단일 CLIF 명령어를 하향 변환할 때는 VCode 명령어를 정방향 순서로 방출하고 싶지만, CLIF 명령어는 역방향으로 방문한다. 이를 위해 CLIF 명령어마다 정방향 순서의 하향 변환된 VCode 명령어 버퍼를 유지한다. 단일 CLIF 명령어가 끝나면, 이를 역순으로 기본 블록용 하향 변환 VCode 버퍼에 복사한다. 블록 내 명령어를 역방향으로 방문하므로, 이 버퍼는 기본 블록의 VCode 시퀀스를 역순으로 담게 된다. 그런 다음 블록 끝에서 이를 다시 뒤집어 VCode 버퍼의 끝에 붙인다. 최종 결과는 CLIF 명령어의 정방향 순서에 대해 각 명령어의 VCode가 정방향 순서로 보이고, 기본 블록도 정방향 순서로 포함되는 것이다(휴!).