符号执行中的循环依赖分析方法

符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,从而在不展开循环的情况下生成覆盖归纳变量分支的测试用例。对开源工具Libxml2进行实验,该方法能发现其中2个while循环所引发的数组访问越界错误。     

基于LLVM Pass的复杂嵌套循环自动并行化框架

随着多核处理器的普及应用,针对嵌入式遗留系统中串行代码的自动并行化方法是研究热点.其中,针对具有非完美嵌套结构、非仿射依赖关系特征的复杂嵌套循环的自动并行化方法存在技术挑战.提出了一种基于LLVMPass的复杂嵌套循环的自动并行化框架(CNLPF).首先,提出了一种复杂嵌套循环的表示模型,即循环结构树,并将嵌套循环的正则区域自动转换为循环结构树表示;然后,对循环结构树进行数据依赖分析,构建循环内和循环间的依赖关系;最后,基于OpenMP共享内存的编程模型生成并行的循环程序.针对SPEC2006数据集中包含近500个复杂嵌套循环的6个程序案例,分别对其进行复杂嵌套循环占比统计和并行性能加速测试.结果表明,提出的自动并行化框架可以处理LLVMPolly无法优化的复杂嵌套循环,增强了LLVM的并行编译优化能力,且该方法结合Polly的组合优化,比单独采用Polly优化的加速效果提升了9%-43%.     

嵌套循环到多处理机的映射

给出了将具有变相关的嵌套循环映射到具有分布式存储的多处理机上的两种方法.通过相关向量的分解或由相关向量导入方向向量,可将具有变相关的嵌套循环分解成若干互相没有相关关系的独立部分.由于它们可以被独立地执行,从而可以被映射到各个处理机上并行处理.     

基于GCC的高性能DSP Matrix向量指令集扩展

自动向量化技术是编译器提高程序并行性的优化方法。随着支持SIMD结构处理器的计算平台的广泛应用,自动向量化技术也成为编译器技术研究的热点。GCC编译器是一种开源、跨平台的编译器。本文基于GCC内部自动向量化算法,结合Matrix芯片的体系结构和指令集特点,完成了Matrix向量指令集在GCC后端扩展,实现了基本的自动向量化支持。测试结果表明,扩展后的编译器能够支持Matrix向量指令集,进行基本的自动向量化,同时支持以内建函数方式开发基于Matrix的并行程序。     

出口分支语句的向量化方法

传统的向量化方法和超字并行方法依靠数据依赖关系分析确定程序中的并行性,而依赖关系分析无法处理非结构化控制流语句,现有的编译器对该类语句的向量化能力有限。为此,给出一种面向SIMD扩展体系结构的出口分支语句向量化方法,该方法针对一个向量因子内的出口分支语句,能够有效地进行自动向量化处理。测试结果表明,该方法既充分发掘了程序数据流中的并行性,又保证了控制流语义的正确性。     

典型编译器自动向量化效果评估与分析

SIMD(Single-Instruction-Multiple-Data)体系结构在现代处理器体系结构中扮演重要的角色。多种国产高性能通用处理器也大都实现了SIMD结构。SIMD体系结构提供了短向量数据并行处理能力,编译器自动向量化是应用程序获得性能提升的主要手段之一。使用成熟的支持SIMD的商用处理器平台评估典型编译器自动向量化的效果,对于处理器体系结构的设计以及编译器的分析和设计非常有益。采用SPECCPU2006和SPECOMPM2001基准测试程序,评估了典型编译器(包括Intel编译器、PGI编译器和GCC编译器)的自动向量化的效果。并且以产品级的开源编译器GCC为目标,用手工编写的程序片段(主要是多种类型的循环结构)评估了当前GCC编译器自动向量化的效果,并深入分析了GCC编译器中现有的自动向量化的能力和局限。此项工作为进一步研发高效的编译器自动向量化提供了有价值的参考。     

基于GCC实现飞腾处理器向量处理单元的编译器后端

编译器后端是针对特定目标机器的编译器实现,不同的指令集体系结构需要实现不同的编译器后端。面向飞腾处理器中向量处理单元(FT-VPU)的体系结构和指令集,基于GCC编译器实现了编译器后端,使GCC能够正确编译面向FT-VPU的SIMD指令的内嵌函数。从四路双精度SIMD指令的机器描述出发,总结了在GCC后端所做的实现工作。其对基于GCC编译器实现面向特定目标机器的编译器后端有较大的参考价值。     

FORALL实现过程中的局部性优化

FORALL结构是FORTRAN 95的一种语法，在编译器中高效地实现FORALL结构是一项富有挑战性的工作，局部性优化对其高效实现尤其重要。本文介绍作者在G95编译器中实现FOR ALL结构时用到的两种局部性优化方法--临时空间合并和嵌套循环排序。实验结果表明，局部性优化对提高FORALL结构的性能非常有效。对某类FORALL结构，与Intel的EFC 编译器相比，我们的实现方法能提高30％的性能。     

基于Tree-SSA优化框架的高级循环优化

现代的计算机处理器和计算机系统实现了很多先进技术,要利用这些技术更需要编译器的支持以取得高性能。GCC中Tree-SSA优化框架提供了一个功能强大的程序分析框架。增强的数据依赖分析信息允许编译器变换一个算法以取得更大的局部性,提高资源的利用率以增大吞吐量,提高性能。该文对数据依赖、矩阵变换、循环变换进行了研究,分析了它们的特点,算法和性能,陈述了GCC中循环变换的现状,对以后的研究做出了一定的展望。     

基于数据对齐属性指导的GCC自动向量化优化

主流通用处理器都已经实现了多核并行以及处理器核内的SIMD并行。虽然GCC编译器实现了面向SIMD并行的自动向量化,但是编译器针对OpenMP并行程序的自动向量化效果仍很不理想。针对多线程并行的OpenMP程序,基于GCC的OpenMP编译实现,扩展了数据对齐属性指导语句,使编译器在自动向量化时能够进行更准确的数据对齐与否的判断,优化了GCC编译器的自动向量化。     

复杂非紧密嵌套循环变换在并行编译中的应用

在并行编译中,循环变换是开发程序并行度的主要方法,但存在复杂控制流的非紧密嵌套循环往往无法得到有效的并行化。文章结合分析Benchmark和实现自动并行化系统AFT中复杂非紧密嵌套循环变换的经验,给出复杂非紧密嵌套循环变换的特点及其在并行编译中的应用。     

基于指令Cache和寄存器压力的循环展开优化

循环展开是一种常用的编译优化技术,能够有效减少循环开销,提升指令级并行程度和数据局部性,提升循环的执行效能。然而,过度的循环展开会造成指令Cache溢出,增大寄存器压力,循环展开次数太少又会浪费潜在的性能提升机会,因此寻找恰当的展开因子是研究循环展开问题的核心。基于GCC开源编译器,面向循环展开问题开展深入的分析与研究,针对指令Cache和寄存器资源对循环展开的影响,提出了一种基于指令Cache和寄存器压力的循环展开因子计算方法,并在GCC编译器中实现了该计算方法。申威和海光平台上的实验结果显示,相较于目前GCC中存在的其它展开因子计算方法,所提出的方法可以获得更为有效的循环展开因子,提升了程序性能。在SPEC CPU 2006测试集上的平均性能分别提升了2.7%和3.1%,在NPB-3.3.1测试集上的分别为5.4%和6.1%。     

COMPILE TIME PARTITIONING OF NESTED LOOP ITERATION SPACES WITH NON-UNIFORM DEPENDENCES*

In this paper we address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Parallelizing and partitioning of nested loops requires efficient inter-iteration dependence analysis. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependences. Unlike the case of nested loops with uniform dependences these will have a complicated dependence pattern which forms a non-uniform dependence vector set. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. Cross-iteration dependences are analyzed by forming an Integer Dependence Convex Hull (IDCH). Every integer point in this IDCH corresponds to a dependence vector in the iteration space of the nested loops. A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations within a tile can be executed in parallel and the different tiles can then be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques.     

Evaluation of fortran vector compilers and preprocessors

Many scientific codes can achieve significant performance improvement when executed on a computer equipped with a vector processor. Vector constructs in source code should be recognized by a vectorizing compiler or preprocessor. This paper discusses, from a general point of view, how a vectorizing compiler/preprocessor can be evaluated. The areas discussed include data dependence analysis, IF loop analysis, nested loops, loop interchanging, loop collapsing, indirect addressing, use of temporary storage, and order of arithmetic. The ideas presented are based on vectorization of over a million lines of production codes and an extensive test suite developed to evaluate preprocessors under varying degrees of code complexity. Areas for future research are also discussed.     

A Loop Transformation Algorithm for Communication Overlapping

Overlapping communication with computation is a well-known approach to improving performance. Previous research has focused on optimizations performed by the programmer. This paper presents a compiler algorithm that automatically determines the appropriate loop indices of a given nested loop and applies loop interchange and tiling in order to overlap communication with computation. The algorithm avoids generating redundant communication by providing a framework for combining information on data dependence, communication, and reuse. It also describes a method of generating messages to exchange data between processors for tiled loops on distributed memory machines. The algorithm has been implemented in our High Performance Fortran (HPF) compiler, and experimental results have shown its effectiveness on distributed memory machines, such as the RISC System/6000 Scalable POWERparallel System. This paper also discusses the architectural problems of efficient optimization.     

基于GCC的VLIW编译系统研究

VLIW机器在单个机器周期中同时发射并执行多个的并行操作,从而获得较高的指令级并行度,这些操作之间的依赖分析和调度工作则被完全交给相应的编译器执行,因此VLIW的并行性能能否充分发挥取决于VLIW体系结构相关编译器的质量。GNU开发的GCC是被最广泛使用的编译系统之一,它具有多语言、多平台支持的能力和开放的结构,能够运用各种成熟的常规编译优化技术生成高效的代码。文章分析了VLIW及GCC的结构特点,提出了一种基于GCC的VLIW编译系统设计方案,利用GCC进行RTL中间代码一级的体系结构无关优化和少量体系结构相关优化,在汇编代码一级针对VLIW结构进行体系结构相关的优化,从而充分利用GCC的成熟编译技术快速开发高效的VLIW多语言编译系统。     

支持多重循环软件流水的循环控制机制

ＩＬＳＰ－内外层交替执行的多重循环的软件流水算法是对多重循环进行优化的有效方法。为了保证ＩＬＳＰ算法具有良好的时间效益和空间效益，就必须有一套支持这个算法的行之有效的多重循环软件流水机制。文中将比较详细地介绍一套控制机制。它与多重循环优化编译器相配合，可以有效地支持多重循环的软件流水，并且可以保证ＩＬＳＰ算法具有较高的加速比和较低的空间代价。     

GCC后端中四路双精度短向量寄存器的实现

设计和实现一个新的产品化的编译器通常需要几年时间。基于已有的编译器进行修改和扩展,是研发面向新体系结构的编译器的主要途径。GNU编译器集合(GCC)支持多种高级语言和多种目标处理器平台、文档及源代码开放等。基于GCC的Sparc后端,实现了支持四路双精度SIMD指令的四路双精度短向量寄存器的描述。在此过程中,定义了新的目标机,扩充了一类向量模式,定义了一类新的寄存器约束,实现了四路双精度寄存器的描述,定义了四路双精度SIMD指令的机器描述。对于面向此类SIMD指令的内嵌函数,GCC编译器能够正确使用该类向量寄存器来生成对应的SIMD指令。