【作者】 刘刚；

【导师】 吴艳霞；

【作者基本信息】 哈尔滨工程大学 ， 计算机系统结构， 2014， 硕士

【摘要】 随着程序设计语言和计算机系统结构的发展,如何对新的语言特性和系统结构进行优化成为现代编译设计的核心。由于“存储墙问题”,循环中数组访问的时间占程序总执行时间的比重通常都比较大。因此,如何更好地优化循环中的数组访问是提升编译性能的关键问题之一。LLVM是目前比较流行的编译器架构,由于在代码优化上的良好表现,越来越多的编译优化研究转向于此框架。但是在处理循环中数组访问时,LLVM所采取的归纳变量优化造成了数组引用计算过于复杂的问题。为了解决此问题,本文提出了一种迭代间数据重用优化算法,以弥补LLVM在循环优化中对数组引用计算的不足。迭代间数据重用优化算法基于LLVM的循环规范化和循环优化处理,用于简化循环中数组访问的地址运算。在该算法的实现过程中,本文结合了归纳变量优化和数组引用标量替换两种优化技术。即在一次循环迭代中,首先对数组引用进行标量替换,将地址变量转化为可识别的归纳变量,使得寄存器分配对数组引用有效;然后对寻址操作进行强度削弱,针对不同体系结构设定不同的归纳变量自增步长,将地址计算转化为简单的标量运算;最后将地址计算结果保存至新的寄存器,以便用于下一次迭代,从而增加数据在循环迭代之间的重用。该优化算法可以有效降低循环体内地址计算的复杂度,再加上LLVM自身的优势,使整个程序的性能得到提升。实验结果表明,在LLVM中加入本文提出的迭代间数据重用优化算法后,与GCC以及添加优化之前的LLVM的对比中,从汇编代码和程序执行时间两个方面验证了该优化算法对于提升程序性能的作用。更多还原

【Abstract】 With the development of programming languages and computer architectures,optimization for new language features and new architectures is becoming the heart of modern compiler design. Since "Memory Wall" problem,time spent on array access in loops accounted for the proportion of total execution time is usually large. Therefore optimization on array access in loops has been one of the key problems for improving compilers’performance.LLVM is a popular optimizing compiler framework currently. More and more researches on compiling optimization turn to this framework for its good performance on code optimization. When dealing with array access in loops, traditional induction variable optimization is used in LLVM, which results in the complication of array reference. To solve this problem, an inter-iteration data reuse optimization algorithm is proposed in this thesis,which makes up for the deficiencies of LLVM in array access.The inter-iteration data reuse optimization algorithm is used to simplify the calculation of array reference in loops based on LLVM loop canonicalization and optimization. This algorithm combines induction variable optimization and scalar replacement of array reference.At each iteration, array reference is substituted with scalar, which converts address variables to recognizable induction variables, and makes register allocation effective for array reference.Then strength reduction is implemented on induction variables by setting stride for different architecture,which converts address calculations to simple scalar ones. At last,the result is stored in a register for the next iteration,so that data can be reused between iterations. This algorithm can effectively reduce the complexity of address computation in loops, and improve the whole program’s performance, coupled with the advantage of LLVM itself.The experiment results show that both assembly code and execution time are better when adding the inter-iteration data reuse optimization presented in the thesis, compared with the result generated by GCC or LLVM without this optimization.更多还原