基于指令Cache和寄存器压力的循环展开优化

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (12): 2111-2119.

基于指令Cache和寄存器压力的循环展开优化

王翠霞,韩林,刘浩浩

(中原工学院前沿信息技术研究院，河南郑州 450007)

收稿日期:2021-11-25 修回日期:2022-01-30 接受日期:2022-12-25 出版日期:2022-12-25 发布日期:2022-12-26

Optimization of loop unrolling based on instruction Cache and register pressure

WANG Cui-xia,HAN Lin,LIU Hao-hao

(Research Institute of Front Information Technology,Zhongyuan University of Technology,Zhengzhou 450007,China)

Received:2021-11-25 Revised:2022-01-30 Accepted:2022-12-25 Online:2022-12-25 Published:2022-12-26

摘要/Abstract

摘要： 循环展开是一种常用的编译优化技术，能够有效减少循环开销，提升指令级并行程度和数据局部性，提升循环的执行效能。然而，过度的循环展开会造成指令Cache溢出，增大寄存器压力，循环展开次数太少又会浪费潜在的性能提升机会，因此寻找恰当的展开因子是研究循环展开问题的核心。基于GCC开源编译器，面向循环展开问题开展深入的分析与研究，针对指令Cache和寄存器资源对循环展开的影响，提出了一种基于指令Cache和寄存器压力的循环展开因子计算方法，并在GCC编译器中实现了该计算方法。申威和海光平台上的实验结果显示，相较于目前GCC中存在的其它展开因子计算方法，所提出的方法可以获得更为有效的循环展开因子，提升了程序性能。在SPEC CPU 2006测试集上的平均性能分别提升了2.7%和3.1%，在NPB-3.3.1测试集上的分别为5.4%和6.1%。

关键词: 编译优化, 循环展开, 展开因子, 指令Cache, 寄存器压力

Abstract: Loop unrolling is a common compiler optimization technique, which can effectively reduce loop overhead, improve instruction-level parallelism and register locality, and improve the execution efficiency of loop. However, excessive loop unrolling will cause instruction Cache overflow and increase register pressure, and too little loop unrolling will waste potential performance improvement opportunities. Therefore, finding an appropriate unroll factor is the core of the study of loop unrolling. Based on the open-source compiler GCC, the loop unrolling problems are deeply analyzed and studied. In view of the influence of instruction Cache and register resources on the loop unrolling, a loop unrolling factor calculation method based on instruction Cache and register pressure is proposed and implemented in GCC compiler. Experiments on Sunway and Hygon platforms show that, compared with the current loop unrolling factor calculation method in GCC, this method can obtain more effective unrolling factor and improve the program performance. The average performance of the SPEC CPU 2006 is increased by 2.7% and 3.1%, respectively, and NPB-3.3.1 is increased by 5.4% and 6.1%.

Key words: compiler optimization, loop unrolling, unrolling factor, instruction Cache, register pressure

王翠霞, 韩林, 刘浩浩. 基于指令Cache和寄存器压力的循环展开优化[J]. 计算机工程与科学, 2022, 44(12): 2111-2119.

WANG Cui-xia, HAN Lin, LIU Hao-hao. Optimization of loop unrolling based on instruction Cache and register pressure[J]. Computer Engineering & Science, 2022, 44(12): 2111-2119.

参考文献［17］

［1］	Carminati A,Starke R A,Oliveira R D.Combining loop unrolling strategies and code predication to reduce the worst-case execution time of real-time software［J］.Applied Computing & Informatics,2017,13(2):184-193.
［2］	Kumar S A.Enhancing the scope for automated code generation and parallelism by optimizing loops through loop unrolling［C］∥Proc of the 4th International Conference on Inventive Systems and Control,2020:790-795.
［3］	Yang C,Yang X,Xue J.Improving the performance of GCC by exploiting IA-64 architectural features［C］∥Proc of the 10th Asia-Pacific Conference on Advances in Computer Systems Architecture,2005:236-251.
［4］	Rocha R C O,Porpodas V,Petoumenos P,et al.Vectorization- aware loop unrolling with seed forwarding［C］∥Proc of the 29th International Conference on Compiler Construction,2020:1-13.
［5］	Dong Yu-shan,Li Chun-jiang,Xu Ying.Implementation and effects of loop-array-prefetching optimization in GCC［J］.Computer Engineering and Applications,2016,52(6):19-25.(in Chinese)
［6］	Liu H,Guo Z J.A loop unrolling method based on machine learning［J］.Vibroengineering PROCEDIA,2018,18(6):215-221.
［7］	Stephenson M, Amarasinghe S. Predicting unroll factors using supervised classification［C］∥ Proc of the 3rd International Symposium on Code Generation and Optimization,2005:123-134.
［8］	Zhang Peng.Exploiting some key techniques on the loop unrolling in GCC compiler［D］.Changsha:National University of Defense Technology,2015.(in Chinese)
［9］	Wang Dong,Zhao Rong-cai,Gao Wei,et al.Loop unrolling method based on random decision forest［J］.Computer Engineering and Design,2018,39(1):199-204.(in Chinese)
［10］	Balamane A,Taklit Z,Baghdadi R.Using deep neural networks for estimating loop unrolling factor［J］.arXiv:1911.0399,2019.
［11］	Li Wen-long,Liu Li,Tang Zhi-zhong.Loop unrolling optimization for software pipelining［J］.Journal of Beijing University of Aeronautics and Astronautics,2004,30(11):1111-1115.(in Chinese)
［12］	Gao Wei,Zhao Rong-cai,Yu Hai-ning,et al.Loop unrolling in vectorized programs［J］.Computer Science,2016,43(1):225-231.(in Chinese)
［13］	Liu X H,Ding L P,Li Y F,et al.Research of register pressure aware loop unrolling optimizations for compiler［C］∥Proc of the 3rd International Conference on Circuits and Systems,2018:1-5.
［14］	Leopoldseder D,Schatz R,Stadler L,et al.Fast-path loop unrolling of non-counted loops to enable subsequent compiler optimizations［C］∥Proc of the 15th International Confe- rence on Managed Languages & Runtimes,2018:2:1-2:13.
［15］	The GNU compiler collection［EB/OL］.［2021-11-01］.http://gcc.gnu.org.
［16］	Shobaki G,Kerbow A,Pulido C,et al.Exploring an alternative cost function for combinatorial register-pressure-aware instruction scheduling［J］.ACM Transactions on Architecture and Code Optimization,2019,16(1):1:1-1:30.
［17］	Wang Jun,Pang Jian-min,Fu Li-guo,et al.A dynamic and static combined register mapping method in binary translation［J］.Journal of Computer Research and Development,2019,56(4):34-44.(in Chinese)
［18］	Makarov V N.Fighting register pressure in GCC［C］∥Proc of the 4th GCC Developers’ Summit,2004:85-104.
	附中文参考文献：
［5］	董钰山,李春江,徐颖.GCC编译器中循环数组预取优化的实现及效果［J］.计算机工程与应用,2016,52(6):19-25.
［8］	张鹏.基于GCC编译器的循环展开关键技术研究［D］.长沙:国防科学技术大学,2015.
［9］	王冬,赵荣彩,高伟,等.基于随机决策森林的循环展开方法［J］.计算机工程与设计,2018,39(1):199-204.
［11］	李文龙,刘利,汤志忠.软件流水中的循环展开优化［J］.北京航空航天大学学报,2004,30(11):1111-1115.
［12］	高伟,赵荣彩,于海宁,等.循环展开技术在向量程序中的应用［J］.计算机科学,2016,43(1):225-231.
［17］	王军,庞建民,傅立国,等.二进制翻译中动静结合的寄存器分配优化方法［J］.计算机研究与发展,2019,56(4):34-44.