Computer Science ›› 2021, Vol. 48 ›› Issue (6A): 587-595.doi: 10.11896/jsjkx.200600061

• Interdiscipline & Application • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] LU Hao-song, HU Yong-hua, WANG Shu-ying, ZHOU Xin-lian, LI Hui-xiang. Study on Hybrid Resource Heuristic Loop Unrolling Factor Selection Method Based on Vector DSP [J]. Computer Science, 2022, 49(6A): 777-783.
[2] HU Wei-fang, CHEN Yun, LI Ying-ying, SHANG Jian-dong. Loop Fusion Strategy Based on Data Reuse Analysis in Polyhedral Compilation [J]. Computer Science, 2021, 48(12): 49-58.
[3] WANG Jian-zhong and YANG Lu. Data Acquisition and Transmission in High Speed Real-time System [J]. Computer Science, 2016, 43(Z11): 604-606.
[4] ZHOU Guo-chang, GUO Bao-long, GAO Xiang, WANG Jian and YAN Yun-yi. Fast Estimation of WCET Based on Distribution Function [J]. Computer Science, 2016, 43(5): 157-161.
[5] SUN Hai-yan, CHEN Yue-yue, WANG Feng, YANG Can-qun, YANG Liu and WANG Ji. Correctness Test of TI DSP C Compiler [J]. Computer Science, 2015, 42(Z6): 513-515.
[6] YANG Lin, WU Jia-zhu, HU Xiao and TIAN Xi. Realization and Optimization of Cross-correlation Based on YHFT-QDSP [J]. Computer Science, 2015, 42(11): 53-55.
[7] WANG Wang,YAO Shu-zhen and TAN Huo-bin. Modeling and Performance Analysis of TTE Bus Based on DSPN [J]. Computer Science, 2014, 41(7): 45-48.
[8] GE Hong-mei,XU Chao,CHEN Nian and LIAO Xi-mi. Low Power Optimization Method Oriented to Embedded System’s Bus [J]. Computer Science, 2013, 40(12): 31-36.
[9] . Application of DSP in the Data Security of Data Link Terminal [J]. Computer Science, 2012, 39(Z11): 14-15.
[10] ZOU Xiu-guo. Framework Detecting in Parallel DSP Network Based on Wormhole Algorithm [J]. Computer Science, 2011, 38(Z10): 76-77.
[11] TIAN Zu-wei,SUN Guang. Research of Compiler Optimization Technology Based on Predicated Code [J]. Computer Science, 2010, 37(5): 130-133.
[12] SU Shu-guang, SU Yue-ming, LIU Yun-sheng. Design and Implement of Multichannel Video Coding Terminal Based on DSP [J]. Computer Science, 2009, 36(9): 252-254.
[13] . [J]. Computer Science, 2009, 36(2): 78-81.
[14] CHEN Sheng-lai,ZHENG Ai-min,LI Tao. Study on Compression Algorithm of Cruise Missile Image Based on Wavelet Code [J]. Computer Science, 2009, 36(12): 263-266.
[15] HE Jun-Mei ,ZOU Xian-Chun (Faculty of Computer and Information Science, Southwest University, Chongqing 400715). [J]. Computer Science, 2007, 34(7): 282-283.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!