论文部分内容阅读
嵌入式系统通常对性能、实时性、功耗等有着严格的要求,需要非常高效的机器代码。因此,嵌入式软件开发常采用汇编语言。但汇编语言编程费时、调试困难,而且代码难以移植。嵌入式系统的广泛应用和嵌入式软件规模的不断扩大,决定了用高级语言代替汇编语言进行嵌入式软件开发是必然趋势。但使用高级语言编译器生成代码的质量和手工编写的汇编代码相比还有很大差距,不能满足嵌入式系统的要求。因此,嵌入式处理器编译技术研究有着非常重要的现实意义。传统编译技术通常不能直接适用于嵌入式领域,需要进行扩展或者设计全新的算法。传统的编译技术一般基于规则的机器模型,并采用简单启发式方法以达到较快的编译速度。嵌入式处理器一般具有不规则的体系结构特征,且在嵌入式环境中,编译器生成高质量代码的重要性高于编译时间。本文主要研究了嵌入式处理器编译技术的三个问题:嵌入式处理器寄存器分配、多媒体扩展指令集的代码生成、双指令集处理器多目标代码选择。在传统图着色寄存器分配方法中,假设机器模型具有简单的寄存器文件。这些算法采用“degree＜k”测试冲突图结点是否局部可着色,并通过特殊的技巧对此扩展,以适用于不规则的寄存器文件特征。经过多年研究,此问题取得了很大进展。但是,传统图着色寄存器分配算法在进行冲突图结点局部可着色测试时,无法知道邻居结点所分配的颜色,只能采取保守的估算,因而降低了编译生成的代码质量。这是它们难以克服的困难。传统树模式匹配和动态规划技术不能有效利用多媒体处理器的指令集并行,基于传统并行编译技术的扩展一般局限于循环级并行,且没有全局优化标量指令和SIMD指令的使用。传统编译技术一般仅优化单一的目标,例如性能、功耗。嵌入式系统常需同时优化多个目标。单一目标的优化对其它目标有何影响,如何在多个目标间权衡,需要进一步研究。嵌入式系统的复杂性决定了需要采用新的方法学来研究嵌入式编译技术。从元启发式算法以及编译器前后端有机结合这两个角度来研究嵌入式编译技术是本文工作的重要思想。近二十年来,元启发式(Meta-heuristics)算法得到广泛研究。这些算法来自于人们从自然界得到的启发,通过模拟物理过程、生物进化等自然现象,能够克服经典优化算法的局限性,系统地搜索问题的解空间,较好地解决多种优化问题。编译技术中同样存在各种优化问题,尤其在嵌入式环境中,这些问题更加复杂,常使得传统编译技术不能简单地适用。元启发式算法为求解复杂的编译优化问题提供了广阔空间。程序分析是编译优化的基础。可以把编译器前端程序分析的优势和编译器后端的机器相关信息结合起来,以适应复杂的嵌入式环境下编译技术研究的需要。本文主要研究成果和创新包括以下几个方面:1.针对嵌入式处理器不规则寄存器文件体系结构特征,本文提出了一种新的图着色寄存器分配混合演化算法HMA-GRA,突破了传统图着色寄存器分配算法在寄存器冲突图结点局部可着色测试问题上难以克服的障碍,为实现嵌入式处理器寄存器分配器提供了新途径。本文的HMA-GRA算法主要由遗传算法和禁忌搜索算法构成,利用Chaitin算法作为前端对冲突图进行预处理,对剩余冲突图中各结点按照其类型随机分配颜色,计算结点间的冲突数量,通过演化过程逐渐减少图的总体冲突,最终实现图成功着色。此算法不仅可以精确计算冲突图结点是否局部可着色,而且能够用规范的寄存器分配模型代替传统算法中的特殊技巧,以适应嵌入式处理器寄存器文件不规则特征带来的复杂性。2.面向多媒体指令集,本文提出了一种新的SIMD代码生成算法ICG-ME。ICG-ME算法扩展了传统的树模式匹配和动态规划技术,通过修改代码生成器的产生器iburg工具为数据流树结点的每个目标非终结符保留多个匹配规则,以识别构造SIMD指令的并行操作;在编译器前端对存储操作相对于向量寄存器的对齐状况进行数据流分析,并把分析结果传递给编译器后端,以辅助构造SIMD和数据重组指令;最终生成多媒体向量指令和非多媒体标量指令混合的汇编代码。通过结合编译器前端程序分析的优势和编译器后端的机器信息,ICG-ME算法不仅简化了SIMD代码的生成,而且能够同时利用SIMD指令和非SIMD指令,以生成高质量的机器代码。3.以ARM/Thumb双指令集处理器为例,本文提出了用元启发式算法求解编译技术中多目标优化问题的方法学。本文把双指令集处理器代码选择问题表示为权衡程序代码大小和运行时间的多目标优化问题,利用程序profiling技术为其建立数学模型,通过一种多目标蚁群算法结合子集选择的方法求解此问题。4.基于SUIF/MachineSUIF编译器研究框架,我们进一步完善了代码选择、寄存器分配和程序分析的实验环境。我们实现了多种传统的图着色寄存器分配算法和元启发式图着色寄存器分配算法HMA-GRA,实现了多媒体代码生成算法ICG-ME和部分程序分析模块,实现了针对多目标代码生成的蚁群优化算法MOARM-ANT-SS。嵌入式处理器编译技术需要扩展传统的编译技术或者设计全新的算法。本文分析了传统编译技术在嵌入式环境中遇到的关键问题,并以元启发式算法和编译器前后端有机结合的方为基础,研究了嵌入式编译技术的三个问题:嵌入式处理器寄存器分配、多媒体扩展指令集的代码生成、双指令集处理器多目标代码选择。实验结果表明了这些方法的有效性。本文把元启发式算法用于嵌入式编译技术的研究与实现尚处于初步阶段。元启发式算法从新的角度为研究嵌入式编译技术提供了广阔空间。