Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (2): 117-123.doi: 10.11896/jsjkx.250300153

• Computer Architecture • Previous Articles     Next Articles

Loop Splitting Based on Conditional Statement Invariance Analysis

HAN Lin1, SHAO Jingjing2, NIE Kai1, LI Haoran1, LIU Haohao1, CHEN Mengyao2   

  1. 1 National Supercomputing Center in Zhengzhou,Zhengzhou University,Zhengzhou 450001,China
    2 College of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450001,China
  • Received:2025-03-28 Revised:2025-06-24 Published:2026-02-10
  • About author:HAN Lin,born in 1978,Ph.D,professor,Ph.D supervisor,is a senior member of CCF(No.16416M).His main research interests include high-performance computing,advanced compilation techniques,program optimization and indigenous innovation of key technologies.
    NIE Kai,born in 1997,Ph.D,lecturer,master’s supervisor.His main research interests include advanced compilation technologies and high-performance compu-ting.
  • Supported by:
    Major Science and Technology Special Projects in Henan Province(241100210100,221100210600),Key Projects of Science and Technology of Henan Province(242102211094) and National Key Research and Development Program of China(2023YFB3002505).

PDF (PC)

77

Abstract: Loop splitting is a key compiler optimization technique that can reduce control overhead,improve instruction pipeline efficiency,and create opportunities for subsequent optimization.To address the limited applicability of the existing loop splitting strategy in GCC compiler,an improved algorithm is proposed based on static single assignment form.It categorizes condition variables by their positions in PHI nodes into loop-header PHI node condition variables and merge PHI node condition variables.For these two types of condition variables,the algorithm performs semi-invariance analysis separately and selects partitioning points accordingly,thereby achieving more general loop splitting optimization.The algorithm is implemented in the Sunway GCCcompi-ler.Experimental results on the new-generation Sunway processor platform show that,compared to the original algorithm,the proposed algorithm improves the performance of the 470.lbm benchmark in SPEC CPU 2006 test suite by 8.8%,and the 620.omnetpp_s benchmark in SPEC CPU 2017 test suite by 4.3%.This method expands the scope of optimizable loop structures,improves the optimization efficiency of the Sunway GCC compiler,and can provide assistance for the basic software ecosystem construction of the domestic Sunway platform.

Key words: GCC compiler, Loop optimization, Loop splitting, Static single assignment, Control dependence

CLC Number: 

  • TP311
[1]SENGUPTA A,BHADAURIA S.Intellectual property coreprotection of control data flow graphs using robust watermar-king during behavioural synthesis based on user resource constraint and loop unrolling factor[J].Electronics Letters,2016,52(6):439-441.
[2]ZIRAKSIMA M,LOTFI S,LZADKH H.Using an evolutionary approach based on shortest common supersequence problem for loop fusion[J].Soft Computing,2019,24(10):1-22.
[3]BIELECKI W,PALKOWSKI M.Space-time loop tiling for dynamic programming codes[J].Electronics,2021,10(18):2233.
[4]GAO W,XU J L,SUN H H,et al.Research on loop optimization techniques for SIMD vectorization[J].Journal of Information Engineering University,2016,17(4):496-503.
[5]TSIRAMUA S,MELADZE H,DAVITASHVILI T,et al.Stru-ctural Analysis of Multi-Core Processor and Reliability Evaluation Model[J].Mathematics,2025,13(3):515.
[6]YANG X C,JIANG J,MA X D,et al.Program Slicing Technique Based on GCC Key Variable Data Flow Analysis Algorithm[J].Computer Engineering and Applications,2017,53(24):40-54.
[7]WANG S D,YIN W J,DONG Y K,et al.Data Flow Analysis for Sequential Storage Structures[J].Journal of Software,2020,31(5):1276-1293.
[8]GAO W,LI Y Y,SUN H H,et al.An Improved Control Flow SIMD Vectorization Method[J].Journal of Software,2017,28(8):2046-2063.
[9]SWEET Y,CHAUDHARY P.An efficient branch predictor for improved accuracy of instruction level parallelism[J].The Journal of Supercomputing,2021,77(10):1-23.
[10]ROGERS S,SLYCORD J,RAHEJA R,et al.Scalable LLVM-Based Accelerator Modeling in gem5[J].Computer Architecture Letters,2019,18(1):18-21.
[11]JEONG S J.A loop splitting method for single loops with non-uniform dependences[J].Journal in computer virology:An independant journal dedicated to computer viral and antiviral technologies,2014,10(2):137-143.
[12]LIU J,WICKERSON J,CONSTANTINIDES G.Loop splitting for efficient pipelining in high-level synthesis[C]//IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines(FCCM).IEEE,2016:72-79.
[13]XU R F,ZHAO Z Y,SHENG W G,et al.An Imperfect LoopMapping Method for Coarse-Grained Reconfigurable Architec-tures[J].Microelectronics & Computer,2018,35(7):50-57.
[14]YANG X.Advanced Loop Optimization Based on Tree-SSAFramework[J].Computer Knowledge and Technology,2009,5(24):7035-7037.
[15]DONG Y S,LI C J,XU Y.Implementation and Evaluation of Loop Array Prefetching Optimization in GCC Compiler[J].Computer Engineering and Applications,2016,52(6):19-25.
[16]BERG D V J,HAGA H.Matching Source Code Using Abstract Syntax Trees in Version Control Systems[J].Journal of Software Engineering and Applications,2018,11(6):318-340.
[17]COLOMBET Q,BRANDNER F,DARTE A.Studying Optimal Spilling in the Light of SSA[J].ACM Transactions on Architecture and Code Optimization(TACO),2015,11(4):1-26.
[18]CHEN M Y.Research on Loop Distribution Techniques forSunway GCC Compilation System[D].Zhengzhou:Zhengzhou University,2021.
[19]HAN L,XU J L,LI Y Y,et al.Loop Distribution and Fusion Optimization for Partial Vectorization[J].Computer Science,2017,44(2):70-81.
[20]GAO W,HAN L,ZHAO R C,et al.Vector Parallelism-Guided Loop SIMD Vectorization Method[J].Journal of Software,2017,28(4):925-939.
[21]LIM I H.An approach to comparing control clow graphs based on basic block matching[J].Indian Journal of Computer Science and Engineering,2020,11(3):289-296.
[22]CYTRON R,FERRANTE J,ROSEN B K,et al.Efficientlycomputing static single assignment form and the control dependence graph[J].ACM Transactions on Programming Languages and Systems,1991,13(4):451-490.
[23]XIE X F,CHEN B H,ZOU L,et al.Automatic Loop Summarization via Path Dependency Analysis[J].IEEE Transactions on Software Engineering,2019,45(6):537-557.
[1] LIU Mengzhen, ZHOU Qinglei, HAN Lin, NIE Kai, LI Haoran, CHEN Mengyao, LIU Haohao. Research on Automatic Vectorization Benefit Evaluation Model Based on Particle SwarmAlgorithm [J]. Computer Science, 2025, 52(7): 248-254.
[2] WANG Zhen, NIE Kai, HAN Lin. Auto-vectorization Cost Model Based on Instruction MKS [J]. Computer Science, 2024, 51(4): 78-85.
[3] HOU Yong-sheng,ZHAO Rong-cai,HUANG Lei and HAN Lin. Research on SIMD-oriented Loop Optimizations [J]. Computer Science, 2014, 41(5): 27-32.
[4] YI Guo-Hong ,LU Yan-Sheng （Department of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074）. [J]. Computer Science, 2007, 34(1): 281-284.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.