RAPO: Retrieval-Augmented Phase Ordering = RAPO: 검색 증강 기반 컴파일러 최적화 단계 순서화 기법

국문 초록 (Abstract)

페이즈 오더링(phase-ordering) 문제, 즉 최적의 최적화 패스 순서를 찾는 문제는 여전히 NP-hard로 알려져 있다. 최근 강화학습에 기반한 접근들은 성능 향상을 보였지만, 각 입력 프로그램마다 막대한 탐색 비용을 요구한다. 본 논문에서는 온라인 강화학습 탐색을 유사도 기반 검색으로 대체하는 검색 증강(retrieval-augmented) 페이즈 오더링 프레임워크인 RAPO를 제안한다. 오프라인 단계에서 RAPO는 IR-BERT를 활용해 LLVM IR을 임베딩한 뒤, k-means로 프로그램들을 클러스터링하고, 각 클러스터에 대해 강화학습으로 발견한 대표적인 패스 시퀀스를 시퀀스 캐시에 저장한다. 컴파일 시에는 새로운 프로그램을 임베딩하여 가장 가까운 클러스터에 매핑하고, 해당 클러스터에 캐시된 시퀀스를 검색해 적용함으로써, “프로그램별 탐색(per-program search)”을 빠른 “유사도 기반 검색(similarity-based retrieval)”으로 전환한다. RAPO는 PPO, DQN, E-greedy 등 다양한 강화학습 정책과 결합 가능한 모델 비종속적(model-agnostic) 구조를 가지며, 경량 폴백 메커니즘도 포함한다. 실험 결과, RAPO는 -Oz 대비 최대 약 18.6%의 IR 명령어 수 감소를 달성하면서 기존 강화학습 기반 베이스라인과 동등하거나 이를 상회하는 성능을 보이는 동시에, 페이즈 오더링 탐색 오버헤드를 최대 약 177배까지 감소시켜, 개별 탐색에 근접한 품질과 실사용에 적합한 효율성을 시사한다.

다국어 초록 (Multilingual Abstract)

The phase-ordering problem—finding optimal pass sequence —remains NP-hard. While recent RL approaches have shown improved results, they impose heavy per-input search costs. We introduce RAPO, a retrieval-augmented phase-ordering framework that replaces online RL exploration with similarity-based retrieval. Offline, RAPO embeds LLVM IR with IR‑BERT, clusters programs via k-means, and stores each cluster’s representative RL‑discovered pass sequences in a sequence cache. During compilation, a new program is embedded, mapped into its nearest cluster, and optimized by retrieving the cached sequence, thereby transforming ``per-program search'' into ``similarity-based retrieval.'' RAPO is model -agnostic (compatible with PPO, DQN, and E-greedy, etc.) and includes lightweight fallbacks for corner cases.
RAPO achieves up to 18.6% of IR instruction count reduction over -Oz, matching or outperforming RL baselines, while reducing phase-ordering search overhead up to 177x.
These results suggest that RAPO delivers near–per‑input quality with deployment‑grade efficiency by transforming online phase ordering into fast, similarity‑driven retrieval.

목차 (Table of Contents)

• Chapter 1. Introduction 1
• Chapter 2. Background 5
• 2.1 Phase Ordering 5
• 2.2 Reinforcement Learning 6
• 2.3 Semantic Caching and Retrieval-Augmented Inference 7
• Chapter 3. Motivation 8
• Chapter 4. Overview 12
• Chapter 5. Framework components 15
• 5.1 IR BERT 15
• 5.1.1 Model Architecture 16
• 5.1.2 Input/Output Representations 17
• 5.1.3 Model Pretraining 19
• 5.2 Sequence Cache 20
• 5.2.1 Populating the Cache 20
• 5.2.2 Reading the Cache 22
• 5.3 Retrieval and Fallback Mechanisms 23
• Chapter 6. Methodology 27
• Chapter 7. Experiments 30
• 7.1 Phase Ordering Performance 31
• 7.2 Cluster-Sequence Alignment 36
• 7.3 IR-BERT Embedding Performance 37
• 7.4 Compilation Overhead 38
• Chapter 8. Related Works 41
• Chapter 9. Conclusion 43
• Abstract (In Korean) 56
• Acknowledgment 57