Certification of Compiler Optimizations Using Kleene Algebra with Tests
Certification of Compiler Optimizations Using Kleene Algebra with Tests
复制标题
使用 Kleene 代数和测试进行编译器优化认证
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Maria
中科院分区：
文献类型：
--
作者：
D. Kozen;Maria
我们使用Kleene代数和测试来验证各种常见的编译器优化，包括死代码消除、公共子表达式消除、复制传播、循环提升、归纳变量消除、指令调度、代数简化、循环展开、冗余指令消除、数组边界检查消除和哨兵的引入。在每种情况下，我们都给出了最优变换正确性的形式方程证明。
We use Kleene algebra with tests to verify a wide assortment of common compiler optimizations, including dead code elimination, common subexpression elimination, copy propagation, loop hoisting, induction variable elimination, instruction scheduling, algebraic simplification, loop unrolling, elimination of redundant instructions, array bounds check elimination, and introduction of sentinels. In each of these cases, we give a formal equational proof of the correctness of the optimizing transformation.