Hacker News 2026.04.30 60

바이너리 번역기를 빠르게 — 컴파일 비용을 줄이는 LLVM 레지스터 할당 기법

로제타가 빠르게 동작하는 이유, 사실 안에선 컴파일러가 돌고 있었다

맥북이 인텔에서 애플 실리콘으로 넘어왔을 때, 기존 x86용 앱들이 어떻게 그대로 돌았는지 기억나세요? 로제타 2(Rosetta 2)라는 마법 같은 도구 덕분이었죠. 이게 바로 바이너리 번역(binary translation)이에요. CPU A용으로 컴파일된 기계어를 CPU B용으로 변환해서 실행하는 거예요. QEMU도, 일부 게임 에뮬레이터도, 윈도우의 ARM 위에서 x86 앱 돌리는 기능도 다 같은 원리고요.

이번에 ACM에 올라온 논문이 다루는 건, 이런 바이너리 번역기가 LLVM 컴파일러 인프라를 빌려서 동적으로 코드를 만들어낼 때 발생하는 "컴파일이 너무 느리다"는 고질병이에요. 특히 레지스터 할당(register allocation) — 어떤 변수를 CPU의 어떤 레지스터에 담을지 정하는 단계 — 이 병목이거든요.

왜 레지스터 할당이 비싸냐면

먼저 바이너리 번역기가 뭘 하는지 짚고 갈게요. 원본 기계어를 한 블록(보통 베이직 블록 단위)씩 가져와서, LLVM의 중간 표현(IR)으로 풀어내고, 그 IR을 다시 타깃 CPU의 기계어로 컴파일해요. 이게 실행 도중에 일어나기 때문에(JIT 방식), 컴파일 시간이 곧 사용자가 체감하는 응답 속도에 직접 영향을 줘요. 정적 컴파일러처럼 몇 분씩 걸리는 무거운 최적화는 사치죠.

그런데 LLVM의 기본 레지스터 할당 알고리즘은 그래프 채색(graph coloring) 기반이라 속도보다 코드 품질을 우선해요. 변수들의 생존 구간을 모두 분석하고, 충돌 그래프를 그리고, NP-hard에 가까운 채색 문제를 휴리스틱으로 풉니다. 정적 컴파일에서는 합리적인 선택이지만, JIT에서는 부담이에요.

이 논문이 제안하는 건 저비용 레지스터 할당기예요. 핵심 아이디어를 풀어볼게요. 첫째, 바이너리 번역에서 다루는 IR은 원본 ISA의 구조를 거의 그대로 반영하는 경우가 많아요. 즉 원본 코드에서 이미 레지스터 사용 패턴이 정해져 있다는 뜻이죠. 이 정보를 활용해서 비싼 분석을 건너뜁니다. 둘째, 번역 단위가 작아요(보통 수십~수백 명령어). 그러니 전역 최적화 대신 로컬, 선형 시간 스캔 알고리즘으로도 충분히 좋은 결과가 나와요. 셋째, 스필(spill) 결정 — 레지스터가 모자라서 변수를 메모리로 내쫓는 결정 — 을 정교한 비용 모델 대신 빠른 휴리스틱으로 처리해요.

결과적으로 컴파일 시간을 크게 줄이면서도 생성된 코드의 실행 성능 손해는 미미하게 유지하는 게 이 연구의 기여예요. 트레이드오프 곡선에서 "의미 있는 새 지점"을 찾았다는 게 핵심입니다.

레지스터 할당 흐름에서 어디쯤 위치할까요?

비슷한 문제의식은 리니어 스캔 알고리즘(linear scan register allocation)으로 거슬러 올라가요. 1999년 Poletto와 Sarkar가 제안한 이 기법은 자바 핫스팟 JVM 같은 JIT 컴파일러에서 널리 쓰였죠. 그래프 채색보다 빠르지만 코드 품질은 살짝 떨어지는 트레이드오프였어요. 이후 PBQP, second-chance binpacking 같은 변형이 나왔고요.

LLVM도 자체적으로 fast 레지스터 할당기라는 옵션이 있어요(O0 빌드용). 하지만 이건 정말 빠르기만 하고 품질은 거친 편이라 JIT용으로는 어딘가 어색하죠. 이 논문은 그 사이의 빈 공간 — JIT/바이너리 번역에 특화된, 빠르면서 품질도 괜찮은 할당기 — 을 노리는 거예요.

QEMU의 TCG, 애플 로제타 2의 내부 동적 번역, RISC-V on x86 에뮬레이터들이 모두 같은 고민을 안고 있어요. 이런 도구의 성능을 끌어올리는 데 직접 적용할 수 있는 연구죠.

한국 개발자에게는 어떤 의미일까요?

레지스터 할당 자체를 직접 구현할 일은 많지 않아요. 하지만 이 논문의 사고방식 — "우리 도메인의 특수성을 이용해서 일반 알고리즘의 비싼 부분을 건너뛰자" — 는 어디든 쓰입니다. 데이터베이스 옵티마이저, ML 컴파일러(MLIR, TVM, XLA), 게임 엔진의 셰이더 컴파일까지요. 만약 여러분이 JIT나 동적 코드 생성을 다루는 시스템을 만들고 있다면 꼭 한 번 훑어볼 가치가 있어요. 또 RISC-V 생태계가 커지면서 ARM↔RISC-V, x86↔RISC-V 번역기 수요가 늘어날 텐데, 이 분야 한국 인력이 더 필요해질 거예요.