Hydra: Generalizing Peephole Optimizations with Program Synthesis
Proceedings of the ACM on Programming Languages(2024)
摘要
Optimizing compilers rely on peephole optimizations to simplify
combinations of instructions and remove redundant instructions.
Typically, a new peephole optimization is added when a compiler
developer notices an optimization opportunity---a collection of
dependent instructions that can be improved---and manually derives a
more general rewrite rule that optimizes not only the original code,
but also other, similar collections of instructions.
In this paper, we present Hydra, a tool that automates the process of
generalizing peephole optimizations using a collection of techniques
centered on program synthesis.
One of the most important problems we have solved is finding a version
of each optimization that is independent of the bitwidths of the
optimization's inputs (when this version exists).
We show that Hydra can generalize 75% of the ungeneralized missed
peephole optimizations that LLVM developers have posted to the LLVM
project's issue tracker.
All of Hydra's generalized peephole optimizations have been formally
verified, and furthermore we can automatically turn them into C++ code
that is suitable for inclusion in an LLVM pass.
更多查看译文
关键词
alive2,generalization,hydra,llvm,peephole optimization,program synthesis,souper,superoptimization
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要