Cranelift의 새 백엔드에서 제어 흐름(CFG)을 효율적으로 기계 코드로 내리기 위해 블록 순서 결정과 분기 스트리밍 편집을 결합하는 방법, 그리고 MachBuffer 기반의 분기 피프홀 최적화를 설명한다.
URL: https://cfallin.org/blog/2021/01/22/cranelift-isel-2/
Title: Cranelift, Part 2: Compiler Efficiency, CFGs, and a Branch Peephole Optimizer
이 글은 Cranelift에 관한 3부작 시리즈 중 두 번째입니다. 첫 번째 글에서는 Cranelift의 맥락과 백엔드 코드 생성 인프라를 교체하는 프로젝트 배경을 설명하고, 명령 선택(instruction selection) 문제와 이를 해결하는 방법을 자세히 다뤘습니다. 남은 두 글은 흥미로운 엔지니어링 문제들에 대한 심층 탐구가 될 것입니다.
이번 글에서는 우리 작업의 컴파일러 성능 측면을 더 깊이 파고들고자 합니다. (다음 글에서는 정확성(correctness)을 다룰 것입니다.) 컴파일 속도에 관해 말할 수 있는 흥미로운 주제는 많지만, 특히 어려운 문제 하나는 제어 흐름(control flow) 처리입니다. 즉, Wasm 수준의 구조적 제어 흐름을 IR 수준의 제어 흐름 그래프(CFG)로, 그리고 최종적으로 기계 코드 수준에서 선형 명령 스트림의 분기(branch)로 어떻게 변환하느냐는 문제입니다.
이 변환을 효율적으로 수행하려면 전체 패스 구조에 세심한 주의를 기울여야 하며, 가장 큰 성능 개선은 어떤 작업 범주를 완전히 제거할 수 있을 때 나옵니다. 우리는 전통적인 로워링(lowering) 설계에서 여러 패스(크리티컬 엣지 분할, 블록 순서 결정, 중복 블록 제거, 분기 완화(branch relaxation), 분기 대상 해석(branch target resolution))를, 다른 패스 중에 일어나는 _인라인 변환(inline transforms)_으로 합치는 방식에서 이를 보게 될 것입니다(즉, CLIF—Cranelift IR—를 머신 특화 IR로 내리는 로워링 과정과, 이후 바이너리 방출(emission) 과정 중에).
이 글은 기본적으로 분기를 이해하고 방출 중에 즉석에서 편집하는 “스마트 머신 코드 버퍼”인 MachBuffer와, 최종 기본 블록 순서로 코드를 로워링할 수 있게 해주며 크리티컬 엣지 분할을 암묵적으로 삽입하기 위해 실제로는 물질화(materialize)되지 않는 암시적 그래프를 순회하는 BlockLoweringOrder를 설명합니다. 이 작업은 주로 Cranelift PR #1718에서 이루어졌고, CPU 집약 벤치마크(bz2)에서 컴파일 시간 약 10% 개선, 컴파일+실행 시간 약 25% 개선을 가져왔습니다.
그에 앞서, 제어 흐름 그래프(CFG)를 복습해야 합니다! CFG는 거의 모든 현대 컴파일러에서 사용하는 핵심 자료구조입니다. 간단히 말해, 실행(즉 프로그램 제어)이 명령들을 어떻게 따라갈 수 있는지를 그래프로 나타내며, 그래프의 노드는 선형 명령 시퀀스를, 그래프의 간선은 분기 명령에서 가능한 모든 제어 흐름 전이를 나타냅니다.
이전 글에서 다룬 명령 선택 과정이 끝나면, 함수 본문은 VCode로 로워링되어 있으며 이 VCode는 기본 블록들로 구성됩니다. 기본 블록은 연속된 명령 시퀀스로서, 끝에서만 외부로 분기하며 시작에서만 외부로부터 분기되어 들어옵니다. 즉 “직선형(straight-line)” 코드입니다. 실행은 항상 위에서 시작해 끝으로 진행합니다. 네 개의 기본 블록으로 이루어진 제어 흐름 그래프(CFG) 예시는 아래와 같습니다.
제어 흐름 그래프는 컴파일러에게 매우 훌륭한 자료구조입니다. 실행 흐름을 프로세서가 보는 메모리 상의 명령 순서로 추론하는 대신 그래프 간선으로 명시하면, 많은 분석을 더 쉽게 수행할 수 있습니다. 예를 들어 데이터흐름 분석 문제는 CFG가 가능한 제어 흐름 전이를 쉽게 순회할 수 있게 해주기 때문에 쉽게 풀 수 있습니다. 그래프 기반 표현은 프로그램의 _코드 이동 및 삽입_도 더 쉽게 해줍니다. 명시적인 그래프를 조작하는 것이 암묵적 제어 흐름(예: 조건 분기에서 분기가 안 걸렸을 때의 폴스루)을 머리로 추론하는 것보다 오류가 적습니다. 마지막으로, 그래프 표현은 성능에 중요할 수 있는 블록 순서 문제를 분리해줍니다. 즉, 그래프 노드(블록)를 직렬화(serialize)하는 방법을 별도로 선택할 수 있습니다. 이런 이유로 Cranelift의 CLIF와 VCode를 포함해 대부분의 컴파일러 IR은 CFG 기반입니다.
(역사적 참고: CFG는 고(故) Frances Allen이 발명했으며, 현대 컴파일러가 사용하는 알고리즘적 기반을 크게 확립했습니다. 그녀의 논문 A catalogue of optimizing transformations1은 오늘날 사용되는 중요한 최적화의 거의 전부를 다루고 있으며 읽어볼 가치가 큽니다.)
CFG의 블록 끝 분기를 명령 수준에서 표현하기 위해, 우리는 _양방향 분기(two-way branch)_를 사용할 수 있습니다. 이는 어떤 조건이 참이면 한 기본 블록 타깃으로, 거짓이면 다른 타깃으로 분기하는 명령입니다. (기본 블록은 단일 타깃의 단순한 무조건 분기로 끝날 수도 있습니다.) 위에서는 이런 분기를 if r0, L1, L2처럼 썼습니다. 이는 블록 L0 다음 실행이 r0 값에 따라 L1 또는 L2가 됨을 의미합니다.2
하지만 CPU는 이런 양방향 분기 명령을 드물게만 제공합니다. 대신, 일반적인 ISA의 조건부 제어 흐름은 거의 항상 _폴스루(fallthrough)가 있는 조건 분기_로 제공됩니다. 이는 어떤 조건이 참이면 다른 위치로 분기하고, 그렇지 않으면 아무것도 하지 않고 순차 실행이 계속되게 하는 명령입니다. 이는 하드웨어 구현 관점에서 여러 이유로 더 적합합니다. 두 타깃보다 한 타깃을 인코딩하기가 쉽고(일부 분기에서는 점프 목적지가 꽤 멀 수 있는데, 명령에는 사용할 수 있는 비트 수가 제한적입니다), 또 컴파일러가 후속 블록 중 하나를 바로 뒤에 배치할 수 있는 경우가 보통이기 때문입니다.
동작하는 컴파일러만 원한다면 큰 문제는 아닙니다. 양방향 분기
if r0, L1, L2
대신 다음과 같은 분기 시퀀스로 쓸 수 있습니다.
br_if r0, L1
goto L2
여기서 br_if는 L1로 분기하거나 무조건 분기 goto로 폴스루합니다. 하지만 이는 많은 경우 비효율적입니다. 기본 블록을 L0, L2, L1, L3 순서로 배치했다고 해봅시다.
L0:
...
br_if r0, L1
goto L2
L2:
...
goto L3
L1:
...
goto L3
L3:
...
return
여기에는 불필요한 무조건 분기(goto) 두 개가 있습니다. 각각은 바로 다음 명령으로 쓸데없이 점프합니다. 우리는 _폴스루_를 이용해 둘 다 부작용 없이 제거할 수 있습니다. 즉 한 블록의 끝에서 다음 블록의 시작으로 바로 실행이 이어지게 합니다.
L0:
...
br_if r0, L1
// ** 아니면, L2로 폴스루 **
L2:
...
goto L3
L1:
...
// ** 항상 L3로 폴스루 **
L3:
...
return
이는 쉬운 문제처럼 보입니다. 분기가 중복인지 인식하고 제거하면 되죠? 네, 맞습니다. 하지만 어떤 경우에는 훨씬 더 잘할 수 있습니다. 아래에서 이 문제를 상당히 더 깊게 파고들겠습니다!
지금까지는 사람이 읽기 쉬운 방식으로, 명령 스트림의 위치를 참조하기 위해 _레이블(label)_을 사용해 기계 명령을 썼습니다. 하지만 하드웨어 수준에서는 이런 레이블이 존재하지 않습니다. 대신 기계 코드 분기는 타깃 _주소_를(대개 분기 명령으로부터의 상대 _오프셋_으로) 담습니다. 즉 goto L3가 아니라 goto +32를 보게 됩니다.
이는 struct로 된 명령 리스트에서 기계 코드를 방출할 때 여러 복잡성을 낳습니다. 가장 기본적으로는 레이블을 오프셋으로 해석한 후 해당 분기를 패치해야 합니다. 이는 링커(linker)의 작업과 유사합니다(다만 더 낮은 수준). 배치를 정한 뒤 심볼을 구체 값으로 해석하고, _재배치(relocation)_에 따라 코드가 심볼을 참조하도록 편집합니다. 즉, 분기를 방출할 때마다(우리 MachBackend에서는 relocation, 또는 “label use”) 나중에 다시 돌아와서 해석된 레이블 오프셋으로 분기를 패치하도록 기록합니다.
두 번째이자 더 흥미로운 문제는, 모든 분기 명령이 반드시 모든 가능한 레이블을 참조할 수 있는 것은 아니라는 점입니다! 구체적으로 AArch64에서는 조건 분기 범위가 ±1MB, 무조건 분기 범위가 ±128MB입니다. 이는 명령 인코딩상의 제약에서 비롯됩니다. 특히 ARM/MIPS/RISC-V처럼 고정 길이 명령 ISA에서는, 명령 워드에 포함되는 즉시 점프 오프셋에 사용할 수 있는 비트가 머신 워드 전체보다 적습니다. (명령은 항상 워드 크기이고, opcode와 조건 코드에도 비트가 필요합니다!) x86에서는 다른 이유로 제한이 있습니다. 가변 길이 인코딩에서 1바이트 오프셋(±128바이트) 또는 4바이트 오프셋(±2GB)을 선택할 수 있습니다.
따라서 멀리 있는 레이블로 분기하려면, 어떤 머신에서는 기본적으로 선택된 분기 종류 대신 다른 분기를 사용하거나, 원래 분기가 도달할 수 있는 _다른 분기_를 타깃으로 삼고 그 분기가 특수한 긴 형태로 원래 목적지로 가도록 하는 간접(indirection) 형태를 사용해야 합니다. 전자는 모든 코드가 로워링되고 배치가 계산되기 전까지 타깃이 범위 내인지 알 수 없어서 까다롭습니다. 그래서 짧은 형태를 낙관적으로 또는 긴 형태를 비관적으로 선택해 로워링한 뒤 나중에 바꿔야 할 수도 있습니다. 더 나쁜 점은, 분기를 더 짧거나 긴 형태로 편집하면 길이가 변해 다른 타깃이 범위에 들어오거나 나갈 수 있다는 것입니다. 가장 일반적인 해법에서는, 변화가 더 이상 없을 때까지 반복하는 “고정점(fixpoint) 문제”가 됩니다.
지금까지는 정확한 기계 코드를 만드는 방법이 있습니다. 두 타깃 분기를 위해 조건 분기 + 무조건 분기를 방출할 수 있습니다. 분기 타깃을 올바르게 해석하기 위해 모든 타깃이 메모리 어디에든 있을 수 있다고 가정하고 항상 긴 형태를 사용한 뒤, 마지막 패스에서 오프셋을 알게 되면 채워 넣을 수 있습니다.
하지만 우리는 훨씬 더 잘할 수 있습니다! 아래에서는 네 가지 문제와 이를 전통적으로 해결하는 방법을 설명하겠습니다.
앞서 설명했듯이 _분기 폴스루_는 최종 바이너리에서 기본 블록이 어떤 순서로 나타날지 확실히 알게 되면 일부 무조건 분기를 생략할 수 있게 해줍니다. 특히 if r0, label_if_true, label_if_false 같은 양방향 분기를 단순하게 두 개의 단방향 분기로 로워링하면
br_if r0, label_if_true
goto label_if_false
label_if_false:
...
label_if_true:
...
여기에는 완전히 중복되고 쓸모없는 goto가 있습니다! 일반적으로 분기 타깃이 바로 다음 명령이라면 그 분기는 삭제할 수 있습니다.
하지만 조금 더 복잡한 경우에도 개선이 가능합니다. 위의 반대(뒤집힌) 버전을 생각해봅시다.
br_if r0, label_if_false
goto label_if_true
label_if_false:
...
label_if_true:
...
여기서는 어떤 분기도 폴스루로 분기하지 않으니 둘 다 필요해 보일 수 있습니다. 하지만 실제로 대부분의 CPU 아키텍처에서 조건 분기는 _반전 형태_를 갖습니다. 예를 들어 x86의 JE(같으면 점프)는 JNE(같지 않으면 점프)로 반전할 수 있습니다. 분기 조건까지 편집할 수 있다면, 위 코드를 다음처럼 바꿀 수 있습니다.
br_if_not r0, label_if_true
label_if_false:
...
label_if_true:
...
이는 실제로 많은 추가 분기를 제거합니다.
최적화 후 어떤 기본 블록이 마지막의 무조건 분기 외에는 완전히 비어 있는 경우가 있습니다. if 또는 else 블록의 코드가 전부 최적화로 제거되거나 함수 본문의 다른 곳으로 이동한 경우에 생길 수 있습니다. 또는 블록이 _크리티컬 엣지 분할_을 위해 삽입된 경우에도 발생할 수 있습니다(아래 참조).
따라서 흔한 최적화가 _점프 스레딩(jump threading)_입니다. 한 분기가 다른 분기로 곧바로 향하면, 첫 분기를 최종 타깃으로 편집할 수 있습니다. 일반화하면, 여러 번의 분기를 “추적(chase)”하여 중간 단계를 제거할 수 있습니다. 예를 들어
...
goto L1
L1:
goto L2
L2:
goto L3
L3:
...
는 다음처럼 될 수 있습니다.
...
goto L3 // <--- 편집된 분기
L1:
goto L2
L2:
goto L3
L3:
...
여기서 중간 분기들은 _제거되지 않았음_에 주의하세요. 다른 분기들의 타깃일 수도 있습니다. 우리는 첫 분기에서 출발할 때 이들을 건너뜁니다. 하지만 이 중간 분기들이 다른 방식으로도 사용되지 않음을 알 수 있다면, 삭제해 코드 크기를 줄일 수 있습니다.
앞서 말했듯 “분기 완화” 문제는 각 분기 명령에 대해 여러 형태 중 하나를 선택해야 하며, 각 형태는 도달 범위(현재 PC 위치로부터의 최대 거리)가 다를 수 있다는 점입니다. 이는 필요한 범위가 분기와 타깃의 최종 위치에 달려 있고, 그 위치는 기계 코드에서의 명령 크기에 달려 있는데, 그 명령들 중 일부는 분기라는 점에서 복잡합니다. 즉 순환 의존성이 있습니다.
프로세서 주소 공간의 임의 위치로 분기하는 어떤 방법은 항상 존재하므로, 최악의 경우 분기 형태를 쓰는 사소하지만 비효율적인 해법은 항상 있습니다. 하지만 대부분의 분기는 비교적 작은 오프셋을 향하므로 보통은 훨씬 더 잘할 수 있습니다.
일반적인 해결법은 “고정점 계산(fixpoint computation)”을 포함합니다. 즉 더 이상 개선이 남지 않을 때까지 반복 루프를 돌립니다. “완화(relaxation)”라는 이름은, 타깃이 범위 내임을 알게 되면 더 최적 형태로 분기를 바꾸고, 그로 인해 다른 완화가 가능한지 보기 위해 코드 오프셋을 다시 계산하는 과정에서 나옵니다. 분기 범위와 분기 명령 크기의 관계가 단조적(필요 범위가 더 작으면 더 짧은 명령이 가능)이라면, 이는 항상 유일한 고정점으로 수렴합니다. 하지만 비용이 클 수 있고, 코드 편집/오프셋 재계산을 빠르게 하려면 자료구조 설계가 까다롭습니다.
여러 이유로 우리는 CFG에서 _크리티컬 엣지(critical edge)_를 분할(split)하고 싶습니다. 크리티컬 엣지는 여러 out-edge를 가진 블록에서 나와, 여러 in-edge를 가진 블록으로 들어가는 제어 흐름 전이 간선입니다. 어떤 크리티컬 엣지를 따라갈 때만 실행되어야 하는 코드를 삽입해야 하는 경우가 있습니다. 예를 들어 레지스터 할당기는 타깃 블록이 기대하는 레지스터 배치에 맞추기 위해 레지스터 간 값을 옮기는 “픽스업(fixup)”이 필요할 수 있습니다. 이런 코드를 어디에 넣을 수 있을까요? 점프 전에 넣으면 어떤 out-edge를 타든 실행됩니다. 점프 타깃에 넣으면 타깃 블록으로 들어오는 모든 경로에서 실행됩니다.
해결책은 크리티컬 엣지를 “분할”하는 것입니다. 즉 새 기본 블록을 만들고, 분기가 이 블록을 가리키도록 편집한 뒤, 그 블록에서 원래 타깃으로 무조건 분기하도록 합니다. 이 기본 블록은 필요한 픽스업 코드를 삽입할 수 있는 자리이며, 한 특정 블록에서 다른 특정 블록으로 넘어갈 때만 실행됩니다. 크리티컬 엣지 분할은 아래 그림에 나타나 있습니다.
이 문제를 처리하는 방법은 여러 가지가 있습니다. 모든 크리티컬 엣지를 미리 분할하거나, 필요할 때만 주문형으로 분할할 수 있습니다. 후자는 CFG를 제자리에서 편집해야 하고, 여러 이유로 이는 피하고 싶습니다. 많은 분석 결과를 무효화하고 자료구조를 복잡하게 만들기 때문입니다. 또한 많은 알고리즘을 이미 분할된 엣지가 있다고 가정하면 더 쉽게 추론할 수 있습니다. 하지만 모든 엣지를 분할하면 빈 블록이 많이 생깁니다. _대부분_의 경우 엣지에 픽스업 코드를 넣을 필요가 없기 때문입니다. 추가로 엣지를 분할하면 분할 블록을 어디에 둘지 문제가 됩니다. 가장 단순하게 함수 끝에 붙이면, 분기 폴스루 단순화 기회를 크게 줄일 것입니다. 선행/후행 블록 근처에 두는 더 똑똑한 휴리스틱이 낫습니다.
이 모든 문제에 대한 전통적 접근은 작업을 여러 _패스_로 분해하고, 그 패스들에서 _제자리 편집(in-place edits)_을 수행하는 것입니다. 예를 들어 LLVM에서는 IR이 머신 특화 형태(MachineBasicBlock의 MachineFunction)로 로워링되며, 명시적 레이아웃과 머신 수준 분기 명령을 갖습니다. 그 후 레이아웃 변경 시 분기를 갱신하는 등 각종 편집이 이뤄집니다.
예를 들어 다음 패스 시퀀스는 위 이슈 대부분을 처리할 수 있습니다.
모든 크리티컬 엣지를 분할하고, 분할 블록을 선행 블록 뒤에 배치한다. (LLVM의 SplitCriticalEdges 패스.)
다른 최적화 및 레지스터 할당을 수행한다. 이 과정에서 분할 블록을 사용할 수 있다.
점프 스레딩 변환을 수행한다. 이는 빈 블록을 통한 제어 흐름 전이를 제거한다. (LLVM의 BranchFolding 패스.)
도달 가능성(reachability)을 계산하고, “죽은 블록”(더 이상 도달 불가능한 블록)을 삭제한다. (LLVM에서는 BranchFolding이 함께 수행.)
점프 거리를 최소화하고 가능하면 각 블록 뒤에 적어도 하나의 후속 블록을 바로 배치하려는 블록 순서를 계산한다. (LLVM의 MachineBlockPlacement 패스.)
이 블록 순서를 사용해 CFG 노드(블록)에서 단일 머신 명령 스트림으로 코드를 선형화한다. (LLVM에서는 블록이 먼저 MachineFunction으로 로워링된 후 MachineBlockPlacement로 재정렬된다.)
폴스루 블록으로 가는 분기를 제거하고, 추가 폴스루를 만드는 조건을 반전한다.
현재 명령 시퀀스의 머신 코드 크기에 기반해 블록 오프셋을 계산하되, 모든 분기에 대해 최악의 크기를 가정한다.
분기들을 스캔하며 블록 위치가 가까운 타깃을 허용해 더 짧은 형태가 가능한지 검사한다. 가능하면 분기를 갱신하고 블록 오프셋을 다시 계산한다. 고정점까지 반복한다. (LLVM의 BranchRelaxation 패스가 수행.)
최종 오프셋을 사용해 분기 타깃을 채워 넣는다. 이제 분기는 기계 코드 방출에 적합한 형태가 된다.
분명 위 방법은 동작하며, 블록 배치 휴리스틱을 특히 잘 다듬으면 매우 좋은 코드를 생성할 수 있습니다. 하지만 위 단계들은 많은 제자리 편집을 요구합니다. 이는 느리며(편집할 때마다 일부 작업을 다시 수행) 편집을 허용하는 자료구조(예: 연결 리스트)를 강제해 IR의 다른 모든 연산에도 비용을 부과합니다. 더 좋은 방법은 없을까요?
위에서 설명한 코드 변환 패스 일부를 피할 수 있다면 이상적일 것입니다. 가능할까요? 실제로는 위의 기능적 동등물을 전부 다른, 이미 존재하던 작업 일부로 수행할 수 있습니다.
최종 블록 순서를 미리 결정하고, 이 순서로 CLIF→VCode 로워링을 수행하면 VCode를 나중에 재정렬할 필요가 없습니다. 이미 선형화되어 있습니다. 또한 이 로워링 과정에서 크리티컬 엣지 분할을 삽입할 수 있습니다.
그 외 모든 작업—조건 반전, 점프 스레딩, 죽은 블록 제거, 다양한 분기 크기 처리—은 기계 코드 방출 중의 스트리밍 방식으로 할 수 있습니다! 핵심 통찰은 “피프홀 최적화” 같은 것을 할 수 있다는 것입니다. 방출 버퍼의 _꼬리(tail)_에서 분기를 즉시 삭제하고 재방출(re-emit)할 수 있습니다. 단일 방출 스캔 동안 도달 가능성, 현재 방출 지점의 레이블, 코드 앞쪽의 미해결 레이블 참조 목록, 단거리 분기의 “마감기한(deadline)” 같은 보조 상태를 추적하면, 버퍼 끝에서 몇 개의 연속된 분기 이상으로는 절대로 되돌아가지 않고도 필요한 모든 작업을 수행할 수 있습니다.
각 항목을 더 자세히 살펴봅시다!
이전 글)에서 설명한 명령 선택 파이프라인의 일부로, 우리는 CLIF의 기본 블록을 순회하며 각 블록의 코드를 VCode 명령으로 로워링해야 합니다. 이후 VCode를 재정렬할 필요가 없도록, 이 순회를 최종 기계 코드 레이아웃과 같은 순서로 하고 싶습니다.
로워링 알고리즘이 요구하는 유일한 제약은 _값 사용(value uses)_을 _값 정의(value defs)_보다 먼저 보아야 한다는 것입니다. 이는 어떤 블록도 그 지배자(dominator)보다 먼저 방문하지 않도록 하면 보장할 수 있습니다. 그 외에는 로워링 순서에 상당한 자유가 있습니다.
그게 전부라면 후위 순회(postorder)로 끝낼 수 있습니다. 하지만 문제를 복잡하게 하는 요소가 하나 더 있습니다. 바로 크리티컬 엣지 분할입니다!
앞서 말했듯 크리티컬 엣지를 전부 미리 분할하거나 나중에 제자리 편집을 해야 합니다. 제자리 편집의 복잡성을 피하려고 우리는 전부 분할합니다. 이는 CFG 로워링 관점에서 저렴합니다. 왜냐하면 이후 분기 최적화가 빈 블록을 거의 공짜로 제거하기 때문입니다. (블록 수가 늘면 레지스터 할당기의 분석 비용이 늘 수 있지만, 실제로 큰 문제가 되지 않았습니다.)
과제는 이러한 블록들을 즉석에서 올바른 위치에 생성하는 것입니다. 로워링 순서를 생성하기 위해, 우리는 실제로 물질화되지 않는 _가상 그래프(virtual graph)_를 정의합니다. 이 그래프의 노드는 CLIF 블록과 간선으로 암시되며(모든 CLIF 간선은 분할-엣지 블록이 됨), 간선은 후속자 함수(successor function)로만 정의됩니다. 로워링 순서를 만들기 위해 우리는 이 가상 그래프에서 깊이 우선 탐색(DFS)을 수행하고, 그 후위 순회(postorder)를 기록합니다. 이 후위 순회는 요구사항대로 사용을 정의보다 먼저 보게 함을 보장합니다. DFS 자체도 블록 배치에 꽤 좋은 휴리스틱입니다. 구조적 제어 흐름 코드를 계층적 단위로 묶어주는 경향이 있기 때문입니다.
구현에는 모든 엣지가 아니라 크리티컬 엣지만 분할하도록 하는 추가 디테일, 로워링된 블록을 생성하는 즉시 블록-후속자 정보를 기록해 이후 백엔드 단계가 재계산하지 않도록 하는 점, 그리고 기타 작은 최적화가 있습니다.
아래 그림은 CLIF 수준 CFG를 분할 엣지로 변환하고 엣지-블록을 병합한 다음 개념적으로 선형화한 것을 보여줍니다. 또한 DFS를 구동하기 위해 실제로 정의된 후속자 함수를 보여줍니다. 분할-엣지 CFG를 순진하게 로워링하면 14개의 분기(14개의 CFG 간선 때문)가 생기지만, 최종 로워링된 기계 코드는 4개의 분기만 포함하면서도 어떤 CFG 엣지에도 필요한 픽스업 명령을 넣을 수 있는 슬롯을 제공합니다.
VCode를 로워링한 뒤에는 기계 코드를 방출해야 합니다! 전통적 설계에서는 단 한 바이트의 기계 코드도 만들기 전에 선형화, 여러 분기 최적화, 분기 타깃 해석이 필요합니다. 하지만 우리는 훨씬 더 잘할 수 있습니다.
Cranelift 설계에서 머신 백엔드는 모든 조건 분기를 _순진하게 조건+무조건의 양방향 조합_으로 MachBuffer라는 기계 코드 버퍼에 방출합니다. 그러나 중요한 점은 MachBuffer가 단순한 Vec<u8>가 아니라는 것입니다. 이는 (많은) 내용에 대해 알고 있습니다. 예를 들어 분기가 어디에 있는지, 분기 타깃이 무엇인지, 필요하면 분기를 어떻게 반전할지 등을 알고 있습니다.
MachBuffer는 코드가 방출되는 동안 _스트리밍 편집(streaming edits)_을 수행하여, 버퍼의 접미(suffix)—끝까지의 연속된 바이트, 즉 현재 방출 지점—만을 편집해 가능하면 양방향 분기 조합을 더 단순한 형태로 바꿉니다.
머신 백엔드가 보는 추상화는 다음과 같습니다.
MachBuffer는 기계 코드 바이트를 방출할 수 있게 해준다.
우리가 방금 방출한 기계 코드 바이트의 특정 구간이 _분기_임을 MachBuffer에 알릴 수 있다. 조건/무조건 여부, 조건 분기라면 반전 방법, 그리고 분기 타깃 _레이블_을 함께 제공한다.
현재 방출 지점에 레이블을 _바인드(bind)_할 수 있다.
MachBuffer는 LabelUse 트레이트 구현으로 파라미터화되는데, 이는 분기 타깃 참조의 여러 종류, 해석된 오프셋으로 기계 코드를 패치하는 방법, 그리고 원래 분기가 더 멀리 도달하기 위해 간접할 수 있는 더 긴 형태의 분기(베니어, veneer)를 _방출_하는 방법을 정의한다.
이것이 전부입니다! MachBuffer가 뒤에서 모든 일을 합니다. 분기를 방출하면 때로는 바이트를 “씹어 먹고(chomp)”(즉 잘라내고) 레이블을 정의하면 때로는 지연된 픽스업 목록을 스캔해 앞쪽 기계 코드를 패치합니다.
아래는 (단순화한) 예시입니다. 머신 백엔드는 항상 조건+무조건 분기를 방출해 양방향 분기를 순진하게 구현합니다(예: 기본 블록 L0의 끝). 또한 MachBuffer에 레이블 위치, 분기 위치, 분기 타깃 레이블, 조건 분기 반전 방법을 설명하는 메타데이터를 제공합니다. MachBuffer는 코드가 방출되는 동안 나열된 스트리밍 편집을 수행해, 중간 버퍼링이나 추가 패스 없이 오른쪽의 최종 기계 코드를 만들어냅니다. 아래에서 이 편집이 어떻게 이뤄지는지 더 자세히 설명하겠습니다.
MachBuffer 설계의 핵심 통찰은, “가장 최근”의 분기들—정확히는 버퍼 꼬리에 연속으로 붙어 있는 분기들—을 추적하면 코드가 방출되는 동안 버퍼 꼬리에서 분기를 편집할 수 있다는 점입니다.
첫 번째 최적화는 _분기 반전(branch inversion)_이며, 이는 때때로 무조건 분기를 제거할 수 있습니다. 위 예에서 백엔드가 기본 블록 L0의 모든 기계 코드 바이트를 방출했을 때, MachBuffer는 꼬리에 연속된 마지막 두 분기가 L1로 가는 조건 분기와 L2로 가는 무조건 분기라는 것을 알고 있습니다. 그 다음 레이블 L1(첫 분기의 타깃)이 이 오프셋에 바인드되는 것을 보면, 간단한 규칙을 적용할 수 있습니다. 즉, 바로 뒤에 무조건 분기가 따라오는 조건 분기는 반전할 수 있고 무조건 분기는 제거할 수 있습니다. 중요한 점은 이 분기들이 _꼬리에 연속_되어 있기 때문에 편집이 이미 해석된 어떤 오프셋도 바꾸지 않는다는 것입니다. 우리는 여기서 코드 크기를 줄여도 안전하며, 이후 방출되는 코드의 오프셋은 추가 픽스업 없이도 올바릅니다.
다르게 말하면, 우리의 접근은 코드를 절대로 이동시키지 않습니다. 대신, 방출 직후에만, 코드 방출이 분기를 지나 계속 진행하기 전에, 방금 방출한 분기를 때로는 _삭제하거나 조정_합니다.
다음 최적화는 _점프 스레딩_과 _죽은 블록 제거(dead-block removal)_입니다. 점프 스레딩은 점프 체인 중 중간 단계를 없애는 것입니다. X로 가는 점프로 가는 점프는 X로 바로 가는 점프가 됩니다. 우리는 이를 위해 레이블→레이블 별칭(alias)을 추적하는 _최신의(alias) 테이블_을 유지합니다. 이 테이블은 무조건 점프가 방출되고 어떤 레이블이 그 주소에 바인드될 때 갱신됩니다. 이후 레이블을 최종 오프셋으로 해석할 때 별칭 테이블을 통해 간접합니다. 두 번째 작업인 죽은 블록 제거는 현재 버퍼 꼬리의 _도달 가능성_을 추적하는 부수 효과로 일어납니다. (i) 무조건 점프 바로 뒤이고, (ii) 거기에 바인드된 레이블이 없는 오프셋은 도달 불가능합니다. 도달 불가능한 오프셋에서의 무조건 점프는 생략할 수 있습니다. (사실 도달 불가능한 오프셋의 어떤 코드도 제거할 수 있지만, 단순함과 정확성 추론을 위해 MachBuffer의 편집을 분기 명령으로 명시된 코드에만 제한합니다.)
이것이 올바르게 동작하려면, 현재 버퍼 꼬리에 바인드된 모든 레이블을 추적하고 버퍼를 chomp(트렁케이트)하거나 레이블을 리다이렉트할 때 이들을 조정해야 합니다. 이 때문에 레이블 바인딩, 레이블 사용 해석, 분기 chomp는 상호작용하는 자료구조 집합에 긴밀히 통합되어 있습니다.
요약하면, 우리는 다음을 추적합니다.
코드를 방출하면, emitted-bytes 버퍼에 추가합니다. 우리는 “현재 오프셋의 레이블 집합”이 유효한 오프셋을 추적해 이 집합을 지연 무효화(lazily invalidate)합니다. 새 코드를 추가하면 암묵적으로 이 집합이 비워집니다.
머신 백엔드가 MachBuffer에 분기 정보를 알려주면, 마지막 연속 분기 목록에 추가합니다. 이 역시 분기가 아닌 코드가 방출되면 무효화됩니다.
label-use가 기록될 때 레이블이 이미 해석되어 있다면, 즉시 버퍼를 패치합니다. 레이블이 어떤 오프셋으로 해석되면 그 오프셋은 바뀔 수 없으므로, 이 픽스업은 한 번만 하면 되고 메타데이터를 버릴 수 있습니다.
모든 분기 단순화는 레이블이 _바인드_될 때 일어납니다. 이때 새로운 행동이 가능해지기 때문입니다. 우리는 다음 알고리즘을 수행합니다(자세한 내용은 MachBuffer::optimize_branches() 참조).
최신 분기 목록에 분기가 있는 동안 루프:
현재 버퍼 꼬리가 최신 분기의 끝보다 뒤라면 종료(그리고 목록 클리어).
꼬리에서 끝나는 최신 분기의 타깃이 현재 꼬리로 해석되면, 그 분기를 chomp하고 루프 재시작.
최신 분기가 무조건 분기이고 자기 자신으로 분기하지 않는다면:
최신 분기가 무조건 분기이고, 그 앞에 또 무조건 분기가 있으며, 이 분기에 바인드된 레이블이 없으면, 도달 불가능이므로 chomp하고 루프 재시작.
최신 분기가 무조건 분기이고, 그 앞이 조건 분기이며, 조건 분기 타깃이 현재 꼬리라면, 조건을 반전하고 무조건 분기를 chomp한 뒤 루프 재시작.
루프가 끝나면 최신 분기 목록을 클리어한다. 더 이상 단순화할 수 없다.
이 알고리즘은 복잡도가 나빠 보일 수 있지만, 실제로는 강하게 제한됩니다. 레이블은 별칭 체인 아래로만 이동하고, 분기당 고정 작업이 수행되며(각 분기는 한 번만 검사되어 조치되거나 제거됨), 전진(progress)이 보장됩니다. 전체적으로 알고리즘은 선형 시간에 동작합니다.
이처럼 선형 시간에 국소적으로 편집하고, 코드 이동을 피하고, 최종 형태로 버퍼에 스트리밍하는 알고리즘은 전통적 백엔드의 다중 패스 제자리 편집 설계보다 점근적으로도, 실제로도 훨씬 낫습니다(CPU는 스트리밍 알고리즘과 최소화된 데이터 이동을 좋아합니다). 훨씬 낮은 비용으로도 더 복잡한 분기 단순화기와 거의 비슷한 품질의 코드를 생성하는 것으로 보입니다.
분기 단순화 알고리즘은 (포스트-옵티마이저) 컴파일러 백엔드의 정확성에 가장 중요한 부분 중 하나입니다. 아마 레지스터 할당기 다음일 것입니다. 매우 미묘하고, 버그는 치명적일 수 있습니다. 잘못된 제어 흐름은 디버깅이 거의 불가능한 잘못된 프로그램 결과(제가 어떻게 아는지 물어보세요! 그리고 여기도요!)부터 심각한 보안 취약점까지 무엇이든 일으킬 수 있습니다.
그래서 우리는 정확성을 보장하기 위해 광범위한 주의를 기울였습니다. 실제로 MachBuffer 구현 라인의 3분의 1 이상이 정확성 증명이며, 여기에 설명된 몇 가지 핵심 불변식(invariant)에 기반합니다. 각 자료구조 변이마다 (i) 불변식이 유지됨과 (ii) 코드 변이가 실행 의미론을 바꾸지 않았음을 보입니다.
또한 Knuth의 인용구 “나는 그것이 맞다고 증명만 했을 뿐, 시도해보진 않았다”에는 큰 지혜가 있으므로(명세와 현실 사이에는 항상 간극이 있으며, 기계 검증된 증명에서 구현을 생성하지 않는 한, 영어 산문 또는 그것의 코드 번역에도 버그가 있을 수 있습니다3), 모든 불변식은 Cranelift 디버그 빌드에서 각 레이블-바인드 이벤트마다 완전히 검사됩니다. 새 백엔드를 두들기는 여러 퍼징(fuzzing) 하네스는 이 검사들을 지속적으로 구동하게 됩니다.
여기서 다루지 않은 분기 단순화와 코드 레이아웃 문제의 미묘한 점이 많습니다! 특히 _분기 베니어(branch veneer)_와 분기 범위 문제를 전혀 다루지 않았습니다. 앞서 “분기 완화” 문제는 봤지만요. MachBuffer는 “마감기한(deadline)”을 추적하여 범위를 벗어난 분기를 처리합니다. 즉 아직 해석되지 않은 레이블이 범위를 벗어나지 않고 바인드될 수 있는 마지막 지점입니다. 마감기한에 도달하면, 해석되지 않은 각 레이블에 대해(대개는 장거리 무조건 분기인) _분기 베니어_의 _섬(island)_을 방출하고, 레이블을 그 분기로 해석합니다. 그러면 마감기한이 연장됩니다. 실제로 섬 방출은 거의 발생하지 않으므로, 원래 분기를 장거리 형태로 되돌아가 편집할 필요를 피하기 위해 이 경우를 비관적으로 처리(간접 한 번 추가)해도 괜찮습니다.
또한 상수 풀(constant pool)도 다루지 않았습니다. 이는 같은 “섬” 메커니즘으로 처리되어, 방출된 기계 코드가 근처 상수 데이터를 참조할 수 있게 합니다.
이번 글은 분기 단순화의 세계를 깊이 탐구했으며, 제어 흐름 처리 및 분기 로워링/단순화를 예로 들어 Cranelift의 새 백엔드를 어떻게 설계해 매우 좋은 컴파일 속도를 얻었는지를 강조했습니다. 우리는 컴파일러 백엔드의 핵심 알고리즘을 _스트리밍 동작을 극대화_하고, _간접을 최소화_하며, _데이터에 대한 패스 수를 최소화_한다는 관점에서 재고하고 세심하게 엔지니어링할 수 있는 또 다른 중요한 기회들이 있다고 믿습니다. 이는 “이론적 표준 컴파일러 교과서 알고리즘”의 세계를 넘어, 영리한 새 설계 트릭을 찾기 위한 문제 해결을 요구한다는 점에서 흥미롭고 신나는 엔지니어링 추구입니다.
이 글 끝부분에서 설명했듯이, _정확성_은 어떤 컴파일러 엔지니어링 노력에서도 중요한 초점입니다—아마도 가장 중요한 초점일 것입니다. 그래서 이 시리즈의 다음(그리고 마지막) 글에서는 정확성을 위해 우리가 어떻게 엔지니어링했는지에 대해, _레지스터 할당기 체커(register allocator checker)_를 심층적으로 다룰 계획입니다. 이는 추상 해석의 한 적용으로 볼 수 있는 새로운 기호적(symbolic) 체커로, 특정 레지스터 할당기 실행이 올바른 할당 결과를 냈음을 _증명_할 수 있게 합니다. 퍼징 프런트엔드에 의해 구동되는 이 체커가, 프로덕션에서는 결코 찾지 못했을 법한 _정말 미묘하고 흥미로운 버그들_을 어떻게 찾아냈는지도 이야기하겠습니다. 그럼 다음 글에서 뵙겠습니다. 즐거운 컴파일 되세요!
이 글에 대한 토론은, 저희 Zulip 인스턴스의 이 스레드에서 자유롭게 참여해 주세요.
이 글을 리뷰하고 매우 유용한 피드백을 준 Benjamin Bouvier에게 감사드립니다! 또한 그림의 오타를 수정해 준 bjorn3에게도 감사합니다.
1
Frances E. Allen and John Cocke. A catalogue of optimizing transformations. In Design and Optimization of Compilers (Prentice-Hall, 1972), pp. 1--30.
2
이는 IR의 분기를 약간 단순화한 것입니다. CLIF(그리고 대부분의 CFG 기반 컴파일러 IR)에는 여러 분기 타입이 있습니다. 또 하나는 정수 인덱스로 N개의 가능한 타깃 중 하나를 선택하는 “switch” 또는 “branch table” 분기입니다. 단일 타깃의 단순 무조건 분기도 있고, return 명령도 기본 블록을 끝내는 일종의 “분기”이긴 하지만 후속자가 없습니다. 중요한 요점은 IR 수준의 분기가 기계 코드 제어 흐름보다 한 단계 높은 추상화로서, 여러(혹은 많은) 타깃 사이의 직접 선택을 하나의 연산으로 제공한다는 것입니다.
3
위의 PR #2083를 보세요. 이는 제가 정확성 증명을 쓴 이후에 발생한 버그로, 증명은 타깃 별칭이 임의로 긴 분기 체인을 지원한다고 가정했지만 실제 구현은 한 단계만 따라갔기 때문에 생겼습니다. 이는 분기 사이클에서 무한 루프를 피하기 위한 의도적인 초기 구현 선택이었습니다. 별칭 테이블에서 사이클을 구성적으로 피할 수 있음이 밝혀졌고, 우리는 이것이 가능함을 신중히 증명한 다음 체인을 따라 리다이렉트를 추적할 수 있게 했습니다. 추가적인 편집증을 위해(비종료하는 컴파일러는 나쁘고 우리는 인간이므로), 우리는 여전히 리다이렉트 추적을 100만 개 분기로 제한하고 그 이상은 패닉하도록 했습니다(조심해서 나쁠 것 없죠). 이 제한은 Wasm 프런트엔드를 사용할 때는(함수 크기 제한 때문에) 절대 도달하지 않으며, 다른 경우에도 도달할 가능성은 극히 낮습니다.