论文摘要
目前程序语言层出不穷,计算机日新月异,导致了程序语言与计算机的多样性,这就给编译器的构造带来了沉重的负担。中间代码的出现,将优化尽量施加到中间语言上,而不是施加到高级语言或低级语言上。中间代码优化过程包含非循环优化和循环优化两个部分。数据流分析是非循环优化技术必要的模型,然而目前的数据流分析模型不能增量式地修改数据流信息,因此构建可增量式的数据流分析模型就成为了非循环优化技术的研究重点;另一方面,循环优化可提高程序的局部性,然而对多个数组访问要分别确定获得理想步长向量对应的变换矩阵,如果这些变换矩阵不相同,解决冲突措施的计算复杂度非常高。本文通过对数据流分析技术的深入研究,引入控制块分解流图来构建控制流树,确定了流图中的回边及循环路径中所包含的节点,通过将这些回边从原流图中消去可构建无环流图,从而简化流图的数据流分析。控制块将流图的控制关系转移到新构建的控制流树的内部控制节点上。使用控制块分解算法将流图转换到控制流树过程中,所创建节点数目不超过n,使用控制流树求解路径表达式和确定回边的时间复杂度不超过O(nlogn)。另外,本文采用将加权系统矩阵每一列的元素相加得到一个新的向量,确定嵌套循环中的大多数数组访问的顺序与存储顺序相一致,在一个较粗粒度上提高嵌套循环的局部性,并大大地降低了计算复杂度。本文还对GCC高级循环变换实现机制进行了深入的研究,确定了影响GCC高级循环变换的主要因素是GCC计算矩阵变换机制不足,通过使用整个嵌套循环统一分析框架,确定理想的循环层次结构,解决了GCC计算矩阵变换机制不足的缺点。最后,使用性能评测数据程序,以GCC编译器为基础平台,对改进前后的GCC编译器进行测试,测试结果表明:改进后的GCC编译器循环变换能力有了较好的提高。