编译器优化范文

编译器优化范文（精选9篇）

编译器优化 第1篇

关键词：Keil C51,优化设计

C语言是一种结构化的程序设计高级语言。80C51单片机是目前国内外工业测控领域中使用极为广泛的一类8位MCU,C51是面向80C51单片机的C语言。在单片机应用系统开发中采用C语言编程,易于开发复杂的单片机应用程序,易于进行单片机应用程序的移植,有利于产品中的单片机重新选型,可大大加快单片机应用程序的开发速度。因此,用好C51,优化编程,提高执行代码的执行效率、可靠性和易维护性,显得尤为重要。

用C51编写的应用程序须经C51编译器转换生成单片机可执行的代码程序。Keil C51编译器生成的代码紧凑、使用方便、全面支持8051单片机主流产品及其众多的派生系列。因此,下面就针对Keil C51编译器介绍一下C51程序优化设计方法。

1 存储器和数据类型选择

1.1 存储器类型选择

由于单片机系统的存储器资源有限,为了提高执行效率,对存储器类型的设定,应该根据以下原则:只要条件满足,尽量先使用直接寻址片内数据存储器(data),其次设定变量为间接寻址片内数据存储器(idata),在内部存储器数量不够的情况下,才使用外部存储器,而且在外部存储器中,优先选择分页寻址的数据存储器pdata,最后才是片外数据存储器xdata。并且,在内部和外部存储器共同使用的情况下,要合理分配存储器,对经常使用和计算频繁的数据,应该使用内部存储器,其他的则使用外部存储器。根据它们的数量进行分配,尽量减少访问外部存储器,从而提高程序运行效率。

1.2 数据类型选择

(1)尽可能使用最小的数据类型char、unsigned char或bit。这类数据只占用1B或者1位,由于80C51是8位机,显然对它们的操作要比对int或long类型数据操作要方便得多。

(2)尽可能使用unsigned数据类型,原因是80C51机器指令不支持符号运算。当在C源代码中使用了有符号的变量,尽管从字面上看,其操作十分简单,但C51编译器将要增加相应的库函数,产生更多的程序代码去处理符号运算。

所以除了根据变量长度来选择变量类型以外,还要考虑该变量是否会用于负数的场合,如果程序中可以不需要负数,那么可把变量都定义成无符号类型的。

2 避免使用浮点变量

在80C51单片机系统上使用32位浮点数是得不偿失的,这样做会浪费单片机大量的存储器资源和程序执行时间。一定要在系统中使用浮点数的时候,可以通过提高数值数量级或使用整型运算代替浮点运算。在运算时,可以进行定点运算的尽量进行定点运算,避免进行浮点运算。尽量减少乘除法运算,如*2或/2,就可以使用移位操作代替乘除法运算,这样不仅可以减少代码量,同时还能大大提高程序执行效率。处理ints和longs比处理doubles和floats要方便得多,代码执行起来会更快,C51编译器也不用连接处理浮点运算的模块。

3 使用局部变量

一个源文件可以包含一个或几个函数。在一个函数内部定义的变量是局部就是它只在本函数范围内有效。在函数之外定义的变量是全局变量,它可以为本源文件中其它函数所共用,有效范围为:从定义变量的位置开始到本源文件结束。

在编写C51语言程序时,不是特别必要的地方一般不要使用全局变量,而尽可能地使用局部变量,因为:

(1)局部变量只是在使用它时,编译器才为它在内部存储区分配存储单元,而全局变量在程序的全部执行过程中都要占用存储单元。

(2)全局变量使函数的通用性降低了,因为函数在执行时要依赖于其所在的外部变量。如果将一个函数移到另一个文件中,还要将有关的外部变量及其值一起移过去。但若该外部变量与其他文件的变量同名时,就会出现问题,降低了程序的可靠性和通用性。在程序设计中,在划分模块时要求模块的“内聚性”强、与其他模块的“耦合性”弱,即模块功能要单一,与其他模块的相互影响尽量少。而全局变量是不符合这个原则的,一般要求把C51程序中的函数做成一个封闭体,除了可以通过“实参—形参”的渠道与外界发生联系外,没有其他渠道。这样的程序移植性好、可读性强。

(3)使用全局变量过多,会降低程序的清晰性,人们往往难以清楚地判断出每个瞬时各个外部变量的值。在各个函数执行时都可能改变外部变量的值,程序容易出错。因此,要限制使用全局变量。

4 使用库函数

从用户的角度来看,有两种函数:库函数和用户自定义函数。库函数是Keil C51编译器提供的,不需要用户进行定义,可以直接调用。用户自定义函数是用户根据自己需要编写的能实现特定功能的函数,它必须先进行定义之后才能调用。正确而灵活地使用库函数可使程序代码简单、结构清晰、易于调试和维护。

4.1 重视本征库函数

本征库函数是库函数中的一类,它在编译时直接将固定的代码插入到当前行,而不是用汇编语言中的“ACALL”和“LCALL”指令来实现调用,从而大大提高了函数的访问效率。

例如单字节循环位移指令RL A和RR A相对的调令是_crol_(循环左移)和_cror_(循环右移)。如果想对int或long类型的变量进行循环位移,汇编调令将更加复杂,而且执行的时间会更长。对于int类型C库函数为_irol_、iror_,对于long类型函数为_lrol_、_lror_。

再例如JBC指令相对的调令是_testbit_,如果参数位置位,它将返回1;否则将返回0。

4.2 重视复制、比较、移动等子符串处理库函数

子符串处理库函数位于string.h中,其中包括复制、比较、移动等函数:memccpy、memchr、memcmp、memcpy、memmove、memset。在这些函数中,字符串的长度由调用者明确规定,函数可以工作在任何模式下,使用这些函数可以很方便地对字符串进行处理。

例1:使用库函数对字符串进行复制、比较、移动。

5 宏替代无符号数据类型和函数

5.1 宏替代无符号数据类型

在输入源程序时,为了提高输入效率,可使用宏替代无符号数据类型。其方法是在源程序开头,使用#define语句定义。

例2:

#define uchar unsigned char

#define uint unsigned int

#define ulong unsigned long

这样,在输入源程序时,可以uchar、uint、ulong代替unsigned char、unsigned int、unsigned long。在后面的叙述中有可能不加说明地使用uchar、uint、ulong说明定义的变量。

5.2 宏替代函数

对于小段代码,像从锁存器中读取数据,可通过使用宏来替代函数,使得程序有更好的可读性,可把代码定义在宏中,这样看上去更像函数编译器在碰到宏时,按照事先定义的代码去替代宏。宏的名字应能够描述宏的操作,当需改变宏时,只要修改宏定义处即可。

例3:

宏能够使得访问多层结构和数组更加容易,可以用宏替代程序中经常使用的复杂语句,以减少程序输入时的工作量,且有更好的可读性和可维护性,与函数调用相比较,执行效率更高,但程序的执行代码较大,因编译器将定义的宏内容直接嵌入到代码中。

6 尽量使用小存储模式

C51提供了3种存储器模式存储变量、过程参数和分配再入函数堆栈。应该尽量使用小存储器模式,即SMALL模式。应用系统很少需要使用其他两种模式,像有大的再入函数堆栈系统那样。一般来说如果系统所需要的内存数小于内部RAM数时,都应以小存储模式进行编译,对其它存储模式可以由PDATA和XDATA进行说明。

在SMALL模式下,DATA段是所有的内部变量和全局变量的默认存储段,所有参数传递都发生在DATA段中。如果有函数被声明为再入函数,编译器会在内部RAM中为它们分配空间。这种模式的优势就是数据的存取速度很快,但由于片内RAM空间有限,对于较大的程序还得采用LARGE存储器模式。

7 C51和汇编语言的混合编程

在模块化程序开发过程中,一般用汇编语言编写与硬件有关的程序,用C51语言编写主程序及数据处理程序。使用混合编程技术可以很方便地在一些较大的C51程序中加入已有的汇编驱动程序。在编写较大的程序时利用已有的汇编程序一方面可以节约大量的程序开发时间;另一方面在编写驱动程序时,使用汇编语言可以保证部分对时间和稳定性有严格要求的程序段。同时,混合编程中的C51和汇编语言的使用仍然和独立开发时基本一样,只是在使用不同的语言时,需要注意不同函数之间的调用格式和参数传递的规定。

8 结语

在实际进行项目开发时,如果能遵守科学的工程开发规则,灵活地运用C语言的强大功能,熟悉硬件特点,就能够在较短时间内编写出高效率、高可靠、易维护的嵌入式系统的执行代码。

参考文献

[1]谭浩强.C程序设计[M].北京:清华大学出版社,1991.

[2]张齐,杜群贵.单片机应用系统设计技术-基于C语言编程[M].北京:电子工业出版社,2004.

[3]徐爱钧.8051单片机实践教程-asm51汇编语言与C51高级语言应用[M].北京:电子工业出版社,2005.

[4]李鸿.单片机原理及应用[M].长沙:湖南大学出版社,2004.

C编译器的设计 第2篇

作者：陆晓春

下载设计文档与代码

前言：这个是我们这学期编译课所要求的大程，我做的是一个C－的编译器，功能不多，但运行正常，开发步骤比较明确，希望与大家共享，

编译器运行效果图如下：

设计文档基本内容如下：

1) 整体框架

2) 词法分析

Class CTokenizer

Class CScaner

C关键字表

标识符词法

3) 语法分析

Class CParser

Grammar

基本树形结构

支持的语句及运算

4) 建立符号表

Class LineListRec

Class BucketListRec

Class CSymbolTable

Class CFunArgsCheck

5) 类型检测

Class CAnalyzer

类型匹配

函数调用参数检测

6) 代码生成

PCode

80X86 ASM

7) 总结

虚拟机中的编译优化技术 第3篇

过去10年, 能够在虚拟机上运行的程序语言“大行其道”, 非常典型的例子:Java语言以及最近流行的CLR (Common Language Runtime) 。基于虚拟机执行的编程语言的流行使得针对虚拟机技术的研究也越来越热。

虚拟机体系结构与传统静态编译相比, 具有一些优势特性, 例如:可移植的程序表示、安全机制、内嵌的自动内存管理、线程管理、以及动态类加载等等。有些编程语言充分利用并实现了这些特性从而获得了巨大成功。同时, 这些新特性也给传统静态编译技术带来了巨大的挑战。怎样充分利用这些传统优化技术来获得高性能成为业界和科研机构关注的重要问题。自适应编译优化技术在这种背景下应运而生, 它的主要原理就是通过监测并获得一个程序运行时的行为信息, 并利用这些行为信息来指导优化决策和优化级别。本文介绍了在虚拟机上出现过的程序执行方式以及自适应编译优化技术的产生发展和主要核心技术。

1 虚拟机中的选择性编译

这一部分将详细回顾一些关于虚拟机执行方式核心概念的发展过程, 这些概念极大的影响了当代虚拟机应用的选择性优化技术。

1.1 解释器

早期的解释器, 如Lisp解释器可以看作是最早的“虚拟机”。解释执行并没有因为大量动态编译技术的出现而退出历史舞台, 像Perl, Python和MATLAB等一些解释执行的编程语言目前仍在特定的应用领域有着广泛应用。现代解释器采用各种新技术来提高运行效率, 而不是仅仅采用原始的基于switch的实现。例如Lisp提供一项称作尾部递归优化的性能优化技术, Lisp编译器或解释器能够将特定形式的递归翻译为迭代, 从而允许以一种更为简单明快的方式来使用递归数据结构 (如树结构) 。一些研究人员也提出采用特殊硬件支持来提高解释器的执行效率, 出于性价比上的考虑这种方式并没有得到广泛应用。

1.2 即时编译

为了改变解释器执行慢的不足, 众多虚拟机开始利用动态编译器来实现:执行DIR与执行DER, 以及两种执行方式间的相互转换。最简单的一种机制也就是众所周知的即时编译器 (JIT) 。按照约定, 基于JIT的虚拟机在执行之前, 得把所有的程序代码转换成机器码。但是它采用了惰性方式来做这项工作:JIT只有在确定某个代码路径将要执行的时候, 才编译这个代码路径 (因此有了名称“即时编译”) 。这个技术使程序能启动得更快, 因为在开始执行之前, 不需要冗长的编译阶段。Deutsch and Schiffman在Parc Place Smalltalk-80中首次详细描述这种方法。

JIT技术看起来很有前途, 但是它有一些不足。JIT消除了解释的负担 (以额外的启动成本为代价) , 但是由于若干原因, 代码的优化等级仍然是一般般。为了避免应用程序严重的启动延迟, JIT编译器必须非常迅速, 这意味着它无法把大量时间花在优化上。所以, 早期的JIT编译器在优化方面做的比较保守一些。

1.3 选择性动态编译

选择性动态编译执行过程组合了编译、性能分析以及动态编译。基于一个被广泛认同的现实:程序大部分时间都在那些执行得最频繁的代码, 很多虚拟机实现实现了选择性动态编译, 即将编译资源主要用在那些经常要被执行的代码上, 这部分代码通常被称作“热点 (hotspot) ”。虚拟机都利用两种执行方式:一种较为“便宜”的默认执行方式 (解释执行或者是一个无优化的编译器编译执行) , 另一种是比较“昂贵”的执行方式, 也就是用可以做大量优化的编译器专门处理那些程序“热点”。主要过程描述如下:

先以那种“便宜”的方式运行程序, 虚拟机会搜集性能分析数据, 用来决定哪个代码段执行得足够频繁, 值得编译。然后再利用那种“昂贵”的执行方式来执行这些程序中的“热点”。只编译执行最频繁的代码有几项性能优势:没有把时间浪费在编译那些不经常执行的代码上;这样, 编译器就可以花更多时间来优化“热点”代码路径, 因为它知道在这上面花的时间物有所值。而且, 通过延迟编译, 编译器可以访问性能分析数据, 并用这些数据来改进优化决策, 例如是否需要内联某个方法调用。

Hansen在Adaptive FORTRAN实现了第一个能够选择性编译的系统;SELF-93项目不仅实现了Hansen提出的很多技术而且还做了大量的改进;Detlefs和Agesen研究了多种执行方式如解释执行、JIT、hotspot的混合执行相关的许多问题;Jikes RVM可以通过对调用栈采样来获得程序状态信息, 从而用来指导编译器的优化级别。JVM的“hotspot”编译器可以说是选择性动态编译技术的集大成者所, 这里重点介绍一下。

Hot Spot提供了两个编译器:客户机编译器和服务器编译器。默认采用客户机编译器;在启动JVM时, 可以指定server开关, 选择服务器编译器。服务器编译器能够执行许多静态编译器中常见的标准优化, 例如代码提升、公共的子表达式清除、循环展开、范围检测清除、死代码清除、数据流分析, 还有各种在静态编译语言中不实用的优化技术, 例如虚方法调用的聚合内联。服务器编译器进行大量优化以最大化峰值操作速度, 适用于需要长期运行的服务器应用程序。客户机编译器的优化目标, 是减少应用程序的启动时间和内存消耗, 优化的复杂程度远远低于服务器编译器, 因此需要的编译时间也更少。

Hot Spot技术另一个有趣的方面是:编译不是一个全有或者全无的命题。在解释代码路径一定次数之后, 会把它重新编译成机器码。同时JVM会继续进行性能分析, 而且如果认为代码路径特别热门, 或者未来的性能分析数据认为存在额外的优化可能, 那么还有可能用更高一级的优化重新编译代码。

最初版本的Hot Spot在编译的时候每次编译一个方法。如果某个方法的累计执行次数超过指定的循环迭代次数, 那么这个方法就被当作热门方法, 计算的方式是:为每个方法关联一个计数器, 每次执行一个后向分支时, 就会递增计数器一次。但是, 在方法编译之后, 方法调用并没有切换到编译的版本, 需要退出并重新进入方法, 后续调用才会使用编译的版本。结果就是, 在某些情况下, 可能永远不会用到编译的版本, 例如对于计算密集型程序, 在这类程序中所有的计算都是在方法的一次调用中完成的。重量级方法可能被编译, 但是编译的代码永远用不到。为了解决这个问题引入了栈上替换 (OSR) 技术, 支持在循环过程中间, 从解释执行切换到编译的代码 (或者从编译代码的一个版本切换到另一个版本) 。

2 在线反馈导向优化中的剖析技术

所谓在线反馈导向优化 (FDO) 就是收集程序的运行时信息, 然后利用这些反馈信息来动态的决定系统代码何时做何种级别的编译优化。而指导这种决定的信息来源主要是通过对程序进行剖析得到的, 提出FDO这个概念主要有3个原因: (1) FDO能克服静态编译优化技术的限制, 充分发掘不能静态预测的动态信息; (2) FDO能在程序运行状态改变的时候实时的更改编译优化策略; (3) 运行时绑定可以让软件系统更灵活多变。

研究表明通过有效的利用离线剖析信息可以大大提高静态编译优化的性能, 然而如果虚拟机要充分的利用在线剖析信息做到FDO, 就必须解决一个关键问题:怎样减少采集和处理剖析信息以及执行相关的实时变换为程序执行所带来的额外开销。

尽管选择性优化的系统可以为正在运行的程序选择出需要做动态编译优化的候选代码段, 但是FDO常常需要更细粒度的剖析信息, 比方说许多FDO技术需要关于单独的程序语句、对象以及控制流等等的数据。怎样用最小的开销来获得这些细粒度的剖析信息成为阻止很多FDO技术不能有效地实现的主要问题。

为了解决这个问题, 众多虚拟机实现引入了各种各样的剖析技术, 笔者将这些用为实现FDO而采用的程序剖析技术分为4大类:实时服务监测;硬件性能监测;采样;程序插入分析。

(1) 实时服务监测。系统监测虚拟机中各种与运行时服务相关的信息。通常情况下程序对运行时服务的调用可以很好地表现出程序的时间局部性, 系统可以很好地利用这些局部性信息来做出相应的优化, 如动态分派技术利用系统监测那些记录过去分派行为的运行时数据结构, 从而来指导系统当前的分派行为;内存管理系统可以详细地观察到内存分配、垃圾收集、堆的利用等趋势, 这也为FDO提供了丰富的运行时剖析信息。

(2) 硬件性能监测。许多微处理器提供专门的硬件来提供处理器级的在线剖析信息。尽管很多主流处理器都提供了丰富的硬件性能监视单元, 但是很少有虚拟机实现直接利用它们来指导FDO。2004年发表在PLDI的一篇文章描述了ORP虚拟机怎样利用硬件性能监测单元采样Itanium (R) 2上的cache miss信息来指导内存预取。DCPI提供了一个采样系统, 该系统利用ALPHA处理器上的硬件性能计数器产生的中断来确定一个程序中经常被执行的部分。当代虚拟机很少利用硬件性能监测单元来获得剖析信息, 可能是由于与体系结构相关的计数器结构过于复杂, 以及将底层的计数数据映射到高层的程序数据结构比较困难。

(3) 采样。使用采样, 系统可以按照某种机制找到一类事件中有代表性的子集, 利用观测到的这一部分事件的特征来代表整个事件集合的特征, 这样可以大大降低系统收集剖析信息的开销。对很多FDO, 虚拟机需要进一步对程序的调用栈进行采样, 这可以提供上下文相关的调用关系图, 从而指导FDO的内联优化。两个典型的例子是SELF-93和Jikes RVM分别利用了count-down机制和一个timer来决定何时对调用栈进行采样。此外, 很多FDO依赖于更细粒度的剖析信息, 例如基本块的执行频度等等, 只使用基于采样的方式是难以达到目的的, 为此很多系统同时使用了硬件的支持。

(4) 程序插入分析。在运行的程序中插入一些特定指令, 虚拟机就可以利用这些指令来收集丰富的程序动态运行信息。虽然很多剖析技术利用了程序插入分析来指导FDO, 但是许多类型的插入分析会导致巨大的时间开销, 程序运行时间增加30%-1000%是很常见的, 甚至10000%。所以VM如果要将程序插入分析应用在在线剖析上, 就必须想办法降低插入分析的而导致的巨大开销以获得较好的性能。

减少插入分析开销的主要机制就是限制插入代码执行的时间段。例如, 规定虚拟机只能对未被优化的代码做插入分析, 并且允许当虚拟机利用选择性优化机制来重编译一个“热点”时自动终止插入动作。这种方式有很多好处: (1) 插入分析带来的开销与未被优化过的代码的低性能性能相比是非常合算的; (2) 优化器第一次编译一个方法的时候就可以利用剖析信息, 得以尽早进行FDO; (3) 实现这种方法的工程量相对较小;然而, 除了以上好处, 对未被优化的代码进行插入分析也有两个明显的限制; (4) 由于系统仅仅对方法执行的早期阶段进行剖析, 如果方法的行为在执行后期改变了, 剖析信息可能就不能很好的反映候选方法的行为了; (5) 有一些指导FDO的剖析信息很难从通过对未被优化过的代码进行插入分析得到。例如强制内联优化会极大的影响一个方法的结构, 利用在内联之前得到的剖析信息对于通过内联后的代码才能决定的热点路径是非常困难的。

为解决以上问题, Whaley提出了一个“三阶段”模型。在该模型中, 更细粒度的插入分析被放在了第二阶段。另外一个通用解决方案就是选择适当的时候对优化过的代码也进行插入分析。这两种方案在解决上面的两个问题的同时又导致一个新的问题:被选择来进行重优化编译的方法通常是执行频繁的方法, 对这些方法进行大量的插入分析有可能会导致严重的性能退化。

3 结束语

本文主要关注的是虚拟机中对于较低层次程序表示的执行方式, 而对于较高层次的虚拟机应用如J2EE, ASP.NET, Web Services等关注较少, 这些系统也提供了许多自适应的优化技术来管理运行时数据结构, 诸如线程库和消息队列。但是目前还不得而知这些高层次的虚拟机应用是否真正地从这些技术中能够得到性能上的提升或者提升多少。随着虚拟机技术应用日益广泛, 针对虚拟机中的编译优化技术也成为研究的焦点。过去只有很少的几个研究团体具备构建一个可信的虚拟机的资源, 但是今天, 研究人员已经可以很方便地构建起一个高质量的开源虚拟机, 例如Jikes RVM, Mono和ORP。这些资源使得进入这个研究领域的门槛越来越低, 并且也将极大了促进虚拟机以及自适应动态优化编译相关技术的发展。

参考文献

[1]J GOSLING, B JOY, AND G.Steele, The Java Language Specifica-tion[M].Addison Wesley, 1996.

[2]J AYCOCK.A brief history of just-in-time[J].ACM Computing Surveys, 2003 (11) .

[3]G J HANSEN.Adaptive systems for the dynamic run-time optimiza-tion of programs[D].Ph D.dissertation, Carnegie-Mellon University, 1974.

[4]L P.DEUTSCH AND A M.SCHIFFMAN, Efficient implementation of the Smalltalk-80system[C].in Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, 1984.

[5]C CHAMBERS AND D UNGAR.Making pure object-oriented lan-guages practical[C].in ACM Conference on Object-Oriented Pro-gramming Systems, Languages, and Applications, 1991.

[6]U HOLZLE AND D.UNGAR, A Third Generation SELF Implemen-tation:Reconciling Responsiveness with Performance[M].ACM SIG-PLAN Notices, 1994.

[7]B R RAU.Levels of representation of programs and the architecture of universal host machines[C].in11th Annual Workshop on Micro-programming.IEEE Press, 1978.

[8]G L STEELE, JR AND G J.SUSSMAN, Design of a lisp-based mi-croprocessor[C].Communications of the ACM, 1980.

[9]A BERLIN AND H WU.Scheme86:a system for interpreting scheme[C].in1988ACM Conference on LISP and Functional Pro-gramming.ACM Press, 1988.

[10]L P DEUTSCH AND A M.SCHIFFMAN, Efficient implementation of the Smalltalk-80system[C].in Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, 1984.

[11]D E KNUTH.An empirical study of FORTRAN programs[J].Soft-ware-Practice and Experience, 1971 (1) .

编译器优化 第4篇

介绍：smmy_win为Tany小语言的windows版虚拟，通过此款虚拟机可让使用者更直观的观察程序执行情况，可更深入的调试程序。

① 代码区  ：加载好可运行文件后将显示运行代码。并且鼠标左键单击代码，可指定运行断点。（可看到CPU的8号IP寄存器更随改变运行地址）

② 屏幕信息： 显示输入和输出信息。（如果程序中有变量输入，虚拟机会自动弹出输入界面要求输入）

③ CPU信息 ：以‘开始’按钮运行的时候，实时显示寄存器的信息，并可在暂停状态下更改寄存器中的值，方便调试。

④ 运行时钟：以‘开始’按钮运行的时候，CPU按此时钟间隔运作，方便调试，

⑤ 内存状况：以‘开始’按钮运行的时候，实时显示内存的信息，但不可更改内存信息。（设置‘内存显示开始地址’并按‘显示’可按段查看内存）

‘快速运行’功能，将不会有CPU寄存器，和内存的实时显示。将在一个死循环中以最大性能执行代码，用户几乎可以在瞬间得到结果显示在‘屏幕信息’中。

‘命令行’功能，将可以以命令格式启动此款虚拟机。格式：“tmmy_win.exe 运行文件名 1或2” (1.按‘运行’执行；2.按‘快速运行’执行)

作者：孙靖  (您可以任意复制传播此作品，但请附带这份帮助及此声明)

★ 最美的语言范文400字

★ 父亲节短信祝福语最经济版

★ 最简版男女平等广告标语

★ 世间最美的情诗 外国版

★ 中班语言最奇妙的蛋教案

★ 关于微笑是最美丽的语言作文

★ 国旗下讲话微笑是最美的语言

★ 我最欣赏的一个人高中生版作文

★ 中班语言整条街最胖的妈妈教案

编译器优化 第5篇

关键词：多簇,超长指令字,复数指令,编译优化

0 引 言

BWDSP10x数字信号处理器是一款多簇的静态超标量处理器,采用了16发射的超长指令字的体系结构[1]。它有4个计算簇和3个地址产生单元。BWDSP10x拥有丰富的汇编指令集,支持在一个周期执行时间内处理一些比较复杂的操作,如复数运算指令、双字的读写指令。BWDSP10x提供的双字读写指令、复数加法指令和乘法指令[2],指令的形式如下:

其中Macro表示该指令的分簇情况,由指令可以看出可以仅仅利用一条指令来解决一种复数运算操作。然而通常编译器对于复数的运算都会转化到实数范围内对复数的实部和虚部分别进行多次的实数运算之后再将实部和虚部分别写回,这样的处理方法使得程序并不能利用到DSP自身提供的各种复数运算指令。

本文通过对复数运算添加编译指示[3],利用对LD/ST指令的调度和对复数运算的识别将程序中复数运算的多条实数运算指令合并为一条复数运算指令,减少了运算的时钟周期。图1描述了复数运算优化的框架。

1 复数运算的机器描述

在利用目标机器提供了有关复数运算的指令时,首先要对相关的目标或机器指令进行描述,以便在后端的分簇、指令调度等相关阶段使用。在编译器中机器描述分为描述语言和描述转化两部分。描述语言按照一种易表达的规则来描述目标机器,描述转化利用描述语言编写的目标机器信息文件来生成编译器的内部数据表示,并提供外部使用的接口[4]。BWDSP100机器描述主要通过描述目标机器的指令格式信息、资源使用信息、延迟信息和指令信息来将目标机器的指令集信息提供给编译器。机器描述文件主要有以下六个部分组成:

( 1) SECTION Operation_Format描述了源操作数和目的操作数的数目以及类型;

( 2) SECTION Resource,SECTION Resource_Usage描述资源使用信息;

( 3) SECTION Table_Option描述资源选项;

( 4) SECTION Reservation_Table描述资源约束信息;

( 5) Opreand _ Latency和Operation _ Latency来描述延 迟信息。

( 6) SECTION Scheduling_Alternative描述指令调度信息。

复数指令的机器描述的资源使用和延时信息的表示形式如下:

指令格式和指令调度信息的表示形式如下:

2 复数指令的识别与生成

2. 1 概 述

针对BWDSP100的特点,本文设计了复数指令的处理方法。在编译器的前端给复数指令添加编译指示,通过对LD/ST指令的调度处理使得复数的运算指令相对集中,从而在中间寻找复数指令合成的机会。复数指令的优化算法框架如图2所示。

编译器的后端在接收到复数指令的编译指示信息[5]之后,在相应的复数运算基本块内将LD指令前移、ST指令后置,然后利用相应的复数运算的特点识别出复数指令并打上属性信息。LD指令前移、ST指令后置之后就会出现冗余的LD / ST指令,将其删除之后可合成双字的LD/ST指令、复数指令。

2. 2 复数指令的编译指示

在复数运算之前加上编译指示,编译器前端在识别出编译指示命令之后,传递该信息至编译器的后端,显示的告诉编译器对该运算进行针对性的优化。BWDSP100编译器中支持的复数运算指示有六个: 浮点型: COMPLEX_MUL_F,COMPLEX_SUB_F,COMPLEX_ADD_F整型: COMPLEX_MUL ,COMPLEX_SUB,COMPLEX_ADD。一个浮点复数加法的编译指示可如下表示:

指令的编译指示是可以嵌套使用的。如果程序中间有嵌套的编译指示出现,那么在编译的中间代码中间编译指示将按照它们出现次序的逆序方式,放在包含其左右括号( 内) 代码的控制块( cb) 的属性域中。在有些情况下复数运算的控制块中可能含有多种复数编译指示,如程序包含复数乘法和减法的编译指示,那么,在Lcode中可能出现这样的代码序列,四个乘法在前,连接着一个减法和一个加法,再连接着两个加法的情况。而此时如果先做复数加法,则可能将来自复数乘法操作的那条加法( 对于虚部计算) 和复数加法中的第一条加法操作识别合成为一个复数加法目标指令。为了避免此类情况发生,在处理编译指示的顺序上做了一些要求,即: 先做乘法,再做加减。

2. 3 LD / ST 指令的调度

通过移动包含复数编译指示的源语句所对应的Lcode中的读取( LD) 和存储( ST) 操作,将那些加法、减法、乘法等复数运算操作聚合成一段连续的代码,便于后续的识别和变换。具体包括: LD指令的前移和ST指令的后置。LD指令和ST指令的调度算法如下:

在经典的指令调度中,LD指令是不能移动到他前面的那条ST指令之前的[6]。这是由于编译器在无法判断LD指令与之前的ST指令的访存地址是否相同的情况下会默认这两条指令访问同一个地址,而在实际的复数运算中我们需要打破这一默认情况来得到我们需要的结果。另外,由于在程序运行的时候可能有数据依赖或者是函数调用的副作用的存在,因此移动加载和存储操作需要注意防止此类情况导致的程序执行结果错误。所以我们在移动指令的时候必须检测待移动的指令与它越过的指令之间的依赖关系。针对这种情况采取了下面的移动策略:

( 1) 对于控制块( cb) 中的所有LD操作,做顺控制流的正向处理,尽可能前移,但不越过同类操作和过程调用,而且应该与所越过的指令之间不能有依赖关系。LD提前的判定算法如下:

( 2) 对于控制块( cb) 中的所有ST操作,做逆控制流的反向处理,尽可能后移。因为是后移,控制条件稍显复杂些。但基本类似,即不越过同类操作、过程调用和不与所越过的指令发生依赖关系,还不能跨越控制流转移操作,如跳转指令、返回指令等操作。ST后置的判定算法如下:

其中的依赖关系检测主要检测流依赖、反依赖和输出依赖三种常见的依赖关系。在满足这些条件下,将LD/ST指令尽可能地前移/后置,并汇聚成一段连续的加载操作片,这种汇聚不仅有利于双字读写指令的合成同时也为后续的SIMD加载优化提供了便利。在进行LD、ST指令前移后置之后,冗余的LD、ST指令将会显现出来,对于在删除冗余的指令时可能引入的mov操作,可以在后续的优化中利用复写传播进行优化。

从上述介绍知道,在经历了加载和存储操作的移动后,相关的复数运算操作成为连续的操作片,同时LD和ST指令也会在控制块中间连续存放。由于我们在移动这些指令的时候对指令的依赖性进行过检测,连续的LD和ST指令不存在依赖关系,这时候我们又可以将连续的LD和ST指令分别合并成一条指令并行执行,从而能减少始终周期。

2. 4 复数运算操作的识别

对LD、ST指令调度完成之后,相关的复数操作就集中到一起,此时根据不同的复数运算特点来识别出相应的复数指令。对于复数的加法和减法的识别,在编译指示信息的提示下首先需要找到连续的两条加法指令或减法指令,加法/减法操作中必须含有四个寄存器操作数; 对于复数的乘法[7]的识别,需要找到六条连续的指令分别是乘法、乘法、加法、乘法、乘法、减法。前两个乘法操作的目的操作数必须是减法的源操作数( 实部) ,而后两个乘法则必须是加法的源操作数( 虚部) 。在满足这些前提下,识别出复数运算的实部和虚部操作数。复数操作的识别工作能够处理控制块( cb) 中某类复数运算的所有操作序列,将识别出来 的符合条 件的操作 保存到一 个特定的 数组current中。

2. 5 指令合成

1) 双字读写指令的合成

在BWDSP100中提供了一种双字读写指令,针对复数的实部虚部的加载操作,我们刚好可以利用一条双字读写指令将进行运算的复数实部虚部一起加载到寄存器中。在合成双字读写指令之前要先对各指令进行条件判定。

在对用数组形式存放复数的实部虚部时,在进行指令合成判定时候我们根据源操作数是否相同来判定哪两条指令可以合成一条双字指令。其中间代码的形式如下:

例如op 15和op 26的源操作数均为( r 2 pnt) 而,op 25表示将偏移量增加一个,因此我们可以判定这两条指令是从同一基址的相邻地址中加载数据。据此我们可以将这两条指令合成为一条双字的读取指令。指令合成后生成的汇编代码如下:

2) 复数运算操作的目标指令生成变换

根据current中记录的复数运算操作信息,进行相关新操作的生成。如对浮点复数乘法,则产生proc_opc = = LBWop_MUL_COMPLEX_F的乘法操作,其源和目的操作数均为四个寄存器。其中,源操作数来自四个乘法的源操作数,而四个目的操作数则分别来自减法和加法的源操作数。在生成该新指令后,即可删除原来的那四条乘法操作,而保留减法和加法指令,这是因为在bwdsp100中,浮点复数乘法指令不能一步到位,仅返回四次乘法的结果,需要再次计算得到最终结果。而对于整型复数乘法则可以一次完成,因此整型复数乘法指令中,目的操作数仅涉及两个寄存器就已经包含了最终结果。

由于BWDSP拥有16个发射槽,而一般复数运算块中的运算指令没有任何数据依赖关系,他们可以组成超长指令字,因此即使不做指令合成每个复数运算理论上会在1 ~ 2个时钟周期内完成。所以单单从理论时钟周期上来看每个控制块的理论周期不会明显减少。但是经过指令合成之后复数运算块中指令会大大减少,所需要的发射槽也减少,这样节省下来的发射槽可以分配给后续的无依赖关系的指令从而增加了指令的并行性,减少了实际的执行周期,提高编译的性能。

3 复数操作的分簇与寄存器分配

3. 1 分 簇

由于BWDSP100中的复数指令中采用双字连续寄存器,因此,在Lcode中相关的伪寄存器之间的关系必须在指令分簇[8]和实际寄存器分配之前加以明确。比如在复数操作中,伪寄存器r0和r1将来是分派连续物理寄存器,而在某个双字LD中,伪寄存器r0和r3却要分派到连续寄存器,这样的话,就会在随后的分簇或寄存器分派阶段出现矛盾。为解决这些问题,在分簇阶段,我们需要保障复数寄存器均位于相同簇。在进行操作数为数组的复数运算时,由于lcode中的伪寄存器使用过多,就会出现这些操作数被分配到不同的簇上来减少寄存器的压力,这种情况以第一个操作的目的操作数所在的簇信息[9]为基准,其他与复数有关的目的操作数和源操作数的簇信息如果与基准不一致则添加簇间传输操作,并添加bind信息。

3. 2 寄存器分配

BWDSP100编译器使用启发式的图着色算法[10]进行全局的寄存器分配[11]。基本的算法流程是先为函数中的寄存器建立寄存器干涉图[12],然后统计虚拟寄存器的使用频率,依照使用频率的大小依次进行着色。针对复数操作对寄存器的特殊要求,对寄存器分配作出一点修改。将复数指令上的所有寄存器看成是一个整体分配相应的连续寄存器。具体的实现是在寄存器分派阶段,为复数指令操作数分配寄存器时,利用vreg_ptr > flags & = ( ~ R_CONTAINS_COMPLEX) 将寄存器属性标记为R_CONTAINS_COMPLEX,并将这些寄存器添加到vreg_complex_list中,表示寄存器为复数操作所需的寄存器。

4 性能测试

为了验证复数优化方法对编译性能的提升,实验通过对比BWCC在打开复数优化选项和未打开复数优化的情况下FFT_radix4程序的时钟周期进行新能测试。

上面的程序为FFT_radix4程序最内层循环中复数运算,程序的最内层有4次的复数运算,在进行复数编译优化之后这三次的复数运算可以用三条指令在一个周期内完成( 不计读写操作) 。表1对比了FFT_radix4最内层循环在优化前后的指令条数和可并行的指令条数,结果表明最内层指令条数减少了,可并行的指令条数也减少了,这是因为在删除冗余的LD指令的时候有些LD指令是可以和之前的指令并行执行,另外删除冗余的指令可以空出DSP的发射槽,为减少整个程序的时钟周期提供条件。

表2为FFT_radix4程序执行的时钟周期,实验结果表明在进行复数优化之后FFT_radix4程序周期数减少。在性能上有14% ~ 15% 的提升。

5 结 语

编译器优化 第6篇

为了提高多媒体业务的整体集成性能,当代处理器均已陆续采用了基于SIMD的指令集扩展,意图在一个时钟周期上操作多个同构数据,并且该方法已在专用处理器和通用处理器中得到了高效使用,较早如Texas C62XX(Texas Instruments,1998)、Intel IA32(Intel 2000)、AMD K6(Advanced Micro Devices,1999)等等。SIMD是single instruction and multiple data的简写,主要用于实现同时处理相同数学运算的同构操作数[1]。

上世纪,Intel率先在奔腾处理器中加入MMX[2],旨在提高有关图形、影像和声音等应用的处理速度,同时,支持的指令也较为清晰简单。随后即有SSE、SSE2、SSE3、SSE4.1的相继面世,其中的SSE[3]是MMX的超集。具体来说,SSE能够提供更高分辨率的图像浏览,获取高精优质的音视频,在指标效果愈加改进的语音识别方面却只需占取更少的CPU资源,当然,在功能方面,完善了之前非对齐访问相关的应用设计,增加了跨幅、插入、寻找等操作。在此之后应运而生的AVX、AVX2与IMCI,涉及的编译技术则从基于基本块对程序进行分析转到基于循环的分析,尤其对逻辑关系更加复杂的多重循环展开了向量化并行度的深入讨论;更进一步地,应用场景也由图形图像处理延伸到高性能计算中。与此同时,除了Intel积极行动之外,还有许多厂商纷纷进入SIMD的研发天地,重点包括VIS(Sun SPARK)〗、MAX(HP PA-RISC处理器)、Blue Gene/L[4](IBM)、MVI-2(DEC Alpha)[5]、国产的SW-蓝光,以及龙芯[6]、魂心一号[7]等。综上可知,处理器的体系结构一直都在向着更高层次的并行而始终处于可持续、不间断的发展创新中。

如今,SIMD插件不仅在多媒体加速方面获得了成功应用,还已延拓到数字信号处理、图形图像、游戏加速等多个领域[8]。当然就优化实力而言,现阶段SIMD扩展在天然的数据并行、重复的访存模式、重复性的操作局部数据,FFT(快速傅里叶变换)、编解码方面的效果较为明显。并且,在后续的发展实践中,人们发现同样可以使用SIMD来加速科学计算程序,如在对DNA序列进行比对、求根运算和矩阵运算、以及加解密算法等的研发处理中,SIMD早已渗透到方方面面[9]。而指针的别名分析、复杂的数据依赖和控制依赖、以及不规则的访问模式等等,却都阻碍着向量指令的有效挖掘[10]。

本文第一节对比传统向量机和SIDM扩展部件的体系结构说明SIMD的优势,通过列举手写汇编和自动向量化引出自动编译。第2、3节探讨分析了发掘方法、数据布局和部分优化算法。第4节论述了编译优化的未来发展趋势,第5节则给出了全文总结。

1 SIMD研发概述

1.1 体系结构的对比

并行处理计算机在结构方面主要为以下几种:流水线结构、多功能部件结构、阵列结构、多处理机结构和数据流结构[11]。其中,流水线结构将指令执行过程分为若干段,每段执行指令的一部分。当本段指令执行后而即将进入下一段时,下条指令就会流入本段。因此,流水线计算机在整个流水线上可以对若干指令来设定并行处理。SIMD就是在一个控制器下对多个处理单元来选择提供控制[12],对一队列数据中的所有元素进行同类操作,以此实现空间并行,相对于SIMD只是一个通用处理器的插件而言,传统向量机的存储系统和互联结构都展开了专门的设计。

1.2 使用途径

SIMD挖掘可划分为2类:手写汇编和自动向量化。具体来说,手写汇编即手工向量化[13],这就对程序员提出了重点要求,也就是需要具备丰富的实战经验。以及对体系结构和指令集的丰厚知识。但在大规模并行的条件下,指令间数据、控制依赖关系较为复杂,手写汇编工作量甚大,出错概率增加,因而生成的代码很难具备普适性[14],且不同的处理器,向量化指令集在配置上也各有不同,相应地也未能呈现良好可移植性。而自动向量化则是从编译器角度出发,通过对程序的控制流、数据流进行分析,自主实现标量代码向量化的方法。在此过程中,程序员已无需考虑应用程序的具体细节,更遑论对程序的单独设计修改,工作量由此将大大减少。不仅如此,编译器还可以对程序生成各种优化处理,这一切均已使得编译器自动向量化正日渐成为SIMD程序向量化的主要工作方式。

1.3 相关研究

目前,SIMD的研究已引起了广泛关注,关注焦点即是围绕关键技术的研究,例如对于相应编译器的研发设计。如VAST编译器对Atil Vec[15]扩展指令集代码的定制融合,支持SSE/SSE2的PGI Workstation Fortran/C/C++编译器、以及支持SSE/MMV/AVX的Intel icc[16]、IBM的xlc、gcc、神威蓝光、龙芯[17]等。

目前,历经十余年的发展演变,SIMD的优化效果仍有待改进与提升,主要可从如下方面斟酌入手:指针别名和挖掘向量化的方法。向量化的挖掘就是如何识别可并行指令,生成向量指令,一般从循环、基本块和函数级进行分析。

2 向量化的挖掘

一般而言,并行处理可分为5个等级和2个粒度,如图1所示。层次越高,粒度越大;层次越低,粒度越小。对于粒度,可将其分为粗粒度和细粒度,SIMD属于细粒度[18]。目前,SIMD涉及的典型向量化方法主要有:基于循环的传统向量化方法、SLP(superword level parallelism)及模式匹配等。

2.1 循环级向量化

循环级向量化在设计上包括着如下步骤:控制流分析、循环预处理、依赖分析、循环变换、向量化代码生成。其中,控制流分析,用于建立中间表示层的控制流分析,在此基础上,通过控制流图识别循环。预处理,用于实现对循环信息的记录,删除冗余代码和外提循环不变代码与规范指针。依赖分析,分析循环中的数据依赖,并以此构造数据流图。循环变换和向量化代码生成实现标量代码到向量代码的替代。经由研究得知,循环变换技术可进一步解析为标量扩张、循环分布、循环合并、分段和展开以及剥离技术[19,20,21]。在此,各分项技术的功能阐释可概述如下。

1)标量扩张。是用编译器生成的临时数组T-temp替代循环中的标量,主要使用场景为循环中标量和数组混用[22]。标量依赖产生的原因是使用相同的存储空间存储临时单元,在此使用标量依赖可以消除依赖,进行向量化。

2)循环分布。循环分布基于语句,将一个循环分解为多个,分解后的循环与原循环拥有相同的迭代空间,是原循环语句的子集。通常,循环分布适用于如下方面:

(1)可向量化循环的分解。(2)将原循环分解为较小的循环,改善Cache与TCB局部性。(3)紧嵌套循环的创建。(4)为减小寄存器压力,将原循环分解为较少变量引用的循环的集合[23]。

循环分布依赖于语句间的依赖关系,以强联通子图对语句依赖关系图进行分解,在循环分布之先,一般需前置语句重排,强联通分量的查找等操作,语句重排可参照tarjian算法[24,25]。

3)循环合并。循环分布的逆过程是循环合并[26],循环合并是将2个及其以上的循环合并为一个大的循环,以此减小组织循环并行的开销,并提高数据局部性。一般,循环合并技术都是在开发并行程序时设计引入的,用于增加程序并行粒度,从而降低额外的同步开销。

4)循环分段和展开。循环分段[19,21]将一个循环划分为不同的段,每个循环中包含了多个原循环的迭代,主要用于将迭代次数较多的一层循环改写为外层并行化和内层向量化的循环。SIMD向量化指令的生成过程同时也是一种隐式循环分段,段长为向量寄存器可以一次处理的数据的个数,同时也是SIMD部件可以一次执行的标量操作数个数。

5)循环交换。循环交换[20,21,27]将紧嵌套循环中2个循环的顺序进行交换,在程序变换中呈现出最高执行效率。主要可在以下方面对性能提供设计改进:

(1)将内外层无依赖循环和有依赖循环进行交换,使得内层循环可向量化。(2)将范围较大的循环交换至外层,增加向量长度。循环交换在本质上是一种迭代空间重排序的方式,其合法性与数据依赖关系有关。

2.2 基本块级

指令级并行中SLP应用广泛,可追溯至2000年由Larsen和Amarasingle[10]首创提出,其设计侧重于在一段代码空间展开并行性的挖掘,最终,仍旧为循环的向量化服务,主要思路是在基本块内寻找相邻的内存访问,并将其配对、打包;同时通过定义使用链(DU)/使用定义链(UD)进行包扩展;而后,组合同构操作[22],实现向量化代码的生成。在具体过程中,按照一定的迭代次数对循环依序处理展开,将地址连续的数据打包,再用向量指令替代同构语句。对迭代内和迭代间SIMD数据向量化,可以将不同循环块中的语句融合到一个基本块中。SLP并行算法流程如图2所示。

综合前述分析可知,超字级并行的优点可做如下基本概述[9]:

1)超字级并行是对基本块进行操作,这既适用于迭代内并行性的挖掘,又对迭代间也实际有效。

2)SLP从内存连续的数据访问出发,提供了对迭代内连续内存数据访问的机会。

3)通过DU和UD完成包扩展,减少寄存器重组等操作。

同样,SLP也存在一定的不足,可具体表述为:首先,SLP实现基本块内语句的并行性是通过循环合并和基本块展开来设计得到的,盲目的循环合并和基本块的展开有时可能会带来比收益更多的性能损耗;其次,三地址化、数据流优化等变换也可能会加大优化难度。

2.3 模式匹配的向量化方法

模式匹配是面向程序特性的一种方法,按照某种特定的模式,使用语句生成树的模式匹配,同时得到典型操作的扩展指令,如许多程序中大量出现的饱和运算、max/min、计算平均值、乘加运算等。这些运算通常处于程序中的功能热点,在执行时间中占据较大比重,但对高级语言来说,大多数却都不能支持这些典型操作,SIMD扩展通常为此提供一些特殊指令的设计,一般而言,使用这些特殊的指令可以显著降低执行时间[22,28]。

通常情况下,因为受限于SIMD扩展体系结构,模式识别则仅是作为传统向量化方法和SLP的补充,而这2种方法在高校等研究机构中则更为常见及普遍。

3 对齐分析及优化

一般来说,SIMD扩展支持展示的数据访问都是在向量寄存器宽度对齐的情况下指定发生的,对于不同的SIMD扩展,内存访问的对齐方式要求也各不相同,同时,无论何种结构,非对齐数据的访问必然引入额外的开销。对齐分析时,需全面分析数据访存与向量寄存器宽度[29],从属于流分析的一种,主要包括过程间对齐分析和别名分析。

为此,展开针对性的研究指出:别名分析来源于c语言中对指针和引用并未设定限制的选择开发。当多于2个存储表达式在同一程序点引用相同存储位置就是指针别名。指针引入了2个基本的问题。一是指针变量在使用过程中可以指向的内存单元不同,预先对某时刻访问的内存单元进行定位将具备一定难度;二是内存单元因为可被多个指针定制访问而形成的内存单元的别名。即指针操作的灵活性使得在运行时期对其指向位置的定位成为一个难题,但其结果往往是其他程序分析、变换的基础,指针别名的精度严重影响着许多应用的性能,包括:自动向量化、安全性分析、bug的检测、硬件合成、以及多线程分析。而且,经过梳理20年的发展历程,已陆续提出了一些技术主要围绕提高别名分析的精度而各显其独特优势,诸如:考虑控制流的流敏感分析[30,31],参考聚类数据类型成员指向关系的域敏感分析[32,33],以及上下文敏感分析[34,35]和路径敏感等多维度静态分析。但是对于动态指针别名分析,还较少见到完备研究。现在,对于指针的别名分析大多就是通过动态插桩和试运行来最终获得[36],将插桩得到的别名信息反馈到向量化阶段指导向量化代码的生成。设计实现框架如图3所示,主要可分为预分析、插桩试运行和反馈阶段。具体地,在预分析阶段,使用静态指针分析与向量化识别的方法构建候选的别名分析集合,而在后续的插桩试运行阶段,将重点研究预分析中确定的候选别名分析集,分析运行时的指针地址、循环迭代次数、上下文和应用点的跨步的长度信息;以此为基础,再依据profiling信息对向量化进行测试,依据测试结果控制运行时版本。

4 未来的挑战

1)现有的向量化算法大多都预设在一种没有控制依赖的理想实现条件下,但在实际使用中,许多的循环内部都存在着严重的控制依赖,虽然已有一部分研究正在关注着应该如何向量化存在控制流的循环,但在处理上却并未臻至有效和成功,如何完善循环中存在着控制流依赖将是自动向量化面临的重大挑战[37]。

2)向量化条件严格。只有在无对齐问题和数据依赖问题均不存在的情况下,循环才可进行向量化,并且对于非对齐和非连续的访存,或者将不能获取向量化,即使能转入向量化也需要使用专门的指令展开设计处理,这就将显著降低向量化的进程效率。对此,有些研究尝试在向量化之前即对收益求取价值评估,以此避免向量化之后可能造成的性能下降的不利后果[23,29]。

3)虽然,基于编译指导的SIMD编译优化技术实现了一部分的向量化功能,但与目前比较主流的Open MP并行化编程语言在种类和功能上都存在较大的差距,所以,需要针对基于编译指导的SIMD编译增加有效知识体系拓展,进一步丰富、强化其功能[27]。

5 结束语

编译原理——C教学编译器设计 第7篇

因此该论文设计了一个简单的类C教学编译器。目的是使学生真正理解编译程序的构造原理和技术,学好“编译原理”课程。选择编写C编译器主要因为C是一种常用的过程式,当前对象式语言的基本上是过程式的,因此掌握类似的C等过程式语言的编译技术,不难实现对象式语言编译程序。此外,该论文最终实现的目标代码是基于一个自定义虚拟机代码,通过对些代码的解释执行来得到最终运行结果。这个技术可以保证该编译器基于平台的无关性,易于移植到不同体系结构的计算机上去。

1 系统分析

C教学编译器的设计目标是将完成从源代码到目标代码生成这一阶段的工作。由于设计该编译器目的是用于教学,所以尽量采用教学上较成熟并已广泛应用的技术和算法。此外为让学生对当前流行的虚拟技术有所了解,该编译器在生成目标代码时先生成虚拟代码,再对虚拟机代码进行解释执行得出最终运行结果。这样就便于在不同目标机器上移植了。C教学编译器采用C语言开发,通过C的编译器自编译生成。

2 总体设计

本文所实现的是一个针对教学编译的编译系统。所以在编译程序实现过程中,要体现出《编译原理》课程的基本内容:词法分析、语法分析、语义分析、中间代码及目标代码的生成及出错处理等,以帮助学生学习,此外[2],在实现过程中,不宜单纯追求运行效率而使用过于复杂的算法;而助为便于学生进一步扩充,程序规模必须适度,因此功能也不应过于复杂。所以,C教学编译器由词法分析、编译预处理、语法分析、语义分析、出错处理、符号表、中间代码生成及优化、选择和发送指令、寄存器分配、生成目标代码执行等等模块组成。在C教学编译器的实现过程中,我们尽量引用新思想、新方法,使学生在学习编译器设计和实现过程中,还会学到其他的知识。比如基于需要给标识符分配空间,对缓冲区的应用,分离哈希链表的设计。同时,在实现目标代码时,行先生成虚拟机的目标代码,再对虚拟机的目标代码指令进行解释执行,得出最终执行结果。这样,便于各种不同机器体系结构之间的移植工作。因为只需要重写将模拟机目标代码转换成机器代码的解释程序即可。整体设计(如图1所示整体设计图)

3 各模块详细设计

模块设计均采用学生比较熟悉且较新的算法,一方面避免了学生陷入算法的细节中,而忽略了对整体的把握。另一方面能帮助学生学习其他的技术。

3.1 词法分析器

词法分析器工作的第一步是接受输入的源程序,每次读入一行源程序代码进入缓冲区,每识别出一个符号,就将其转化为程序的内部约定Token记号,留给语法分析程序识别处理。

为提高扫描器工作的效率,把缓冲区模式设计为一个成对且对半互补的输入缓冲区模式。即一个缓冲区分为两个半区,每个半区的长度为n。每次,扫描器把长度为民的源程序输入到缓冲区的一个半区,如果最后一个单词恰好被截断了,则将源程序中后继长度为n的字符读入别一个半区,两个半区交替使用,达到互补的作用。

在C教学编译器的词法分析阶段,需要识别以下各类符号,并返回内部约定的记号。如关键字、标识符、常数、字符串、运算符、分隔符、注释。除了注释,其余六种符号以根据C语言里的标准定义,先写出它们的DFA,然后编程实现。因为将C语言里的注释写成DFA是非常困难,我们直接根据定义编程处理即可。

由于关键字比较少,至多有三十几个,所以在处理用户自定义标识符过程序中,为节约空间,采用的是动态分配空间,即使用realloc标准C函数。

3.2 语法分析器

C教学编译器的语法分析模块主要进行语法分析,确认输入是否符合语言的文法规则,并建立源程序的编译器内部表示形式-语法树,供进一步处理。C教学编译器的语法分析程序,选择自顶向下的方法,应有Yacc[3.6]工具和手工编写方式进行构造。一方面ANSIC语法的上下文无关描述已经存在。而且是满足自底向上的条件,可以验证是满足LALR(1)文法的。采用YACC工具,不仅一点困难都没有,还可以带来有利的一面,比如,Yacc可以生成语法树,这对下一步的语义分析非常有帮助。有利于以后在语法树上添加语义、代码生成动作。另一方面,C教学编译器主要应用于教学,故为使学生能够清楚的了解语法分析的构造过程,也要手工进行编写。

3.3 符号表构造模块

为了便于进行维护,在符号表模块中采用离链表的杂凑表这一数据结构方式实现,具体方法如下:为每个作用域建立一个新的符号表链接在一起。这样如果查找操作在当前表中没有找到名字,就自动到链接在一起。这样如果查找操作在当前表中没有找到名字,就自动链接的上一层表中查找。离开操作则非常简单,对应于作用域的整个符号表能在一步中释放,不需要每个作用域有一张符号表,由最内层向最外层链接。离开一个作用域只要重设访问(在左边有指示)指向最近的外层作用域。(如图2)所示即符号表结构图。

3.4 语义分析器

C教学编译器的语义分析包括:类型构造、类型检查、一致性检查、相关名字检查、作用域分析、还要各种运算符进行语义检查(不同的运算符对操作数的类型有不同的要求),对if,while,for等语句的条件表达式进行类型判断、优化及其它一些操作。其中,最为重要的是对C语言中特有的指针进行处理,只有把指针处理好,上述,各步骤才能顺利进行。因此,C教学编译器采用了较简单的线性链表来表示C语言中所有类型的指针表示,使复杂的指针处理得到了很好的解决,使类型的指针表示,使复杂的指针处理得到了很好解决,使类型判断、类型检查和类型提升的处理得到简化和顺利完成。

3.5 运行环境

C教学编译器采用简单的栈式运行环境。其中C中的malloc和free等自由分配空间的函数,需要堆式式方法来实现,为减轻学习编译难弃。故将这一函数从类编译器的源语言集合里面剔除了。

3.6 目标代码

虚拟机是针对于真正的计算机而言的一个概念。它是一个假想的模拟真实计算机进行工作的软件系统。它同真实计算机一样,有自己的CPU、指令系统、存储器组织、寄存器组、编制语言及高级语言编写的程序,完成计算或数据处理工作。在C教学编译器中,采用的技术是宏扩展技术,中间代码采用P-代码形式。实现思路是:先用P-代码实现一个虚拟机,然后再用代码解释执行方式,完成源程序的最终运行和得出结果。编译器的最终目的是要正确的对源程序完成任务编译和执行。从语法树过度到机器语言还有很大的距离。编译程序生成的代码可以被一个用汇编语言写的小程序解释执行。

4 未完成的任务

由于定义的C教学语言是一种用于编译原理教学的语言,为了不陷入无穷尽的细节考虑和实现中,只保留了C语言的精华部分,没有预处理部分和库函数部分。

参考文献

[1]刘平安.改革实践性教学模式加强学生工程素质培养[J]。机械工业高教研究,2002,(4):42-45。

[2]吕映芝,张素琴,蒋介石维杜.编译原理[M]。北京:清华大学生出版社,1998。

三阶高密度双极性码编译器系统设计 第8篇

目前,线路编码广泛地用于数字移动通信、数字微波通信和数字光纤通信系统中,是数字通信系统中不可缺少的部分。HDB3(High Density Bipolar3)码除具有AMI(Alternatemark Inversion)码功率谱中无直流分量和可进行差错自检等优点外,还克服了A-MI码在信息中出现连“0”时,定时提取困难的缺点,而且其频谱能量主要集中在基波频率以下,占用频带较窄,广泛用于PCM(Pulse Codemodulation)线路传输码。在实际应用中,HDB3编译码器的高效设计非常重要。

1 HDB3码简介及编码原理

HDB3码是AMI码的一种改进型,主要是为了克服AMI码中连“0”时所带来的提取定时信息的困难。

它的编码原理为:首先将信码变换为AMI码,然后检查AMI码序列中连“0”的情况。当出现4个以上的连“0”时,将每4个连“0”小段中的第4个“0”位变成一个非0的破坏位V,其极性和前一个非“0”位同极性。这样就破坏了“极性交替反转”的规律,可以在接收端很快发现破坏位,使原信码得到恢复,但也破坏了AMI码无直流分量的优点。为了保持无直流分量这一特点,还必须保证相邻V码也应极性交替。这一点在相邻V码之间有奇数个非“0”位时,可以得到保证。当有偶数个非“0”位时,就得不到保证,这时再将该小段第一个“0”位变换成+B或-B,B的极性与前一个非“0”位相反,并让后面的非“0”位从V位开始再交替变化。虽然HDB3码的编码规则比较复杂,但译码却比较容易,从上述原理看出,每一个破坏符号V总是与前一个非0符号同极性(包括B在内)。这就是说,从收到的符号序列中可以容易地找到破坏点V,于是也断定V符号及其前面的3个符号必是连0符合,从而恢复4个连0码,再将所有的-1变成+1后便得到原消息代码。

HDB3码编码波形如图一所示:

2 设计思路

(1)HDB3编码部分

编码部分的模块如图二所示,其中关键部分是BV码元判决和BV极性判决2部分电路。

①BV码元判决

将编码后的信码“1”、补信码“B”和破坏码“V”都看作是“1”码。根据编码规则,“V”必须与前一“V”同极性,如果条件不满足,则必须插入与“V”同极性的补信码“V”。因此,当遇到4个连“0”时,除了第一个4连“0”固定用“000V”取代外,取代节“B00V”或“000V”的选取由前一B、V的极性是否相同来判决。

②BV极性的判决

根据编码规则,HDB3码序列中的“B”和“V”都应保持极性交替变化的规律,并且应该保证“V”与前一“B”同极性,利用这一性质,很容易实现正负极性码元的分开。从BV极性判决电路输出的P1、N1信号经过单-双极性变换电路合成一路双极性脉冲序列,即HDB3码序列。

(2)HDB3译码部分

相对于编码,HDB3译码过程较为简单,从实用性的角度出发,在译码电路部分融入误码检测和位同步提取电路,总体框图如图三所示。

①误码检测

由于HDB3码具有一定的内在检错能力,因此从实用性考虑,设计此部分电路。当输入码元序列中连续出现3个以上的“0”码,或同极性码元连续到达的个数大于2个时,均表示接收到的编码或位同步提取出错,“ERROR”输出为高电平。

②位同步提取电路

位同步提取是否正确是译码器能否正确译码的关键。本设计是将位同步提取集成于译码器内部,通过配置数字锁相环,实现片内位同步提取,提高系统的集成度。

③取代码译码部分

从编码原理看出,每一破坏符号总是与前一非“0”符号同极性。因此,从收到的符号序列中很容易找到破坏点V,从而用“0000”取代消息码,再将所有的“+1、-1”变成“1”后便得到原信息代码。

3 系统设计

HDB3编译码设计系统方框图如图四所示:

本系统的设计采用了编译码芯片对AMI/HDB3进行编译码,通过编译码器输出两路并行信号+HDB3-OUT和-HDB3-OUT,它们都是半占空比的正脉冲信号,分别与AMI/HDB3码的正极性信号及负极性信号相对应,这两路信号经模拟开关单/双极性变换后可得到HDB3码。在对AMI/HDB3码进行译码之前,同样也是将信号经双/单极性变换得到相应的正极性信号和负极性信号再送译码芯片。首先,由于对信号上拉电平值的不同所对应的控制门限不同,可通过判决整流电路选出两路极性信号,这两路极性信号同样也是半占空比的正脉冲信号,要对HDB3信号译码得到NRZ信号,必须从HDB3码中提取位同步信号。但HDB3码本身不含有位同步频率成分,故不能直接从HDB3码中提取位同步信号。双/单极性变换器及相加器构成一个整流器,HDB3码经全波整流后得到的正脉冲信号HDB3-D中含有位同步信号频率离散谱。

摘要：HDB-3码(三阶高密度双极性码)保持AMI码极性反转的特点,减少连0串的长度,有利于提取定时信息,广泛用于数字通信系统中。针对现有HDB-3编码器中存在编码复杂、输出延时长等缺点,设计一种统一位置判断和极性判断的HDB-3编码器,并从实际应用出发,将误码检测和位同步提取融入译码器芯片中。该种编译码器的相对延时较小,灵活性高,具有实用价值。

关键词：编码,译码,HDB-3

参考文献

[1]潘新民.计算机通信技术[M].北京:电子工业出版社,2006.

[2]季福坤.数据通信与计算机网络技术[M].北京:中国水利水电出版社,2001.

[3]张辉.现代通信原理与技术[M].西安:西安电子科技大学出版社,2006.

[4]毛朝土.Protel DXP基础教程[M].北京:清华大学出版社,2005.

编译器优化 第9篇

嵌入式C编译器作为嵌入式C系统开发的重要工具, 广泛应用于嵌入式研发、生产以及应用的各个领域, 其可靠性的高低直接关系到产品的成败, 因而, 对嵌入式C编译器功能准确性进行测试成为了编译器开发商们的迫切需求。嵌入式C编译器测试是一项耗费巨大、困难复杂的工程, 需要设计规模庞大的测试用例集[1]。传统的手工编写用例的方式不能满足编译器测试这类软件测试项目的需求, 通过自动化的方式能在较短时间内产生大量符合要求的测试用例, 节约测试成本[1,2,3]。

目前用于编译器测试的用例生成工具研究主要是面向ANSI-C/C++本地编译器和其特定功能的测试需求[3,4], 文献[5,6]设计了能够自动覆盖所有程序调用规约的用例生成工具;文献[7]设计了一款ANSI-C程序自动生成工具来检验编译器对于volatile修饰的变量执行结果是否正确;文献[8]设计了一款测试浮点类型变量全部应用的程序自动生成工具;文献[9]开发了一款面向对象编译器测试工具O-OCTT, 实现了C++编译器测试用例的自动生成及测试过程的自动化。由于嵌入式C语言和ANSI-C/C++存在一定的区别, 现有的测试用例生成工具无法直接应用于嵌入式C编译器测试中。

嵌入式C编译器测试与ANSI-C编译器测试的区别体现在: (1) 嵌入式系统自身硬件资源的局限, 决定其测试方法与普通软件测试有很大的不同[10], 如何选择一种合适的测试用例执行验证方法来检验嵌入式编译器功能正确性, 成为亟待解决的问题。 (2) 嵌入式C语法会根据实际应用需要对ANSI-C进行扩展和限制[11], 如增加嵌入式汇编、中断服务函数和内建函数, 不支持多维数组, 不支持长字节的变量, 不支持函数的递归调用。其中, 由于嵌入式微处理的堆栈空间有限, 对应的嵌入式语法一般不支持函数的递归调用, 因此如何在测试用例中避免函数的递归调用, 成为了嵌入式编译器测试中用例生成技术面临的一个难点[12]。文献[9]通过在函数调用树中增加“下层函数不能调用上层函数”的约束避免函数递归;文献[12]将函数按照生成时间的先后排成一个链表, 在调用时每个函数只能调用链表中位于它之前的函数, 不能调用位于它之后的函数;文献[13]给Java的类方法赋予不同的优先级, 级别高的类方法才能调用级别低的类方法。这些方法虽能有效地防止递归, 但是人为增加了调用约束, 无法真实地反映函数间的随机调用, 造成对函数调用语法点测试不够完整。因此, 有必要寻找一种既能有效避免递归又能尽可能实现随机调用的方法。

本文首先提出了一种嵌入式编译器执行验证的方法, 在此基础上设计了一款针对嵌入式编译器测试的用例自动生成工具ECPAG (Embedded C Program Automatic Generator) , 给出了该工具的总体框架和关键算法, 并对ECPAG在实际测试项目中的应用结果进行了分析, 最后一节对本文工作进行总结。

2基于串口传输的变量值验证

针对嵌入式硬件资源的局限, 本文提出了一种基于串口传输的变量值验证测试策略来检验编译器功能的正确性。图1是基于该策略建立的嵌入式交叉测试环境, 测试用例集合经过宿主机端的编译器编译链接后, 生成的可执行代码下载到目标机端的硬件设备上运行, 获得测试用例的运行结果, 这些运行结果不是在目标机端进行分析, 而是通过串口传输回宿主机端保存。宿主机端的数据比较工具收集这些运行结果, 通过和参考编译器运行结果进行比较的方式[10,13,14]验证待测编译器的功能是否正确, 并将测试结果记录到测试报告中。

为了便于分析待测编译器功能的正确性, 并根据错误准确定位待测编译器在语法语义处理上存在的缺陷, 我们在测试用例中每个函数结束的位置植入变量输出语句, 将函数所用到的所有全局变量和局部变量的数值传送回宿主机端, 宿主机端的数据比较工具对比待测编译器和参考编译器运行后的变量结果值, 如果发现变量运行结果不一致, 测试者便可以结合测试用例检查对该变量执行的相应语法操作是否存在问题, 发现待测编译器存在的缺陷。为此, 我们针对不同的变量类型, 定义了相应的变量输出语句用于传输测试用例中各种数据类型的变量, 输出语句的详细介绍如表1所示。

3ECPAG的设计实现

基于上节提出的变量值验证测试策略, 我们设计了一款针对嵌入式C编译器测试的用例自动生成工具ECPAG, 产生用于嵌入式编译器功能测试的测试用例集合。

3.1ECPAG总体框架

ECPAG的总体框架如图2所示, 该工具主要由六个部分组成:用户界面、初始化模块、生成模块、美化模块、输出模块以及自定义参数表。使用者通过用户界面设定测试用例的规格, 如每个测试用例的最大函数个数、最大语句嵌套深度、语句生成概率等, 定义好的参数存储于自定义参数表中。生成测试用例时, 初始化模块提取自定义参数表中的用户配置, 将其传递给生成模块中的对应参数, 生成模块根据用户设定的测试用例规格参数, 调用测试用例生成方法进行语法的随机组合和嵌套, 生成符合用户要求的测试用例, 并将测试用例规格参数以注释的形式附加到程序的起始位置。美化模块按照C程序编程风格, 对生成的测试用例内容进行缩进排版, 生成便于测试者阅读的测试用例。最后, 输出模块对生成的测试用例进行统一命名, 并将用例集合存放到测试者指定的目标文件夹中。

3.2测试用例生成方法

采用随机算法和概率算法相结合的思想组合嵌入式C语法, 设计了测试用例的生成方法。该方法遵循“函数—语句—变量—数据类型”的思路产生测试用例结构, 将语法点按类别封装成语法模块, 把具有类似功能的语法模块归类成组, 总共有三个组:语句组、变量组和数据类型组。测试用例生成中各语法模块调用流程如图3所示, 测试用例首先调用函数模块生成函数框架, 函数模块随机调用语句组中的任意一种语句模块生成相应的语句框架, 在语句深度未达上限的情况下, 语句模块还可以随机调用该组中任意一种语句模块继续生成语句框架。当所有语句框架生成完毕, 各语句模块随机选择变量组中的全局变量或者局部变量填充到框架中的适当位置, 变量又随机选择一种数据类型, 根据对应的数据类型对该变量进行初始化。在测试用例的生成过程中, 各语法模块的组合和嵌套都是随机挑选的, 函数模块可以随机调用任意一种语句模块, 语句模块随机挑选其他语句模块和变量组中的各种变量, 变量随机选择数据类型, 从而可以生成大量不同语法组合的测试用例, 达到任何语法点和语法组合都可能测试到的效果, 排除了人为设计用例造成的语法组合不够完整的影响。

针对嵌入式C对ANSI-C的扩展和限制, 引入概率限定的思想, 通过编写脚本设定各语法点在测试用例中出现的概率, 当随机算法挑选到某种语法后, 便会读取脚本中测试者对该语法的概率设置, 从而决定该语法结构被选中的可能性有多大。通过这种方式, 我们可以增大一些重要语法如bit数据位操作、嵌入式汇编、中断服务函数和内建函数的产生概率, 限制大规模数组、长字节变量、多层循环结构嵌套的出现, 从而有针对性地测试某些语法点。

3.3函数调用算法

由于测试用例生成方法采用的是随机算法, 调用函数和被调用函数是随机选择的, 所以不可避免会在测试用例中出现函数的递归调用。函数的递归调用是指在调用一个函数的过程中又出现直接或者间接调用该函数本身[15], 图4 (a) 是一种函数直接递归调用的结构, 在调用fun1 () 的过程中又出现了调用它本身的情况, 图4 (b) 是一种函数间接递归调用的结构, 在调用fun1 () 的过程中调用了fun2 () , 而在调用fun2 () 过程中又调用了fun1 () , 这些都会在函数调用中形成调用环路, 从而使编译器进入函数调用的死循环。嵌入式微处理由于堆栈空间有限, 一般不支持函数的递归调用。

为了防止函数的随机调用中出现递归, 我们采用基于深度优先搜索的有向图拓扑排序方法来解决。将有向图理论应用于函数调用中, 用有向图表示函数间的随机调用关系, 有向图中的节点表示函数, 有向图中的有向弧线表示两个函数之间的调用关系, 箭头由调用函数指向被调用函数, 因此, 函数的递归调用便可以表示为有向图的节点循环。在有向图理论中有判定循环的定理:有向图中有环的产生, 当且仅当对有向图进行深度优先搜索发现反向边[16]。根据该定理, 要使函数调用中不出现递归调用, 只要保证函数调用所对应的有向图不存在环, 即对该有向图进行深度优先搜索没有发现反向边。我们设计了一种防止递归的函数调用算法, 实现如下:算法执行前, 初始化有向图G来表示函数间的随机调用关系, 定义邻接矩阵edges存储G中的有向弧线信息, 邻接矩阵的维数随函数个数增加而动态增长, 如果函数i调用函数j, edges[i][j]=1, 否则为0。在函数调用过程中, 假设当前有n个函数, 调用函数为i, 首先判断是否生成一个新函数进行调用, 如果是的话, 由于调用新生成的函数不会导致有向图中环的产生, 只需在有向图G中增加节点 (n+1) 和有向弧线i→ (n+1) , 同时edges维数增1, edges[i][n+1]=1;如果调用已经生成的函数, 假设为j, 将有向弧线i→j添加到G中, 设edges[i][j]=1, 以i为起始节点对有向图进行基于深度优先搜索的拓扑排序, 生成包含所有节点的拓扑序列L。从L的末节点开始搜索L是否存在反向边, 如果L存在反向边, G中有循环产生, 函数调用出现递归, 则删除先前添加的有向弧线i→j, 设edges[i][j]=0, 重新挑选被调用函数;如果L不存在反向边, 则G中没有环的产生, 函数调用没有出现递归, 调用结束。

由于调用函数和被调用函数是根据随机算法在有向图中随机选择的, 既可以调用已经生成的函数, 也可以调用一个新生成的函数。只要保证不出现调用循环, 即可构成函数调用关系, 从而在防止函数递归调用的前提下尽可能地实现函数的随机调用。

4ECPAG的应用与评价

4.1ECPAG的应用

我们将ECPAG应用于某嵌入式C编译器的功能测试项目中, 采用目前常用的参考编译器对比方式[10,13,14]设计了自动化测试流程, 验证待测编译器功能的正确性, 同时结合代码覆盖测试工具分析编译器源码的执行情况, 客观评价ECPAG的有效性[17]。

嵌入式C编译器自动化测试流程如图5所示, 引入一款经过长期实践证明的成熟的商用编译器作为参考编译器, 利用块覆盖测试工具SAT[17]分析代码的块覆盖率情况。首先, 调用SAT对待测编译器的源码进行结构分析, 划分各基本块并植入跟踪探针, 编译生成插装后的待测编译器程序;将ECPAG产生的测试用例集合分别输入插装后的待测编译器和参考编译器编译, 生成的可执行代码分别下载到待测目标机和参考目标机上运行, 获得测试用例的运行结果并通过串口传送回主机端, 主机端的数据比较工具对比两种编译器的运行结果是否相同, 如果相同, 说明待测编译器能实现和参考编译器相同的功能, 测试通过, 反之, 则说明待测编译器可能存在错误。在待测编译器运行过程中, SAT收集编译器源码中各基本块的执行信息, 计算各语法文件的块覆盖率。

4.2覆盖率评价

随机选取编译器源码中四个重要语法文件进行块覆盖率分析:Lex.c、Stmt.c、String.c、Sym.c。其中, Lex.c负责测试用例中的词法分析, Stmt.c负责各种语句类型的语义分析, String.c负责各种数据类型的识别和处理, Sym.c负责测试用例中的各种标识符的管理, 四个语法文件的功能介绍如表2所示。

图6是运行ECPAG生成的440个测试用例后四个重要语法文件的块覆盖率增长情况。从图6可以发现:当测试用例数量达到40个的时候, String.c的覆盖率已经达到93%, 说明ECPAG能够比较完整地生成待测编译器所支持的大部分数据类型, 而其它语法文件的块覆盖率相对较低一些;随着测试用例数量的增加, 语法组合的种类和数量逐渐增加, 各语法文件的块覆盖率逐渐提高;当测试用例数量达到360个的时候, 各语法文件的块覆盖率达到最高值, Lex.c为78%, Stmt.c为81%, String.c为98%, Sym.c为77%, 通过覆盖率情况可知ECPAG生成的测试用例能够较好地覆盖待测编译器的源代码, 以较少的测试用例数量达到较高的测试覆盖率 (75%以上) , 从而达到测试嵌入式编译器在语法语义处理是否正确的目的。

从图6还可以发现:当测试用例数量超过360个的时候, 即使增加新的测试用例, 由于新生成的语法类型、组合与先前的用例出现重复, 块覆盖率无法继续提高。通过对源代码的分析, 我们得出覆盖率无法继续上升的三点原因:第一, 源代码中存在大量的不可达代码块和不可达函数, 这些代码的存在是阻碍块覆盖率进一步提高的主要原因;第二, ECPAG只能生成符合编译器语法文档的测试用例, 无法生成错误的测试用例, 导致编译器源码中涉及错误处理的相应代码片段无法被执行;第三, ECPAG所支持的语法类型还不够完整, 无法生成一些较为复杂的语法结构, 如函数返回类型为struct、函数指针等, 这些不足之处有待今后的工作继续改进。

5结束语

本文提出了一种嵌入式编译器测试验证方法, 即基于串口传输的变量值验证的测试策略, 并在此基础上设计了一款嵌入式编译器测试用例自动生成工具ECPAG, 该工具采用随机算法进行任意语法组合, 达到任何测试点都可能测试到的效果, 采用概率算法限定语法组合的生成概率, 从而有针对性地测试某些语法点, 并将基于深度优先搜索的有向图拓扑排序方法用于函数随机调用中的递归问题的解决。我们将该工具应用于某嵌入式编译器的测试项目中, 测试结果表明:该工具生成的测试用例集合能够较好地覆盖待测编译器语法, 达到75%以上的块测试覆盖率, 基本达到测试嵌入式编译器在语法语义处理是否正确的目的。

摘要：首先提出了一种嵌入式编译器测试验证方法, 即基于串口传输的变量值验证法, 在此基础上设计了一款针对嵌入式C编译器测试的测试用例生成工具ECPAG。该工具根据嵌入式C语法, 采用随机算法产生符合规则的任意语法组合, 采用概率算法限定各语法要素的生成概率, 成功地将基于深度优先搜索的有向图拓扑排序方法应用于函数随机调用中的递归问题的解决。工程应用表明:该自动化工具生成的测试用例集合能够较好地覆盖嵌入式C语法, 达到75%以上的块测试覆盖率。