一句话：提出分层分解与并行搜索的超优化框架，可在大指令集上完整合成最优程序。
现代优化编译器难以达到理论最优，向量处理器的大指令集更使超优化器受限于可合成程序长度。HieraSynth 通过层次化划分候选程序空间来分解超优化问题，降低有效指令集规模；当求解器证明不可实现时剪枝，并并行探索独立子空间以获得近线性加速。它可在许多困难问题上完整穷尽程序空间，从而保证按代价模型最优。作者将其实现为库，并用 RISC-V Vector 超优化器评估：支持最多 700 条指令的指令集、合成 7–8 条指令程序，而此前类似规模仅能处理 1–3 条指令；相同程序大小下可处理大 10.66 倍的指令集，固定指令集下可合成大 4.75 倍的程序，并能超越人类专家优化、缩短合成时间。
Modern optimizing compilers generate efficient code but rarely achieve theoretical optimality, often necessitating manual fine-tuning. This is especially the case for processors with vector instructions, which can grow the instruction set by an order of magnitude. Super-optimizers can synthesize optimal code, but they face a fundamental scalability constraint: as the size of the instruction set increases, the length of the longest synthesizable program decreases rapidly. To help super-optimizers deal with large instruction sets, we introduce HieraSynth , a parallel framework for super-optimization that decomposes the problem by hierarchically partitioning the space of candidate programs, effectively decreasing the instruction set size. It also prunes search branches when the solver proves unrealizability, and explores independent subspaces in parallel, achieving near-linear speedup. HieraSynth is sufficiently efficient to run to completeness even on many hard problems, which means that it exhaustively explores the program space. This ensures that the synthesized program is optimal according to a cost model. We implement HieraSynth as a library and demonstrate its effectiveness with a RISC-V Vector superoptimizer capable of handling instruction sets with up to 700 instructions while synthesizing 7–8-instruction programs. This is a significant advancement over previous approaches that were limited to 1 − 3 instructions with similar instruction set sizes. Specifically, HieraSynth can handle instruction sets up to 10.66× larger for a given program size, or synthesize up to 4.75× larger programs for a fixed instruction set. Evaluations show that HieraSynth can synthesize code surpassing human-expert optimizations and significantly reduce synthesis time, making super-optimization more practical for modern vector architectures.
@article{paperbot2892,
title = {HieraSynth: A Parallel Framework for Complete Super-Optimization with Hierarchical Space Decomposition},
author = {Sirui Lu and Rastislav Bodík},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA2},
year = {2025},
doi = {10.1145/3763162}
}