Computer Science ›› 2019, Vol. 46 ›› Issue (6): 196-200.doi: 10.11896/j.issn.1002-137X.2019.06.029

Previous Articles     Next Articles

Optimization Algorithm of Complementary Register Usage Between Two Register Classesin Register Spilling for DSP Register Allocation

QIU Ya-qiong, HU Yong-hua, LI Yang, TANG Zhen, SHI Lin   

  1. (School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China)
  • Received:2018-04-17 Published:2019-06-24

Abstract: Register allocation has become one of the most important optimization techniques for compiler for that registers are limited and valuable resources in hardware architecture of computer.One of the key factors affecting the results of register allocation is the access and storage costs incurred from spilling signed registers.For DSP architectures with two classes of general-purpose registers,this paper proposed a complementary utilization strategy between the registers and a corresponding register spilling optimization algorithm on the basis of graph coloring register allocation method.Through distinguishing the interference between candidates of the same register class from those of different register classes,an undirected graph is built by improving the analysis for variables’ live ranges.Compared with the conventional graph coloring register allocation,the improved algorithm fully consideres the interferences among the register allocation candidates for two register classes,thus achiving less memory access operations in register spilling and higher code performance.

Key words: Register allocation, Compiler, Graph coloring algorithm, Register spilling, Optimization

CLC Number: 

  • TP311
[1]AHO A V,SETHI R,ULLMAN J D.Compilers,Principles, Techniques[M].Boston:Addison wesley,1986.
[2]RAU B R,LEE M,TIRUMALAI P P,et al.Register allocation for software pipelined loops[C]∥Acm Sigplan Conference on Programming Language Design & Implementation.1992:283-299.
[3]REN K,YAN X L,SUN L L,et al.ASIP register allocator based on improved graph coloring algorithm[J].Journal of Zhejiang University,2010(12):2309-2313.(in Chinese)
任坤,严晓浪,孙玲玲,等.基于改进图染色算法的 ASIP 寄存器分配器[J].浙江大学学报(工学版),2010(12):2309-2313.
[4]JIANG J,WANG C,YU H M .A Local Register Allocation Optimization Strategy[J].Computer Applications and Software,2013(12):215-217.(in Chinese)
[5]BRIGGS P,COOPER K D,KENNEDY K,et al.Coloring,heuristics for register allocation[J].ACM SIGPLAN Notices,1989,24(7):275-284.
[6]CHAITIN G J.Register allocation & spilling via graph coloring[J].ACM Sigplan Notices.ACM,1982,17(6):98-105.
[7]CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer languages,1981,6(1):47-57.
[8]ACM Transactions on Programming Languages and Systems [M].Association for Computing Machinery,1979.
[9]BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].Acm Letters on Programming Languages & Systems,1992,1(1):3-13.
[10]BRIGGS P,COOPER K D,TORCZON L.Improvements to graph coloring register allocation[J].Acm Transactions on Programming Languages & Systems,1994,16(3):428-455.
[11]PENG Z S,DUAN Y Y,WANG B.Introduction of Mainstream Processor Architecture and Intel Microarchitecture Development[J].Information System Engineering,2017(3):29-31.(in Chinese)
[12]WANG X,FU J W,HE H.Instruction Processing Method Based on ARM Instruction Set in General DSP[J].Microelectronics and Computers,2016,33(9):10-14.(in Chinese)
[13]NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[C]∥ACM Sigplan 1990 Conference on Programming Language Design and Implementation.ACM,1990:40-52.
[14]WOLFE J.Optimizing Super-compilers for Supercomputers[M]∥ Optimizing Super-compilers for Supercomputers.MIT Press Cambridge,MA,USA,1990.
[15]HUANG L,FENG X B.Combined instruction scheduling and register allocation techniques[J].Application Research of Computers,2008,25(4):979-982.(in Chinese)
[16]Instruction Set Manual of YHFT-Matrix2 DSP[G].Institute of Microelectronics,National University of Defense Technology.2013.(in Chinese)
YHFT-Matrix2 DSP 指令集手册[G].国防科学技术大学计算机学院微电子所.2013.
[1] LIANG Wei, DUAN Xiao-dong, XU Jian-feng. Three-way Filtering Algorithm of Basic Clustering Based on Differential Measurement [J]. Computer Science, 2021, 48(1): 136-144.
[2] YANG Ping, WANG Sheng-yuan. Analysis of Target Code Generation Mechanism of CompCert Compiler [J]. Computer Science, 2020, 47(9): 17-23.
[3] CHI Hao-yu, CHEN Chang-bo. Prediction of Loop Tiling Size Based on Neural Network [J]. Computer Science, 2020, 47(8): 62-70.
[4] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[5] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[6] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[7] LI Yang, LI Wei-gang, ZHAO Yun-tao, LIU Ao. Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy [J]. Computer Science, 2020, 47(8): 291-296.
[8] ZHANG Zhi-qiang, LU Xiao-feng, SUI Lian-sheng, LI Jun-huai. Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator [J]. Computer Science, 2020, 47(8): 297-301.
[9] LI Zhang-wei, XIAO Lu-qian, HAO Xiao-hu, ZHOU Xiao-gen, ZHANG Gui-jun. Multimodal Optimization Algorithm for Protein Conformation Space [J]. Computer Science, 2020, 47(7): 161-165.
[10] SUN Jun-yan, ZHANG Yuan-yuan, WU Bing-ying, NIU Ya-ru, CHEN Chan-juan. Evolution Analysis of Household Car Supply Chain Based on Multi-Agent [J]. Computer Science, 2020, 47(7): 171-178.
[11] ZHENG You-lian, LEI De-ming, ZHENG Qiao-xian. Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling [J]. Computer Science, 2020, 47(7): 186-191.
[12] QI Wei, YU Hui-qun, FAN Gui-sheng, CHEN Liang. WSN Coverage Optimization Based on Adaptive Particle Swarm Optimization [J]. Computer Science, 2020, 47(7): 243-249.
[13] LI Xin, DUAN Yong-cheng. Network Security Situation Assessment Method Based on Improved Hidden Markov Model [J]. Computer Science, 2020, 47(7): 287-291.
[14] ZHANG Yu-qin, ZHANG Jian-liang and FENG Xiang-dong. Parametric-free Filled Function Algorithm for Unconstrained Optimization [J]. Computer Science, 2020, 47(6A): 54-57.
[15] TANG Cheng-e and WEI Jun. Application of Power Load Prediction Based on Improved Support Vector Regression Machine [J]. Computer Science, 2020, 47(6A): 58-65.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .