Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (6): 82-87.doi: 10.11896/jsjkx.240800128

• High Performance Computing • Previous Articles     Next Articles

Pre-selection Optimization for Spill Heuristic on Shenwei Platform

CAI Chunhao, LIANG Shuping, JIANG Jun, SHAO Ningyuan   

  1. Wuxi Institute of Advanced Technology,Wuxi,Jiangsu 214122,China
  • Received:2024-08-23 Revised:2024-10-16 Online:2025-06-15 Published:2025-06-11
  • About author:CAI Chunhao,born in 1997,master.His main research interests include compilation principle,advanced language virtual machine and JIT compilation.
    JIANG Jun,born in 1980,master.His main research interests include compilation design and optimization,architecture oriented performance analysis and optimization,and so on.
  • Supported by:
    Key Project of the Ministry of Science and Technology(GG20210701).

PDF (PC)

94

Abstract: The C2 just-in-time compiler implemented on the SWJDK allocates registers according to the graph coloring register allocation algorithm.The just-in-time compiler ignores the characteristics of the SW processor when allocating registers,which results in excessive memory access codes.In order toget the most out of SW processor,this paper proposes a compilation optimization algorithm.The optimization algorithm is based on the graph coloring register allocation algorithm.And the spill strategy is adjusted based on a priori assumptions about the characteristics of registers representing special information on the SW server.The proposed algorithm has been implemented in SWJDK.The optimization of the algorithm also has been verified based on the benchmark SPECjbb2015 and SPECjvm2008.After optimization,the max-jOPS of SPECjbb2015 increases by 4.20% and critical-jOPS of SPECjbb2015 increases by 5.98%.The SPECjvm2008 increases by 2.02%。

Key words: Register allocation via graph coloring, Memory addressing, Spill code, Compiler optimization

CLC Number: 

  • TP314
[1]ULRICH D.What every programmer should know about memory[EB/OL].https://people.freebsd.org/~lstewart/articles/cpumemory.pdf.
[2]COOPER K D,TORCZON L.Engineering a compiler(2nd ed.)[M].Beijing:Posts & Telecom Press,2020:499-527.
[3]ALFRED V A,MONICA S L,JEFFREY D U.Compilers Principles,Techniques & Tools[M].Singapore:Pearson Education,2007:237-265.
[4]BRIGGS P,COOPER K,TORCZON L.Improvements to Graph Coloring Register Allocation[J].ACM Transactions on Programming Languages and Systems,1994,16(3):428-455.
[5]CHAITIN G J.Register allocation & spilling via graph coloring[J].ACM SIGPLAN Notices,1982,17(6):98-101.
[6]KEMPE A B.On the geographical problem of the four colours[J].American Journal of Mathematics,1879,2(3):193-200.
[7]BRIGGS P,COOPER K D,KENNEDY K,et al.Coloring heuristics for register allocation [C]//Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation.New York:ACM,1989:275-284.
[8]SPECjbb2015 Benchmark User Guide [EB/OL].(2017-05-25) [2024-04-14].https://www.spec.org/jbb2015/docs/userguide.pdf.
[9]BERNSTEIN D,GOLUMBIC M,MANSOUR Y,et al.Spillcode minimization techniques for optimizing compliers[J].ACM SIGPLAN Notices,1989,24(7):258-263.
[10]BRIGGS P,COOPER K D,TORCZON L.Rematerialization[C]//Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation.1992:311-321.
[11]KURLANDER S M,FISCHER C N.Zero-cost range splitting[C]//Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation.1994:257-265.
[12]KOSEKI A,KOMATSU H,NAKATANI T.Spill code minimization by spill code motion[C]//2003 12th International Confe-rence on Parallel Architectures and Compilation Techniques.IEEE,2003:125-134.
[13]BERGNER P,DAHL P,ENGEBRETSEN D,et al.Spill codeminimization via interference region spilling[J].ACM SIGPLAN Notices,1997,32(5):287-295.
[14]SPECjvm2008 User's Guide [EB/OL].(2008-04-16) [2024-04-14].https://www.spec.org/jvm2008/docs/UserGuide.html.
[15]NARIHIRO N.Tetteikaibou g1gc algorithm hen[M].Beijing:Posts & Telecom Press,2016:155-173.
[16]CHAITIN G.Register allocation and spilling via graph coloring[J].ACMSIGPLAN Notices,2004,39(4):66-74.
[17]BRIAN G,JOSHUA B,DOUG L.Java concurrency in practice [M].Beijing:China Machine Press,2012:128-135.
[18]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.
[19]CLICK C.From quads to graphs:An intermediate representation's journey:CRPC-TR93366-S [R].Technical Report Center for Resesearch on Parallel Computation,Rice University,1993.
[20]GEORGE L,APPEL A W.Iterated register coalescing[J].ACMTransactions on Programming Languages and Systems,1996,18(3):300-324.
[21]JOHANSSON E,SAGONAS K.Linear scan register allocation in a high-performance erlang compiler[C]//International Symposium on Practical Aspects of Declarative Languages.Berlin:Springer,2001:101-119.
[22]PELEGRI-LLOPART E,GRAHAM S L.Optimal code generation for expression trees:an application burs theory[C]//Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.1988:294-308.
[23]PALECZNY M,VICK C,CLICK C.The Java HotSpotTM server compiler[C]//JavaTM Virtual Machine Research and Technology Symposium(JVM 01).2001.
[24]GALINIER P,HAO J K.Hybrid evolutionary algorithms forgraph coloring[J].Journal of Combinatorial Optimization,1999,3:379-397.
[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] GAO Xiu-wu, HUANG Liang-ming, JIANG Jun. Optimization Method of Streaming Storage Based on GCC Compiler [J]. Computer Science, 2022, 49(11): 76-82.
[3] TANG Zhen, HU Yong-hua, LU Hao-song, WANG Shu-ying. Research on DSP Register Pairs Allocation Algorithm with Weak Assigning Constraints [J]. Computer Science, 2021, 48(6A): 587-595.
[4] 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.
[5] 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.
[6] TIAN Zu-wei,SUN Guang. Research of Compiler Optimization Technology Based on Predicated Code [J]. Computer Science, 2010, 37(5): 130-133.
[7] TANG Wei, WU Cheng-Yong, ZHANG Zhao-Qing （Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100080）. [J]. Computer Science, 2006, 33(4): 250-252.
[8] . [J]. Computer Science, 2006, 33(2): 257-262.
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.