Matrix编译器中饱和算术指令映射的设计与实现＊

淡孝强，陈跃跃，孙海燕，阳 柳，罗 杰，辛乃军，王 霁

（国防科学技术大学计算机学院，湖南 长沙410073）

1 引言

当前，DSP芯片在多媒体、信号处理等领域中的应用越来越广泛，由于嵌入式芯片功耗和成本的限制，DSP芯片对编译器指令映射的精确性和高效性的要求也越来越高，同时选择快速、有效、低成本的编译器开发平台也越来越重要。

Matrix是一款面向软基站的、自主指令集的高性能DSP，Matrix编译器的开发平台是gcc，它是一个开发运行在不同系统平台的高效快速的开源的编译系统。对于特定的目标体系结构，通过移植gcc可以开发出这个平台的编译系统，是一种快速、有效、低成本的方案。

gcc目前只支持基于Fixed－point数据类型饱和算术指令映射。Fixed－point是一种精度介于整数和浮点之间的数据类型，有别于整数类型和浮点类型［1］。由于Matrix指令集的饱和指令是基于整数和浮点的，所以需要移植gcc，使其支持整数和浮点的饱和算术指令的映射。饱和算术指令使得数字信号处理算法更加准确、更加高效，是Matrix指令集中很重要的一种指令。对gcc进行移植，使得在Matrix编译器支持饱和算术指令的映射。本文对gcc指令映射过程的分析以及实现饱和算术指令映射的思路，对于其他指令映射的实现具有一定的借鉴作用。

本文第2节介绍了饱和算术的定义和特征；第3节介绍了gcc中指令映射的一般过程；第4节给出了饱和算术指令映射的实现过程；第5节描述了饱和加法指令映射实验结果；第6节对全文总结。

2 饱和算术简介

饱和算术使得一些算法更加准确、更加高效，尤其是在DSP算法中。例如：调整声量可能导致声音信号溢出，而饱和算术可以明显减少对信号的扭曲。把两个数的补码形式相加，会导致环绕现象（wrap－around），这可能会对DSP系统的信噪比造成灾难性结果，运用饱和算术则可以避免。

饱和算术运算是一种值被限定在固定范围内的运算操作，有最大值和最小值［2］。比如饱和加法操作：如果两个数相加后的结果比最大值要大，那么最终的结果就等于最大值；如果相加后的结果比最小值要小，最终结果就等于最小值；如果相加后的结果在最大值和最小值之间，这就是最终的结果。对于这样的C语言描述，gcc目前只能完成基于Fixed－point数据类型的映射。因此，在gcc中实现基于整数和浮点类型的饱和算术指令的映射会使得编译器更加高效。

3 gcc指令映射机制分析

gcc的编译流程是：词法分析→语法分析→中间代码生成→代码优化→代码生成。词法分析和语法分析称之为前端，中间代码生成和部分优化称之为中端，部分优化、机器描述 MD（Machine Description）和代码生成称之为后端。

3.1 前端处理过程

在gcc内，前端预处理、词法分析、语法分析三个过程统称为解析过程。gcc前端的主要任务是对输入的C代码进行解析并记录有效信息，形成抽象语法树AST（Abstract Syntax Tree）。解析过程的依据是C标准，C标准在前端的信息可以分为基本词汇符号和语法规则两类。一般以hash表的形式把基本词汇符号的信息组织起来，供解析过程查询。语法规则实际是基本词汇符号排列组合的规则，一般体现在语法分析过程中。前端大致分为两个阶段：预处理和词法分析把输入代码转换成gcc的内部表示（内码），语法分析再根据内码来建立抽象语法树，两个过程都伴随着出错处理。

3.1.1 前端中的C标准基本词汇符号

C标准的基本词汇符号可以分为字符集和标识符。字符集分为英文字母、阿拉伯数字和特殊符号。标识符包括保留字、预定义标识符、用户定义标识符［3］。预处理器和词法分析将对源代码中的所有词汇符号（token）进行分类解析，不同类的信息在gcc内部用不同的变量。输入代码中所有字符在gcc内部都有对应的内码来表示。下面初步介绍gcc中的基本词汇及其内部表示。

所有的保留字定义在c－parser.c的一个结构体数组reswords［］中，这个数组的成员在解析器初始化的过程中将根据名字被索引到hash表中，以供解析时查找匹配。其内码是一个枚举数组中的值，一般形式为RID＿＊。对于用户定义的标识符，一般解析为CPP＿NAME。

C中各种符号的定义。以“＋”来说明定义过程。“＋”的gcc内部表示CPP＿PLUS是枚举数组cpp＿ttype（in cpplib.h）中的一员。CPP＿PLUS包含在宏定义TTYPE＿TABLE中。对输入代码进行分析时函数cpp＿lex＿direct会将外部表示“＋”和内码CPP＿PLUS对应起来。其他的英文字母和阿拉伯数字包含在字符识别函数＿cpp＿lex＿direct中。基本词汇符号的信息在初始化时以静态数组的形式被组织进hash表。词法分析完成内外信息转换过程之后，进入语法分析过程。根据本文需要，下面仅重点介绍语法分析中的数据类型。

3.1.2 前端C数据类型

基本的数据类型节点对于编译器至关重要，是编译器将高级语言精确而高效地映射到汇编语言的基础。整型数据节点是C语言最基础、最重要的部分，其使用频率很高，必须保证对这些节点的访问尽可能高效。因此，这些节点定义在全局数组integer＿types［］（in tree.h）中。

内建节点的初始化过程实际上是对tree结构中许多子成员的赋值过程。tree结构是定义在tree.h中的联合，其成员涵盖了C语言的各种语法类型，因此tree结构十分庞杂，所以对tree结构的操作是通过函数和宏来进行的。

前两小节所介绍的基本词汇字符和基本数据节点大多是以静态形式存在的，而整个词法语法分析会将这些信息串联起来。

3.1.3 前端分析过程简介

函数c＿parse＿file是前端对一个文件开始解析的入口。c＿parser＿declaration＿or＿fndef处理变量声明和函数定义，在此过程将调用更底层的函数来对输入的程序进行识别和分类并将信息记录到相关的数据结构中。c＿lex＿one＿token函数对一个字符进行分析，首先调用函数c＿lex＿with＿flags来确定字符的type，＿cpp＿lex＿direct在这里被进一步调用，使得输入字符和它们的gcc内码对应起来，比如，字符“＋”将返回的type是CPP＿PLUS。然后，根据得到的类型进行分类处理，CPP＿NAME的case分支中包含了对标识符或者保留字的处理，保留字将被识别并用gcc内部的数据结构表示。其他的外部信息也由相应模块来处理。

外部信息表示成内码之后进行语法解析。语法解析的主要任务是抽象语法树的建立、出错处理、符号表的建立。gcc中所有语法树都定义在tree.def中［4］。在语法解析过程中，解析器会根据操作符的内部表示映射到相应的树节点，如CPP＿PLUS映射为PLUS＿EXPR。更为复杂的语法树建立是由tree.c中的build＿＊族函数来完成的。

抽象语法树是一种语言相关的中间语言表示IR（Intermediate Representation），为了方便对其进行优化将进一步转化成语言无关的中间语言表示（GIMPLE）。

3.2 gcc中端分析

GIMPLE IR是抽象语法树的子集，两者之间的不同之处就在于GIMPLE IR只含有顺序和分支结构，其他的控制流都转化成这两种结构。GIMPLE阶段最关键的步骤是GIMPLE转化成RTL。GIMPLE是机器无关的，而RTL是机器相关的。GIMPLE到RTL的转化过程在函数expand＿expr中，此函数包含一个巨大的switchcase，每一个GIMPLE的节点都会映射到后端的标准名（SPN），这些标准名必须被编码到gcc中去。在中端，标准名实际上是＊＿optab的一类变量。扩展到RTL的过程从函数声明的顶部开始，深度优先遍历整个GIMPLE树［5］。

选择了某个后端的标准名之后就进入到后端RTL生成过程了。

3.3 后端RTL生成过程

中端映射到标准名之后，gcc会自动根据模式（mode）去查找后端模板中是否有满足条件的指令。所以，对于添加新的指令而言，标准名的定义和后端模板描述最值得关注，最后会在此基础上简要说明匹配过程以及最后的RTL生成。

3.3.1 标准名的添加

标准名的添加包括以下几个方面：（1）在rtl.def文件中定义RTL操作符。（2）optabs.c中函数init＿optabs对库函数的初始化。（3）后端模板自动生成程序genopinit.c的修改，增加optabs成员，描述新操作下数据模式的映射规则。

标准名添加之后，后端机器描述必须要使用该准名来描述指令，才能完成匹配。下面介绍机器描述。

3.3.2 机器描述（MD）

机器描述包括指令集、指令延迟、功能部件、流水线等［4］。机器描述MD是一个内容较丰富的部分，本文中只涉及到指令集的描述。在MD文件中描述指令集，gcc编译生成CC1的过程会根据MD文件自动生成一系列的insn－＊.c和insn－＊.h文件，供编译过程更有效地获取机器相关的信息。自动生成的过程由一系列的gen＊.c文件来完成［6］。

在编译生成CC1时，genemit.c文件会根据MD描述自动生成文件insn－emit.c，此文件集合了许多产生rtx的函数，这些函数在CC1运行C程序的时候使用。

3.3.3 GIMPLE到RTL生成总结

通过前面的描述，现在可以总结GIMPLE到RTL生成的过程。

（1）目标无关的expand＿＊函数集完成GIMPLE到RTL的映射过程。

（2）目标相关的gen＿＊函数集完成RTX的具体生成过程。gen＿＊函数由自动生成程序根据机器描述自动生成。

（3）expand＿＊函数集和gen＿＊函数集的操作接口主要是：optab＿table［］和insn＿data［］。例如，针对CODE为PLUS的表达式，其调用过程为：首先找到PLUS对应的optab＿table［code］；接着根据正确的 mode来找到optab＿table［code］.handlers［mode］.insn＿code；再由insn＿code找到insn＿data［insn＿code］；最后insn＿data［insn＿code］.genfun对应上insn－emit.c文件中的gen＿addsi3函数，调用该函数生成合适的RTL。

（4）经过RTL的优化遍，最后汇编输出。

3.4 指令映射过程总结

gcc内部指令映射的过程本质上是多种语言之间的转化过程。首先是词法分析将输入的C代码转化成内部表示，语法分析在此基础上建立AST，对AST进行简化生成GIMPLE，经过优化过程之后再映射到RTL，经过RTL优化遍之后就是汇编输出。这些中间语言都有相应的数据结构和变量来描述，它们是静态的；gcc的编译流程是由一系列重要的函数实现的，它们控制了中间语言之间的转化，是动态的过程。所以，实现新的类型的指令映射，就是给中间表示增加静态的变量成员，并控制相应函数的动态转化过程。接下来将以饱和加法的实现为例来简要介绍饱和算术在gcc中的设计与实现。

4 饱和算术指令映射机制的实现

gcc将高级语言映射到汇编语言的过程，本质上是几种中间语言的转化过程。因此，对于饱和这一新的数据类型，不同的中间语言需要增加描述它的词汇，并在映射过程中控制中间语言之间的转化过程，使之映射到正确的目标代码。对于饱和属性，仿照C语言中signed这个作为修饰作用的保留字，扩展C语言增加一个修饰保留字sat。针对这一扩展，在前端、中端、后端的中间语言中增加新的数据变量，并控制这些变量之间的转化，完成映射过程。本节将以饱和加法指令的实现过程为例来实现上述思路。

饱和加法的基本目标是：对C标准进行扩展，用sat来描述数据类型（类似于C保留字signed，修饰作用），那么sat int a，b，c；c＝a＋b；能够映射到整数饱和有符号加法指令SADD32。

4.1 前端设计与实现

前端涉及的中间表示有两种：词法分析之后的内码以及语法分析建立的AST。首先要在这两种中间表示中增加新的成员，然后控制新成员在前端的转化过程。

4.1.1 前端增加新的保留字sat

所有的保留字定义在c－parser.c的一个结构体数组reswords［］中，以保留字“char”为例作简要说明：｛“char”，RID＿CHAR，0｝，成员一代表保留字在输入代码中的写法；成员二是该保留字在gcc内部的表示，是一个枚举数字的成员，定义在ccommon.h的枚举数组rid［］中；第三个成员是一个数字，表示该保留字是为哪种C标准所有。

（1）在c－parser.c的一个结构体数组reswords［］中，增加保留字"sat"：｛"sat"，RID＿SAT，0｝。

（2）c－common.h的枚举中增加 RID＿SAT。

4.1.2 增加内建数据节点

整数的内建数据节点定义在integer＿types［］（in tree.h）的全局数组中，而不像其它类型节点被放在哈希表里。这只是一个简单的tree结构数组的声明。函数build＿common＿tree＿nodes和函数build＿common＿tree＿nodes2完成了所有的内建数据节点的初始化过程。record＿builtin＿type把已经初始化的节点类型和它们的输入名称联系起来。

（1）在tree.h中增加sat＿integer＿type＿node。

＃define sat＿integer＿type＿node integer＿types［itk＿sat＿int］枚举integer＿type＿kind中增加itk＿sat＿int。（2）build＿common＿tree＿nodes函数中增加对新增内建节点的初始化过程。

sat＿integer＿type＿node＝ make＿signed＿type（INT＿TYPE＿SIZE，1）

（3）函数 make＿signed＿type是确定数据的有无符号属性，在此函数中增加satp参数来判断是否为饱和属性。make＿signed＿type（INT＿TYPE＿SIZE，satp）函数体内增加代码：

if（satp）

TYPE＿SATURATING（type）＝1；

make＿unsigned＿type需要类似修改。调用这两个函数的地方都要做出相应修改。

（4）c＿common＿nodes＿and＿builtins的修改：用函数record＿builtin＿type把外部 C语法“sat int”与新增数据节点对应起来。

4.1.3 前端解析过程移植

词法分析和语法分析过程都是在函数c＿parser＿declaration＿or＿fndef中进行的。

specs是函数c＿parser＿declaration＿or＿fndef中记录C声明特征的变量，其中包括描述属性的许多标志位，如有无符号，是否为long，是否是short等。函数declspecs＿add＿type会根据specs的信息并结合C标准来判断不同保留字组合的合法性，不合法就报警告或者错误，合法就进一步完善specs的信息。记录在specs中的数据类型的信息传递是通过函数finish＿declspecs来完成的。根据specs中的信息可以判断对于当前的一个变量a是一个什么类型的内建数据节点。

（1）declspecs＿add＿type函数修改：

case RID＿SAT时修改使得sat int合法不报错，并且记录有效信息。

（2）修改finish＿declspecs使得新增加的节点被使用。case cts＿int时增加一个饱和属性的分支情形：

specs→type＝ （specs→saturating＿p？sat＿integer＿type＿node：integer＿type＿node）

4.2 中端设计与实现

GIMPLE转化成RTL首先是由树节点（＊＿EXPR）结合机器模式信息映射到后端数组optabs［］的成员＊＿optab（SPN 包含在其中），再由＊＿optab中的信息找到后端生成RTL的函数gen＿＊。这个过程是用标准名联系起来的。

以c＝a＋b的转化过程为例简要说明。前端已经解析得到：（1）a、b、c为有符号的整数；（2）“＋”的GIMPLE表示为PLUS＿EXPR。由GIMPLE到RTL的转化是由expand＿＊函数集来完成的。expand＿expr＿real＿1函数包含加法操作的转化过程，在此函数可以根据操作符的操作数情况做相应的转化，可以转化为其他的＊＿EXPR，也可以根据操作数来确定＊＿optab。加法的过程是进一步调用函数optab＿for＿tree＿code才确定的，在这个函数里，可以根据加法的性质（有无符号，是否饱和）来选择相应的＊＿optab。

中端修改使得PLUS＿EXPR能选择新增的ssadd＿optab，在函数optab＿for＿tree＿code做以下修改：case PLUS＿EXPR：时根据是否饱和、有无符号判断返回对应的＊＿optab。

4.3 后端设计与实现

标准名的添加首先要分析＊＿optab，结合其内容来添加相应的定义。以加法为例来分析：

（1）add＿optab在tree.h被宏定义转换成数组optab＿table的一个成员。

＃define add＿optab （＆optab＿table［OTI＿add］）

（2）跟踪查看optab＿table［OTI＿add］如图1所示（有省略）。

Figure 1 Standard pattern names in optab图1 操作表中的标准名变量

optab＿table是一个结构体。code是一个RTL操作，定义在rtl.def：DEF＿RTL＿EXPR（PLUS，"plus"，"ee"，RTX＿COMM＿ARITH）中，PLUS是optab＿table中用到的值。

libcall＿basenam、libcall＿gen是库函数调用的接口信息，如果在后端模板中没有匹配到合适的信息，这些信息将被用来匹配库函数。这几个成员的初始化是由optabs.c的函数init＿optabs完成的。

handlers是一个结构体数组，每一个成员代表某一个模式下后端是否有相应的指令来匹配，如果有，数组中insn＿code的值的名称就是操作和模式下的一个组合。例如，加法的整数（SI）模式为CODE＿FOR＿addsi3（3为操作数个数），如果没有值就是CODE＿FOR＿nothing。这个数组是机器指令描述信息的体现。从上面的值可以看出，该加法只有整数（SI）和浮点单双精度模式（SF、DF）有指令模板供匹配。程序genopinit.c自动将后端模板描述信息映射到optab＿table的handlers数组中。genopinit.c中的数组optabs记录了不同操作不同数据类型映射的规则，函数gen＿insn会根据这些信息来完成映射。

根据以上分析，做出如下修改：

（1）rtl.def中新增饱和有符号加法的rtl操作符SS＿PLUS；

（2）新增ssadd＿optab：＃define ssadd＿optab（＆optab＿table［OTI＿ssadd］）；

（3）在enum optab＿index中增加 OTI＿ssadd；

（4）修改init＿optabs函数，使得ssadd＿optab初始化（包括code和库函数名称的初始化）；

（5）修改genopinit.c中的数组optabs，使之建立后端整数饱和加法机器描述的自动映射过程；

（6）机器描述中新增有符号饱和加法的扩展规则（define＿expand）和指令描述（define＿insn）。

define＿expand描述了中端GIMPILE向RTL的扩展规则。define＿insn是一种机器描述构造的方式，用来为gcc新增标准名操作，描述机器指令。

4.4 映射过程总结

本节以饱和加法指令映射过程为例说明了本文饱和算术指令在gcc中的实现方案。首先对C语言扩展增加描述饱和属性的保留字sat，在前端增加保留字的内码表示，增加新的数据类型，在中端增加新的操作，在后端增加新的标准名以及新的机器描述。在完成静态信息的添加的基础上，进一步改变前端、中端函数的映射路径，使得前端对饱和属性数据的操作最终能映射到后端相应的机器描述上去，从而完成整个饱和加法的映射过程。

与gcc已有的基于Fixed－point数据类型饱和算术指令映射比较，本文的饱和指令映射实现过程更加简洁。原因在于Fixed－point是一种新的数据类型，为支持新的数据类型，需要在gcc中构建新的框架，这本身就是一个浩大的工程。本文是基于整数类型的饱和指令的实现，同时也借鉴了基于Fixed－point饱和指令映射的方法，方案实现的可操作性和复杂性就相对较低。与gcc已有饱和指令映射过程的不同点在于：C扩展的关键字不同，映射过程变量数据模式不同；映射过程相对单一简洁。

5 实验结果

根据上节描述的方案和过程，基于gcc－4.3.2版本实现了Matrix指令集中整数饱和加法的映射过程。gcc－4.3.2版本支持 Fixed－point数据类型饱和算术指令，不支持整数和浮点数据类型饱和算术指令映射。

Figure 2 Generation of saturation addition instruction图2 饱和加法指令映射实验结果

图2 a是Matrix编译器整数饱和加法的指令映射的示例。对于c＝a＋b的饱和加法程序，a、b、c均为整数类型，用关键字sat int来定义，表示通过Matrix编译器编译生成的汇编代码中产生了预期的饱和加法指令SADD32。图2b是gcc中支持的Fixed－point数据类型饱和加法指令映射示例。对于c＝a＋b的饱和加法程序，a、b、c均为Fixed－point类型，通过Matrix编译器编译会映射到代表Fixed－point类型加法的指令ADDF（Matrix指令集中不存在ADDF，为实验对比添加）。

未实现饱和算术的编译器中，饱和加法的描述需要两个嵌套的if－else结构才能实现。对于实现了饱和算术的Matrix编译器，只需要在定义变量时给变量增加一个饱和属性的保留字sat，编译器就能映射到一条有符号饱和加法指令——SADD32指令。这样的设计大大减轻了编译器饱和算术指令映射的复杂度，映射更加准确，且提高了效率。

6 结束语

饱和算术指令使得数字信号处理算法更加准确、更加高效，是Matrix指令集中很重要的一种指令。gcc目前只支持基于Fixed－point数据类型的饱和算术指令映射。Matrix指令集的饱和指令是基于整数和浮点的，所以需要移植gcc使其支持整数和浮点的饱和算术指令的映射。

本文首先针对饱和算术指令映射的实现，对gcc的一般加法指令映射过程从前端到后端做了针对性的分析，在此基础上，设计并实现了一种基于C扩展关键字sat的饱和算术指令映射机制；然后基于Matrix编译器实现了算术饱和指令的映射，并以饱和有符号的整数加法指令的映射为例介绍了本文提出的饱和算术指令映射方案具体的实现过程；最后的实验结果验证了实现策略和过程的正确性和简洁性。本文对标准C的扩展方法也适用于对Embedded－C进行此类扩展；类似的策略和实现过程也可以用来实现其它的饱和算术指令的映射，对于其他类型指令的映射过程，有一定的借鉴作用。

［1］ http：／／gcc.gnu.org／wiki／FixedPointArithmetic.

［2］ http：／／en.wikipedia.org／wiki／Saturation＿arithmetic.

［3］ Huang Wei－tong，Lu Ming－yu.C programming language［M］.Beijing：Tsinghua University Press，2005.（in Chinese）

［4］ http：／／gcc.gnu.org／onlinedocs／gccint／.

［5］ Vichare A，Deshpande S.GCC 4.0.2—The implementation［EB／OL］.［2008－10－15］.http：／／www.iitb.ac.in.

［6］ Ren Shan－hong，Zhao Ke－jia，Zhao Xiong－fang.The intermediate language and the back－end information translation in GCC［J］.Computer Engineering ＆ Science，1995，17（2）：74－82.（in Chinese）

附中文参考文献：

［3］ 黄维通，鲁明羽.C程序设计教程［M］.北京：清华大学出版社，2005.

［6］ 任珊虹，赵克佳，赵雄芳.GCC的中间语言以及后端信息的转换［J］.计算机工程与科学，1995，17（2）：74－82.