论文部分内容阅读
摘要：魂芯DSP是一款具有分簇结构的、支持SIMD的VLIW高性能通用处理器。为了提高循环执行的效率，魂芯DSP设计了硬件支持的零开销循环机制。提出了一个通用的从编译层面支持的零开销循环的识别转换算法。以典型的DSP测试用例进行实验评测，零开销循环的识别可以带来6%～37%的性能提升。
关键词：循环执行；零开销循环；识别转换算法
中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2015）12-0100-03
Compiler Optimization on Zero-overhead Loop for DSP
XIANG Li-ping， WANG Xiang-qian
（No.38 Research Institude，China Electronics Technology Group Corporation，Hefei 230088， China）
Abstract： BWDSP is a VLIW DSP processor supporting cluster and SIMD. In order to improve the efficiency of loop execution， the DSP provides hardware support for zero-overhead loop mechanism. A general framework for zero-overhead loop recognization as well as transformation on level of compiler is presented. Through the classsic DSP test set， zero-overhead loop recognization optimization can bring performance improvement ranging from 6% to 37%.
Key words： loop execution； zero-overhead loop； recognization and transformation algorithm
提高循环执行效率有多种软硬件技术。硬件技术包括分支预测、超标量。但这些技术提高了循环执行效率的同时，也导致了硬件的复杂度。而软件方法循环展开虽然可以提高性能，但是增加了生成代码的大小。零开销循环[1]是DSP处理器中常见的体系结构特性。它可以加快循环执行的效率而不会引起生成代码的增大。零开销循环不需要循环计数更新、测试和回跳指令，因此能够加速处理能力。典型DSP算法很大部分的执行时间[2，3]花费在执行循环上，从硬件上支持零开销循环对于提高DSP处理器的性能非常必要。零开销循环机制可以在TI、ADI等众多DSP处理器中发现，这些厂商提供的编译器生成循环代码时，已经使用零开销循环来提高代码生成质量。本文分析BWDSP中编译器针对循环代码效率的瓶颈所在，给出了BWDSP上的零开销循环编译优化框架，提出识别可转化为零开销循环的一般性算法；提出零开销循环变换的方法。
1 魂芯编译器循环生成主要问题
在可重定向编译基础设施IMPACT[4]的基础上，我们开发了针对BWDSP体系结构的 C编译器。
BWDSP C编译器针对DSP典型程序（如图1所示） 的循环生成的代码如图2所示。
可见BWDSP100编译器针对两个程序生成的循环代码的并行度不高，计算代码和循环控制代码之间有依赖关系[5]，循环控制过程复杂，需要随着循环的迭代同时计算步长，如图3、图4所示。如果进行零开销循化的变换，可以减小关键路径，提高循环执行效率。
2 零开销循环的识别和转换
2.1 循环的正规表示
一般在循环的正规表示[6，7]上进行零开销循环的识别。如果一个循环不是正规表示，在进行零开销循环
换前，则先进行一系列的预处理转化阶段：循环简化、归纳变量正规化、尾函数调用删除。
1）循环简化
循环简化阶段转换自然循环为控制流具有同样结构的循环表示。保证每一个循环有一个循环前置结点（loop preheader）。另外保证每一个循环只有一个唯一的回边。循环前置结点是在循环首结点前面建立的一个新的基本块，原来从循环外进入循环首结点的所有边改成指向前置结点，并且从循环前置结点有一个新的边指向循环首结点。
2）归纳变量正规化
该预处理阶段是改变具有可识别归纳变量的循环为从零开始以一定的步长计数的归纳变量形式。如果循环迭代的次数可以计算出来，循环的退出条件转换为归纳变量和循环迭代次数的比较。
3）尾函数调用删除
循环可以用递归函数实现，可以转换递归函数为其循环表示。
2.2 零开销循环转换的限制条件
条件1： 循环体里不能含有函数调用。
循环体里含有函数调用的循环不能进行零开销循环转换。因为调用的函数有可能也包括有零开销循环。
条件2： 转换为零开销循环的循环个数不能超过硬件提供的零开销循环个数。
BWDSP支持两个硬件零开销循环同时执行。
条件3：循环规约变量必须是循环退出条件指令的操作数。
条件4：如果循环有多个出口，则该循环不能进行零开销循环转换。
条件5：如果循环次数不可数，则该循换不能进行零开销循环转换。
循环次数可数，是指循环次数可以用一个寄存器或者立即数表示。
2.3 零开销循环的转换
进行零开销循环的转化是在以上所有判断条件都满足的情况下才能进行。 零开销循环转换分为三步。第一步，在preheader插入循环次数到零开销循环寄存器的拷贝指令；第二步是用零开销循环指令替换循环跳转条件；第三步骤把转换之后不需要的循环归纳条件和比较指令删除以及产生的其它冗余指令删除。
第二步中，循环跳转指令分为两种情况讨论。
1）循环跳转指令由条件跳转指令和跟着的无条件跳转指令组成。这种情况下条件判断跳转指令的跳转目标是否落在循环体外。如果是，则保留该跳转指令。如果不是，则予以删除。
2）循环跳转指令只有一个条件跳转指令，直接跳到循环起始处。直接把该指令替换为零开销循环指令。
2.4 实现算法
在循环的正规表示形式上实现零开销循环识别转换算法[8-10]，如图5所示。
3 实例分析
图2（a）中循环体执行需要10个周期，而在进行零开销循环转换后的代码，如图6（a）上所示，循环体执行只需要7个周期，执行效率提高约30%。图2（b）中循环体执行需要8个周期，而在进行零开销循环转换后，如图6（b）上所示，循环体执行只需要5个周期，执行效率提高约37%。可见零开销循环的识别和转换极大地提高了循环的执行效率。在进行零开销循环转换后，消除了循环体中计算部分和循环控制部分的不必要的依赖关系，使得计算部分和循环控制部分的关联代码降至最少。
4 测试结果
选取数字信号处理的典型应用dspstone[11]作为性能测试集合，图7为零开销循环优化在各个典型应用上的性能提升百分比。
可见，零开销循环识别技术使得测试集合获得不同程度的性能，从6%～37%。程序在零开销循环识别技术下性能提升的百分比取决于零开销循环技术可以节省的周期在整个循环体执行周期占的百分比。这是不同的测试用例获得不同的性能提升的原因。
5 结束语
本文分析了魂芯DSP C编译器生成循环代码效率的主要问题所在，提出了一般性的零开销循环的识别和转换算法。最后通过dspstone测试集验证了零开销循环优化取得的效果，dspstone测试集合用例获得了6%～37%的代码执行效率的提升。
参考文献：
[1] Eyre J， Bier J. The evolution of DSP processors[J]. IEEE Signal Processing Magazine， 2000， 17（2）： 43-51.
[2] 吴强， 任琳， 张杰，等. 快速归一化互相关算法及 DSP 优化实现[J]. 电子测量与仪器学报， 2011， 25（6）： 495-499.
[3] 牛海军， 樊瑜波， 杨松岩， 等. 基于 ARM 和 DSP 的超声膀胱容积检测与预警系统的设计[J]. 仪器仪表学报， 2011， 32（8）：1858-1863.
[3] HU W M.The IMPACT Research Group[EB/OL].http：//impact.crh
c.illinois.edu/.
[4] Allen R， Kennedy K. Optimizing compilers for modern architectures[M]. San Francisco： Morgan Kaufmann， 2002.
[5] Novillo D. Tree SSA A New Optimization Infrastructure for GCC[C]//Proceedings of the 2003 GCC Developers’ Summit. 2003： 181-193.
[6] Liu S M， Lo R， Chow F. Loop induction variable canonicalization in parallelizing compilers[C]//Parallel Architectures and Compilation Techniques， 1996：Proceedings of the 1996 Conference on. IEEE， 1996： 228-237.
[7] Uh G R， Wang Y， Whalley D， et al. Effective exploitation of a zero overhead loop buffer[C]//ACM SIGPLAN Notices. ACM， 1999， 34（7）： 10-19.
[8] Uh G R， Wang Y， Whalley D， et al. Techniques for effectively exploiting a zero overhead loop buffer[C]//Compiler Construction. Springer Berlin Heidelberg， 2000： 157-172.
[9] Cao V P， Fajardo L A， Jinturkar S， et al. Compiler optimization techniques for exploiting a zero overhead loop mechanism： U.S. Patent 6，367，071[P]. 2002-4-2.
[10] The Institute for Integrated Signal ProcessingSystems.
DSPstone[EB/OL].http：//www.ert.rwth-aachen.de/Projekte/Tools/DSPSTONE/dspstone.
关键词：循环执行；零开销循环；识别转换算法
中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2015）12-0100-03
Compiler Optimization on Zero-overhead Loop for DSP
XIANG Li-ping， WANG Xiang-qian
（No.38 Research Institude，China Electronics Technology Group Corporation，Hefei 230088， China）
Abstract： BWDSP is a VLIW DSP processor supporting cluster and SIMD. In order to improve the efficiency of loop execution， the DSP provides hardware support for zero-overhead loop mechanism. A general framework for zero-overhead loop recognization as well as transformation on level of compiler is presented. Through the classsic DSP test set， zero-overhead loop recognization optimization can bring performance improvement ranging from 6% to 37%.
Key words： loop execution； zero-overhead loop； recognization and transformation algorithm
提高循环执行效率有多种软硬件技术。硬件技术包括分支预测、超标量。但这些技术提高了循环执行效率的同时，也导致了硬件的复杂度。而软件方法循环展开虽然可以提高性能，但是增加了生成代码的大小。零开销循环[1]是DSP处理器中常见的体系结构特性。它可以加快循环执行的效率而不会引起生成代码的增大。零开销循环不需要循环计数更新、测试和回跳指令，因此能够加速处理能力。典型DSP算法很大部分的执行时间[2，3]花费在执行循环上，从硬件上支持零开销循环对于提高DSP处理器的性能非常必要。零开销循环机制可以在TI、ADI等众多DSP处理器中发现，这些厂商提供的编译器生成循环代码时，已经使用零开销循环来提高代码生成质量。本文分析BWDSP中编译器针对循环代码效率的瓶颈所在，给出了BWDSP上的零开销循环编译优化框架，提出识别可转化为零开销循环的一般性算法；提出零开销循环变换的方法。
1 魂芯编译器循环生成主要问题
在可重定向编译基础设施IMPACT[4]的基础上，我们开发了针对BWDSP体系结构的 C编译器。
BWDSP C编译器针对DSP典型程序（如图1所示） 的循环生成的代码如图2所示。
可见BWDSP100编译器针对两个程序生成的循环代码的并行度不高，计算代码和循环控制代码之间有依赖关系[5]，循环控制过程复杂，需要随着循环的迭代同时计算步长，如图3、图4所示。如果进行零开销循化的变换，可以减小关键路径，提高循环执行效率。
2 零开销循环的识别和转换
2.1 循环的正规表示
一般在循环的正规表示[6，7]上进行零开销循环的识别。如果一个循环不是正规表示，在进行零开销循环
换前，则先进行一系列的预处理转化阶段：循环简化、归纳变量正规化、尾函数调用删除。
1）循环简化
循环简化阶段转换自然循环为控制流具有同样结构的循环表示。保证每一个循环有一个循环前置结点（loop preheader）。另外保证每一个循环只有一个唯一的回边。循环前置结点是在循环首结点前面建立的一个新的基本块，原来从循环外进入循环首结点的所有边改成指向前置结点，并且从循环前置结点有一个新的边指向循环首结点。
2）归纳变量正规化
该预处理阶段是改变具有可识别归纳变量的循环为从零开始以一定的步长计数的归纳变量形式。如果循环迭代的次数可以计算出来，循环的退出条件转换为归纳变量和循环迭代次数的比较。
3）尾函数调用删除
循环可以用递归函数实现，可以转换递归函数为其循环表示。
2.2 零开销循环转换的限制条件
条件1： 循环体里不能含有函数调用。
循环体里含有函数调用的循环不能进行零开销循环转换。因为调用的函数有可能也包括有零开销循环。
条件2： 转换为零开销循环的循环个数不能超过硬件提供的零开销循环个数。
BWDSP支持两个硬件零开销循环同时执行。
条件3：循环规约变量必须是循环退出条件指令的操作数。
条件4：如果循环有多个出口，则该循环不能进行零开销循环转换。
条件5：如果循环次数不可数，则该循换不能进行零开销循环转换。
循环次数可数，是指循环次数可以用一个寄存器或者立即数表示。
2.3 零开销循环的转换
进行零开销循环的转化是在以上所有判断条件都满足的情况下才能进行。 零开销循环转换分为三步。第一步，在preheader插入循环次数到零开销循环寄存器的拷贝指令；第二步是用零开销循环指令替换循环跳转条件；第三步骤把转换之后不需要的循环归纳条件和比较指令删除以及产生的其它冗余指令删除。
第二步中，循环跳转指令分为两种情况讨论。
1）循环跳转指令由条件跳转指令和跟着的无条件跳转指令组成。这种情况下条件判断跳转指令的跳转目标是否落在循环体外。如果是，则保留该跳转指令。如果不是，则予以删除。
2）循环跳转指令只有一个条件跳转指令，直接跳到循环起始处。直接把该指令替换为零开销循环指令。
2.4 实现算法
在循环的正规表示形式上实现零开销循环识别转换算法[8-10]，如图5所示。
3 实例分析
图2（a）中循环体执行需要10个周期，而在进行零开销循环转换后的代码，如图6（a）上所示，循环体执行只需要7个周期，执行效率提高约30%。图2（b）中循环体执行需要8个周期，而在进行零开销循环转换后，如图6（b）上所示，循环体执行只需要5个周期，执行效率提高约37%。可见零开销循环的识别和转换极大地提高了循环的执行效率。在进行零开销循环转换后，消除了循环体中计算部分和循环控制部分的不必要的依赖关系，使得计算部分和循环控制部分的关联代码降至最少。
4 测试结果
选取数字信号处理的典型应用dspstone[11]作为性能测试集合，图7为零开销循环优化在各个典型应用上的性能提升百分比。
可见，零开销循环识别技术使得测试集合获得不同程度的性能，从6%～37%。程序在零开销循环识别技术下性能提升的百分比取决于零开销循环技术可以节省的周期在整个循环体执行周期占的百分比。这是不同的测试用例获得不同的性能提升的原因。
5 结束语
本文分析了魂芯DSP C编译器生成循环代码效率的主要问题所在，提出了一般性的零开销循环的识别和转换算法。最后通过dspstone测试集验证了零开销循环优化取得的效果，dspstone测试集合用例获得了6%～37%的代码执行效率的提升。
参考文献：
[1] Eyre J， Bier J. The evolution of DSP processors[J]. IEEE Signal Processing Magazine， 2000， 17（2）： 43-51.
[2] 吴强， 任琳， 张杰，等. 快速归一化互相关算法及 DSP 优化实现[J]. 电子测量与仪器学报， 2011， 25（6）： 495-499.
[3] 牛海军， 樊瑜波， 杨松岩， 等. 基于 ARM 和 DSP 的超声膀胱容积检测与预警系统的设计[J]. 仪器仪表学报， 2011， 32（8）：1858-1863.
[3] HU W M.The IMPACT Research Group[EB/OL].http：//impact.crh
c.illinois.edu/.
[4] Allen R， Kennedy K. Optimizing compilers for modern architectures[M]. San Francisco： Morgan Kaufmann， 2002.
[5] Novillo D. Tree SSA A New Optimization Infrastructure for GCC[C]//Proceedings of the 2003 GCC Developers’ Summit. 2003： 181-193.
[6] Liu S M， Lo R， Chow F. Loop induction variable canonicalization in parallelizing compilers[C]//Parallel Architectures and Compilation Techniques， 1996：Proceedings of the 1996 Conference on. IEEE， 1996： 228-237.
[7] Uh G R， Wang Y， Whalley D， et al. Effective exploitation of a zero overhead loop buffer[C]//ACM SIGPLAN Notices. ACM， 1999， 34（7）： 10-19.
[8] Uh G R， Wang Y， Whalley D， et al. Techniques for effectively exploiting a zero overhead loop buffer[C]//Compiler Construction. Springer Berlin Heidelberg， 2000： 157-172.
[9] Cao V P， Fajardo L A， Jinturkar S， et al. Compiler optimization techniques for exploiting a zero overhead loop mechanism： U.S. Patent 6，367，071[P]. 2002-4-2.
[10] The Institute for Integrated Signal ProcessingSystems.
DSPstone[EB/OL].http：//www.ert.rwth-aachen.de/Projekte/Tools/DSPSTONE/dspstone.