LLVM의 중간 표현(IR)은 전반적으로 잘 설계되어 있지만, 핵심 IR 설계에서 비롯된 몇 가지 고질적인 문제들이 있으며 이는 실제로 고치기 어렵다. 이 글에서는 그 문제들을 다룬다.
« 글 목록으로 돌아가기. 2021년 6월 02일
전반적으로 LLVM은 언어 레퍼런스에 명시된 잘 설계된 중간 표현(IR)을 갖고 있다. 하지만 설계 실수가 일어난 영역도 여럿 존재한다. 그리고 LLVM 프로젝트는 일반적으로 이런 문제를 해결하는 데 열려 있는 편이지만, 핵심 IR 설계의 실수는 코드베이스에 깊이 박혀 있어 실제로 고치기 어렵다. 이 블로그 글에서는 그 문제들 중 일부를 논의한다.
미들엔드에서는 변환을 최적화(optimization)라기보다는 정규화(canonicalization)로 보는 경우가 많다. 같은 프로그램을 표현하는 방법은 매우 다양하며, 타깃 독립적인 미들엔드 변환의 목적은 이를 하나의 형태로 줄이는 것이다. 물론 선택된 형태는 종종(항상은 아니지만) 더 효율적인 형태와 일치한다. (이 말은 모든 변환에 해당하지는 않는다. 예를 들어 런타임 언롤링이나 벡터화는 분명 정규화 변환이 아니다.)
왜 정규화가 중요할까? 가장 큰 이유는 다른 패스가 처리해야 하는 경우의 수를 줄여주기 때문이다. 1 + a가 a + 1로 정규화된다면, 다른 모든 곳에서는 후자만 처리하면 된다. 또 다른 이유는 공통 부분식 제거(CSE)나 전역 값 번호 매기기(GVN) 같은 중복 제거 변환의 효과를 높여주기 때문이다. 예를 하나 보자:
llvmdefine i1 @test(i32 %x) { %y = sub i32 %x, 1 %z = add i32 %x, -1 %c = icmp eq i32 %y, %z ret i1 %c }
인스트럭션 결합(instruction combining)은 x - 1을 x + (-1)로 정규화한다:
llvmdefine i1 @test(i32 %x) { %y = add i32 %x, -1 %z = add i32 %x, -1 %c = icmp eq i32 %y, %z ret i1 %c }
이제 %y와 %z가 사실 동일하다는 것을 알아내기 쉬워졌으니, %z를 %y로 바꿀 수 있다:
llvmdefine i1 @test(i32 %x) { %y = add i32 %x, -1 %c = icmp eq i32 %y, %y ret i1 %c }
그 다음에는 등가 비교가 자명하게 참이라는 것도 알 수 있다:
llvmdefine i1 @test(i32 %x) { ret i1 true }
그런데 이게 IR 설계와 무슨 관련이 있을까? 좋은 IR 설계는 어떤 중복이 아예 설계 차원에서 존재하지 않도록 만들 수 있다. 핵심은 “불필요한 정보는 인코딩하지 않는 것”이다.
예를 들어 초기 LLVM 버전은 부호 있는 정수(signed)와 부호 없는 정수(unsigned)를 구분했지만, 이후 버전은 (비트폭이 주어졌을 때) 하나의 정수 타입만을 가지며, 부호성은 필요한 몇 군데에만 인코딩한다: 비교, 확장, 오버플로 플래그. 이는 x가 signed인지 여부와 무관하게 x + 1의 표현이 하나뿐임을 의미한다. 이는 핵심 IR 설계의 결과이며, 추가적인 정규화를 필요로 하지 않는다.
아래에서 논의하는 문제들도 비슷한 성격을 띤다는 것을 알아차릴 수 있을 것이다.
현재 LLVM의 포인터 타입은 C의 포인터 타입과 매우 비슷하다: i8*는 8비트 정수에 대한 포인터다. i8* 포인터를 복사해 보자:
llvmdefine void @copy.i8ptr(i8** %dst, i8** %src) { %val = load i8*, i8** %src store i8* %val, i8** %dest ret void }
이번에는 i32* 포인터를 복사해 보자:
llvmdefine void @copy.i32ptr(i32** %dst, i32** %src) { %val = load i32*, i32** %src store i32* %val, i32** %dest ret void }
눈치 빠른 독자라면 이 두 코드가 정확히 같은 일을 한다는 것을 알아챌 것이다. 포인터 크기의 값을 한 위치에서 다른 위치로 복사할 뿐이며, 그것이 i8에 대한 포인터인지 i32에 대한 포인터인지는 전혀 중요하지 않다. 이 사실을 감지하고, 한 함수를 다른 함수로 구현해서 두 함수를 병합하고 싶다면 bitcast를 삽입해야 한다:
llvmdefine void @copy.i32ptr(i32** %dst, i32** %src) { %dst.i8ptr = bitcast i32** %dst to i8* %src.i8ptr = bitcast i32** %src to i8* call void @copy.i8ptr(i8** %dst.i8ptr, i8** %src.i8ptr) ret void }
bitcast는 바이너리 표현을 바꾸지 않고 값의 타입만 다르게 해석하는 캐스트를 표현하는 LLVM의 방식이다. 이런 포인터 bitcast는 LLVM이 불필요한 “포인터 요소 타입”을 인코딩하기 때문에 필요해진다.
포인터 타입 변환은 매우 흔하며, 데이터가 여러 계층을 거치면서 자주 발생한다. 어떤 포인터는 크기가 알려진 특정 객체를 나타낼 때는 [8 x i32]*로 시작했다가, 슬라이스로 해석되면 [0 x i32]*가 되고, memcpy에 범용 포인터로 전달될 때는 i8*가 되기도 한다.
다행히 LLVM은 포인터 요소 타입을 제거하고 불투명 포인터(opaque pointers)로 전환하는 과정에 있다. 불투명 포인터를 사용하면 위 코드는 다음처럼 된다:
llvmdefine void @copy.ptr(ptr %dst, ptr %src) { %val = load ptr, ptr %src store ptr %val, ptr %dest ret void }
이는 두 함수를 설계 차원에서 동등하게 만들어 주며, 포인터 bitcast가 필요 없어진다. 여기서 흥미로운 질문이 하나 생긴다: 한 단계 더 나아가서 포인터를 그냥 정수로 취급할 수는 없을까? 예를 들어 64비트 주소 공간 플랫폼에서 i64로 말이다:
llvmdefine void @copy.i64(i64 %dst, i64 %src) { %val = load i64, i64 %src store i64 %val, i64 %dest ret void }
이는 두 가지 주요 이유로 불가능하다. 첫째, 포인터는 프로비넌스(provenance)를 담고 있는데, 이는 에일리어싱 분석(alias analysis)에 중요하다. 포인터에는 그 기반이 되는 “기저 객체(underlying object)”가 있으며, 그 포인터를 역참조하는 것이 유효한 것은 해당 객체 내부를 가리킬 때뿐이다. 정수는 프로비넌스를 추적하지 않으므로 정수와 포인터 간 변환은 no-op으로 간주되지 않는다(그래서 bitcast로 표현되지도 않는다).
둘째, 포인터에는 여러 종류가 있다. 불투명 포인터를 사용하더라도 LLVM은 여전히 서로 다른 주소 공간(address space)의 포인터를 구분한다. 폰 노이만 구조에서는 동일하겠지만, 어떤 타깃은 데이터와 명령어에 대해 별도의 주소 공간을 가질 수 있으며, 이는 ptr과 ptr addrspace(1)처럼 표현될 수 있다. 포인터는 심지어 비정수형(non-integral)일 수도 있는데, 이 경우 아예 정수 표현 자체가 없다.
불투명 포인터로의 마이그레이션은 이미 여러 해 동안 “진행 중”이었지만, 진척은 상당히 느렸고 최근에서야 다시 속도가 붙었다. LLVM 자체에서의 불투명 포인터 상태는 비교적 괜찮은 편인데, 이는 문제에 대한 전반적인 인식이 있고 포인터 요소 타입을 활용하려는 최적화는 리뷰를 통과하지 못하기 때문이다. 하지만 clang 쪽의 상태는 외교적으로 말하자면 그다지 훌륭하지 않다. 특히 이 귀여운 코멘트가 마음에 든다 — “simply(간단히)”라니.
LLVM은 주소 계산을 getelementptr 인스트럭션으로 수행하는데, 이는 베이스 포인터와 여러 인덱스를 받는다:
llvm%struct = type { i32, { i32, { [2 x i32] } } } define i32* @test(%struct* %base) { %ptr = getelementptr %struct, %struct* %base, i64 1, i32 1, i32 1, i32 0, i64 1 ret i32* %ptr }
첫 번째 i64는 C에서 &base[1]에 해당하듯이 포인터가 가리키는 두 번째 원소를 취한다는 뜻이다. 그 다음 인덱스들은 중첩된 구조체와 배열을 따라 특정 원소로 내려간다. i32가 4바이트 정렬이라고 가정하고 모든 오프셋을 합치면, 이 getelementptr은 다음과 동등하다는 것을 알 수 있다:
llvm%struct = type { i32, { i32, { [2 x i32] } } } define i32* @test(%struct* %base) { %base.i8 = bitcast %struct* %base to i8* %ptr = getelementptr i8, i8* %base.i8, i64 11 ret i32* %ptr }
이 두 GEP는 같은 주소를 서로 다른 방식으로 계산한다. 이는 또 하나의 정규화 문제를 만든다. 또한 분석은 보통 타입 기반 GEP를 오프셋 기반 계산으로 분해해야 한다는 뜻이기도 하다. 이는 놀랄 정도로 비용이 큰데, 데이터 레이아웃 정보로부터 관련된 모든 타입의 alloc size를 계산해야 하고 잠재적인 정렬 제약까지 포함해야 하기 때문이다. 전체 컴파일 시간의 몇 퍼센트가 GEP 오프셋 계산에만 쓰이는 것도 드물지 않다.
더 나은 대안은 GEP를 직접 오프셋 기반으로 만드는 것이며, 이는 불투명 포인터와 결합될 때 가장 잘 동작한다:
llvmdefine ptr @test(ptr %base) { %ptr = getelementptr ptr %base.i8, i64 11 ret ptr %ptr }
완전히 명확하지 않은 부분은 가변 인덱스를 어떻게 인코딩할 것인가다. 필요한 스케일을 GEP 인스트럭션에 포함시킬 수도 있다:
llvmdefine ptr @test(ptr %base, i64 %index) { %ptr = getelementptr ptr %base.i8, 4 * %index ret ptr %ptr }
혹은 인덱스 계산을 IR에서 명시적으로 할 수도 있다:
llvmdefine ptr @test(ptr %base, i64 %index) { %offset = shl i64 %offset, 2 %ptr = getelementptr ptr %base.i8, i64 %offset ret ptr %ptr }
후자의 변형은 정규화 관점에서 다시 한 번 이점이 있는데, 명시적 오프셋 계산과 GEP 내부에 박힌 오프셋 계산 사이의 선택지가 없어지기 때문이다. 하지만 inbounds GEP는 오프셋 계산에 대한 추가 제약을 담고 있어서, 이런 인코딩에서는 그 정보가 사라지게 된다.
GEP만 과도한 타입 정보로 괴롭는 인스트럭션은 아니다. 예를 들어 스택 공간을 예약하는 alloca 인스트럭션은 타입을 받지만, 실제로 필요한 것은 예약할 바이트 수뿐이다:
llvm%ptr = alloca [8 x i32], align 4 ; should be %ptr = alloca i64 32, align 4
하지만 실제로 alloca에 대해서는 정규성이 그리 중요하지 않은데, 보통 중복 제거 또는 구조적 동등성 검사 대상이 아니기 때문이다.
인스트럭션과 더불어 LLVM은 상수 표현식(constant expressions)도 지원한다. 다음 함수의 add 인스트럭션은
llvmdefine i64 @test() { %res = add i64 1, 2 ret i64 %res }
상수 표현식을 사용해 다음처럼 동등하게 작성할 수 있다:
llvmdefine i64 @test() { ret i64 add (i64 1, i64 2) }
상수 표현식의 좋은 점은 생성 시점에 최대한 접히고(fold) 유일화(uniqued)된다는 것이다. 그래서 이 예시는 파일을 파싱할 때 실제로
llvmdefine i64 @test() { ret i64 3 }
로 바뀐다. 정규화에 정말 좋은 것 아닌가? 생성 자체로 인해 같은 상수 표현식을 서로 다른 방식으로 표현할 수가 없다. 항상 완전히 접히니까!
하지만 현실은 그렇게 단순하지 않다. 상수 표현식은 LLVM 컨텍스트 단위로 유일화되는데, 이 컨텍스트는 데이터 레이아웃(data layout)을 알지 못한다. 즉 생성 시점에는 데이터 레이아웃에 의존하지 않는 접기만 수행할 수 있다.
예를 들어 이런 표현식은 접을 수 없다:
llvmdefine i64 @sizeof_int64() { ret i64 ptrtoint (i64* getelementptr (i64, i64* null, i64 1) to i64) }
이 표현식은 i64의 alloc size를 인코딩한 것으로, i64의 ABI 정렬을 알아야 한다. 이는 데이터 레이아웃이 제공하는 정보이며, 상수 표현식 자체는 이를 알지 못한다.
이는 상수 접기가 두 단계로 나뉜다는 뜻이다. 하나는 타깃 독립적이며 생성 시점에 이뤄지고, 다른 하나는 타깃 의존적이며 인스트럭션 결합 같은 특정 패스에서 수행된다. 두 번째 접기는 참조되는 모든 상수 표현식을 재귀적으로 순회하면서 모든 레벨에서 접기를 시도해야 하며, 사실상 “항상 접힌” 표현의 이점을 무력화한다.
하지만 문제는 그것보다 더 크다. 인스트럭션과 상수 표현식은 보통 동일한 제약을 가져야(균일하게 다루기 위해) 하므로, 데이터 레이아웃에 의존하는 IR 유효성 제약을 강제할 수 없다. 예를 들어 ptrtoint 인스트럭션/표현식은 정수 타입의 크기가 포인터 타입과 달라도 되며, 크기가 맞지 않으면 암묵적으로 truncation 또는 zero extension을 수행한다. 실제로 이런 IR은 나타나지 않는데, 명시적인 trunc나 zext로 정규화되기 때문이다. 하지만 모든 패스는 그런 가능성을 여전히 처리해야 한다. 상수 표현식에는 데이터 레이아웃이 없기 때문에 “크기가 같아야 한다”는 제약을 실제로 강제할 수 없다.
그러나 데이터 레이아웃은 문제의 일부일 뿐이다. 또 다른 문제는 연산이 인스트럭션으로도, 상수 표현식으로도 표현될 수 있다는 단순한 사실이다. 이는 코드가 일반적으로 두 표현을 모두 처리할 수 있어야 한다는 뜻이며, 상수 폴딩(표현식으로의 폴딩)이 일어났다고 해서 최적화가 비관적으로 되지 않도록 해야 한다. LLVM은 인스트럭션과 상수 표현식을 투명하게 다루는 제네릭 패턴 매처가 많아서, 대체로 이를 잘 처리하는 편이다.
하지만 중요한 복잡성이 하나 있다. 많은 코드는 “상수에 어떤 연산을 적용하는 것은 공짜”라고 가정한다. 예를 들어 어떤 최적화가 인스트럭션 시퀀스에 걸친 부정(negation)을 밀어 넣을 때, 상수 피연산자에 부정을 밀어 넣는 것은 공짜라고 가정할 수 있다. 그냥 1이 -1이 되는 식이니까. 하지만 상수 표현식에서는 그렇지 않다. 부정이 접히지 않을 수 있고, 결국 sub (i64 0, i64 ...) 같은 형태가 남게 된다.
이는 옵티마이저에서 무한 루프를 만드는 가장 흔한 원인 중 하나다. 어떤 변환이 “접힐 것”이라 생각하고 연산을 상수로 밀어 넣지만, 상수 표현식 때문에 접히지 않는다. 다른 변환은 새로 생긴 상수 표현식을 보고 역변환을 수행할 수 있고, 그 결과 인스트럭션 결합 루프가 무한히 반복된다.
상수 표현식은 IR 출력에서도 병적인 사례를 만든다:
llvmdefine i64 @test(i64 %x1) { %x2 = mul i64 %x1, %x1 %x3 = mul i64 %x2, %x2 %x4 = mul i64 %x3, %x3 %x5 = mul i64 %x4, %x4 ret i64 %x5 }
인스트럭션으로 작성하면 각 인스트럭션이 두 번씩 사용되는 깔끔한 선형 체인이다. 상수 표현식을 사용해도 메모리 내 표현은 마찬가지로 공유 구조를 유지한다. 하지만 텍스트 IR로 출력할 때는 여러 번 등장하는 상수 부분식을 재사용할 방법이 없으므로, 루트 값 %x1이 2^4번 반복되는 결과가 된다. 합리적인 시간 내에 출력이 불가능한 IR을 만드는 것은 어렵지 않다.
마지막으로, 상수 표현식 내부에 나눗셈이 들어갈 수 있기 때문에 상수 구체화(materialization)가 미정의 동작(UB)을 유발할 수도 있다. 이는 이상한 함의를 낳는다. 예를 들어 어떤 인스트럭션이 “상수” 피연산자 때문에 추측 실행(speculate)이 불가능해질 수 있다. 실제로 이런 일은 거의 일어나지 않겠지만, 그 가능성은 여전히 고려하고 처리해야 한다.
그렇다면 대안은 무엇일까? 생성 시점에 데이터 레이아웃을 사용할 수 있게 한다면(설령 결과 상수가 데이터 레이아웃 독립적이더라도) 문제의 일부는 해결된다. 나머지를 해결하려면 상수 표현식이라는 개념을 제거하거나, 정확히는 그 범위를 줄여야 한다.
상수 표현식이 존재하는 이유는 전역 초기화(global initializer) 때문이다. 전역 초기화는 상수만 받을 수 있다. 하지만 이 초기화 값은 LLVM IR 레벨에서는 임의의 상수 표현식을 담을 수 있는 반면, 로워링(lowering) 과정에서는 제한된 “재배치 가능(relocatable)” 표현식만 받아들인다. 상수 표현식 메커니즘이 정말로 필요한 것은 이런 재배치 가능 표현식을 위해서뿐이다. LLVM의 실수는 이런 재배치 가능 표현식의 표현(representation)과 상수 폴딩 기계를 한데 섞어버린 것이다.
여기서 논의한 설계 문제들은 지나고 나서 보면 분명해진 것들이다. 물론 이러한 선택이 처음에 이루어졌던 데에는 대개 그럴듯한 역사적 이유가 있다. 예를 들어 포인터 요소 타입과 타입 기반 GEP는 프런트엔드가 LLVM IR로 직접 로워링하는 구현을 편하게 해준다 — 즉 clang에게 편리하다. 타입 추적이라는 일을 LLVM에 위임할 수 있기 때문이다. 비슷하게 상수 표현식 설계는 LLVM이 데이터 레이아웃이 연관되지 않은 타깃 독립 모듈 개념을 아직 지원하던 시절로 거슬러 올라간다고 나는 믿는다.
이 글에서 다룬 이슈는 IR의 정규성(canonicality)과 관련이 있다. 별도로 정확성(correctness)과 관련된 문제의 부류도 있다. 그중 가장 큰 것은 모든 가능한 비트 패턴의 양자 중첩 상태를 나타내는 undef 값이라는 개념이다. 맞다, 이름만큼이나 끔찍하다. 다행히 undef 값은 poison 값으로 대체되는 과정에 있다. 하지만 그 이야기는 다음 기회에 하자.
