ZSP400目标代码优化算法的设计

甘 玲，丁振江

(重庆邮电大学计算机科学与技术学院，重庆 400065)

0 引言

数字信号处理(digital signal processor，DSP)芯片不仅具有可编程性，而且实时运行速度可达每秒数以千万条复杂指令程序，远远超过通用微处理器，是数字化电子世界中日显重要的电脑芯片［1］。ZSP作为DSP中的一类，其大部分芯片的目标代码只满足了其正确性，而没有考虑其效率，从而导致ZSP芯片的高性能没有得到充分发挥。目前的主流编译器不支持ZSP，因此不能利用这些编译工具对ZSP代码进行优化。同时，国内对其研究较少，并且大多对目标代码的优化方法只是停留在手工处理或是在理论探索上，没有用软件工程的方法进行具体的设计和实现［2］。

ZSP 芯片有ZSP200，ZSP400，ZSP500，ZSP600 等，本文选取ZSP400作为研究对象，其主要应用在全球的无线、IP电话、消费类音频等领域。本文根据代码优化思想设计ZSP400目标代码优化算法以提高ZSP芯片的硬件资源利用率，同时将这些优化算法以软件工程的方法集成为一个ZSP400优化处理器。

1 ZSP400简介

图1是一个典型的ZSP400系统［3］，图1中描述了ZSP400的各个功能单元，以及它们之间的关系，还进一步描述了功能单元与外设的关系。

1 )指令单元。指令单元包含指令缓存、指令预取单元、分支预测逻辑单元以及一个指令发射单元。

2 )数据单元。处理器的数据单元包含数据缓存、数据预取和循环缓存单元。数据单元负责数据连接操作，可以减轻将操作数从内存中载入到寄存器中的负担。

图1 ZSP400体系结构图Fig.1 ZSP400 structure chart

3 )流水线控制单元。ZSP400处理器采用了超标量体系结构，并且具有5级流水线，如图2所示。

图2 ZSP400流水线Fig.2 ZSP400 pipeline

①取指与解码(Fetch＆Decode):处理器从主存储器中取得指令，然后将所取出的指令进行解码。

②指令组合(Group):处理器将指令进行组合，并且检查其依赖规则，然后提交给流水线。

③读操作数(Read):处理器将指令要使用的操作数从数据单元中读出。

④执行(Execution):处理器进行算术逻辑和乘法累加操作，并且将结果写入寄存器或者交给数据单元。

⑤写回(Write－back):数据单元将结果写入存储器，并且更新所有控制寄存器。

流水线控制单元(pipeline control unit，PCU)在Group阶段会检查指令之间的依赖，只有能够并行执行的指令才能在同一个周期中被发射，并且ZSP400不支持乱序执行(out of order)。

4 )指令执行单元。指令执行单元包含了2个16位算术逻辑单元、2个16位乘法累加单元和1个通用寄存器文件，它将会执行DSP芯片的所有算术逻辑运算操作。

2 代码优化简介

代码优化的含义是对程序代码(中间代码或者目标代码)进行等价变化，生成运行时间更短、占用空间更小的代码［4－5］。编译过程中的优化可分为中间代码优化和目标代码优化，其中中间代码优化不依赖于具体的计算机［6］，本文的优化算法是针对目标代码的。根据优化涉及的范围又可分为局部优化和全局优化，本文将从这两方面进行ZSP400优化算法的设计。

本文的优化算法有:基于ZSP400的指令调度算法、ZSP400指令替换算法、ZSP400多余传递赋值删除算法。为了进一步提高目标代码的效率，本文还进行了无用代码剔除和指令强度削弱处理。这些算法充分结合了ZSP400芯片的硬件性能和结构特性，对汇编代码进行多方面的优化，与目前通用的优化算法相比，具有专用性、高效性和特殊性。

3 ZSP400目标代码的局部优化算法设计

局部优化是在基本块中进行的，这里主要针对ZSP400超标量体系结构的特性进行优化算法设计。

3.1 ZSP400指令调度算法设计

ZSP400采用5级流水线技术，在指令组合阶段ZSP400处理器会分析指令之间的依赖关系，没有依赖关系的指令将会被发射，ZSP400支持单周期最多发射4条无相互依赖关系的指令。通过调度相关指令，使ZSP400尽可能的在一个周期内发射多条指令，这是此优化算法的主要思想。此指令调度算法将2条相邻的具有依赖关系的指令分开到一定的距离，中间用与这2条指令都没有依赖关系的后续指令填充。要进行此优化处理，首先要判断2条指令是否具有依赖关系，这里涉及到的依赖关系有如下3种。

1 )读后写:先读取一个寄存器的值，然后将某个值写入到这个寄存器中。

2 )写后读:先将某个值写入到某个寄存器中，然后再读取这个寄存器的值。

3 )写后写:先将某个值写入某个寄存器中，然后再将另外一个值写入到这个寄存器中。

以上3种情况，不能改变任何一种读写操作顺序，否则将发生错误。该指令调度算法如下。

1 )扫描整个目标代码文件，每次提取相邻的2条指令进行判断。2条指令记为(a，a+1)，其中a的值为靠前指令的位置。

2 )若它们没有依赖关系，则转到下一对相邻指令(a+1，a+2)继续扫描;若它们有依赖关系，继续判断(a+1，a+2)以及(a，a+2)的依赖关系。

3 )若(a+1，a+2)以及(a，a+2)没有依赖关系，交换a+1和a+2指令的位置;如果a≥1，将a进行减1操作，回溯处理(a－1，a);如果a＜1，将a进行加1操作，继续扫描。若(a+1，a+2)以及(a，a+2)中有一个依赖关系，则将a进行加1操作，继续扫描。

4 )当a大于目标代码的总长度，结束扫描，退出，否则重复执行1)到4)的步骤。

指令调度算法充分利用了ZSP400的硬件性能特征，是使得指令能快速并行运行的核心处理过程。在整个优化处理过程中，它是最后被调用的。

3.2 ZSP400无用代码剔除

无用代码剔除主要是删除这样一类指令，即该指令的行为不会影响到任何寄存器中的内容。主要的一些无用指令如表1所示。在优化过程中，通过扫描各个基本块中的指令，与表1中的各条指令形式进行匹配，如果匹配成功，则剔除。

表1 ZSP400部分无用指令列表Tab.1 ZSP400 invalid part instruction

4 ZSP400目标代码的全局优化算法设计

4.1 ZSP400指令替换算法设计

全局优化是以所有基本块中的代码作为处理对象。

由于基本块主要是通过分支语句来进行划分的，故本文通过减少分支指令来减少基本块。当程序中涉及到取较大值或较小值时，一般会进行比较操作，这样就会产生分支语句。ZSP400指令集提供了形如 min，min.e，max，max.e 等指令，直接使用这些指令不但可以减少代码的长度，也可以避免分支指令的引入。同时，这里的替换操作也减少了局部优化中所消耗的时间和空间资源。此操作涉及的指令条数一般为4条、3条或2条，若为4条，则要用2条指令替换，其他情况用1条指令替换即可。

4.2 ZSP400多余传递赋值删除算法设计

本节主要是优化立即数、地址和寄存器值的传递赋值操作，进一步缩短代码长度和减少时间开销。此优化主要是解决隐藏在程序中多余的赋值操作。比如有如下形式的3条赋值操作指令。

若从指令(1)到(2)的过程中，如果X，Y的值没变，那么可以将指令(1)，(2)合并成指令(3)。其具体算法如下。

1 )扫描各条指令，判断指令的类型，查找形如指令(1)的指令。

2 )根据该指令中各个操作数的类型，扫描该条指令的后续指令。

3 )在扫描过程中，若发现X或者Y的值可能被某条指令所改变，则停止扫描，回到指令(1)继续查找。若找到形如指令(2)的指令，则首先删除指令(1)和(2)，在指令(2)的位置插入指令(3)，同时更新指令(2)位置后的各个标签位置。

4 )若第一趟扫描完还没完成，继续，否则接着进行下一趟扫瞄，进一步优化指令更新之后的目标代码，直到没有任何更新为止，否则一直重复1)到4)的步骤。

算法伪代码如下所示。

4.3 ZSP400指令强度削弱

ZSP400支持16位和32位2种类型数的操作，由于ZSP400中所有寄存器都是16位的，故16位数的操作比32位数的操作简单、高效得多。若用等价的16位操作指令替换32位操作指令将有效提高代码的执行效率，其中比较常用的替换有:将add.e rX.e，rY.e替换为padd.a rX.e，rY.e或padd.b rX.e，rY.e;将 sub.e rX.e，rY.e 替换为 psub.a rX.e，rY.e或psub.b rX.e，rY.e等等。这里用标志寄存器%hwflag来处理替换过程中的结果溢出现象。

5 测试

为了评价本文优化算法的效果和测试这些优化算法的正确性，本文还开发了一款 ZSP400模拟器［7］。按图3过程进行测试。本文选取如图4所示的测试用例，经过ZSP400优化器处理后，目标代码如图5所示。

从图4和图5(标号为N的是优化后引进的新指令)可以得出:优化处理后，不仅代码长度减少，基本块也得到减少;更重要的是调整了指令的顺序，从而使ZSP400目标代码运行时间更短。

本文选取20个具有代表性的用例，其优化效果如表2所示。

表2 ZSP400目标代码优化效果表Tab.2 Effect for ZSP400 object codes optimizing algorithms

表2中，x代表指令条数;C优前(x)表示优化前整个程序运行过程中单周期内执行x条指令的次数;C优后(x)表示优化后整个程序运行过程中单周期内执行x条指令的次数;T为时间效率提高率;P为空间效率提高率。

将所有的循环展开后统计所有用例中指令条数的总和为306+2×68+3×34+4×21=628条，优化后指令条数的数目为35+2×103+3×65+4×39=592条。由表2可知，优化前执行完所有指令需要429个机器周期，而优化后只需要242个机器周期。

由以上测试结果可知，优化处理前后ZSP400目标代码的时间效率有较大提高，空间效率也有提高。

6 结束语

本文中我们把代码优化思想与ZSP400体系结构的特性结合起来，设计了几种针对ZSP400目标代码的优化算法，在时间效率上有较大提高。由于ZSP家族的其他芯片具有和ZSP400大体一致的体系结构和指令集，故本文的优化算法可以轻松移植到其他ZSP芯片上。但是，还可以通过寄存器重分配提升其优化，这将在后期工作中进行。

［1］YU Xian－bin.High－speed ultra－wideband wireless signals over fiber systems:hotonic generation and DSP detection［J］.Journal of China Universitys of Posts and Telecommunications，2009，16(4):7－11.

［2］林峰，林毅.TMS320C6000代码优化技术［J］.重庆邮电大学学报:自然科学版，2006，18(1):60－64.

LING Feng，LING Yi.TMS320C6000 Codes Optimizing Technology［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2006，18(1):60－64.

［3］LSI Logic Corporation.ZSP400 Digital Signal Processor Architecture［EB/OL］.(2001－12－20)［2010－07－05］.http://pdf.51dzw.com/ic_pdf/ZSP400－pdf－1538091_733079.htm l.

［4］伍仲祥，孙名松.浅析嵌入式系统编程中的代码优化［J］.自动化技术与应用，2005，24(12):18－21.

WU Zhong－xiang，SUN Ming－song.Code Optimization in Embedded System Programming［J］.Techniques of Automation and Applications，2005，24(12):18－21.

［5］张振宇，胡兆权.嵌入式操作系统编译器优化技术分析［J］.信息与电子工程，2003，1(04):269－271.

ZHANG Zhen－yu，HU Yao－quan.Compiler Optimization Technique Analysis in Embedded Operating System［J］.Information and Electronic Engineering，2003，1(04):269－271.

［6］ALFRED V，RAVIS，MONICA S，etal.编译原理［M］.2版.赵建华，郑滔，戴新宇，译.北京:机械工业出版社，2009:427－609.

ALFRED V，RAVI S，MONICA S，et al.Compilers:Principles，Techniques，and Tools［M］.2nd ed.ZHAO Jian－hua，ZHEN tao，DAIXing－yu，translation.Beijing:Mechanical industry press，2009:427－609.

［7］GAN Ling，DING Zhen－jiang.A Simulator Support for LSI Logic ZSP400 Instruction Set［C］//3CA 2010，2010 International Symposium on Computer，Communication，Control and Automation.Taiwan:Far East University，2010:10－13.

(编辑:田海江)