一句话：提出基于约束编程的组合优化方法，统一求解寄存器分配与指令调度，生成优于 LLVM 的可执行代码。
寄存器分配与指令调度是编译器后端核心问题，传统启发式难以全局最优并充分利用处理器特性。本文提出组合优化方法，用约束编程统一建模二者，覆盖现代编译器的完整程序变换，实现开源工具 Unison 并集成 LLVM，可生成可执行代码。在 MediaBench、SPEC CPU2006 及 Hexagon、ARM、MIPS 上评测，平均估计加速 1.1%–10%，代码体积减少 1.3%–3.8%；Hexagon 实测验证了加速。固定时限内可最优求解多达 946 条指令的函数，规模较此前方法近一个数量级，表明组合方法能以编译时间换取代码质量。
This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential in practice : it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain. An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches. The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.
@article{paperbot704,
title = {Combinatorial Register Allocation and Instruction Scheduling},
author = {Roberto Castañeda Lozano and Mats Carlsson and Gabriel Hjort Blindell and Christian Schulte},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {41},
number = {3},
year = {2019},
doi = {10.1145/3332373}
}