摘要
循环优化对于提高Cache性能、发掘程序的并行性以及减少执行循环的开销都有着重要的作用,证明带循环优化功能的现代编译器的正确性已成为可信编译的一个挑战性的问题.形式化证明一个羽翼丰满的优化编译器本质上是不可行的,可以使用替代的方法,即不是证明优化编译器本身,而是形式化证明每一次循环变换前后编译对象的正确性.提出一种新颖的基于扩展逻辑变换系统μTS来证明循环优化正确性的方法.系统μTS在逻辑变换系统TS的基础上扩展了若干条派生规则,经谓词抽象将源程序与目标程序转换为形式化Radl语言后,使用μTS的派生规则能证明常见循环变换的正确性,如循环融合、循环分配、循环交换、循环反转、循环分裂、循环脱皮、循环调整、循环展开、循环铺盖、循环判断外提、循环不变代码外提等.循环优化可以看作一系列循环变换的组合,从而系统μTS能证明循环优化的正确性.为了支持自动化证明循环优化的正确性并出示证据,进一步提出了一个辅助证明算法.最后通过一个典型实例对这一方法进行了详细的阐述,实际效果表明了该方法的有效性.该方法对设计高可信优化编译器具有重要的指导意义.
Loop optimization plays an important role in improving cache performance, making effective use of parallel processing capabilities, and reducing overheads associated with executing loops. Verifying the correctness of modern compilers with loop optimization is a challenge of trustworthy compiling. Formally verifying a full-fledged optimizing compiler is not feasible in nature. Rather than verifying the compiler itself, after every run of the loop transformation, formally verifing the target code produced is a correct translation of the source program. A novel approach is proposed to verify the correctness of loop optimization based on extended logic transformation system ~TS, which extends a number of derived rules from logic transformation TS. After converting source program and target code into formal language Radl by predicate abstracting, one can verify the correctness of common loop transformations using the derived rules of I^TS, such as loop fusion,loop distribution, loop interchange, loop reversal, loop splitting, loop peeling, loop alignment, loop unrolling, loop tiling, loop unswitching, loop-invariant code motion, etc. Loop optimization can be regarded as a series of loop transformation composition so that/zTS can verify the correctness of loop optimization. Furthermore, an aided certified algorithm is put forward in order to automatic verify the correctness of loop optimization and show its proof. Finally this approach is elaborated using one typical example. Practical effects manifest its effectiveness. This approach has important instructive significance in designing high-trusted optimization compiler.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第9期1863-1873,共11页
Journal of Computer Research and Development
基金
江西省教育厅青年科学基金项目(GJJ09461)
关键词
循环优化
可信编译
扩展逻辑变换系统
循环变换
辅助证明算法
loop optimization
trustworthy compiling
extended logic transformation system
looptransformation
aided certified algorithm
