[LLVM & Clang] LLVM 최적화, 어디까지 아시나요?(LTO, PGO, BOLT)
![[LLVM & Clang] LLVM 최적화, 어디까지 아시나요?(LTO, PGO, BOLT)](https://images.unsplash.com/photo-1581093806997-124204d9fa9d?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=MnwxMTc3M3wwfDF8c2VhcmNofDN8fGVuZ2luZWVyfGVufDB8fHx8MTY3ODIwNzE1NQ&ixlib=rb-4.0.3&q=80&w=2000)
[요약]
- Clang은 LLVM 기반 C/C++/Objective C 오픈소스 컴파일러다. Clang을 사용하면 LLVM의 최적화 기법을 적용하여 프로그램 성능 향상을 이끌어낼 수 있다.
- C/C++ 외 다른 언어도 맞는 프론트엔드를 사용하면 LLVM을 사용할 수 있다.
- LTO는 컴파일시 link 단계에서 적용되는 최적화이다. 함수를 사용하는 파일들이 나눠지거나 언어가 달라도 최적화를 할 수 있다.
- PGO는 런타임에서 생성된 profile data를 사용해 최적화를 하는 방법이다. Profile data를 이용해 다시 컴파일하여 최적화한다.
- BOLT는 링크까지 완료된 바이너리 파일에서 profile data를 이용해 최적화를 한다. PGO, LTO와 같이 적용할 수 있으며 I-캐시 미스 및 메모리 사용량을 줄여준다.
목차
- Intro: GCC를 대체하러 나온 Clang
- Link-Time Optimization(LTO)
- Profile-Guided Optimization(PGO)
- Binary Optimization and Layout Tool(BOLT)
- Recap
1. Intro: GCC를 대체하러 나온 Clang
1-1. GCC - 전통있는 C/C++/ObjC 오픈소스 컴파일러
GCC(GNU Compiler Collection)는 C/C++, Objective-C 등을 지원하는 GNU 프로젝트의 오픈 소스 컴파일러 컬렉션이다. 리처드 스톨만이 1987년 GNU 운영체제용 무료 오픈소스 컴파일러를 공개했는데 이것이 바로 GCC이다.
- 자유 소프트웨어(Free software)
- 프론트엔드-미들엔드-백엔드 구조로 다양한 언어 및 아키텍처 지원
- 활발한 개발 커뮤니티
위와 같은 이유들로 GCC는 Unix 기반 OS에서 가장 많이 쓰이는 컴파일러 중 하나가 되었다.
그런데 맥의 터미널에서 gcc의 버전을 확인하면 Free Software Foundation이 만든 gcc가 나오지 않고 clang이 나온다.
- Clang: LLVM 위에 구축된 C/C++/Objective-C 컴파일러.
- LLVM(Low-Level Virtual Machine): 재사용할 수 있는 모듈러 컴파일러 툴체인
즉, 애플은 Unix 기반 OS인 macOS를 사용함에도 불구하고 gcc를 사용하지 않고 Clang과 LLVM을 사용하고 있다.
왜 애플은 gcc를 사용하지 않을까? 먼저 Clang과 LLVM에 대해서 먼저 알아보자.
1-2. LLVM은 또 뭔데요?
컴파일러의 일반적인 아키텍처
GCC를 포함한 대부분의 컴파일러는 프론트엔드 - 미들엔드 - 백엔드의 3개의 컴포넌트로 구조가 이루어져 있다.
- 프론트엔드: 소스 코드를 파싱해 AST(abstract syntax tree)를 만든다.
- 미들엔드: AST를 loop unrolling과 같은 최적화 작업을 수행한다.
- 백엔드: 코드를 명령어 세트에 매핑해 machine code를 생성한다.
GCC는 이러한 구조를 충실히 잘 따랐기 때문에 C/C++/Objective-C는 물론 Fortran, Ada, D, Go 등의 여러 언어를 지원하고 있다.
그러나 GCC는 모놀로식 어플리케이션으로 한계가 있다. 다시 말하면 GCC의 일부를 다른 컴파일러에 사용하기 어려웠다. 예를 들어 GCC의 C++ 프론트엔드를 문서 생성, 코드 인덱싱, 리팩토링 등에 사용하고 싶어도 GCC 전체를 사용해야 했기 때문이다.
LLVM은 다르다 - 모듈식 컴파일러 프로젝트
LLVM은 재사용 가능한 모듈식 컴파일러 프로젝트를 목표로 2000년 크리스 래트너가 시작하였다.
LLVM은 기존 컴파일러 구조와 비슷하게 프론트엔드-Optimizer(미들엔드)-백엔드로 구성되어 있다.
GCC와의 차이점은 Optimizer가 IR(Intermediate Representaion)을 받아서 처리한다. IR은 RISC(Reduced Instruction Set Computing) 셋으로 표현된 저수준 언어다. IR을 VM이나 인터프리터가 실행할 수 있기 때문에 GCC가 지원하지 못하는 VM 및 인터프리터 방식 언어도 지원할 수 있다.
또한 LLVM은 IR을 받아서 처리하기 때문에 사용하고 싶은 언어의 프론트엔드만 구현하면 Optimizer와 백엔드는 공유해서 사용할 수 있다. GCC도 프론트엔드를 추가하면 가능하지만 LLVM은 훨씬 쉬운 코드 베이스로 되어 있다.
Clang은 LLVM 네이티브 C/C++/Objective-C++ 컴파일러이다. Clang 프론트엔드를 C/C++/Objective-C 프론트엔드로 사용하고 LLVM을 백엔드로 사용한다. GCC 대비 유용한 에러 및 경고 메시지를 제공한다.
이제 Clang과 LLVM이 뭔지 간략히 알아봤으니 애플이 왜 Clang과 LLVM을 사용하게 되었는지로 돌아가보자.
1-3. Clang의 등장 배경 - 애플이 GCC 사용을 대체하기 위해
2007년 아이폰이 발표되기 몇 시간전, 리처드 스톨만은 GPLv3을 발표한다. 그리고 이 GPLv3는 그 이후로 나온 모든 gcc에 적용이 되었다. 이는 사실상 아이폰을 저격한 발표였다. 애플 생태계에서 사용하는 Objective-C의 컴파일러로 gcc를 사용하고 있었기 때문이다.
아이폰은 서명된 앱만 실행할 수 있는 정책을 펼쳤는데 이는 GPLv3를 위배한다. GPLv3의 섹션6에서는 사용자가 프로그램의 소스 코드를 수정한 버전을 장치에 설치할 수 있다고 명시했다. 그러나 아이폰은 수정된 버전의 소프트웨어의 사용을 막는다(DRM).
따라서 애플은 GCC를 대체할 다른 컴파일러가 필요했다. 가장 유력한 후보는 LLVM이었다.
1-4. Clang의 출시
다행히 2005년 애플은 LLVM 프로젝트를 제안한 래트너를 고용했었다. Objective-C를 사용하고 있던 애플은 GCC의 느린 코드 반영 속도와 오래된 코드 베이스가 좋지 않아 LLVM에 관심이 있었기 때문이다. 애플은 GPLv3을 예상하지 못했겠지만 다행히 최고의 전문가가 있던 것이다.
애플은 급하게 LLVM의 C 프론트엔드인 Clang을 출시한다 (Clang 출시 7월 11일, 아이폰 출시 6월 29일).
왜 급하게 출시한 것을 알 수 있냐면...
- C/C++/Objective-C 프론트엔드를 목표로 하지만 C 밖에 지원 안함
- C 컴파일시 배열 초기화 못함, warning 및 에러 못 만듬
즉, 초기의 Clang은 말그대로 허점 투성이였다. 하지만 현재 Clang은 애플, MS, 구글, ARM, 소니, 인텔, AMD 등이 컨트리뷰터로 참여하고 많은 기업에서 쓰고 있는 검증된 컴파일러가 되었다.
1-5. 핵심은 LLVM이다
LLVM이 프론트엔드, Optimizer, 백엔드로 구조가 잘 나누어져 있기 때문에 다양한 최적화 기법들이 쉽게 적용이 될 수 있다. 그리고 LLVM 프론트엔드를 가지고 있는 언어들은 이러한 최적화 기법을 바로 누릴 수 있는 것이 매우 큰 장점이다.
LLVM에 적용된 최적화 기법들 중 몇 가지를 이번 글에서 소개하고자 한다.
- LTO(Link Time Optimization)
- PGO(Profile Guided Optimization)
- BOLT(Binary Optimization and Layout Tool)
이제 다음 문단부터 위 3가지 기법을 하나하나 살펴볼 것이다.
2. Link-Time Optimization(LTO)
2-1. LTO란?
LTO는 컴파일시 link 단계에서 수행되는 최적화다. LLVM은 LTO를 지원하여 개발자가 빌드 시스템이나 Makefile을 변경하지 않아도 최적화를 할 수 있도록 도와준다.
2-2. 컴파일러 최적화 옵션
먼저 LTO를 사용하지 않았을 때 만들어지는 바이너리를 살펴보자.
#include <stdio.h>
int doubleNum(int a) {
return 2*a;
}
int square(int a) {
return a*a;
}
int calculation(int a, int b) {
// square(3) = 9
// double(5) = 10
// return 90;
return square(a) * doubleNum(b);
}
int main() {
int v = calculation(3, 5);
printf("%d\n", v);
return v;
}위의 샘플 코드는 간단한 계산을 출력하는 코드이다. 이 코드를 clang으로 컴파일해보자. 이때 clang의 최적화 옵션은 하나도 주지 않았다.
clang main.c -o main만들어진 바이너리를 dump한 뒤 살펴보자.
0000000100003edc <_doubleNum>:
100003edc: ff 43 00 d1 sub sp, sp, #16
100003ee0: e0 0f 00 b9 str w0, [sp, #12]
100003ee4: e9 0f 40 b9 ldr w9, [sp, #12]
100003ee8: 48 00 80 52 mov w8, #2
100003eec: 00 7d 09 1b mul w0, w8, w9
100003ef0: ff 43 00 91 add sp, sp, #16
100003ef4: c0 03 5f d6 ret
0000000100003ef8 <_square>:
100003ef8: ff 43 00 d1 sub sp, sp, #16
100003efc: e0 0f 00 b9 str w0, [sp, #12]
100003f00: e8 0f 40 b9 ldr w8, [sp, #12]
100003f04: e9 0f 40 b9 ldr w9, [sp, #12]
100003f08: 00 7d 09 1b mul w0, w8, w9
100003f0c: ff 43 00 91 add sp, sp, #16
100003f10: c0 03 5f d6 ret
0000000100003f14 <_calculation>:
100003f14: ff 83 00 d1 sub sp, sp, #32
100003f18: fd 7b 01 a9 stp x29, x30, [sp, #16]
100003f1c: fd 43 00 91 add x29, sp, #16
100003f20: a0 c3 1f b8 stur w0, [x29, #-4]
100003f24: e1 0b 00 b9 str w1, [sp, #8]
100003f28: a0 c3 5f b8 ldur w0, [x29, #-4]
100003f2c: f3 ff ff 97 bl 0x100003ef8 <_square>
100003f30: e0 07 00 b9 str w0, [sp, #4]
100003f34: e0 0b 40 b9 ldr w0, [sp, #8]
100003f38: e9 ff ff 97 bl 0x100003edc <_doubleNum>
100003f3c: e8 03 00 aa mov x8, x0
100003f40: e0 07 40 b9 ldr w0, [sp, #4]
100003f44: 00 7c 08 1b mul w0, w0, w8
100003f48: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003f4c: ff 83 00 91 add sp, sp, #32
100003f50: c0 03 5f d6 ret
0000000100003f54 <_main>:
100003f54: ff 83 00 d1 sub sp, sp, #32
100003f58: fd 7b 01 a9 stp x29, x30, [sp, #16]
100003f5c: fd 43 00 91 add x29, sp, #16
100003f60: bf c3 1f b8 stur wzr, [x29, #-4]
100003f64: 60 00 80 52 mov w0, #3
100003f68: a1 00 80 52 mov w1, #5
100003f6c: ea ff ff 97 bl 0x100003f14 <_calculation>
100003f70: e0 0b 00 b9 str w0, [sp, #8]
100003f74: e9 0b 40 b9 ldr w9, [sp, #8]
100003f78: e8 03 09 aa mov x8, x9
100003f7c: 00 00 00 90 adrp x0, 0x100003000 <_main+0x28>
100003f80: 00 b0 3e 91 add x0, x0, #4012
100003f84: e9 03 00 91 mov x9, sp
100003f88: 28 01 00 f9 str x8, [x9]
100003f8c: 05 00 00 94 bl 0x100003fa0 <_printf+0x100003fa0>
100003f90: e0 0b 40 b9 ldr w0, [sp, #8]
100003f94: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003f98: ff 83 00 91 add sp, sp, #32
100003f9c: c0 03 5f d6 ret
바이너리를 살펴보면 main 함수가 calculation 함수를 호출하고, calculation이 square 함수와 doubleNum 함수를 호출하는 것을 알 수 있다.
이제 optimization 옵션을 붙여서 clang으로 컴파일을 해보자.
clang -O3 main.c -o main
마찬가지로 만들어진 바이너리를 dump해보자.
0000000100003f50 <_doubleNum>:
100003f50: 00 78 1f 53 lsl w0, w0, #1
100003f54: c0 03 5f d6 ret
0000000100003f58 <_square>:
100003f58: 00 7c 00 1b mul w0, w0, w0
100003f5c: c0 03 5f d6 ret
0000000100003f60 <_calculation>:
100003f60: 08 7c 00 1b mul w8, w0, w0
100003f64: 08 7d 01 1b mul w8, w8, w1
100003f68: 00 79 1f 53 lsl w0, w8, #1
100003f6c: c0 03 5f d6 ret
0000000100003f70 <_main>:
100003f70: ff 83 00 d1 sub sp, sp, #32
100003f74: fd 7b 01 a9 stp x29, x30, [sp, #16]
100003f78: fd 43 00 91 add x29, sp, #16
100003f7c: 48 0b 80 52 mov w8, #90
100003f80: e8 03 00 f9 str x8, [sp]
100003f84: 40 01 00 10 adr x0, #40
100003f88: 1f 20 03 d5 nop
100003f8c: 05 00 00 94 bl 0x100003fa0 <_printf+0x100003fa0>
100003f90: 40 0b 80 52 mov w0, #90
100003f94: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003f98: ff 83 00 91 add sp, sp, #32
100003f9c: c0 03 5f d6 retO3로 최적화 옵션을 붙이면 main함수가 calculation 함수를 호출하지 않고 바로 90을 리턴 값으로 반환한다(mov w0 #90). 또한 calculation 함수도 square와 doubleNum 함수를 호출하지 않고 2*(a^2)을 반환하는 것을 알 수 있다.
O3 최적화 옵션은 간단한 함수 호출을 inline으로 처리한다.
2.3 LTO가 하는 일
그런데 inline 최적화가 함수가 들어있는 파일이 분리돼도 적용될까? 아래 코드로 실험을 해보자.
// main.c
#include <stdio.h>
#include "calculation.h"
int main() {
int v = calculation(3, 5);
printf("%d\n", v);
return v;
}
---
// calculation.c
#include "operation.h"
int calculation(int a, int b) {
return square(a) * doubleNum(b);
}
---
// operation.c
int doubleNum(int a) {
return 2*a;
}
int square(int a) {
return a*a;
}이번에도 O3 최적화 옵션을 넣어서 바이너리를 생성하였다.
0000000100003f18 <_main>:
100003f18: ff c3 00 d1 sub sp, sp, #48
100003f1c: f4 4f 01 a9 stp x20, x19, [sp, #16]
100003f20: fd 7b 02 a9 stp x29, x30, [sp, #32]
100003f24: fd 83 00 91 add x29, sp, #32
100003f28: 60 00 80 52 mov w0, #3
100003f2c: a1 00 80 52 mov w1, #5
100003f30: 0f 00 00 94 bl 0x100003f6c <_calculation>
100003f34: f3 03 00 aa mov x19, x0
100003f38: f3 03 00 f9 str x19, [sp]
100003f3c: 60 03 00 10 adr x0, #108
100003f40: 1f 20 03 d5 nop
100003f44: 16 00 00 94 bl 0x100003f9c <_printf+0x100003f9c>
100003f48: e0 03 13 aa mov x0, x19
100003f4c: fd 7b 42 a9 ldp x29, x30, [sp, #32]
100003f50: f4 4f 41 a9 ldp x20, x19, [sp, #16]
100003f54: ff c3 00 91 add sp, sp, #48
100003f58: c0 03 5f d6 ret
0000000100003f5c <_doubleNum>:
100003f5c: 00 78 1f 53 lsl w0, w0, #1
100003f60: c0 03 5f d6 ret
0000000100003f64 <_square>:
100003f64: 00 7c 00 1b mul w0, w0, w0
100003f68: c0 03 5f d6 ret
0000000100003f6c <_calculation>:
100003f6c: f4 4f be a9 stp x20, x19, [sp, #-32]!
100003f70: fd 7b 01 a9 stp x29, x30, [sp, #16]
100003f74: fd 43 00 91 add x29, sp, #16
100003f78: f3 03 01 aa mov x19, x1
100003f7c: fa ff ff 97 bl 0x100003f64 <_square>
100003f80: f4 03 00 aa mov x20, x0
100003f84: e0 03 13 aa mov x0, x19
100003f88: f5 ff ff 97 bl 0x100003f5c <_doubleNum>
100003f8c: 00 7c 14 1b mul w0, w0, w20
100003f90: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003f94: f4 4f c2 a8 ldp x20, x19, [sp], #32
100003f98: c0 03 5f d6 ret
하지만 이번에는 main 함수와 calculation 함수가 하위 함수들을 호출하는다. 함수가 정의된 파일과 호출한 파일이 분리돼있으면 inline이 적용되지 않는 것이다.
그 이유는 컴파일러와 링커의 역할을 보면 알 수 있다.
컴파일러는 소스 파일들을 각각 오브젝트 파일로 만들고 마지막에 링커가 하나의 executable file로 만든다. 컴파일러는 오브젝트 파일을 만들 때 다른 소스 파일을 참고하지 않아 파일을 넘나드는 최적화를 진행할 수 없는 것이다.
하지만 링커는 모든 오브젝트 파일을 참고하므로 링커에서 최적화를 수행하면 가능하지 않을까? 맞다. 그것이 바로 LTO다. LTO 옵션을 넣고 바이너리를 만들어보자.
0000000100003f78 <_main>:
100003f78: ff 83 00 d1 sub sp, sp, #32
100003f7c: fd 7b 01 a9 stp x29, x30, [sp, #16]
100003f80: fd 43 00 91 add x29, sp, #16
100003f84: 48 0b 80 52 mov w8, #90
100003f88: e8 03 00 f9 str x8, [sp]
100003f8c: 40 01 00 10 adr x0, #40
100003f90: 1f 20 03 d5 nop
100003f94: 05 00 00 94 bl 0x100003fa8 <_printf+0x100003fa8>
100003f98: 40 0b 80 52 mov w0, #90
100003f9c: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003fa0: ff 83 00 91 add sp, sp, #32
100003fa4: c0 03 5f d6 ret
Disassembly of section __TEXT,__stubs:
0000000100003fa8 <__stubs>:
100003fa8: 10 00 00 b0 adrp x16, 0x100004000 <__stubs+0x4>
100003fac: 10 02 40 f9 ldr x16, [x16]
100003fb0: 00 02 1f d6 br x16
LTO 옵션을 넣고 바이너리를 만들면 main 함수에서 함수를 호출하지 않고 90을 리턴한다. 더 놀라운 것은 O3에서도 하지 못한 호출하지 않는 calculation, square, doubleNum 함수가 바이너리에서 지워진 것이다. LTO가 꽤 강력한 최적화임을 알 수 있다.
정리하면 LTO를 사용하면 함수가 정의된 파일 위치에 구애받지 않는 최적화가 가능하다.
2-4 LTO는 cross language compile을 가능하게 한다
- 어떤 언어던 프론트엔드 구축시 LLVM 백엔드를 사용해 컴파일을 할 수 있다.
- 링커는 오브젝트 파일들을 모아서 하나의 executable 파일을 만든다.
- 언어가 달라도 LLVM을 사용하면 같은 형식의 오브젝트 파일을 사용하기에 LTO를 쓸 수 있지 않을까?
.c --clang--> .bc --LLVM--> .bc (opt) ---------+
|
.c --clang--> .bc --LLVM--> .bc (opt) ---------+
|
+-ld+LLVM--> bin
.rs --+ |
| |
.rs --+--rustc--> .bc --LLVM--> .bc (opt) -----+
|
.rs --+Rust의 컴파일러 rustc는 LLVM으로 구현되어 LLVM bitcode module (.bc)를 생성한다. clang으로 c를 컴파일해도 마찬가지다. LLVM 링커는 이 LLVM bitcode 모듈을 읽고 합칠 수 있어 언어와 상관 없이 최적화를 수행할 수 있다.
C로 main 함수를 짜고, Rust로 calculation 함수를 만들어 컴파일을 해보자.
#include <stdio.h>
int calculation(int, int);
int main() {
printf("%d\n", calculation(3, 5));
return 0;
}fn double_num(a: i32) -> i32 {
2*a
}
fn square(a: i32) -> i32 {
a*a
}
#[no_mangle]
pub extern "C" fn calculation(a: i32, b: i32) -> i32 {
square(a) * double_num(b)
}
$ rustc --crate-type=staticlib -Clinker-plugin-lto -Copt-level=2 calculation.rs
$ clang -c -flto=thin -O2 main.c
$ clang -flto=thin -fuse-ld=lld -O2 ./main.o ./libcalculation.a -pthread -ldl -o main
$ ./main00000001000005e8 <_main>:
1000005e8: ff 83 00 d1 sub sp, sp, #32
1000005ec: fd 7b 01 a9 stp x29, x30, [sp, #16]
1000005f0: fd 43 00 91 add x29, sp, #16
1000005f4: 48 0b 80 52 mov w8, #90
1000005f8: e8 03 00 f9 str x8, [sp]
1000005fc: e0 02 00 10 adr x0, #92
100000600: 1f 20 03 d5 nop
100000604: 09 00 00 94 bl 0x100000628 <dyld_stub_binder+0x100000628>
100000608: 00 00 80 52 mov w0, #0
10000060c: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100000610: ff 83 00 91 add sp, sp, #32
100000614: c0 03 5f d6 ret
0000000100000618 <_calculation>:
100000618: 08 7c 00 1b mul w8, w0, w0
10000061c: 08 7d 01 1b mul w8, w8, w1
100000620: 00 79 1f 53 lsl w0, w8, #1
100000624: c0 03 5f d6 ret
main에서 함수를 따로 호출하지 않고 바로 90을 리턴한다. C와 Rust로 함수를 분리해 구현했음에도 LTO가 효과적으로 적용된 것이다.
Firefox는 이미 2019년에 LTO를 이용해 C++과 Rust를 넘나드는 빌드 시스템을 구축했다. LLVM과 LTO를 이용하면 C/C++코드에 Rust로 모듈을 작성하고 최적화까지 할 수 있다.
3. Profile-Guided Optimization(PGO)
3-1. PGO란?
PGO는 profile data를 사용해 특정 시나리오에 대한 성능을 높이는 최적화를 말한다. Profile data는 어떤 시나리오에서 프로그램의 사용량(CPU, 메모리, 함수 호출 횟수 등)을 말한다.
PGO는 특히 inline과 layout 변경으로 좋은 성능 향상을 이끌어낸다.
PGO는 다음의 순서로 진행된다.
1) profile data를 얻기 위해 instrumentation 수행
2) profile data 처리
3) profile data로 최적화
Instrumentation은 다음 순서로 진행된다.
- 빌트인 함수(Intrinsic)를 컴파일러가 삽입
- 나중에 컴파일러가 intrinsic들을 최적화된 코드 및 라이브러리로 교체(lowering)
intrinsic 삽입시 모든 함수마다 intrinsic을 삽입할 필요가 없다. MST로 변환하면 카운터 intrinsic의 삽입을 최소화 할 수 있다.
3-2. PGO가 하는 일
Microsoft의 블로그 예시를 따왔습니다
Inline 예시
첫 번째 그림에서 goo, foo, bat에 전부 bar를 inline 해버리면 두 번째 그림처럼 될 것이다. 이렇게 모든 함수에 inline을 해버리면 코드의 크기가 너무 커진다는 단점이 있다.
PGO는 profie data를 사용하여 많이 호출되는 부분만 inline하여 크기와 속도의 트레이드 오프를 맞춘다. 세 번째 그림이 PGO inline을 사용한 예시이다.
Layout 예시
브랜치에서 A->B->D가 실행될 확률이 제일 높으므로 layout에서 A, B, D가 가까이 위치하도록 변경한다.
그 밖의 최적화
위 Switch - case 문에서 가장 많이 들어오는 입력 값이 10이라면, 그 경우 swich case문을 통과하지 않게 최적화를 할 수 있다.
3-3 LLVM PGO 사용 사례
1) 크롬
구글은 2020년 Chrome 85에서 Clang 컴파일러에 PGO를 사용함으로써 10% 성능 향상을 만들었다.
2) Firefox
Mozilla는 최적화된 Clang을 PGO를 통해 만들어 firefox의 컴파일 타임을 9% 감소시켰다.
3) Rust
rustc도 LLVM을 사용하므로 PGO를 사용할 수 있게 되었다.
3-4 PGO는 LLVM만 사용하는가? NO
PGO는 사실 상당히 오래된 기법이다.
1994년 Optimally Profiling and tracing programs에서 profile data를 수집하고 최적화를 하는 기술을 제안하였다.
역사가 오래된만큼 쓰이는 곳도 다양하다. JAVA는 표준 컴파일러에 들어가있지 않지만, GraalVM 컴파일러를 사용하면 PGO를 사용할 수 있다. GCC를 사용하는 Fortran이나 MS의 Visual studio를 사용하는 .Net도 사용할 수 있다. Go는 올해 2월에 릴리즈된 버전 1.20부터 PGO를 지원한다.
언어 외의 예를 보면, 오라클의 Hotspot JVM은 프로그램을 실행시킬 때 리얼 타임으로 profile하여 바이트 코드에서 CPU 네이티브 코드로 컴파일할 때 최적화를 한다. 즉, JIT를 할 때 PGO를 사용하는 것이다.
4. Binary Optimization and Layout Tool(BOLT)
4-1. BOLT란?
2018년 페이스북에서 제안한 더 빠른 로딩시간을 위해 바이너리 파일의 레이아웃을 최적화하는 기법이다. BOLT 적용시 효과가 좋은 어플리케이션은 instruction 캐시와 iTLB 미스가 잦은 대용량 어플리케이션이다. 참고로 논문에서는 데이터 센터 어플리케이션을 예로 들고 있다.
BOLT는 CPU가 캐싱과 branch prediction을 잘 하도록 도와준다. 특히 Instruction TLB 및 CPU의 instruction 캐시의 효율을 높인다. 자주 실행되는 코드 및 함수를 메모리 내부에 가까이 위치시키는 것이 그 예이다.
BOLT는 2022년 1월에 LLVM에 머지되었다. 이제 Clang등 LLVM을 사용하는 컴파일러에서 BOLT를 사용할 수 있다.
4-2. Binary Optimizer
BOLT도 PGO처럼 profile data를 사용해 최적화를 한다. PGO와 다른 점은 BOLT는 post-link 최적화라는 것이다. 이름에서 알 수 있듯이 BOLT는 Binary Optimizer이고, Link까지 완료된 바이너리 파일에서 최적화를 한다.
Binary Optimizer가 가지는 장점은 무엇이 있을까? Profile data는 바이너리 파일의 실행에서 얻어진다. 따라서 바이너리에 Profile data를 사용해 최적화를 하면 IR 레벨에서 사용할 때보다 profile data가 높은 정확도를 가진다.
다시 말하면, 컴파일 파이프라인에서 Profile data를 사용해 최적화를 할 때 초기 단계에서 적용하면 더 많은 최적화를 할 수 있지만 정확도는 떨어진다. BOLT는 바이너리에 Profile data를 사용해 높은 정확도의 데이터로 최적화를 한다.
그러나 Binary Optimizer는 구현하기 까다롭다.
위 코드에서 bar()는 foo 함수에 양수 인자를 집어넣어 B1만 실행이 되고, baz()는 음수 인자를 집어넣어 B2만 실행이 된다. 컴파일러가 bar과 baz에 inline을 하고 바이너리를 생성하면 Binary Optimizer 입장에서 B1과 B2가 동일한 비율로 호출이 되어 layout을 짜기 어렵다. Profile data가 있으면 이를 완화할 수 있으나 foo가 bar와 baz와 다른 모듈에 있으면 link 타임에 inline이 되지 않아 해결되지 않는다.
따라서 Binary Optimizer도 한계를 가지고 있다.
4-3. BOLT가 하는 일
단순히 바이너리 파일을 disassembly해서 최적화를 하는 것은 쉽지 않기 때문에 BOLT는 ELF symbol table 정보에 의존한다. 더 자세히 말하면 BOLT는 Function discovery를 통해 함수 이름과 주소 바운더리를 가져온다. 그 후 debug 정보와 profile data를 통하여 각 함수를 disassembly한다.
Disassembly 후 각 함수마다 branch prediction 정보로 최적화된 CFG(control-flow graph)를 구축하고, 이를 다시 최적화하는 과정을 거친다(Optimization pipeline).
Optimization pipeline에서 최적화하는 과정은 컴파일러와 비슷하다.
- NOP 명령어를 지우거나 짧은 instruction 등을 사용함으로써 I-캐시의 점유를 줄인다.
- ICF(identical code folding)을 사용해 코드 크기를 추가적으로 줄인다. 링커에서 수행했을 때보다 더 많은 함수에 적용 가능하다.
- 자주 호출되는 함수를 성능이 좋게 변경한다.
- load instruction을 단순화한다 - immediate loading instruction으로 변경해 D-cache의 부담을 줄이는 대신 I-cache의 부담을 늘린다.
- 자주 실행되는/되지 않는(hot/cold) 코드 블럭을 재배열하고 나눈다.
- 함수를 재정렬하고 코드 레이아웃을 변경해 I-TLB와 I-cache의 성능을 향상시킨다.
4-4 BOLT의 효과
위 heat map은 주소들이 I-cache에서 fetch되었는지를 알려주는 매트릭스이다. X축의 단위는 블록이다. 예를 들어 Y=0이고 X=0~63는 64개의 블록을 나타내고 각 블록은 14290 byte의 address space이다.
(a) 그래프와 (c) 그래프를 비교하면 BOLT를 적용하는 경우 hot 코드를 모아 적은 블록을 사용하는 것을 알 수 있다. Splitting과 reordering을 통하여 I-cache 및 I-TLB에서 이득을 보았기 때문이다.
정리하면 BOLT를 적용함으로써 Instruction 캐시 미스를 줄여 성능을 향상시키고 프로그램을 사용하는데 필요한 메모리 양을 줄일 수 있다.
5. Recap
LLVM 및 Clang이 무엇인지 간단하게 알아보고 LLVM의 최적화 방법 3가지를 알아보았다.
개발자 입장에서 컴파일러의 최적화 옵션을 사용하면 프로그램의 코드를 바꾸지 않고도 성능을 향상한 것이기 때문에 정말 가성비가 좋은 방법이다.
BOLT의 경우 비교적 최신 기술이고 자료가 많지 않지만 LTO와 PGO는 지원하는 언어도 많고 자료도 많다.
어플리케이션 성능 향상이 필요하다면 적극적으로 도입을 검토해보자.
Reference
만화로 나누는 자유/오픈소스 소프트웨어 이야기 - LLVM 프로젝트
Cross-language link-time optimization using Red Hat Developer Tools
BOLT: A Practical Binary Optimizer for Data Centers and Beyond