LLVM IR가 무엇이며 어떻게 읽는지, 기본 블록과 SSA·phi 노드, 제어 흐름, 타입과 집합체, GEP, 동기화/원자 연산, 포이즌과 UB, 인트린식, 그리고 실제 코드 생성물을 예로 들어 설명한다.
며칠 전, 이 트윗을 봤습니다. 그 글에서 Andrew Gallant는 어셈블리 대신 LLVM IR을 들여다보는 것이 성능 작업을 하는 사람에게 유용한 도구라고 주장합니다. 불행히도 LLVM 학습 자료는 보통 컴파일러 엔지니어를 대상으로 하고, 일반 실무 프로그래머에게 맞춰져 있지는 않습니다.
이런데도 저는 컴파일러 엔지니어라, 대답은 물론 “최적화기의 IR을 알아야 한다”입니다. 하지만 어셈블리를 읽어서 프로세서가 무엇을 하는지 이해하는 능력이 강력한 도구이듯, LLVM IR을 읽는 것도 정당한 이유가 있다고 봅니다. 1년쯤 전에 어셈블리 입문 글을 썼습니다(후속편을 아직 못 끝냈네요… 💀). 먼저 읽어 보시길 권합니다.
LLVM IR을 배우는 것도 비슷하지만, 이는 컴파일러가 고도로 최적화된 코드를 만들기 위해 무엇을 하는지 이해하는 데 도움을 줍니다. LLVM IR은 매우 인기 있고 그만큼 문서화가 잘 되어 있으며 사양도 꽤 안정적이라, 조금 특이한 프로그래밍 언어처럼 다뤄도 될 정도입니다.
이번 글에서는 LLVM IR이 무엇인지, 그리고 어떻게 읽는지를 파고들어 보겠습니다.
“LLVM”은 컴파일러를 구축하는 데 사용할 수 있는 여러 소프트웨어 컴포넌트를 아우르는 이름입니다. 성능이 중요한 코드를 작성한다면 아마 들어 보셨을 겁니다.
간판 제품은 Clang으로, 고급 C/C++/Objective-C 컴파일러입니다. Clang은 정통 컴파일러 구조를 따릅니다: 소스 코드를 AST로 파싱하고 이를 중간 표현, 즉 “IR”로 내리는 프런트엔드; IR을 더 나은 IR로 변환하는 옵티마이저(혹은 “미들엔드”), 그리고 IR을 특정 플랫폼의 기계어로 변환하는 백엔드가 있습니다.
optimizer (opt)
___
| v
.c file --> AST --> LLVM IR --> assembly
^ ^ ^
parser lowering backend (llc)
\____________________/ \_____________________/
Clang Frontend LLVM
LLVM은 종종 Clang의 옵티마이저와 백엔드 부분만을 가리키기도 합니다. 이는 “LLVM 언어” 또는 “LLVM 어셈블리”를 위한 컴파일러로 생각할 수 있습니다. Clang과 Rust 같은 다른 언어 프런트엔드는 본질적으로 LLVM IR로 컴파일하고, LLVM은 이를 기계어로 다시 컴파일합니다.
LLVM IR은 문서화가 잘 되어 있고… 어느 정도는 안정적입니다. 이는 훌륭한 컴파일 대상이 됩니다. 언어 구현자는 이미 LLVM에 쏟아부어진 수천 시간의 엔지니어링을 재사용할 수 있기 때문입니다. “LLVM IR이 무엇인가?”에 대한 진실의 원천은 LangRef입니다.
LLVM IR은 바이너리 포맷(“비트코드”라고도 함)이기도 하지만, 여기서는 텍스트 포맷만 다룰 것입니다(확장자는 .ll).
LLVM을 타깃팅하는 컴파일러는 최종 산출물 대신 IR을 내보내는 디버깅 플래그를 갖고 있습니다. Clang에서는 예를 들어 clang++ -S -emit-llvm foo.cc, Rust에서는 rustc --emit=llvm-ir foo.rs입니다. Godbolt 역시 이 옵션을 인식해 LLVM IR 출력을 올바르게 보여줍니다.
LLVM IR은 어셈블리 덤프보다 부가 정보가 훨씬 많아서 읽기가 꽤 위압적일 수 있습니다. 다음 함수를 보죠:
pub fn square(x: i32) -> i32 {
x * x
}
“Godbolt” 위젯을 클릭하면 이 함수를 LLVM IR로 내리는 Godbolt로 이동합니다. 코드의 대부분은 메타데이터지만, 처음 보면 정말 압도적입니다!
컴파일러 출력부터 시작하면 난이도 곡선이 가파릅니다. LLVM IR의 모든 복잡성과 마주해야 하기 때문입니다. Rust의 경우 패닉 구현에 쓰이는 예외 처리나, Rust의 보장(예: 널이 아님 포인터)을 LLVM에 전달하는 함수 속성 등을 접하게 될 가능성이 큽니다.
대신 LLVM IR의 기초 문법을 먼저 소개하고, 그 다음에 컴파일러 출력을 읽어 보겠습니다.
LLVM IR의 핵심은 define으로 도입되는 함수 정의입니다. declare도 있는데, 이는 C에서 몸체가 없는 함수와 정확히 같습니다. 외부 심볼을 스코프로 끌어오는 역할을 합니다.
예를 들어, 다음 함수는 인수를 받지 않고 즉시 반환합니다:
define void @do_nothing() {
ret void
}
LLVM IR
함수의 반환 타입(void)은 define 키워드 바로 뒤에 옵니다. 함수 이름은 @로 시작하는데, 여기서 “시길(sigil)” 개념을 접합니다. 사용자가 정의한 모든 심볼은 어떤 종류의 심볼인지 나타내는 시길로 시작합니다. @는 전역과 함수에 사용됩니다. 즉, 주소를 취할 수 있는 것들입니다(값으로 사용될 때 항상 ptr 타입).
함수의 본문은 어셈블리를 닮았습니다. 레이블과 명령어의 목록이죠. 하지만 일반 어셈블리와 달리, 이 명령어들의 구조에는 의미 있는 제약이 있습니다.
이 경우 명령어가 하나뿐입니다. void 타입의 반환입니다. 대부분의 어셈블리 언어와 달리 LLVM IR은 강한 타입을 가지며, 거의 모든 곳에서 명시적 타입 표기를 요구합니다.
다음은 또 다른 사소한 함수입니다.
define void @do_not_call() {
unreachable
}
LLVM IR
이 함수가 호출되면 정의되지 않은 동작(UB)을 유발합니다. unreachable 명령어는 컴파일러가 결코 실행되지 않는다고 가정할 수 있는 코드 경로를 나타냅니다. 이는 x86의 구현되지 않은 ud2 명령어와 달리, 결함을 일으키도록 보장되어 있지 않습니다.
이 점은 LLVM IR과 어셈블리 언어의 중요한 차이입니다. 일부 연산은 잠재적 최적화를 위해 의도적으로 정의되지 않은 상태로 남겨 둡니다. 예를 들어 LLVM은 @do_not_call이 즉시 UB를 유발한다는 점에서, @do_not_call에 대한 모든 호출도 도달 불가능하다고 추론할 수 있고(거기에서 도달 불가능성이 전파됩니다).
정수에 대해서만 동작하는 기본 함수부터 시작해 봅시다. 32비트 정수를 제곱하는 다음 함수를 보죠:
define i32 @square(i32 %x) {
%1 = mul i32 %x, %x
ret i32 %1
}
LLVM IR
이제 함수가 인수를 받고, 여러 명령어를 가집니다.
인수는 i32 %x로 지정합니다. % 시길이 붙은 이름은 로컬 변수와 비슷하지만, 최적화에 더 친화적이 되도록 몇 가지 제약이 있습니다. 뒤에서 보겠지만 실제로는 “변수”가 아닙니다. LLVM은 이를 가끔 “레지스터”라고 부릅니다. 어떤 의미에서 LLVM IR은 무한 개의 레지스터를 가진 추상 기계에 대한 어셈블리입니다. 이 글에서는 %로 시작하는 이름을 “레지스터”라고 부르겠습니다.
i32는 원시 정수 타입입니다. LLVM의 모든 정수 타입은 iN 꼴이며, N은 어떤 값이든 가능합니다(8의 배수일 필요도 없습니다). 부호 있는/없는 타입의 구분은 없습니다. 대신 부호 해석이 필요한 명령어가 어떤 의미를 쓰는지 명시합니다.
첫 번째 명령어는 mul i32로, 두 i32 피연산자를 곱하고 결과 값을 반환합니다. 이 값을 새 레지스터 %11에 대입합니다. 다음 명령어가 이 값을 반환합니다.
다른 산술 연산의 이름도 예상과 같습니다: add, sub, and, or, xor, shl(왼쪽 시프트). 나눗셈과 나머지는 부호 있는 버전(sdiv, srem)과 부호 없는 버전(udiv, urem)이 있습니다. 오른쪽 시프트도 두 가지(ashr는 부호 있는, lshr는 부호 없는)입니다.
독자 연습: 왜
/,%,>>만 부호 있는/없는 버전이 따로 있을까요?
trunc, zext, sext로 한 정수 타입에서 다른 정수 타입으로 변환할 수 있습니다. 각각 잘라내기, 제로 확장, 부호 확장입니다(sext와 zext는 또 다른 부호 있는/없는 쌍이죠). 예를 들어, square 함수가 절대 오버플로되지 않게 하려면 다음처럼 쓸 수 있습니다:
define i64 @square(i32 %x) {
%1 = sext i32 %x to i64
%2 = mul i64 %1, %1
ret i64 %2
}
LLVM IR
여기서는 %x를 i64로 부호 확장(우리는 부호 있는 정수를 제곱한다고 가정)한 뒤 결과를 제곱합니다. trunc와 zext도 sext와 문법이 같습니다.
물론 흥미로운 함수에는 제어 흐름이 있습니다. 0으로 나누기는 UB이므로, 이를 안전하게 처리하는 나눗셈 함수를 만들어 보죠. 아마 이런 느낌일 겁니다:
fn safe_div(n: u64, d: u64) -> u64 {
if d == 0 { return u64::MAX; }
n / d
}
Rust
LLVM의 3항 연산자 격인 select로 해 보려 할 수 있습니다.
define i64 @safe_div(i64 %n, i64 %d) {
%1 = icmp eq i64 %d, 0
%2 = udiv i64 %n, %d
%3 = select i1 %1, i64 -1, i64 %2
ret i64 %3
}
LLVM IR
하지만 문제가 있습니다. 0으로 나누기는 UB2이고, select는 단락 평가를 하지 않습니다. 의미상 x86의 cmov에 더 가깝습니다.
이를 올바르게 컴파일하려면, 일반 분기 연산을 나타내는 br 명령어를 써야 합니다3. C로 치면 br i1 %cond, label %a, label %b는 if (cond) goto a; else goto b;와 같습니다.
다음처럼 쓸 수 있습니다:
define i64 @safe_div(i64 %n, i64 %d) {
%1 = icmp eq i64 %d, 0
br i1 %1, label %iszero, label %nonzero
iszero:
ret i64 -1
nonzero:
%2 = udiv i64 %n, %d
ret i64 %2
}
LLVM IR
이제 함수에 레이블이 생겼고, 이는 br 명령어가 점프 대상으로 사용합니다.
첫 번째 블록에서 d == 0 검사를 합니다. icmp eq로 구현합니다. 이 명령은 i1(LLVM이 불리언에 쓰는 타입)을 반환합니다. 이 결과를 br에 전달하면, 0인지 아닌지에 따라 첫 번째 또는 두 번째 레이블로 점프합니다.
두 번째 블록은 조기 반환으로 “센티널” 값을 돌려줍니다. 세 번째 블록은 자명합니다.
각 블록은 “기본 블록(basic block)”입니다. 제어 흐름이 없는 연산의 시퀀스에, 블록에서 제어 흐름을 이동시키는 명령어 하나가 더해진 구조입니다. 이 블록들이 함수의 제어 흐름 그래프(CFG)를 이룹니다.
다른 “블록 종결자” 명령어들도 몇 가지 있습니다. br의 단일 인자 형태는 단일 레이블을 받아 단순한 무조건 goto가 됩니다. C의 switch와 비슷한 switch도 있습니다:
switch i32 %value, label %default [
i32 0, label %if_zero
i32 1, label %if_one,
; etc
]
LLVM IR
switch의 타입은 정수 타입이어야 합니다. 이 연산을 br 사슬로 표현할 수도 있지만, 별도의 switch 명령어가 있으면 LLVM이 점프 테이블을 생성하기가 더 쉽습니다.
앞서 본 unreachable은 특별한 종결자로, 자체로 제어 흐름을 즉시 발생시키는 것은 아니지만, 도달하면 UB이므로 블록을 종료할 수 있습니다. C++의 std::unreachable()에 해당합니다.
LLVM이 내 코드를 지워 버렸어요!
unreachable은 LLVM이 기본 블록 CFG를 쓰는 이유를 잘 보여 줍니다. 순진한 죽은 코드 제거(DCE) 최적화 패스를 다음처럼 구현할 수 있습니다:
unreachable로 끝나는 모든 블록을 집합에 담습니다.모든 블록에 대해, 종결자가 도달 불가능 집합에 있는 레이블을 참조하면, 그 레이블을 종결자에서 지웁니다. 예를 들어
br i1 %c, label %a, label %b이고 도달 불가능 집합이%a를 포함한다면, 이를br label %b로 바꿀 수 있습니다.(2)에서 블록의 모든 나가는 에지가 삭제되었다면, 종결자를
unreachable로 바꿉니다.도달 불가능 집합의 모든 블록을 삭제합니다.
(1)부터 원하는 만큼 반복합니다.
직관적으로,
unreachable은 CFG를 따라 위쪽으로 “거품처럼” 올라가며, 그 사이의 CFG 일부를 녹여 버립니다. 다른 패스가 UB를 나타내기 위해unreachable을 생성할 수 있는데, 이것과 DCE의 상호작용은 UB로 인해 “컴파일러가 정말로 당신의 코드를 지워 버리는” 결과를 낳습니다.실제 DCE 패스는 훨씬 복잡합니다. 함수 호출이 있으면 블록이 “순수”하여 투명하게 삭제 가능한지 결정하기가 어려워지기 때문입니다.
그런데, a / b + 1처럼 더 복잡한 것을 구현하고 싶다면 어떨까요? 이 식은 중간 결과가 필요하므로, 방금처럼 두 개의 return으로는 처리할 수 없습니다.
이를 우회하는 것은 그리 간단치 않습니다. 서로 다른 블록에서 같은 레지스터에 대입하려고 하면 IR 검증기가 불평합니다. 여기서 정적 단일 대입(SSA)의 개념이 등장합니다.
LLVM IR은 정적 단일 대입 형태(SSA)의 IR입니다. LLVM은 사실 세기 전환기에 현대 SSA 옵티마이저를 만들기 위한 학술 프로젝트로 시작했습니다. 오늘날 SSA는 명령형 코드 최적화에서 매우 유행합니다.
SSA 형태란, 각 레지스터가 함수당 최대 한 번의 명령어에 의해 대입된다는 뜻입니다. 같은 함수의 같은 블록이 실행될 때마다 특정 레지스터의 값은 달라질 수 있지만, 이미 대입된 레지스터를 “변경”할 수는 없습니다.
다시 말해:
이는 최적화 작성에 많은 이점을 줍니다. 예컨대 한 기본 블록 안에서는 특정 레지스터 %x의 모든 사용이 항상 같은 값을 가리키므로, global value numbering이나 상수 접기 같은 최적화를 훨씬 쉽게 쓸 수 있습니다. 블록 전체에서 레지스터의 상태를 따로 추적할 필요가 없기 때문입니다.
SSA에서는 변경을 단일 변수의 여러 “버전”으로 재해석합니다. 예를 들어 x += y는 다음처럼 내릴 수 있습니다.
%x.1 = add i32 %x.0, %y.0
LLVM IR
여기서는 변수의 어떤 버전을 특정 레지스터가 나타내는지 var.n 관례로 표기했습니다(LLVM은 명명 규칙을 강제하지 않습니다).
하지만 루프가 섞이면, 버전을 어떻게 관리해야 할지 불분명합니다. 함수에 존재하는 레지스터의 수는 정적이지만, 루프 반복의 수는 동적이기 때문입니다.
구체적으로, 이 함수는 어떻게 구현할까요?
fn pow(x: u32, y: u32) -> u32 {
let mut r = 1;
for i in 0..y {
r *= x;
}
r
}
Rust
다음처럼 해 보려 할 수 있습니다:
define i32 @pow(i32 %x, i32 %y) {
br label %loop
loop:
%r = add i32 %r, %x ; ERROR: Recursive definition.
%i = add i32 %i, 1 ; ERROR: Recursive definition.
%done = icmp eq i32 %i, %y
br i1 %done, label %exit, label %loop
exit:
ret i32 %r
}
LLVM IR
하지만 문제가 있죠! %r과 %i의 원래 정의는 무엇입니까? IR 검증기는 이 레지스터들이 직접 자신에게 의존한다고 불평할 것이며, 이는 SSA 형태를 위반합니다. 이 함수를 구현하는 “올바른” 방법은 무엇일까요?
한 가지 방법은 LLVM에 물어보는 것입니다! 함수를 서툴게 구현해 두고, 옵티마이저가 정리하게 맡깁니다.
먼저, load와 store 같은 메모리 연산으로 변경을 구현해 보겠습니다. alloca 명령어로 정적으로 크기가 정해진 스택 슬롯을 만들 수 있습니다. 이 명령어는 ptr을 반환합니다[^clang-codegen].
Clang은 어질러 놓고, LLVM이 치운다
사실 Clang과 Rust가 LLVM IR을 생성하는 방식이 이렇습니다. 스택 변수는
alloca로 바뀌고,load와store로 조작됩니다. 임시 값은 대체로%reg로 바뀌지만, 컴파일러가phi명령어를 굳이 만들지 않으려고 추가alloca를 내보내는 경우도 있습니다.이는 꽤 편리합니다. LLVM 밖에서는 SSA 형태를 깊이 생각할 필요가 없어지고, LLVM은 불필요한
alloca를 손쉽게 제거할 수 있기 때문입니다. 제가@pow코드 생성을 위해 쓴 코드는 Rust가 LLVM에 보내는 것과 매우 비슷합니다(다만 우리는 이터레이터를 썼기 때문에 Rust가 추가 쓰레기를 많이 내보내고, LLVM이 이를 제거하려고 애써야 합니다).
define i32 @pow(i32 %x, i32 %y) {
; r과 인덱스를 위한 슬롯을 만들고 초기화합니다.
; 이는 C로 치면
; int i = 0, r = 1;
; 와 같습니다.
%r = alloca i32
%i = alloca i32
store i32 1, ptr %r
store i32 0, ptr %i
br label %loop_start
loop_start:
; 인덱스를 로드하여 y와 같은지 검사합니다.
%i.check = load i32, ptr %i
%done = icmp eq i32 %i.check, %y
br i1 %done, label %exit, label %loop
loop:
; r *= x
%r.old = load i32, ptr %r
%r.new = mul i32 %r.old, %x
store i32 %r.new, ptr %r
; i += 1
%i.old = load i32, ptr %i
%i.new = add i32 %i.old, 1
store i32 %i.new, ptr %i
br label %loop_start
exit:
%r.ret = load i32, ptr %r
ret i32 %r.ret
}
LLVM IR
이제 이를 LLVM 옵티마이저에 통과시킬 수 있습니다. LLVM 배포물의 일부인 opt 명령은 IR에 대해 특정 최적화 패스를 실행합니다. 우리 경우에는 opt -p mem2reg가 필요합니다. 단일 “메모리에서 레지스터로” 패스를 실행합니다. opt --O2 같은 것을 실행해도 clang -O2가 실행하는 것과 유사한4 최적화를 얻을 수 있습니다.
결과는 다음과 같습니다.
; `opt -p mem2reg` 이후
define i32 @pow(i32 %x, i32 %y) {
start:
br label %loop_start
loop_start:
%i.0 = phi i32 [0, %start], [%i.new, %loop]
%r.0 = phi i32 [1, %start], [%r.new, %loop]
%done = icmp eq i32 %i.0, %y
br i1 %done, label %exit, label %loop
loop:
%r.new = mul i32 %r.0, %x
%i.new = add i32 %i.0, 1
br label %loop_start
exit:
ret i32 %r.0
}
LLVM IR
alloca가 사라졌지만, 이제 새로운 명령어 phi가 등장했습니다. “φ 노드”는 원래 SSA 논문에서 온 전문 용어입니다. 그리스 문자 φ는 “phony(가짜)”를 뜻합니다. 이 명령어는 “이 블록으로 어디에서 점프해 왔는지”에 따라 목록에서 값을 선택합니다.
예컨대 phi i32 [0, %start], [%i.new, %loop]는 “start 블록에서 왔다면 0, %loop에서 왔다면 %i.new”라고 말합니다.
다른 모든 명령어와 달리, phi는 현재 블록을 지배(dominate)하지 않는 블록에서 정의된 값을 참조할 수 있습니다. 덕분에 변수의 동적인 버전 수를 다룰 수 있습니다! 동적 실행 문맥에서 무슨 일이 벌어지는지 보죠.
블록
%a가 블록%b를 지배한다는 것은,%b의 모든 선행자가%a이거나%a에 의해 지배되는 블록이라는 뜻입니다. 즉, 첫 블록에서%b로 가는 모든 경로가%a를 통과합니다. 일반적으로 명령어는 현재 블록의 이전 명령어에서 정의된 값이나, 이를 지배하는 블록의 값만 참조할 수 있습니다.
%start는 직접 %loop_start로 점프합니다. 첫 블록은 점프 대상이 될 수 없습니다. 함수의 호출 지점이 선행자이므로 phi를 둘 수 없기 때문입니다.
%loop_start에서, %start에서 들어왔으므로 %i.0과 %r.0은 (플라톤적) 변수 i와 r의 첫 번째 버전, 즉 초기값으로 선택됩니다. 그리고 %loop로 점프합니다.
그다음 %loop는 %loop_start에 의해 지배되므로, 그 안에서는 %i.0과 %r.0을 직접 사용할 수 있습니다. *=와 += 연산이죠. 그런 다음 %loop_start로 돌아갑니다.
%loop_start로 돌아오면 이제 phi가 %i.new와 %r.new를 선택하므로, 이제 %i.0과 %r.0은 i와 r의 두 번째 버전입니다. 귀납적으로, %loop_start의 n번째 실행은 i와 r의 n번째 버전을 가집니다.
마침내 %exit로 가게 되면, %r.0을 사용할 수 있습니다(%loop_start가 %r.0을 지배). 이는 r의 %y번째 버전일 것이고, 우리의 반환 값이 됩니다.
지금까지 한 일을 잠깐 곱씹어 볼 만한 지점입니다. SSA, 지배, phi는 이해하기 까다롭고, 대부분의 IR을 읽는 데 반드시 필요하지는 않습니다. 그러나 컴파일러가 코드를 어떻게 추론하려 하는지의 핵심을 담고 있으므로 이해할 가치가 충분합니다5.
phi와 br만으로도 함수 안에서 임의로 복잡한 제어 흐름을 만들 수 있습니다6.
이제 기본 스칼라 함수를 마련했으니, LLVM의 타입 시스템을 훑어봅시다.
이미 i32 같은 임의 비폭 정수를 봤습니다. i1은 특별해서 불리언 타입으로 쓰입니다. LLVM 최적화는 2의 거듭제곱이 아닌 크기의 정수 타입을 만들어 내기도 합니다.
LLVM에는 float와 double, 그리고 bfloat 같은 다소 이국적인 부동소수 타입도 있습니다. 이들은 고유한 산술 명령어와 다양한 옵션을 사용합니다. 이 글에서는 다루지 않겠습니다. 자세한 내용은 LangRef의 fadd 등 관련 항목을 보세요.
반환값에만 쓰이는 void와, 타입이 없는7 포인터 ptr도 봤습니다.
블록 레이블을 나타내는 의사 타입 label도 있습니다. 이는 런타임에 직접 나타나지 않으며 사용처가 제한됩니다. token과 metadata 타입도 비슷합니다.
배열은 [n x T]로 표기합니다. n은 정수여야 하고 타입은 확정 크기를 가져야 합니다. 예: [1024 x i8]. 크기가 0인 배열도 지원합니다.
구조체는 {T1, T2, ...}로 표기합니다. 예: {i64, ptr}는 Rust의 슬라이스입니다. 구조체 필드는 이름이 없고 인덱스로만 접근합니다. <{...}> 형태는 “packed” 구조체로, 필드 사이의 패딩을 제거합니다. 예: #[repr(packed)]는 이것으로 컴파일됩니다.
벡터는 배열과 비슷하지만 <n x T>로 표기합니다. SIMD 연산에 쓰는 타입을 나타냅니다. 예컨대 <4 x i32> 두 개의 덧셈은 x86에서 AVX2 벡터 덧셈으로 내려갈 수 있습니다. 이 글에서는 SIMD를 더 다루지는 않겠지만, 높은 최적화 단계에서는 LLVM이 스칼라 연산을 벡터 연산으로 병합하기도 하므로 마주칠 수 있습니다.
파일 스코프에서 다음 문법으로 타입 별칭을 만들 수 있습니다.
%Slice = type {i64, ptr}
LLVM IR
이는 문맥에 따라 %T가 타입일 수도 있고, 함수 내부라면 레지스터/레이블일 수도 있음을 뜻합니다.
insertvalue와 extractvalue는 구조체나 배열 타입에서 정적으로 필드를 접근하는 데 씁니다. 예를 들어,
%MyStruct = type {i32, {[5 x i8], i64}}
; Rust 유사 문법으로는 `let v = s.1.0[4];`
%v = extractvalue %MyStruct %s, 1, 0, 4
LLVM IR
insertvalue는 그 반대입니다. 특정 필드가 바뀐 집합체의 사본을 만들어 냅니다. SSA가 이를 금지하므로, 제자리(in-place) 변경은 아닙니다.
; Rust 유사 문법으로는
; let s2 = { let mut s = s; s2.1.1 = 42; s };
%s2 = insertvalue %MyStruct %s, i64 42, 1, 1
LLVM IR
벡터에 대해서는 비슷한 insertelement와 extractelement가 있지만, 문법과 의미가 약간 다릅니다.
마지막으로, “포인터 산술 명령어”인 getelementptr, 줄여서 GEP가 있습니다. GEP는 구조체 안쪽으로의 오프셋 포인터를 계산하는 데 사용할 수 있습니다. 예를 들어,
define ptr @get_inner_in_array(ptr %p, i64 %idx) {
%q = getelementptr %MyStruct, ptr %p, i64 %idx, i32 1, i32 1
ret ptr %q
}
LLVM IR
이 함수는 포인터 하나와 인덱스를 받습니다. 포인터는 겉보기에 %MyStruct의 배열을 가리킵니다. 이 함수는 %p의 %idx번째 요소의 i64 필드를 가리키는 포인터를 반환합니다.
GEP와 extractvalue의 몇 가지 중요한 차이점:
0이 필요합니다(또는 T에 대한 포인터를 길이 1짜리 배열의 포인터로 보는 관점도 가능합니다).LLVM은 GEP 명령어에 대해 도움이 되는8 FAQ를 제공합니다: https://llvm.org/docs/GetElementPtr.html.
IR를 읽을 때 매우 중요한데 특정 범주에 딱 떨어지지 않는 연산들이 있습니다. 언제나 그렇듯 LangRef에 모든 명령어의 전체 설명이 있습니다.
call은 어떤 ptr이든 함수를 호출합니다. 예:
; 인수는 괄호로 전달합니다.
%r = call i32 @my_func(i32 %x)
LLVM IR
여기서 @global 대신 %reg일 수도 있습니다. 그러면 함수 포인터 호출을 의미합니다.
가끔 invoke도 볼 수 있습니다. 이는 C++의 try {} 블록 안에서 함수를 호출하는 것을 구현하는 데 쓰입니다. Rust에서는 드물지만, 일부 C++ 코드에서는 발생할 수 있습니다.
함수 호출 부분은 IR에서 종종 시끄럽습니다. 주석이 매우 많이 달리기 때문입니다.
앞서 본 load와 store는 atomic으로 주석을 달 수 있습니다. 예를 들어 Rust의 AtomicU32::load 같은 것을 구현하는 데 씁니다. 이때는 원자적 순서를 함께 지정해야 합니다. 예:
%v = load atomic i32, ptr %p acquire
LLVM IR
fence 연산은 일반적인 메모리 펜스로, Rust의 std::sync::atomic::fence에 대응합니다.
cmpxchg는 비교-교환(CAS) 원시 연산을 제공합니다. {T, i1}을 반환하는데, 이전 값과 CAS가 성공했는지를 담습니다. cmpxchg weak는 스퍼리어스 실패가 가능한 “약한 CAS”를 구현합니다.
마지막으로, atomicrmw는 읽기-변경-쓰기(예, *p = op(*p, val))를 원자적으로 수행합니다. 이는 AtomicU32::fetch_add 같은 것을 구현하는 데 쓰입니다.
이들 연산은 fence를 제외하고 volatile로도 표시할 수 있습니다. LLVM IR에서는 Rust와 마찬가지로(하지만 C/C++과는 달리) 개별 load와 store가 volatile(즉, 컴파일러에 보이지 않는 부작용이 있음)입니다. volatile은 원자 연산과 결합할 수도 있습니다(예: load atomic volatile), 다만 대부분의 언어는 이를 노출하지 않습니다(오래된 C++ 버전 제외).
bitcast는 Rust의 mem::transmute나 C++의 reinterpret_cast가 궁극적으로 컴파일되는 대상입니다. 이는 집합체가 아닌 타입(정수, 벡터)을 같은 비폭의 다른 타입으로 변환할 수 있습니다. 예를 들어, 부동소수 값을 비트 단위로 보려면 다음처럼 씁니다:
%bits = bitcast double %fp to i64
LLVM IR
또한 예전에는 포인터 타입 간 캐스트(예: i32* → i8*)에도 쓰였습니다. 이제 포인터는 모두 타입이 없는(ptr) 형태이므로 이런 용도는 사라졌습니다.
하지만 bitcast로 포인터와 정수 사이를 캐스팅할 수는 없습니다. 이를 위해서는 inttoptr와 ptrtoint9 명령을 써야 합니다. 문법은 같지만, 포인터-정수 변환과 포인터 프로비넌스의 애매한 의미와 상호작용합니다. 이 부분은 LLVM 의미론에서 여전히 골칫거리입니다. 이 문제의 소개는 Ralf Jung의 글을 보세요.
LangRef에 명시된 방대한 LLVM 인트린식 모음도 있습니다. 예를 들어, 특정 내장 memcpy가 필요하다면 declare로 스코프로 끌어올 수 있습니다:
; ptr %dst, ptr %src, i64 %len, i1 %volatile
declare void @llvm.memcpy.p0.p0.i64(ptr, ptr, i64, i1)
LLVM IR
LLVM 인트린식은 모두 llvm.으로 시작하는 함수입니다. 전부를 파고드는 것은 여기의 범위를 훌쩍 벗어납니다.
부동소수, SIMD, 예외 처리 이야기도 생략합니다. 각각 별도의 글이 필요합니다!
LLVM은 최적화된 코드를 생성하기 위해 존재하며, 최적화는 어떤 머신 상태를 “불가능”하다고 선언해야 우리가 프로그래머가 적은 것을 단순화할 수 있는 때를 알아낼 수 있습니다. 이것이 “정의되지 않은 동작(UB)”입니다.
예를 들어, 앞서 본 unreachable은 LLVM이 실행될 수 없다고 가정합니다. 0으로 나누기나 범위를 벗어난 메모리 접근도 정의되지 않습니다.
대부분의 LLVM UB는 “포이즌 값(poisoned values)” 개념을 통해 흘러갑니다. 포이즌 값은 “한 번에 모든 값을 갖는 것”이라고 볼 수 있으며, 다른 패스와의 일관성은 신경 쓰지 않고 현재 최적화 패스에 편리한 값을 취합니다. 최적화가 포이즌의 사용을 감지하지 못하는 경우, LLVM 관점에서는 임의의 쓰레기 값을 주어도 괜찮습니다. 이는 최적화를 최소화하는 -O0에서 가장 두드러집니다.
포이즌 값을 load, store, call에서 포인터로 쓰는 것은 UB여야 합니다. LLVM이 이를 널 포인터로 선택할 수 있기 때문입니다. 또한 udiv 등의 분모로도 쓸 수 없습니다. LLVM이 0을 선택할 수 있고, 이는 UB이기 때문입니다. br이나 switch에 포이즌을 전달하는 것도 UB로 정의됩니다.
LLVM은 데이터 흐름 분석으로, UB하게 사용된 포이즌 값이 어떤 연산에서 나왔는지 추적하려 노력하며, 따라서 그 연산이 포이즌을 만들 수 없다고 가정합니다. 모든 연산(select와 phi 제외)은 포이즌 입력이 있으면 포이즌을 내놓기 때문에, 역방향 추론으로 LLVM은 UB를 앞으로 전파할 수 있습니다. 이른바 “시간 여행하는 UB”가 여기서 나옵니다.
많은 연산이 포이즌을 생성합니다. 예를 들어 C에서는 부호 있는 오버플로가 UB이므로, 덧셈은 add nsw로 내려갑니다(nsw는 no signed wrap). 오버플로 시 래핑하는 대신, 이 명령은 포이즌을 생성합니다. 부호 없는 버전 nuw도 있습니다.
많은 다른 연산에는 “덜 정의된” 버전이 있습니다. 이는 최적화로 생성되거나, 언어 규칙이 허용할 때 LLVM을 호출하는 컴파일러가 직접 삽입합니다(위의 C 예시처럼). 더 많은 예는 다음과 같습니다:
udiv와 그 친구들은 exact 주석을 가질 수 있고, 나누기의 나머지가 0이 아니면 포이즌을 냅니다.getelementptr에는 inbounds 주석이 있으며, 접근이 실제로 범위를 벗어나면 포이즌을 생성합니다. 이는 순수 산술 연산에서 C의 포인터 산술 제약에 더 가깝게 바뀝니다. inbounds 없는 GEP는 Rust의 <*mut T>::wrapping_offset()에 해당합니다.nnan과 ninf로 표시된 부동소수 연산은 NaN이나 무한대를 내놓는 대신 포이즌을 냅니다(또는 인수가 NaN/무한대일 때).포이즌을 “만드는 것”은 UB가 아닙니다. “사용”만 UB입니다. 이는 대부분의 언어에서의 UB보다 약합니다. C에서는 오버플로가 즉시 UB이지만, LLVM에서는 결코 “목격되지 않는” 오버플로는 그냥 무시됩니다. 이는 최적화의 타당성을 추론하기 위한 더 단순한 작동 의미론입니다. UB는 종종 부작용으로 보아야 합니다. 컴파일러가 프로그램을 망가진 상태로 두는 코드를 생성하기 때문입니다. 예컨대 많은 아키텍처에서 0으로 나누면 결함을 일으킵니다. 즉, UB를 유발하는 연산은 항상 안전하게 재배열할 수 없습니다. “UB를 유발한다”를 “포이즌을 생성한다”로 바꾸면, 대부분의 연산이 순수해지고 자유롭게 재배열할 수 있게 됩니다.
이제 원래의 Rust 예제로 돌아가 봅시다!
pub fn square(x: i32) -> i32 {
x * x
}
메타데이터를 지우고, 가독성을 위해 약간 재배열한 출력입니다.
source_filename = "example.b6eb2c7a6b40b4d2-cgu.0"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; example::square
define i32 @_ZN7example6square17hb32bcde4463f37c3E(i32 %x) unnamed_addr #0 {
start:
%0 = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %x, i32 %x)
%_2.0 = extractvalue { i32, i1 } %0, 0
%_2.1 = extractvalue { i32, i1 } %0, 1
%1 = call i1 @llvm.expect.i1(i1 %_2.1, i1 false)
br i1 %1, label %panic, label %bb1
bb1:
ret i32 %_2.0
panic:
; core::panicking::panic
call void @_ZN4core9panicking5panic17ha338a74a5d65bf6fE(
ptr align 1 @str.0,
i64 33,
ptr align 8 @alloc_1368addac7d22933d93af2809439e507
)
unreachable
}
declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #1
declare i1 @llvm.expect.i1(i1, i1) #2
; core::panicking::panic
declare void @_ZN4core9panicking5panic17ha338a74a5d65bf6fE(ptr align 1, i64, ptr align 8) unnamed_addr #3
@alloc_9be5c135c0f7c91e35e471f025924b11 = private unnamed_addr constant
<{ [15 x i8] }>
<{ [15 x i8] c"/app/example.rs" }>, align 1
@alloc_1368addac7d22933d93af2809439e507 = private unnamed_addr constant
<{ ptr, [16 x i8] }> <{
ptr @alloc_9be5c135c0f7c91e35e471f025924b11,
[16 x i8] c"\0F\00\00\00\00\00\00\00\02\00\00\00\03\00\00\00"
}>, align 8
@str.0 = internal constant [33 x i8] c"attempt to multiply with overflow"
attributes #0 = { nonlazybind uwtable }
attributes #1 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #2 = { nocallback nofree nosync nounwind willreturn memory(none) }
attributes #3 = { cold noinline noreturn nonlazybind uwtable }
LLVM IR
메인 함수는 @_ZN7example6square17hb32bcde4463f37c3E로, example::square의 맹글링된 이름입니다. 이 코드는 디버그 모드에서 컴파일되었기에 오버플로가 발생하면 패닉합니다. 따라서 그 코드를 생성해야 합니다. 첫 연산은 “곱하고 오버플로 여부를 알려 달라”는 LLVM 인트린식을 call하는 것입니다. 이는 (i32, bool)과 같은 것을 반환합니다. extractvalue로 두 값을 각각 추출합니다. 그다음 이 불리언을 @llvm.expect에 통과시키는데, 패닉하는 분기를 “cold”로 취급하라고 옵티마이저에 알려 주는 용도입니다. 성공 분기는 곱셈 결과를 반환하는 ret로 가고, 그렇지 않으면 현재 스레드를 패닉시키는 core::panicking::panic()을 호출하는 함수로 갑니다. 이 함수는 절대 반환하지 않으므로, unreachable로 블록을 끝낼 수 있습니다.
파일의 나머지는 다음으로 이루어집니다:
declare들core::panicking::panic에 대한 declare. 우리가 호출하는 외부 함수는 모두 declare가 필요합니다. 또한 여기에 함수 속성을 매달아 둘 수 있습니다.core::panic::Location과 패닉 메시지에 대한 전역 상수들여기서 속성을 언급하는 것이 좋겠습니다. LLVM에는 함수(와 함수 호출)에 달 수 있는 각종 속성이 있어, 최적화에 유의미한 정보를 기록할 수 있습니다. 예를 들어 @llvm.expect.i1에는 willreturn이 달려 있는데, 이는 이 함수가 결국 반환한다는 뜻입니다. 예컨대 함수 뒤에 오는 UB가 유한 시간 뒤에 발생하는 것이 보장되므로, LLVM은 @llvm.expect.i1 호출이 있더라도 그 뒤의 코드가 도달 불가능하다고 결론낼 수 있습니다. 속성의 전체 목록은 방대하지만, LangRef에 모두 문서화되어 있습니다!
LLVM IR은 방대합니다. 개별 ISA보다도 큽니다. 모든 흥미로운 연산을 포착하는 것이 목적이기 때문입니다. 또한 풍부한 주석 언어를 갖추고 있어, 패스가 이후의 패스가 활용할 정보를 기록할 수 있습니다. 작동 의미론은 최적화가 일어날 공간을 충분히 남겨 두는 동시에, 여러 건전한 최적화를 연달아 적용해도 불건전해지지 않도록 하려 합니다(마지막 부분은 진행 중 과제입니다).
어셈블리를 읽으면 코드가 실행될 때 정확히 무슨 일이 일어날지 드러나지만, 최적화 전후의 IR을 읽으면 컴파일러가 여러분의 코드를 어떻게 “생각”하는지 보게 됩니다. opt로 개별 최적화 패스를 실행해 보는 것도 이해를 돕습니다(사실, “패스 이분 탐색(bisecting)”은 컴파일러 개발에서 강력한 디버깅 기법입니다).
저는 LLVM IR을 읽으면서 컴파일러 세계에 발을 들였습니다. 이 글이 여러분도 더 배우고 싶게 만들길 바랍니다!
%0(레지스터든 레이블이든)을 먼저 정의하고, 그다음 %1, 그다음 %2… 순으로요. 이런 이름은 종종 “임시 결과”를 나타내는 데 쓰입니다.함수가 매개변수의 이름을 지정하지 않으면 암묵적으로 %0, %1 등으로 이름이 붙습니다. 이는 여러분이 명시적으로 사용할 수 있는 첫 숫자 레지스터 이름에 영향을 줍니다. 비슷하게, 함수가 레이블로 시작하지 않으면 다음 숫자 이름이 암묵적으로 첫 블록의 이름이 됩니다.
이는 꽤 혼란을 부를 수 있습니다. 예를 들어 define void @foo(i32, i32) { ... }인 경우 인수는 %0과 %1이 됩니다. 그런데 %2 = add i32 %0, %1
를 쓰려 하면, 첫 블록의 이름이 이미 %2로 점해져 있기 때문에, 파서 오류가 아주 혼란스럽게 튀어나옵니다.↩
select가 쓸모없다는 걸 알아채지 못합니다? 최적화의 정합성을 SMT로 검사하는 Alive2도 이게 유효한 최적화라고 동의하는 듯합니다.beq, bne, bgt, bge가 있습니다. 최적화기 이후 컴파일의 후반 단계에서, LLVM은 특정 LLVM 명령어(또는 그 시퀀스)를 구현하기에 가장 좋은 머신 명령어를 고르는 명령어 선택(isel)을 수행합니다. 이는 맥락 의존적입니다. 예컨대 icmp eq 뒤에 그 결과로 분기하는 br는 beq로 융합하고 싶습니다.Isel은 제 전문 분야가 아니고, 이를 효율적이고 수익성 있게 하는 것은 여전히 활발한 학술 연구 주제입니다.↩
정확히 같지는 않습니다. Clang과 Rust 같은 언어 프런트엔드는 자체 최적화를 수행합니다. 예컨대 어떤 경우 &&를 &로 바꾸지 못하는 LLVM의 버그에 대해 열어 둔 이슈가 있습니다. 이는 Clang이 C/C++에서 LLVM으로 내리는 동안 이 최적화를 수행하기 때문에, Rust가 동등한 최적화를 하지 않는 한 드러나지 않았습니다.↩
더 직관적인 모델은 MLIR 같은 최신 IR에서 사용됩니다. MLIR에서는 다른 블록에서 정의된 변수를 사용할 수 없습니다. 대신 각 블록이 함수 호출처럼 일련의 “인자”를 받습니다. 이는 phi 명령과 동치이지만, 타깃에서 어떤 값을 선택할지 고르는 대신, 각 선행자가 타깃에 무엇을 보낼지 지정하게 됩니다.
각 블록이 “인자”를 갖는다고 보면, 다음과 같은 판타지 문법으로 다시 쓸 수 있습니다. 여기서는 레지스터 이름이 해당 블록의 스코프에 한정됩니다.
;; 실제 LLVM IR이 아님!! ;;
define i32 @pow(i32 %x, i32 %y) {
br %loop_start(i32 0, i32 1)
loop_start(i32 %i, i32 %r)
%done = icmp eq i32 %i.0, %y
br i1 %done, %exit(i32 %r), %loop(i32 %i, i32 %r)
loop(i32 %i, i32 %r)
%r.new = mul i32 %r, %x
%i.new = add i32 %i, 1
br %loop_start(i32 %i, i32 %r)
exit(i32 %r)
ret i32 %r
}
LLVM IR
↩
.dot 파일로 출력하는 “최적화” 패스가 들어 있고, 이는 dot 명령으로 렌더링할 수 있습니다. @safe_div에 대해 다음과 같은 결과를 얻습니다.
이는 복잡한 함수를 이해하는 데 유용합니다. 다음은 Rust의 16진 파싱 함수입니다.
// hex.rs
#[no_mangle]
fn parse_hex(data: &str) -> Option<u64> {
let mut val = 0u64;
for c in data.bytes() {
let digit = match c {
b'0'..=b'9' => c,
b'a'..=b'f' => c - b'a' + 10,
b'A'..=b'F' => c - b'A' + 10,
_ => return None,
};
val = val.checked_mul(16)?;
val = val.checked_add(digit as u64)?;
}
Some(val)
}
Rust
그 다음, 몇 줄의 셸 명령으로 CFG를 생성할 수 있습니다.
$ rustc -O --crate-type lib --emit llvm-ir hex.rs
$ opt -p dot-cfg -o /dev/null hex.ll
Writing '.parse_hex.dot'...
$ dot -Tsvg .parse_hex.dot -o parse_hex.svg
Shell
결과는 이런 난장판입니다.
최적화가 없으면 더 큰 난장판이 나옵니다(대부분의 최적화 패스는 여러 가지 CFG 정리입니다).
연습: 각 기본 블록이 무엇을 하는지 추적해 보세요. SVG를 별도 탭에서 여는 게 좋습니다. 시끄러움이 훨씬 덜한 최적화 버전을 따라가길 권합니다.
최적화 전후를 비교하는 것은, 언어 프런트엔드가 LLVM에 넘겨주는 것을 컴파일러가 얼마나 단순화하는지 보는 좋은 방법입니다. -O0에서는? 전부 alloca. -O2에서는? alloca가 하나도 없음
한때는 i32* 같은 타입 있는 포인터가 있었습니다. 하지만 이는 해결하는 문제보다 만드는 문제가 더 많았습니다. IR에서 잦은 캐스트가 필요해졌고, 타입 안정성은 시원찮았습니다. 더 완전한 역사는 https://llvm.org/docs/OpaquePointers.html을 보세요.↩
빈정거림입니다.↩
int2ptr가 훨씬 보기 좋은데도, inttoptr 같은 이름을 달아 둔 LLVM을 조용히 평가합니다.↩