paperbot · PL 论文追踪

全部论文 待读 收藏

P1 Speeding up SMT Solving via Compiler Optimization

通过编译器优化加速 SMT 求解
FSE Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering2023匹配度 6/10 · 论文属于 SMT/形式化验证基础设施优化,且显式支持浮点理论,可加速浮点程序分析与验证,与用户对浮点程序分析的兴趣相关;但它不涉及 LLM/Agent,也不是直接的静态分析或贝叶斯程序分析工作,因此与核心追踪问题有距离。引用 14 inbox
Benjamin Mikek, Qirun Zhang
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出 SLOT,将 SMT 实例翻译为 LLVM IR 并复用编译器优化进行化简,从而实现求解器无关的 SMT 加速。

SMT 求解器是符号执行、程序合成等工具的核心推理引擎,其速度直接影响这些工具的性能与精度。已有加速手段多依赖在特定求解器内部设计新启发式,工程代价高。本文提出一种新视角:SMT-LLVM Optimizing Translation(SLOT),一种与求解器无关的预处理方法,先把 SMT 问题实例翻译到 LLVM IR,借助成熟的编译器优化通道化简,再转换回 SMT 供原求解器求解。作者针对两类最具应用价值的理论——位向量与浮点数——实现了 SLOT。基于标准 SMT-LIB 基准的广泛实验表明,在固定超时下 SLOT 能显著提高可解公式的数量,对大型基准的平均加速接近 3 倍。

问题
SMT 求解速度是符号执行、程序合成等分析工具的性能瓶颈,而现有加速方法需要在具体求解器内部实现新启发式,工程成本高且难以通用。
方法
提出 SLOT:一种求解器无关的预处理方法,将 SMT 公式(位向量与浮点数理论)翻译为 LLVM IR,利用现有 LLVM 编译器优化通道简化后再转回 SMT 实例。
评估
在标准 SMT-LIB 基准上进行大规模实验,结果显示在固定超时下可解公式数量明显增加,大型基准上平均加速接近 3 倍。
原文摘要(Abstract)

SMT solvers are fundamental tools for reasoning about constraints in practical problems like symbolic execution and program synthesis. Faster SMT solving can improve the performance and precision of those analysis tools. Existing approaches typically speed up SMT solving by developing new heuristics inside particular solvers, which requires nontrivial engineering efforts. This paper presents a new perspective on speeding up SMT solving. We propose SMT-LLVM Optimizing Translation (SLOT), a solver-agnostic pre-processing approach that utilizes existing compiler optimizations to simplify SMT problem instances. We implement SLOT for the two most application-critical SMT theories, bitvectors, and floating-point numbers. Our extensive evaluation based on the standard SMT-LIB benchmarks shows that SLOT can substantially increase the number of solvable SMT formulas given fixed timeouts and achieve mean speedups of nearly 3× for large benchmarks.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@inproceedings{MikekZ23,
  title = {Speeding up SMT Solving via Compiler Optimization},
  author = {Benjamin Mikek and Qirun Zhang},
  booktitle = {FSE},
  year = {2023},
  doi = {10.1145/3611643.3616357}
}