Structured dataflow analysis for arrays and its use in an optimizing compiler

We extend the well-known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations. This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part. The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile-time cost of obtaining and using it.     

基于GCC关键变量数据流分析算法的程序切片技术

随着程序的规模的扩大和复杂度的提高,通过直接分析源码进行程序切片,变得十分困难。在现有的利用编译优化技术来优化程序切片的方法中,存在无法有效利用程序的编译时信息和编译器的优化技术,以及对语言的支持不完善的问题。为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间的关键变量数据流信息。该程序切片技术可以获取源程序中仅与预设目标函数相关的关键变量和关键语句,缩减程序规模。最后通过实验,证明了该算法的可行性。     

硬件流水处理器设计

利用核内空闲资源加速单线程程序执行的方法,将可并行的代码安排在核内空闲单元上执行,实现代码块在核内的流水操作,从而设计一种具有循环加速能力的硬件流水处理器,可通过改变取值结构和寄存器分配逻辑获得编译器的支持.结果表明,应用该处理器后的spec2000测试程序执行性能提升了40%.     

Making compaction-based parallelization affordable

Compaction-based parallelization suffers from long compile time and large code size because of its inherent code explosion problem. If software pipelining is performed for loop parallelization along with compaction, as in the authors' compiler, the code explosion problem becomes more serious. The authors propose the software lookahead heuristic for use in software pipelining, which allows inter-basic-block movement of code within a prespecified number of operations, called the software lookahead window, on any path emanating from the currently processed instruction at compile time. Software lookahead enables instruction-level parallelism to be exploited in a much greater code area than a single basic block, but the lookahead region is still limited to a constant depth by means of a user-specifiable window, and thus code explosion is restricted. The proposed scheme has been implemented in the authors' VLIW parallelizing compiler. To study the code explosion problem and instruction-level parallelism for branch-intensive code, they compiled five AIX utilities: sort, fgrep, sed, yacc, and compress. It is demonstrated that the software lookahead heuristic effectively alleviates the code explosion problem while successfully extracting a substantial amount of inter-basic-block parallelism     

采用两级软件流水技术的VLIW优化编译器

本文首先提出一种能够充分开发循环程序指令级细粒度并行性的编译技术——两级软件流水,该技术基于URPR软件流水算法,把资源分配和代码优化有机地结合起来;然后叙述采用两级软件流水的VLIW优化编译器;最后给出一个FFT内层循环编译过程的实例及初步实验结果.     

A data-driven VLSI array for arbitrary algorithms

The design of specialized processing array architectures, capable of executing any given arbitrary algorithm, is proposed. An approach is adopted in which the algorithm is first represented in the form of a dataflow graph and then mapped onto the specialized processor array. The processors in this array execute the operations included in the corresponding nodes (or subsets of nodes) of the dataflow graph, while regular interconnections of these elements serve as edges of the graph. To speed up the execution, the proposed array allows the generation of computation fronts and their cancellation at a later time, depending on the arriving data operands; thus it is called a data-driven array. The structure of the basic cell and its programming are examined. Some design details are presented for two selected blocks, the instruction memory and the flag array. A scheme for mapping a dataflow graph (program) onto a hexagonally connected array is described and analyzed. Two distinct performance measures-mapping efficiency and array utilization-and some performance results are discussed     

出具证明编译器中代码优化与程序规范转换

出具证明编译器在软件安全研究得到越来越多的关注,是程序验证研究的一个重要方向.但目前关于出具证明编译器的研究主要是在程序逻辑设计和定理自动化证明方面,很少关注编译优化对规范的影响.而编译优化是决定出具证明编译器是否能走向应用的关键因素之一.通过研究数据流优化的基本行为,提出利用数据流分析结果来变换规范的方法,以使原规范的约束准确而充分地施加于优化后的代码,并实现了一个包含多种优化和相应规范转换的编译器原型系统,展示了方法的可行性.     

单片机的PLC编译程序设计

论述基于单片机的PLC独具特点的目标程序框架结构,定义基于单片机的PLC源语句标准集合及数组表示方法和目标代码集合,阐述了源语句和目标代码之间的映射关系和编译方法,并分析该编译程序结构和盲码技术.对其他单片机应用编译程序编制有一定的参考价值.     

面向密码流处理器的AES算法软件流水实现方法

针对轮函数在分组密码实现过程中耗时过长的问题,提出了面向可重构密码流处理器（RCSP）的高级加密标准（AES）算法软件流水实现方法。该方法将轮函数操作划分为若干流水段,不同流水段对应不同的并行密码资源,通过并行执行多个轮函数的不同流水段,从而开发指令级并行性提高轮函数执行速度,进而提升分组密码的执行性能。在RCSP的单簇、双簇和四簇运算资源下分析了AES算法的流水线划分过程和软件流水映射方法,实验结果表明,该软件流水实现方法使得单分组或多分组不同数据分块的操作并行执行,不仅能够提升单分组串行执行性能,还能够通过开发分组间的并行性来提高多分组并行执行性能。     

软件流水的开销模型和决策框架

软件流水是一种重要的指令调度技术,它通过重叠地执行不同的循环体来提高指令级并行性(instruction level parallelism,简称ILP).模调度是一类被广泛采用的软件流水调度算法.软件流水并非一种无损的优化方法,它具有一定的开销,比如延长了编译时间、增加了寄存器压力等.而且,受到体系结构、调度算法以及程序特性的限制,进行软件流水并不一定能达到理想的加速比,有时反而会引起性能下降.提出了一种面向程序特性的软件流水开销模型,对此模型下的软件流水开销进行了量化分析,并提出了一种基于相关性分析的