밸런스 게임

Abstract

LLVM의 모듈화는 유지보수성과 확장성을 높이지만, 독립적인 최적화 단계(pass)는 최적의 성능을 보장하지 못한다. Unison은 컴파일러 뒷단의 명령어 배치(instruction scheduling)와 레지스터 할당(register allocation)을 하나의 제약 해결(constraint solving) 문제로 통합한다¹. 본 글에서는 Unison을 통해 모듈화의 한계를 알아보고, 모듈화와 통합 사이에서 컴파일러가 찾는 균형점을 살펴본다.

본문

모듈화와 통합 사이의 선택은 컴퓨터 공학에서 가장 중요한 밸런스 게임일지 모른다. LLVM은 컴파일러를 독립적인 모듈과 최적화 단계로 구성하여 유지보수성과 확장성을 크게 향상시켰다. 그러나 각 단계가 독립적인 최적화를 하기 때문에, 전체 시스템에서 최선의 성능을 보장하지는 않는다.

컴파일러 뒷단에는 서로 상충되는 목표를 가진 두 최적화 단계가 있다. 명령어 배치기는 $\texttt{load}$와 같이 지연이 큰 명령어를 미리 배치하여, 메모리 접근을 기다리는 동안 독립적인 명령어를 실행해 병렬성을 높인다. 반면 레지스터 할당기는 값의 생존 기간(live range)을 줄여 메모리 접근을 최소화한다. 만약 $\texttt{load}$를 앞당겨 배치하면 메모리 지연은 줄어들지만 생존 기간이 길어져 메모리 접근이 증가할 수 있으며, 반대로 생존 기간을 줄이면 메모리 지연으로 인해 병렬성이 감소할 수 있다. 한 최적화기는 자원을 쉬지 않고 활용하려 하고, 다른 하나는 자원을 오래 점유하지 않으려는 충돌이 발생하는 것이다.

Unison은 명령어 배치와 레지스터 할당을 하나의 통합된 최적화 문제로 해결한다. 두 문제를 제약 해결 문제로 모델링하고, 명령어의 실행 시점과 레지스터 배치, 메모리로 내보낼 값 등을 한번에 결정한다. 한 단계의 결과를 다음 단계의 입력으로 사용하는 기존 방식과 달리, 모든 선택을 함께 고려하여 두 단계의 목적을 동시에 만족하는 해를 찾아 최적 성능을 가진 기계어를 생성한다.

LLVM은 통합된 컴파일러를 모듈화하며 효율적인 컴파일러의 기준이 되었다. 그러나 국소적인 최적화의 한계는 다시 여러 최적화 단계를 통합하여 더 나은 성능을 얻으려는 시도로 이어지고 있다. 모듈화와 통합 사이의 이 오래된 밸런스 게임은 과연 어디로 수렴할까.