计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 561-566.doi: 10.11896/JsJkx.191100017

• 交叉&应用 • 上一篇    下一篇

基于LLVM编译器的节点融合优化方法

胡浩1, 沈莉2, 3, 周清雷1, 巩令钦1   

  1. 1 郑州大学信息工程学院 郑州 450000;
    2 中国科学技术大学计算机科学与技术学院 合肥 230000;
    3 无锡江南计算技术研究所 江苏 无锡 214083
  • 发布日期:2020-07-07
  • 通讯作者: 胡浩(witstorm@163.com)
  • 基金资助:
    国家自然科学基金(61572444)

Node Fusion Optimization Method Based on LLVM Compiler

HU Hao1, SHEN Li2, 3, ZHOU Qing-lei1 and GONG Ling-qin1   

  1. 1 School of Information Engineering,Zhengzhou University,Zhengzhou 450000,China
    2 School of Computer Science and Technology,University of Science and Technology of China,Hefei 230000,China
    3 Wuxi Jiangnan Computer Technology Research Institute,Wuxi,Jiangsu 214083,China
  • Published:2020-07-07
  • About author:OSMIALOWSKI P.How The Flang Frontend Works:Introduction to the interior of the Open-Source Fortran frontend for LLVM//Proceedings of the Fourth Workshop on the LLVM Compiler Infrastructure in HPC.ACM, 2017:1.
    HU Hao, born in 1994, postgraduate.His main research interests include information security.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61572444).

摘要: LLVM是以C++编写的架构编译器的框架系统,支持多后端和交叉编译,用于优化程序的编译时间、链接时间、运行时间和空闲时间。节点融合是一种简单有效的优化方法,其基本思想为将多个节点优化为一个高效的融合节点,减少诸如指令、寄存器、时钟周期和访存等开销,以达到减少程序运行时间,提升访存效率等目的。为了提升LLVM编译器的性能,文中在LLVM编译流程的中间表示阶段和DAG合并阶段、指令选择阶段提出了节点融合优化方法。在国产平台申威处理器下,以CLANG和FLANG为编译器前端,LLVM为编译器后端,基于SPEC CPU2006测试集进行了评估,实验结果表明,节点融合优化有利于提高编译器性能和减少程序运行时间,优化后最大加速比为1.59,平均加速比为1.13。

关键词: DAG合并, LLVM, 国产平台, 节点融合, 指令选择, 中间表示

Abstract: LLVM is a framework system of architecture compiler written in C++,which is a cross-compiler that supports multiple back-ends.It can optimize program compilation time,link time,run time,and idle time.Node fusion is a simple and effective optimization method.The basic idea is to optimize multiple nodes into an efficient fusion node.This optimization can reduce overhead such as instructions,registers,clock cycles,memory access,so as to reduce program running time and improve memory access efficiency.In order to improve the performance of the LLVM compiler,node fusion optimization algorithm is proposed for the LLVM compiler in the intermediate presentation phase,DAG combine phase and instruction selection phase.Under the domestic platform Sunway processor,with CLANG and FLANG as the front end and LLVM as the back end of the compiler,LLVM is evaluated based on the SPEC CPU2006 test set.The results show that node fusion optimization is beneficial to improve compiler performance and reduce program running time.The optimized maximum speedup ratio is 1.59 and the average speedup ratio is 1.13.

Key words: DAG combine, Domestic platform, Instruction selection, Intermediate representation, LLVM, Node fusion

中图分类号: 

  • TP311
[1] LATTNER C.LLVM and Clang:Next generation compiler technology//The BSD Conference.2008,5.
[2] LATTNER C,ADVE V.LLVM:A compilation framework for lifelong program analysis & transformation//Proceedings of the International Symposium on Code Generation and Optimization:Feedback-directed and Runtime Optimization.IEEE Computer Society,2004:75.
[3] ZHAO J,NAGARAKATTE S,MARTIN M M K,et al.Formalizing the LLVM intermediate representation for verified program transformations//Acm Sigplan Notices.ACM,2012,47(1):427-440.
[4] PANDEY M,SARDA S.LLVM cookbook.Packt Publishing Ltd.,2015.
[5] FRASER C W.A compact,machine-independent peephole optimizer//Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages.ACM,1979:1-6.
[6] SPRADLING C D.SPEC CPU2006 benchmark tools.ACM SIGARCH Computer Architecture News,2007,35(1):130-134.
[7] GUOBIN Y E.Getting to know the LLVM compiler.Master’s thesis,The University of Edinburgh,2011.
[8] LATTNER C.Introduction to the llvm compiler infrastructure//Itanium Conference and Expo.2006.
[9] PANDEY M,SARDA S.LLVM cookbook.Packt Publising Ltd,2015.
[10] CYTRON R,FERRANTE J,ROSEN B K,et al.Efficiently computing static single assignment form and the control dependence graph.ACM Transactions on Programming Languages and Systems (TOPLAS),1991,13(4):451-490.
[11] CALLAHAN D,COOPER K D,KENNEDY K,et al.Interprocedural constant propagation//ACM SIGPLAN Notices.ACM,1986,21(7):152-161.
[12] COCKE J.Global common subexpression elimination.ACM Sigplan Notices,1970,5(7):20-24.
[13] LATTNER C,ADVE V.The LLVM instruction set and compi-lation strategy.CS Dept.,Univ.of Illinois at Urbana-Champaign,Tech.Report UIUCDCS,2002.
[14] HOKENEK E,MONTOYE R K,COOK P W.Second-generation RISC floating point with multiply-add fused.IEEE Journal of Solid-State Circuits,1990,25(5):1207-1213.
[1] 刘聃, 郭绍忠, 郝江伟, 许瑾晨.
基于SIMD扩展部件的长向量超越函数实现方法
Implementation of Transcendental Functions on Vectors Based on SIMD Extensions
计算机科学, 2021, 48(6): 26-33. https://doi.org/10.11896/jsjkx.200400007
[2] 陈涛, 舒辉, 熊小兵.
通用代码Shell化技术研究
Study of Universal Shellcode Generation Technology
计算机科学, 2021, 48(4): 288-294. https://doi.org/10.11896/jsjkx.200300151
[3] 胡伟方, 陈云, 李颖颖, 商建东.
基于数据重用分析的多面体循环合并策略
Loop Fusion Strategy Based on Data Reuse Analysis in Polyhedral Compilation
计算机科学, 2021, 48(12): 49-58. https://doi.org/10.11896/jsjkx.210200071
[4] 张其良,张昱,周坤.
CCodeExtractor:一种针对C程序自动化的函数提取方法
CCodeExtractor:Automatic Approach of Function Extraction for C Programs
计算机科学, 2017, 44(4): 16-20. https://doi.org/10.11896/j.issn.1002-137X.2017.04.004
[5] 王涛,韩兰胜,付才,邹德清,刘铭.
软件漏洞静态检测模型及检测框架
Static Detection Model and Framework for Software Vulnerability
计算机科学, 2016, 43(5): 80-86. https://doi.org/10.11896/j.issn.1002-137X.2016.05.015
[6] 陈向,沈立,李家文.
SIMD数据置换操作的自动生成和优化
Automatic Data Permutation Generation and Optimization for SIMD Devices
计算机科学, 2011, 38(5): 290-294.
[7] 田硕,梁洪亮.
二进制程序安全缺陷静态分析方法的研究综述
Survey of Static Analysis Methods for Binary Code Vulnerability
计算机科学, 2009, 36(7): 8-14. https://doi.org/10.11896/j.issn.1002-137X.2009.07.002
[8] 杨书鑫 薛丽萍 张兆庆.
代码生成阶段的循环不变量外提

计算机科学, 2004, 31(11): 158-161.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!