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

Abstract

현재 컴파일러는 순서 매기기 문제(phase ordering problem)로 인해 전역 최적에 도달하기 어렵고, 그 결과 복잡한 규칙과 휴리스틱이 누적된 구조 및 유지보수 문제를 초래한다. 본 글은 이러한 한계를 바탕으로, 최적화 규칙의 자동 생성 및 검증과 최적화 적용 순서에 대한 탐색 효율화를 미래 컴파일러의 핵심 방향으로 제시한다.

본문

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

컴파일러 최적화는 순서 매기기 문제를 안고 살아간다. 임의의 프로그램에 대해 최적의 최적화 경로를 찾는 것은 NP-Hard 문제로, 해결이 불가능에 가깝다. 그 결과, LLVM과 같은 성숙한 컴파일러는 수많은 최적화 규칙과 휴리스틱이 누적된 구조를 가지고, 방대한 탐색 공간 속에서 전역이 아닌 국소 최적점에 머무를 가능성이 높다.

이러한 구조는 유지보수 문제를 지닌다. 새롭게 발견되는 최적화 가능성에 따라 규칙이 덧붙여지며 복잡성이 증가한다. LLVM의 InstCombine과 같은 컴포넌트는 수많은 조건 분기로 이루어져 있으며, 버그에 가장 취약한 영역이다. 하드코딩된 코드의 구조는 확장성과 안정성 모두에서 한계를 드러낸다.

미래의 컴파일러는 최적화를 자동으로 생성하고 검증하며, 이를 효과적으로 탐색하는 시스템으로 발전해야 한다. 컴파일러 최적화는 “어떤 최적화 규칙을 추가할 것인가"와 “최적화 규칙을 어떤 순서로 적용할 것인가"라는 두 가지 탐색 문제를 포함한다.

초월 최적화기(superoptimizer)는 기존 컴파일러가 놓치고 있는 최적화를 자동으로 찾아내며, SMT 검사기를 통해 이러한 규칙의 정당성을 기계적으로 검증할 수 있다. 이는 사람이 규칙을 직접 설계하고 증명하던 기존 방식의 한계를 완화한다. 동치 공간 포화 기법(equality saturation)과 확률적 탐색 기법은 더 넓은 탐색 공간을 효과적으로 탐색할 수 있게 한다.