一句话：Misaal 用硬件指令形式语义离线剪枝重写规则、在线轻量项重写，实现快速可重定向的合成优化编译器。
基于程序合成的编译器能自动为输入程序选择指令并进行优化，但现有方法合成时间常达数分钟甚至数小时，且难以扩展到现代复杂计算与数据重排指令，而这些指令对张量和模板计算性能至关重要。Misaal 在离线阶段利用硬件指令的形式语义自动剪枝面向现代复杂指令的大规模重写规则搜索空间，并提出一种使在线（编译期）项重写过程极为轻量的新方法，从而让程序在数秒内完成编译。实验表明，与最先进的合成编译器 Hydride 相比，Misaal 将编译时间最多降低几何平均 16 倍；在 x86、Hexagon 和 ARM 上，对图像处理和深度学习负载，其运行时性能与生产编译器 Halide 及 Hydride 相比具有竞争力。
Using program synthesis to select instructions for and optimize input programs is receiving increasing attention. However, existing synthesis-based compilers are faced by two major challenges that prohibit the deployment of program synthesis in production compilers: exorbitantly long synthesis times spanning several minutes and hours; and scalability issues that prevent synthesis of complex modern compute and data swizzle instructions, which have been found to maximize performance of modern tensor and stencil workloads. This paper proposes Misaal , a synthesis-based compiler that employs a novel strategy to use formal semantics of hardware instructions to automatically prune a large search space of rewrite rules for modern complex instructions in an offline stage. Misaal also proposes a novel methodology to make term-rewriting process in the online stage (at compile-time) extremely lightweight so as to enable programs to compile in seconds. Our results show that Misaal reduces compilation times by up to a geomean of 16x compared to the state-of-theart synthesis-based compiler, Hydride . Misaal also delivers competitive runtime performance against the production compiler for image processing and deep learning workloads, Halide, as well as Hydride across x86, Hexagon and ARM.
@article{paperbot3081,
title = {MISAAL: Synthesis-Based Automatic Generation of Efficient and Retargetable Semantics-Driven Optimizations},
author = {Abdul Rafae Noor and Dhruv Baronia and Akash Kothari and Muchen Xu and Charith Mendis and Vikram S. Adve},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729301}
}