LLVM 최적화 패스의 구현을 두 가지 간단한 사례로 살펴보며, 작은 소스 코드 변화가 어떻게 전혀 다른 컴파일 결과와 성능 특성으로 이어질 수 있는지 탐구한다.
© 2026 Henrique Cabral
20 Mar 2026
목차
성능 지향 프로그래머들 중 많은 이들은 현대 컴파일러가 코드를 거의 초자연적으로 최적화하는 능력에 매우 익숙하며, 우리 중 다수는 Compiler Explorer에서 gcc와 clang의 서로 다른 버전이 생성한 Assembly의 차이를 살펴보는 데 셀 수 없이 많은 시간을 보냈다. 하지만 그 마법이 어떻게 일어나는지 내부를 들여다본 사람은 아마 그보다 적을 것이다. 우리 대부분이 컴파일러를 블랙박스로 취급한다는 사실은 오히려 그 품질을 증명한다. 어느 정도 읽기 쉬운 코드를 넣으면 빠른 바이너리가 나온다. 그러나 때로는 겉보기에 무해한 변화, 심지어 컴파일러를 돕기 위해 의도한 변화조차도, 내부 기계장치에 대한 더 깊은 이해 없이는 설명하기 어려운 놀라운 성능 문제를 일으킬 수 있다.
이 글에서는 간단하지만, 그럼에도 고도로 최적화된 코드를 만들어내는 데 얽힌 복잡성을 드러내는 데 도움이 되는 두 가지 예제를 통해 몇몇 LLVM1 최적화 패스의 구현을 살펴본다. 작은 소스 변화가 컴파일러 내부 처리의 서로 다른 경로를 촉발해 예상치 못한 결과를 낳는 모습을 보면서, 높은 성능을 달성하는 일이 컴파일러 개발자와 사용자 모두에게 과학이면서 동시에 예술이기도 하다는 점을 확인하게 될 것이다. 손을 더럽혀 보고 싶은 사람들을 위해 몇 가지 연습문제도 넣었지만, 본문을 따라가는 데 필수는 아니다.
이 글 전체에서 기준 구현으로 LLVM 22.1.0을 사용한다. 예제는 매우 기초적인 C++23으로 작성되었고 대상은 x86-64이며, Assembly 코드는 Intel 문법을 사용한다. LLVM IR에 대한 사전 지식은 필수는 아니지만 있으면 도움이 된다(A Gentle Introduction to LLVM IR를 추천한다).
라운드 로빈 방식으로 접근되는 배열이나 벡터의 다음 인덱스를 구하는 다음 C++ 함수를 생각해 보자. 여기서
cur는 현재 인덱스이고
count는 요소의 개수다:
unsigned next_naive(unsigned cur, unsigned count)
{
return (cur + 1) % count;
}
이대로 작성하면 이 코드는 비용이 큰 32비트 나눗셈 명령이 필요하다(Intel IceLake 코어에서 6사이클, 지연은 12사이클이며, 이전 세대에서는 더 나쁘다). 물론 상수로의 나눗셈을 더 싼 산술 연산으로 바꾸는 수많은 기법이 있고, 2의 거듭제곱이 가장 잘 알려진 경우다. 하지만 여기서는
count가 동적인 런타임 값이므로 컴파일러가 도와줄 수 없다:
next_naive(unsigned int, unsigned int):
lea eax, [rdi + 1]
xor edx, edx
div esi
mov eax, edx
ret
하지만 우리는 컴파일러가 모르는 것을 알고 있다.
cur는 인덱스이므로 항상
count보다 엄격히 작아야 한다. 이를 이용해 나눗셈을 훨씬 저렴한 조건부 이동으로 바꿀 수 있다:
unsigned next_cmov(unsigned cur, unsigned count)
{
auto n = cur + 1;
return n == count ? 0 : n;
}
next_cmov(unsigned int, unsigned int):
lea ecx, [rdi + 1]
xor eax, eax
cmp ecx, esi
cmovne eax, ecx
ret
컴파일러가 이 변환을 스스로 할 수 있었을까? 새 C++23
assumeattribute2를 써 보자:
unsigned next_assume(unsigned cur, unsigned count)
{
[[assume(cur < count)]];
return (cur + 1) % count;
}
next_assume(unsigned int, unsigned int):
lea ecx, [rdi + 1]
xor eax, eax
cmp ecx, esi
cmovne eax, ecx
ret
next_cmov()와 정확히 같은 코드다! 그렇다면 clang은 이것을 어떻게 알아낸 걸까?
어떤 최적화가 어디서 오는지, 혹은 왜 빠져 있는지 이해하려고 할 때 첫 번째 단계는 그것이 발생하는 패스를 식별하는 것이다. 현재 서로 다른 LLVM 최적화 패스의 효과를 조사하는 가장 편리한 방법은 Compiler Explorer의 Opt Pipeline 보기다:
(
-mllvm -print-changed옵션을 clang에 넘기면 로컬에서도 같은 정보를 얻을 수 있지만, 보기 좋게 강조된 diff는 없다.)
next_assume()의 LLVM IR 변화 과정을 살펴보면, 모듈로 연산을 나타내는
urem명령이
icmpselect쌍으로 바뀌는 변환(결국 x86의
cmpcmov로 번역된다)이 InstCombine에서 일어남을 금방 찾을 수 있다:
%cmp = icmp ult i32 %cur, %count
call void @llvm.assume(i1 %cmp)
%add = add i32 %cur, 1
- %rem = urem i32 %add, %count
+ %0 = icmp eq i32 %add, %count
+ %rem = select i1 %0, i32 0, i32 %add
ret i32 %rem
InstCombine은 제어 흐름 그래프를 수정하지 않는 많은 피프홀 최적화를 담당한다. 예를 들어 2의 거듭제곱과의 곱셈을 좌시프트로 바꾸는 것 같은 일들이다. 이 패스는 함수의 모든 명령을 방문하면서, 일반적인 패턴 매칭 메커니즘을 사용해 수백 가지 패턴 중 하나와 맞춰 본다. 실제로 이 패스는 컴파일 중 여러 번 실행되는데3, 다른 패스들이 보통 각종 단순화, 루프 언롤링 등을 수행하면서 새로운 최적화 기회를 드러내기 때문이다.
이 경우 핵심 변환 로직은 아주 단순하고 독립적이다. LLVM 저장소의
lib/Transforms/InstCombine디렉터리를 살펴보면, 패스가 맞추는 명령 범주별로 코드가 서로 다른 파일에 잘 정리되어 있고, 각 파일에는 관심 있는 opcode에 대한 방문자 메서드가 들어 있음을 볼 수 있다. 그중 하나가
InstCombineMulDivRem.cpp이고, 여기서 비교적 짧은
visitURem()메서드와, 그 끝부분에서 다음 코드를 찾을 수 있다:4
// For "(X + 1) % Op1" and if (X u< Op1) => (X + 1) == Op1 ? 0 : X + 1 .
if (match(Op0, m_Add(m_Value(X), m_One()))) {
Value *Val =
simplifyICmpInst(ICmpInst::ICMP_ULT, X, Op1, SQ.getWithInstruction(&I));
if (Val && match(Val, m_One())) {
Value *FrozenOp0 = Op0;
if (!isGuaranteedNotToBeUndef(Op0))
FrozenOp0 = Builder.CreateFreeze(Op0, Op0->getName() + ".frozen");
Value *Cmp = Builder.CreateICmpEQ(FrozenOp0, Op1);
return createSelectInstWithUnknownProfile(
Cmp, ConstantInt::getNullValue(Ty), FrozenOp0);
}
}
블록 앞의 주석이 설명하듯, 이 코드는
next_assume()에서 우리가 사용한 패턴과 정확히 일치하며, 증가 전 값이 모듈러스보다 작다는 것을 증명할 수 있는 경우, 손으로 작성한
next_cmov()과 같은 최적화를 생성한다.5 이 보장을 얻기 위해 컴파일러는
icmp명령의 결과를 접는 데 쓰이는 같은 분석, 즉 plaintext simplifyICmpInst() 함수를 영리하게 재사용한다. 구현을 아래로 내려가며 보면 수많은 패턴을 맞추고 있음을 알 수 있는데, 여기서 특히 흥미로운 것은
simplifyICmpWithDominatingAssume헬퍼다. 이 헬퍼는 비교 양쪽에 적용 가능한 모든 가정(
llvm.assume()intrinsic 호출의 형태)을 검사해 그것들이 우리가 관심 있는 조건을 함의하는지 본다.6 이것으로 마침내
assumeattribute에 담아 둔 정보가 어떻게 그 귀찮은 나눗셈을 제거하도록 컴파일러를 도왔는지 설명된다.
simplifyICmpInst()구현을 살펴보면 이 전제 조건을 전달하는 다른 방법도 보인다. 예를 들어, assertion이 활성화되어 있을 때는 다음 버전의 함수도 비슷하게 최적화된다:
unsigned next_assert(unsigned cur, unsigned count)
{
assert(cur < count);
return (cur + 1) % count;
}
여기서는 단순화 분석이
assert()매크로에 숨겨진 조건을 이용해, 우리가
urem명령을 실행하는 것은
cur < count일 때뿐임을 알아낸다(
isImpliedByDomCondition()메서드를 보라). 이것은 뜻밖에도 어떤 경우에는 assertion을 켠 빌드가 더 빠를 수 있다는 결과를 낳을 수 있다. 비활성화된 assertion을 런타임 비용이 없는
assumeattribute로 대체하면 성능을 복원할 수 있다.
연습문제 1: 잠재적 분기를 피하려고 비트 연산으로 함수를 영리하게 다시 써 보더라도, InstCombine은 우리의 속임수를 곧장 간파하고 정확히 같은 출력을 만들어낸다:
unsigned next_bitwise(unsigned cur, unsigned count)
{
auto n = cur + 1;
return n & -(n != count);
}
%add = add i32 %cur, 1
- %cmp = icmp ne i32 %add, %count
- %conv = zext i1 %cmp to i32
- %sub = sub nsw i32 0, %conv
- %and = and i32 %add, %sub
+ %cmp.not = icmp eq i32 %add, %count
+ %and = select i1 %cmp.not, i32 0, i32 %add
ret i32 %and
어떤 패턴을 맞춰서 이렇게 하는지 알아내기 위해 패스의 실행을 추적해 보라.
sub명령에 대한 방문자부터 시작하라. (rr가 매우 유용할 수 있다.)
지금까지 본 모든 예제는 코드가 그에 맞게 최적화되도록
cur와
count사이의 관계를 우리가 명시적으로든 어떤 방식으로든 직접 알려줘야 했다. 다른 경우에는 이 관계가 암묵적일 수 있는데, 예를 들어 루프 안에서 모듈로 값들을 순회할 때가 그렇다:
void iterate_1(unsigned upto, unsigned count)
{
for (unsigned i = 0, r = 0; i < upto; ++i, r = (r + 1) % count)
// force the compiler to calculate r instead of discarding the whole loop
asm("" :: "r" (r));
}
생성된 Assembly를 보면, 컴파일러가 이 최적화를 스스로 추론할 만큼 똑똑해 보이지는 않는다:
iterate_1(unsigned int, unsigned int):
test edi, edi
je .LBB4_3
xor edx, edx
.LBB4_2:
inc edx
mov eax, edx
xor edx, edx
div esi
dec edi
jne .LBB4_2
.LBB4_3:
ret
하지만 흔히 그렇듯, 컴파일러는 우리가 놓친 무언가를 알아챘을 뿐이다. 우리의 최적화는
r < count에 의존하지만,
count가 0이면 이 조건은 만족될 수 없다.7 최적화기가 정확히 어떻게 이 결론에 도달하는지 보는 것은 유익하다. 첫 번째 InstCombine 패스 입력 시점의 IR을 보면,
visitURem()의
(X + 1) % Op1패턴이 이제
X를 다음 phi 명령과 맞춘다는 것을 알 수 있다8:
%r.0 = phi i32 [ 0, %entry ], [ %rem, %for.body ]
phi 명령을 만나면,
simplifyICmpInst()는 검사한다. 즉 비교가 phi로 들어올 수 있는 모든 가능한 입력 값(이 경우 0과,
r에 대해 마지막으로 계산된 값)에 대해 단순화될 수 있는지, 그리고 그렇다면 그 모두에 대해 같은 결과를 내는지를 본다. 위의 코드에서는
0 < count인지 판단할 방법이 없으므로 단순화는 실패한다. 루프 전에
if (count == 0) return;문을 추가해 빈틈을 메우면, 기대한 결과를 얻을 수 있다:
.LBB4_2:
inc ecx
cmp ecx, esi
cmove ecx, eax
dec edi
jne .LBB4_2
하지만 그렇다고 해서, 이제 더 이상 명시적인 가정이나 조건이 없는데도 컴파일러가 어떻게
%rem < %count를 두 번째 phi 입력에 대해 결정했는지는 설명되지 않는다. 그 경우는 명령 접기 루틴 깊숙한 곳에 있는 또 다른 패턴이 처리하며, 주어진 모듈러스의 나머지와 모듈러스 자체 사이의 비교를 특별히 다룬다:
// icmp pred (urem X, Y), Y
if (match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
switch (Pred) {
// ...
case ICmpInst::ICMP_NE:
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
return getTrue(ITy);
}
}
그렇다. 끝없이 패턴이다.
연습문제 2: 대신 루프 조건을
i < std::min(upto, count)로 바꾸면, 컴파일러는 더 이상
urem명령을 대체하지 못한다. 앞서 언급한
isImpliedByDomCondition()메서드부터 시작해서, 함의된 조건을 평가할 때 min/max 관용구를 꿰뚫어 볼 수 있도록 어디에 지원을 추가할 수 있을지, 그리고 기존 분석 코드를 재사용할 수 있을지 알아보라. 이제 중복된 remainder 자체를 완전히 제거하려면 어떻게 해야 할까?
생성된 코드가 효율적이라 하더라도, 나머지를 담는 보조 변수를 하나 더 정의하는 것은 불필요해 보일 수 있다. 루프 카운터 자체로부터 그냥 계산할 수 있기 때문이다. 그것을 없애 보자:
void iterate_2(unsigned upto, unsigned count)
{
for (unsigned i = 0; i < upto; ++i)
asm("" :: "r" (i % count));
}
iterate_2(unsigned int, unsigned int):
test edi, edi
je .LBB5_3
xor eax, eax
xor ecx, ecx
xor edx, edx
.LBB5_2:
inc ecx
cmp ecx, esi
cmove ecx, eax
inc edx
cmp edi, edx
jne .LBB5_2
.LBB5_3:
ret
여기서도 컴파일러가 같은 기회를 알아본 것처럼 보인다. 나눗셈은 여전히 깔끔한 조건부 이동으로 대체되었고, 나머지를 유지하기 위해 별도 레지스터를 사용한다. 하지만 이것은 앞서 본 InstCombine 코드의 결과처럼 보이지 않는다. 그리고 왜 이전처럼 루프 카운터를 감소시키고 zero flag를 쓰지 않고, 증가 시키고 있는 걸까? 그러면 비교가 하나 더 필요해지는데 말이다.
이번에는 서로 다른 최적화 패스의 결과를 살펴보면, 이 변환이 InstCombine이 아니라 다른 패스인 CodeGenPrepare에서 왔음을 알 수 있다. 이 패스는 명령 선택 직전에 실행되지만, 카운터 증가를 감소로 바꾸는 루프 강도 감소(loop strength reduction, LSR) 이후에 실행된다. InstCombine은 더 이상 자신이 기대하는 패턴을 맞출 수 없다.
i < count가 성립하지 않기 때문이다. 또한
i가 루프 본문 내부에서 remainder를 계산하는 데 사용되므로, LSR 역시 그것을 감소 카운터로 대체할 수 없다. 그러면 CodeGenPrepare가 일종의 최후 수단처럼 동작해 특정 패턴을 식별하고 거의 최적인 코드로 변환한다.
이것은 다음 절에서 더 깊이 살펴볼 두 가지 점을 보여 준다:
연습문제 3: LLVM은 최적화기를 적절하게도
opt라는 이름으로, 컴파일러 프런트엔드와 분리된 모듈식 바이너리로 제공한다. 위의
iterate_2()구현을
iterate.cpp파일에 저장하고, 로컬 clang 설치본으로 다음 명령을 실행해 보라:
clang++ -O2 -S -emit-llvm -fno-discard-value-names -o- iterate.cpp \
| opt -S -passes="require<profile-summary>,loop-reduce,codegenprepare" -
Compiler Explorer Opt Pipeline 보기에서 CodeGenPrepare 패스 이후에 볼 수 있는 것과 비슷한 출력을 얻어야 한다. 마지막에
loop-reduce패스를 하나 더 추가하면 어떻게 되는가?
연습문제 4:
iterate_2()의 루프 조건도 연습문제 2와 같은 방식으로 바꾸면, remainder 명령이 생성된 코드에서 제거된다. 이것은 어떤 패스가 하는 일이며, 왜 이전에는 작동하지 않았을까?
저장, IPC, 네트워킹을 위한 대부분의 바이너리 형식은 수치 필드에 특정 바이트 순서를 지정한다. 예를 들어 SQLite 데이터베이스 파일은 빅엔디언 필드를 사용하고, Protobuf
i32와
i64필드는 리틀엔디언이다. 호스트 엔디언에 독립적인 디코딩 함수를 작성하는 관례적인 방법은 개별 입력 바이트를 명시적으로 결합하는 것이다. 32비트 값의 경우 대략 다음과 같다(캐스트가 필요 없도록 32비트
int를 가정한다):
uint32_t load_le32(const uint8_t* data)
{
return data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);
}
uint32_t load_be32(const uint8_t* data)
{
return data[3] | (data[2] << 8) | (data[1] << 16) | (data[0] << 24);
}
비정렬 메모리 로드를 지원하는 x86에서는 이것이
-O1이상에서 최적의 Assembly를 생성한다:
load_le32(unsigned char const*):
mov eax, dword ptr [rdi]
ret
load_be32(unsigned char const*):
mov eax, dword ptr [rdi]
bswap eax
ret
만성적인 DRY 성향을 앓고 있고, 이런 함수들과 그 64비트 대응 함수를 또다시 쓰게 된 상황이거나, 어쩌면 4바이트와 8바이트 이외의 정수 크기를 다뤄야 하는 개발자라면, 대신 하나의 일반화된 버전을 쓰고 싶을 수 있다:
static uint64_t load(const uint8_t* data, size_t sz, bool be)
{
uint64_t val = 0;
for (size_t i = 0; i < sz; ++i)
val |= static_cast<uint64_t>(data[be ? sz - i - 1 : i]) << (8 * i);
return val;
}
uint32_t load_le32(const uint8_t* data) { return load(data, 4, false); }
uint32_t load_be32(const uint8_t* data) { return load(data, 4, true); }
uint64_t load_le64(const uint8_t* data) { return load(data, 8, false); }
uint64_t load_be64(const uint8_t* data) { return load(data, 8, true); }
그러면 코드 리뷰어들은 전통적인 함수들에 비해 성능 저하가 없는지 합리적으로 걱정할 수 있다. 컴파일해 보면 어떤 일이 벌어지는지 보자:
load_le32(unsigned char const*):
mov eax, dword ptr [rdi]
ret
load_be32(unsigned char const*):
mov eax, dword ptr [rdi]
bswap eax
ret
load_le64(unsigned char const*):
mov rax, qword ptr [rdi]
ret
load_be64(unsigned char const*):
mov rax, qword ptr [rdi]
bswap rax
ret
게으르거나, 혹은 멀리 내다본 개발자는 무사한 것처럼 보인다. 적어도 gcc를 써야 할 필요가 없다면 말이다. 적어도 15.2 기준으로 gcc는 이 코드를 최적화하지 못한다. 컴파일러가 이것을 어떻게 해내는지 감을 얻기 위해 최적화 파이프라인의 진행을 다시 살펴보자.
글 전반부에서 본 것을 생각하면, 연속된 로드가 하나의 32비트 또는 64비트 로드로 접히는 시점이 명령 선택 단계(ISel이라고도 함)까지 가서야 나타난다는 사실은 다소 놀라울 수 있다. 다음 절에서는 어떤 경우에는 더 이른 단순화를 어떻게 유도할 수 있는지 보겠지만, 먼저 ISel이 무엇인지, 그리고 어떻게 이런 접기를 구현하는지 이해해 보자.
명령 선택은 컴파일러 백엔드의 첫 번째 단계로, 모든 일반적인 최적화 패스가 끝난 뒤에 실행된다(LLVM에서는 이 구분이
opt와
llc바이너리의 분리에도 반영되어 있다). 목적은 최적화기가 만들어 낸 LLVM IR을 Machine IR(MIR)로 변환하는 것이다. MIR은 스케줄링이나 레지스터 할당 같은 후속 패스에 적합한, 대상별 명령 스트림 표현이다. x86을 포함한 대부분의 LLVM 대상은 명령 선택 프레임워크로 SelectionDAG를 사용한다. 여기서는 SelectionDAG의 세부 사항으로 깊이 들어가지는 않겠지만9, 우리의 목적에는 그것이 InstCombine과 유사한 DAGCombiner라는 자체 피프홀 최적화기를 포함하며, 코드 생성이 드러내는 단순화 기회나 특정 대상에만 해당하는 기회를 포착할 수 있다는 사실만으로 충분하다.
InstCombine이 기본 블록의 각 명령을 방문하듯, DAGCombiner는 그 명령들로부터 만들어진 DAG의 각 노드를 방문한다.
or방문자가 수행하는 많은 변환들 사이에서, 우리는 plaintext MatchLoadCombine() 메서드를 찾게 된다:
/// Match a pattern where a wide type scalar value is loaded by several narrow
/// loads and combined by shifts and ors. Fold it into a single load or a load
/// and a BSWAP if the targets supports it.
물론 이것은 SelectionDAG 입력 시점의 LLVM IR에서 보이는 정확한 패턴이다.
load()가 인라인되고, 상수 인자가 전파되며, 루프가 완전히 언롤된 뒤의 모습이다. 그런데 이 메서드에서 흥미로운 점은, 앞서 InstCombine에서 본 것처럼 단순한 패턴 매칭을 수행하는 것이 아니라,
or명령 출력의 각 바이트가 어디서 왔는지를 DAG를 따라 재귀적으로 추적한다는 것이다(보조 plaintext calculateByteProvider() 함수를 사용한다). 로드뿐 아니라 비트 연산, 바이트 스왑, 0/부호 확장까지 따라간다. 이 덕분에 다음과 같은 식도 처리할 수 있을 만큼 강력하다:
static uint64_t load_alt(const uint8_t* data, size_t sz, bool be)
{
uint64_t val = 0;
for (size_t i = 0; i < sz; ++i)
val = (val << 8) | data[be ? i : sz - i - 1];
return val;
}
하지만 이 경우 확인해 보면, 32비트 함수들만 완전히 최적화된다. LLVM IR 명령 수는 앞과 정확히 같지만, 이 새 버전은 가장 먼저 로드된 바이트의 출처를 밝혀내기 위해 DAG 안에서 더 깊이 재귀해야 한다(반복마다 출력 변수에 한 번이 아니라 두 번 연산을 수행하므로). 그 결과 하드코딩된 10단계 재귀 제한에 걸린다. 이것은 컴파일러 내부 처리에 대한 머릿속 지도를 갖고 있는 것, 그리고 더 흔한 패턴을 따르는 것이 이런 병적인 경우를 피하는 데 어떻게 도움이 되는지를 보여 주는 좋은 예다.10
숙련된 C++ 개발자들 중 일부는 이 예제에 본능적으로 이의를 제기했을지도 모른다. 결국 컴파일 시점에 알려진 인자 값이 몇 개 안 된다면, 왜 컴파일러가 상수를 전파해 주기를 기대하기보다는 함수를 템플릿화하지 않겠는가?
template <size_t sz, bool be>
static uint64_t load(const uint8_t* data)
{
uint64_t val = 0;
for (size_t i = 0; i < sz; ++i)
val |= static_cast<uint64_t>(data[be ? sz - i - 1 : i]) << (8 * i);
return val;
}
uint32_t load_le32(const uint8_t* data) { return load<4, false>(data); }
uint32_t load_be32(const uint8_t* data) { return load<4, true>(data); }
uint64_t load_le64(const uint8_t* data) { return load<8, false>(data); }
uint64_t load_be64(const uint8_t* data) { return load<8, true>(data); }
출력은 바뀌지 않지만, 이번에는 리틀엔디언 함수들의 IR이 명령 선택 단계에 도달하기 훨씬 전에 하나의 로드로 최적화된다. 그 패스는 AggressiveInstCombine이라 불린다. InstCombine과 마찬가지로 이 패스도 다양한 피프홀 최적화를 수행하지만, 비교적 덜 자주 필요하거나 실행 시간이 더 오래 걸리는 최적화에 초점을 맞추므로
-O2에서 한 번만 실행되고(
-O1에서는 아예 실행되지 않는다). 그 최적화 중 하나는 plaintext foldConsecutiveLoads() 함수에 구현되어 있는데, 이것은 우리 함수들에서 보이는 것처럼 “(선택적으로) 좌시프트되고 0 확장된 연속 로드들의 비트 OR” 형태의 패턴을 맞춘다.
단순한 패턴 매칭에 의존하므로, AggressiveInstCombine은 DAGCombiner만큼 강력하지는 않다. 특히 위의
load_alt()에 쓰인 fold는 32비트의 경우조차 최적화할 수 없다. 또한 이 패스는 빅엔디언 로드에는 영향을 주지 않는다. 중간 단계 최적화 패스이기 때문에(DAGCombiner는 컴파일러 백엔드의 일부인 것과 달리), 가능한 한 대상 독립적인 IR을 만들려고 하기 때문이다. 리틀엔디언 대상에서 빅엔디언 로드를 접거나 그 반대를 하려면 대상별 바이트 스왑 intrinsic을 추가해야 하고, 이는 후속 분석 및 최적화 패스를 더 복잡하게 만든다.
연습문제 5: 이 절에서처럼
load_alt()함수를 템플릿화하고 결과 출력을 살펴보라. 이전 결과와 일치하는가? 이것이 템플릿화와 최적화 파이프라인의 상호작용에 대해 무엇을 말해 주는가?
연습문제 6: 엔디언에 따라 바이트를 다른 순서로 로드하는 대신, 순서를 고정하고
load()의 반환값에 선택적으로
__builtin_bswap64()intrinsic을 사용할 수도 있다. 이것이 AggressiveInstCombine의 코드 최적화 능력에 어떤 영향을 주는가?
초기의 비템플릿 버전에서는 왜 AggressiveInstCombine이 개입하지 않았을까? 최적화 파이프라인을 살펴보면, 이 패스가 더 이른 시점에
load()이 인라인된 후에 실행되긴 하지만, 결정적으로 루프가 언롤되기 전 이었다는 사실을 알 수 있다. 그래서 아직 맞출 패턴이 없었다. 반면 함수 템플릿은 각기 다른 매개변수 조합마다 별도로 인스턴스화되므로, 그것들이 인라인될 때쯤이면 루프는 이미 완전히 언롤되어 있고(반복 횟수가 알려져 있으므로),
foldConsecutiveLoads()가 그것을 맞출 수 있다. 처음 코드를 가지고도 다음을 수동으로 실행하면 같은 결과를 얻을 수 있다:
clang++ -S -emit-llvm -O2 -o- endianness.cpp \
| opt -S -passes='aggressive-instcombine' - \
| llc --x86-asm-syntax=intel
이것은 또한 LLVM에서 함수 인라이닝의 중요한 원칙 하나를 잘 보여 준다(다른 컴파일러는 어떤지 확신할 수 없다). 가능하다면 인라이닝 비용 휴리스틱의 정확도를 높이기 위해 호출자보다 피호출자를 먼저 단순화한다. 인라이닝 전에 최적화기에 더 많은 정보가 있을수록, 그런 결정을 더 잘 내릴 수 있다. 사실 일반적으로도, 파이프라인에서 특정 단순화를 더 이른 시점에 가능하게 할수록 최종 결과는 더 최적화된다(더 많은 예시는 연습문제를 보라).
연습문제 7: 특수화된 함수들 중
load_le32()만 남기고 모두 주석 처리하면,
load()을 템플릿화했을 때와 비슷한 결과를 얻는다. 즉 AggressiveInstCombine이 연속 로드를 성공적으로 접는다. 어떤 최적화 패스가 이것을 가능하게 하는가? 성능이 중요한 코드를 어떻게 재구성하면 이를 활용할 수 있을까?
연습문제 8: 이제
load_le64()만 남기되,
load()을 위의
load_alt()로 바꾸면 DAGCombiner가 결과 LLVM IR을 완전히 최적화할 수 있다. 왜 그런지 이해하기 위해 앞선 결과와 비교해 보라.
여기까지 읽었다면, 최적화기는 마법은 아닐지라도 적어도 초인적이라고 생각하게 되었을지 모른다. 컴파일러에게는 당연한 일이 실제로는 그리 당연하지 않은 두 가지 예를 보며 그 생각을 빠르게 깨뜨려 보자.
먼저 초기 예제에 작고(그리고 꽤 쓸모없는) 함수를 하나 추가해 보자:
uint32_t load_le32(const uint8_t* data) { return load(data, 4, false); }
uint32_t load_add_le32(const uint8_t* data)
{
return load_le32(data) + data[0];
}
계속 읽기 전에 이 함수가 어떻게 컴파일될 것이라 예상하는지 잠시 생각해 보라. 로드 두 번과 덧셈일까? 아니면 한 번의 로드, 하위 바이트의 0 확장, 그리고 덧셈일까?
이제 실제 결과와 비교해 보자:
load_add_le32(unsigned char const*):
movzx ecx, byte ptr [rdi]
movzx edx, word ptr [rdi + 1]
shl edx, 8
movzx eax, byte ptr [rdi + 3]
shl eax, 24
or eax, edx
or eax, ecx
add eax, ecx
ret
흠. 무슨 일이 일어난 걸까?
로드들이 하나로 접히는 것은 ISel 단계에 도달해서야 이루어지므로,
load_le32()가 인라인될 때는 아직 완전히 최적화되지 않은 상태다. DAGCombiner는 로드의 각 바이트 출처를 추적할 때, 중복 로드를 도입하지 않기 위해 함수의 다른 곳에서도 사용되는 바이트를 특별히 제외한다. 일반적으로는 그럴듯한 판단일 수 있다. 결국 캐시 히트에도 비용은 있으니까. 하지만 이 경우에는 분명히 최적이 아니다.
DAGCombiner로부터 중복 로드를 “숨기기” 위해 AggressiveInstCombine을 활용할 수 있을까? 답은 그렇다. 하지만 조심해야 한다. 예를 들어 이것은 작동하지 않는다:
uint32_t load_add_le32(const uint8_t* data)
{
return load<4, false>(data) + data[0];
}
여기서는
load<4, false>()가 인라인된 뒤에 AggressiveInstCombine이 실행되기는 하지만, 이 패스 역시 중복 로드를 만드는 것을 거부한다.11 그러나 속담대로, 한 겹의 간접화로 해결할 수 없는 문제는 없다. 대신
load_le32()에서 함수 템플릿을 호출하게 하면,
load_add_le32()에 인라인되기 전 에 AggressiveInstCombine이 언롤된 루프를 최적화하도록 만들 수 있고, 원하는 결과를 생성할 수 있다 (두 번째 로드를 피하는 추가적인 영리함은 GVN 패스의 몫이다).
연습문제 9: 위 예제들에서
data[0]대신
val & 0xFF를 사용하면 어떻게 되고, 왜 그런가? 어느 함수를 호출하든 작동하게 만들기 위해 작은 변경을 하나 줄 수 있는가?12
두 번째이자 마지막 막으로, 애초에 우리가 무엇을 최적화하고 있었는지 다시 생각해 보자. 우리는
-O<n>플래그를 사용하여 실행 시간이라는 의미의 성능에 초점을 맞춰 왔다. 그렇다면
-Os로 크기를 최적화하는 경우는 어떨까? 이 경우 둘은 우연히 일치한다. 단일 32비트 또는 64비트 로드보다 더 빠르거나 또는 더 작은 코드는 분명 없을 것이다. 하지만 컴파일러도 그렇게 생각할까?
안타깝게도 그렇지 않다. 흥미롭게도
load_be32()(더 정확히는
load<4, true>())만 예외인데, 컴파일러는 루프를 언롤하는 것이 코드 크기 최소화라는 자신의 임무에 어긋난다고 판단했고, 그 결과 후속 패스가 로드를 접을 수 없게 만들었다. 여기서의 해결책은 루프 앞에
#pragma unroll을 써서 정중하게 등을 떠미는 것이다. 그러면 AggressiveInstCombine이나 DAGCombiner가 제 일을 제대로 할 수 있다. (pragma를 피하고 싶다면 재귀 함수 템플릿을 써도 된다.)
이 다소 우회적인 탐색에서 무엇을 얻을 수 있을까? 아마도 가장 큰 주제는 이것일 것이다. 자신이 쓰는 컴파일러와 그것이 해 줄 수 있는 일, 해 줄 수 없는 일을 잘 알아두라는 것. 좀 더 실천적인 조언을 정리하면 다음과 같다:
언어 기능을 사용해 의도를 분명히 드러내라. 컴파일 시점에 아는 것이 있다면, 다른 조건이 같을 때 C++ 템플릿이나 Rust 매크로 같은 수단으로 그것을 명시적으로 표현하는 것이 최적화기에 도움이 될 수 있다. 어떤 경우에는 최적화할 수 없는 단일 일반 함수를 쓰기보다, 소수의 특수화된 함수 집합 중에서 런타임에 하나를 선택하는 편이 더 나을 수도 있다.
템플릿화(다시 말해), 보조 변수, 명시적 제약, 특수화된 함수 등을 통해 조기 최적화 가능성을 최대화하라. 서로 다른 최적화 패스와 그 순서에 대해 대략적인 감이라도 갖고 있으면 여기에 도움이 된다. 컴파일러가 어떤 것을 더 일찍 최적화할 수 있을수록, 유익한 연쇄 효과가 생길 기회도 더 커진다.
잘 알려진 패턴을 따르라. 어떤 구문이 더 흔할수록, 누군가가 이미 컴파일러가 그것을 인식하고 최적화하도록 만드는 어려운 일을 해 두었을 가능성이 더 높다. 열 번 중 아홉 번은 영리한 코드보다 단순한 코드가 낫다.
아직도 부족한가? 일반적인 LLVM, 특히 최적화기에 대해 더 깊이 파고들고 싶다면 도움이 될 만한 자료들을 소개한다:
공식 LLVM 문서, 특히:
Nikita Popov의 블로그, 특히:
A whirlwind tour of the LLVM optimizer (YouTube)
여기서 분석하는 최적화를 gcc는 수행하지 않기 때문에 주로 gcc보다 LLVM을 사용하고, 또한 LLVM이 내부 표현에 대한 더 나은 introspection 도구를 제공하기 때문에 LLVM을 사용한다. 개인적으로도 LLVM 코드베이스가 더 잘 문서화되어 있고 찾아다니고 이해하기 쉽다고 느낀다.↩
같은 효과를 위해
__builtin_assume()이나
__builtin_unreachable()를 사용할 수도 있었다(gcc에서도 동작한다). 이들 모두는
llvm.assume()intrinsic으로 번역된다.↩
-O1과
-O2모두에서 여덟 번이다. clang에
-mllvm
-print-pipeline-passes인자를 넘기면 정확히 어떤 패스를 실행하는지 볼 수 있다.↩
LLVM의 중요한 측면 하나는 SSA 변수와 그것을 생성하는 연산 사이에 구분이 없다는 점이다. 이 때문에 명령이 생성한 값(또는 예를 들어 들어오는 인자로서 이용 가능한 값)에 대한 참조는, 이 값을 표현하는 클래스 인스턴스에 대한 직접 포인터로 표현된다.
isImpliedCondition()메서드의 구현을 따라 토끼굴로 내려가 보면, 처리해야 하는 경우가 얼마나 많은지 알 수 있어 유익하다. 다만 상당히 반복적이다.↩
count != 0를 가정하고 변환을 진행해도 충분히 정당하다. 적어도 현재로서는 LLVM이 그렇게까지 냉혹하지는 않다.↩
%rem이다.↩
더 알고 싶다면 A Beginners’ Guide to SelectionDAG (YouTube)를 추천한다.↩
FPGA용 HDL을 작성해 온 하드웨어 엔지니어들에게는 이것이 익숙하게 느껴질 수 있다. AMD Vivado 같은 툴체인은 기대한 방식으로 인식하고 합성할 수 있는 구문 종류에 엄격한 요구사항을 두는데(머신 러닝이 그 용어를 가져가기 훨씬 전부터 inference라고 불리던 과정이다), 예를 들어 상태 기계나 RAM 같은 하드 IP 블록으로 합성할 수 있어야 한다.↩
PR #176101 이전에는 최종 결과만 여러 번 사용되는 경우조차 로드를 접는 것을 거부했지만, 그 변경은 LLVM 22.x 릴리스 브랜치에는 포함되지 않았다.↩
힌트: 글 전반부의
iterate_1()함수는 비슷한 트릭을 사용한다.↩