컴파일러 최적화를 최적화하기

Abstract

꼬마 최적화(peephole optmization)은 컴파일러 성능 향상에 중요한 역할을 하지만, 전역 최적에 도달하기 어렵다는 한계를 가진다. 이는 최적화 규칙의 적용 순서를 정해야 하는 순서 매기기 문제와, 새로운 규칙을 기존 시스템에 추가할 때 발생하는 복잡도에서 비롯된다. 본 글은 이러한 한계를 바탕으로 미래 꼬마 최적화가 나아갈 방향을 논한다. 그 핵심은 최적화 규칙의 자동 생성과 검증, 그리고 적용 순서의 효율적인 탐색이다.

본문

본 글은 성숙한 컴파일러에서 신생 컴파일러로 꼬마 최적화를 이식하는 프로젝트인 Transopt에서 출발한 질문이다. 앞으로의 컴파일러가 가질 꼬마 최적화는 어떤 모습이어야 할까?

꼬마 최적화에는 순서 매기기 문제가 있다. 이는 여러 최적화 규칙을 어떤 순서로 적용할지 정하는 문제이다. 순서 매기기는 NP-Hard이므로 완전한 해결이 어렵다. LLVM도 조건문 기반의 휴리스틱에 의존하기 때문에, 전역 최적이 아닌 국소 최적에 머무를 수 있다.

꼬마 최적화기에 어떤 규칙을 새롭게 추가할지도 중요한 문제이다. 새로운 규칙은 기존 규칙과 복잡하게 상호작용하며, 예기치 않은 버그를 만들 수 있다. 실제로 LLVM에서 꼬마 최적화를 담당하는 InstCombine는 버그가 자주 발생하는 구성 요소로 알려져 있다.

동치 공간 포화 기법(equality saturation)은 다양한 동치 관계를 하나의 표현 공간에 축적한다. 이는 최적화 규칙의 적용 순서에 대한 민감도를 낮추고 효율적인 탐색을 가능케 한다. 초월 최적화기(superoptimizer)는 기존 컴파일러가 놓치고 있는 최적화를 자동으로 찾고, 검사기를 통해 그 정당성을 기계적으로 검증한다.

결국 미래 컴파일러의 꼬마 최적화는 자동화된 탐색 시스템으로 나아가야 한다. 꼬마 규칙은 자동으로 발견되고, 기계적으로 검증되어야 한다. 적용 순서 또한 사람이 하드코딩하는 것에서 벗어나 동치 공간 안에서 자동으로 탐색되어야 한다.