计算机科学 ›› 2021, Vol. 48 ›› Issue (6A): 587-595.doi: 10.11896/jsjkx.200600061

• 交叉&应用 • 上一篇    下一篇


唐镇, 胡勇华, 陆浩松, 王书盈   

  1. 湖南科技大学 湖南 湘潭411201
  • 出版日期:2021-06-10 发布日期:2021-06-17
  • 通讯作者: 胡勇华(huyh@hnust.cn)
  • 作者简介:tangzhenchina@163.com
  • 基金资助:

Research on DSP Register Pairs Allocation Algorithm with Weak Assigning Constraints

TANG Zhen, HU Yong-hua, LU Hao-song, WANG Shu-ying   

  1. School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China
  • Online:2021-06-10 Published:2021-06-17
  • About author:TANG Zhen,born in 1994,postgraduate.His main research interests include DSP compilation and so on.
    HU Yong-hua,born in 1981,Ph.D,professor,supervisor.His main research interests include DSP compilation and so on.
  • Supported by:
    Hunan Provincial Natural Science Foundation of China(2017JJ3087) and National Natural Science Foundation of China(61308001,61872138).

摘要: 在现代高性能数字信号处理器(DSP)中,许多指令把寄存器偶对作为操作数。为了优化寄存器偶对的使用,文中针对寄存器偶对的使用约束条件,提出了一种基于弱约束指派的DSP寄存器偶对分配算法。该算法在寄存器指派过程中优先指派空闲寄存器偶对给符号寄存器对。如果无法指派寄存器偶对给符号寄存器对,则指派两个不能组成寄存器偶对的寄存器。为了确保目标代码中寄存器偶对操作数最终获得的寄存器偶对符合寄存器偶对的使用约束条件,提供了一种指令操作数修正方法。采用6种经典的算法作为测试用例进行实验,结果表明所提算法的实验效果较好。

关键词: DSP, 编译优化, 寄存器偶对, 全局寄存器分配, 图着色方法

Abstract: In modern high performance digital signal processors (DSP),many instructions regard register pairs as operands.To optimize register pair usage,this paper presents a register pairs allocation algorithm for DSP based on weak constraint assignment for the rules of using register pairs.In the process of register assignment,the priority of this algorithm is to assign idle register pairs to symbol register pairs.If it is not possible to assign register pairs to symbol register pairs,two registers that cannot be made up of a register pair are assigned.In order to ensure that the register pairs in the target code are consistent with the rules of register pairs,this paper provides an instruction operand correction method.This paper uses six classical algorithms as test cases.The experimental results show that the proposed algorithm is effective.

Key words: Compiler optimization, DSP, Global register allocation, Graph coloring method, Register pairs


  • TP311
[1] LORENZ M,WEHMEYER L,THORSTEN D.Energy aware compilation for DSPs with SIMD instructions[C]//Proc.of the Joint Conf.on Languages,Compilers and Tools for Embedded Systems.2002,37(7):94-101.
[2] NI Y H,CHEN W W,WANG L,et al.Optimization of Register Allocation Strategy for MLC STT-RAM[J].Computer Science,2018,45(S1):562-567.
[3] EISL J,MARR S,WÜRTHINGER T,et al.Trace Register Allocation Policies:Compile-Time vs.Performance Trade-Offs[C]//Proc. of the 14th International Conf.on Managed Languages and Runtimes.2017:92-104.
[4] POLETTO M,SARKAR V.Linear scan register allocation[J].ACM Trans.on Programming Languages and Systems,1999,21(5):895-913.
[5] WIMMER C,FRANZ M.Linear scan register allocation on SSA form[C]//IEEE/ACM International symp.on Code Generation and Optimization.2010,170-179.
[6] KANANIZADEH S,KONONENKO K.Improving on LinearScan Register Allocation[J].International Journal of Automation and Computing,2018,15(2):228-238.
[7] CHAITIN G J.Register allocation and spilling via graph coloring[C]//Symp.on Compiler Construction.1982:98-105.
[8] CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer Languages,1981:47-57.
[9] BRIGGS P,COOPER K D,TORCZON L.Improvements tograph coloring register allocation[J].Trans.on Programming Languages and Systems,1994,16(3):428-455.
[10] WU S N,LI S K.A Hyrid Evolutionary Algorithm for Register Allocation of Embedded Processors[J].Computer Science,2007,34(8):278-280.
[11] NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[J].Programming Language Design and Implementation,1990,25(6):40-52.
[12] BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].ACM Letters on Programming Languages and Systems,1992,1(1):3-13.
[13] SMITH M D,HOLLOWAY G.Graph-coloring register allocation for irregular architectures[J].Submitted to PLDI,2000,1:1-8.
[14] Intel® 64 and IA-32 Architectures Software Developer's Manual.Intel Corporation[G].2019.
[15] Processor Programming Reference (PPR) for AMD Family 17h Models 01h,08h,Revision B2 Processors[G].Advanced Micro Devices.2019.
[16] YHFT-Matrix2 DSP instruction set manual[G].Institute of Microelectronics.College of Computer Science and Technology,National University of Defense Technology.2013.
[17] ARM946E-S (Rev1) System-on-Chip DSP enhanced processor Product Overview[G].ARM Limited.2000.
[1] 陆浩松, 胡勇华, 王书盈, 周新莲, 李慧祥.
Study on Hybrid Resource Heuristic Loop Unrolling Factor Selection Method Based on Vector DSP
计算机科学, 2022, 49(6A): 777-783. https://doi.org/10.11896/jsjkx.210400146
[2] 胡伟方, 陈云, 李颖颖, 商建东.
Loop Fusion Strategy Based on Data Reuse Analysis in Polyhedral Compilation
计算机科学, 2021, 48(12): 49-58. https://doi.org/10.11896/jsjkx.210200071
[3] 池昊宇, 陈长波.
Prediction of Loop Tiling Size Based on Neural Network
计算机科学, 2020, 47(8): 62-70. https://doi.org/10.11896/jsjkx.191200180
[4] 邱亚琼, 胡勇华, 李阳, 唐镇, 石林.
Optimization Algorithm of Complementary Register Usage Between Two Register Classesin Register Spilling for DSP Register Allocation
计算机科学, 2019, 46(6): 196-200. https://doi.org/10.11896/j.issn.1002-137X.2019.06.029
[5] 王建中,杨璐.
Data Acquisition and Transmission in High Speed Real-time System
计算机科学, 2016, 43(Z11): 604-606. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.137
[6] 周国昌,郭宝龙,高翔,王健,闫允一.
Fast Estimation of WCET Based on Distribution Function
计算机科学, 2016, 43(5): 157-161. https://doi.org/10.11896/j.issn.1002-137X.2016.05.029
[7] 杨琳,吴家铸,扈啸,田希.
Realization and Optimization of Cross-correlation Based on YHFT-QDSP
计算机科学, 2015, 42(11): 53-55. https://doi.org/10.11896/j.issn.1002-137X.2015.11.009
[8] 王望,姚淑珍,谭火彬.
Modeling and Performance Analysis of TTE Bus Based on DSPN
计算机科学, 2014, 41(7): 45-48. https://doi.org/10.11896/j.issn.1002-137X.2014.07.008
[9] 葛红美,徐超,陈念,廖希密.
Low Power Optimization Method Oriented to Embedded System’s Bus
计算机科学, 2013, 40(12): 31-36.
[10] 卞东亮 陈长兴 彭沙沙 牛德智 王博.
Application of DSP in the Data Security of Data Link Terminal
计算机科学, 2012, 39(Z11): 14-15.
[11] 邹修国.
Framework Detecting in Parallel DSP Network Based on Wormhole Algorithm
计算机科学, 2011, 38(Z10): 76-77.
[12] 田祖伟,孙光.
Research of Compiler Optimization Technology Based on Predicated Code
计算机科学, 2010, 37(5): 130-133.
[13] 苏曙光,苏月明,刘云生.
Design and Implement of Multichannel Video Coding Terminal Based on DSP
计算机科学, 2009, 36(9): 252-254.
[14] .

计算机科学, 2009, 36(3): 45-47.
[15] .

计算机科学, 2009, 36(2): 78-81.
Full text



No Suggested Reading articles found!