基于LLVM的NiosⅡ处理器后端快速移植及优化
|
摘要
编译器是嵌入式系统研发的基础,快速实现特定硬件平台的嵌入式系统编译器可以大大缩短嵌入式系统研发周期。目前研究人员主要采用GCC编译器后端移植方法来生成嵌入式系统编译器。GCC主要使用RTL描述后端处理器,但是RTL抽象复杂不便于编写和阅读。同时GCC复杂的软件结构以及后端移植文档缺乏导致GCC后端移植方法无法满足嵌入式系统研发周期短的要求。如何快速实现编译器后端移植仍然是嵌入式系统研究的热点。
首先本文采用新的编译器架构低级虚拟机(Low Level Virtual Machine, LLVM),通过移植NiosⅡ嵌入式处理器来分析LLVM快速后端移植架构。采用LLVM后端移植架构中的TableGen描述NiosⅡ基本体系结构,使用完备的LLVM C++函数库来描述复杂或特殊的操作。TableGen与LLVM C++函数库配合使用,实现LLVM编译器对NiosⅡ处理器后端的支持。实验结果表明与GCC后端移植方法相比,基于LLVM快速后端移植方法大大减少了源代码量及无需模仿已有的处理器,大大节省了后端移植时间。
其次本文研究并实现后端描述辅助系统,以加快目标处理器后端描述速度。针对LLVM后端移植架构中存在大量繁杂且重复的文本TableGen描述,本文设计人性化、可视化的后端描述辅助系统。输入少量目标处理器后端信息,通过后端描述辅助系统快速生成相应的TableGen描述文件。
最后本文以纸张计数系统为出发点,鉴于纸张图像处理的运算量大和循环数目多的特点,研究并实现LLVM编译器循环优化功能,并对该系统进行循环优化。通过实验表明经过LLVM编译器的循环优化,纸张计数系统的图像数据处理速度提高了10.1%-14.6%。
Compiler is the basis of embedded systems development. Implementing quickly embedded systems compiler of hardware platform-specific can greatly shorten the development period of embedded systems. Currently research and development personnel mainly use the method of GCC compiler backend-porting to generate embedded systems compiler. GCC mainly uses Register Transfer Language (RTL) to describe backend processor, but RTL is too abstract and complex to write and read. At the same time, complex software architecture of GCC and the lack of backend-porting documents cause that the method of GCC compiler backend-porting can not meet the requirements of the short development period of embedded system. How to quickly implement compiler backend-porting is still a hot research.
Firstly, this thesis adopts a new compiler framework which is called Low Level Virtual Machine (LLVM), and analyses the backend-porting architecture of LLVM by porting NiosII embedded processor. It uses TableGen in backend-porting architecture to describe basic architecture of NiosII processor, and uses complete LLVM C++library to describe the complex or special operations. The match usage of TableGen and LLVM C++library realizes LLVM compiler to support NiosII backend processor. The experimental results indicate that backend-porting method which based on LLVM reduces the source lines of code (SLOC) and does not need to imitate the existing processors, and compared with backend-porting method based on GCC, the method greatly shortens the backend-porting period.
Secondly, in order to accelerate the backend-description speed of target processor, this thesis studies and implements the backend-description assistant system. Ascribe the existence of a great number of complex and repeated TableGen description which are text format in LLVM backend-porting architecture, this thesis designs a humanization and visualization backend-description assistant system. We input a few backend information of target processor, and the backend-description assistant system quickly generates the corresponding TableGen description files.
At last, this thesis takes paper-counting system as a starting point, in view of the heavy computation and the large loop count features of image-processing for paper, this thesis studies and implements the loop optimization function of LLVM compiler, and optimizes paper-counting system with it. The experimental results indicate that the image-processing speed of paper-counting system is improved by 10.1%～14.6%.
首先本文采用新的编译器架构低级虚拟机(Low Level Virtual Machine, LLVM),通过移植NiosⅡ嵌入式处理器来分析LLVM快速后端移植架构。采用LLVM后端移植架构中的TableGen描述NiosⅡ基本体系结构,使用完备的LLVM C++函数库来描述复杂或特殊的操作。TableGen与LLVM C++函数库配合使用,实现LLVM编译器对NiosⅡ处理器后端的支持。实验结果表明与GCC后端移植方法相比,基于LLVM快速后端移植方法大大减少了源代码量及无需模仿已有的处理器,大大节省了后端移植时间。
其次本文研究并实现后端描述辅助系统,以加快目标处理器后端描述速度。针对LLVM后端移植架构中存在大量繁杂且重复的文本TableGen描述,本文设计人性化、可视化的后端描述辅助系统。输入少量目标处理器后端信息,通过后端描述辅助系统快速生成相应的TableGen描述文件。
最后本文以纸张计数系统为出发点,鉴于纸张图像处理的运算量大和循环数目多的特点,研究并实现LLVM编译器循环优化功能,并对该系统进行循环优化。通过实验表明经过LLVM编译器的循环优化,纸张计数系统的图像数据处理速度提高了10.1%-14.6%。
Compiler is the basis of embedded systems development. Implementing quickly embedded systems compiler of hardware platform-specific can greatly shorten the development period of embedded systems. Currently research and development personnel mainly use the method of GCC compiler backend-porting to generate embedded systems compiler. GCC mainly uses Register Transfer Language (RTL) to describe backend processor, but RTL is too abstract and complex to write and read. At the same time, complex software architecture of GCC and the lack of backend-porting documents cause that the method of GCC compiler backend-porting can not meet the requirements of the short development period of embedded system. How to quickly implement compiler backend-porting is still a hot research.
Firstly, this thesis adopts a new compiler framework which is called Low Level Virtual Machine (LLVM), and analyses the backend-porting architecture of LLVM by porting NiosII embedded processor. It uses TableGen in backend-porting architecture to describe basic architecture of NiosII processor, and uses complete LLVM C++library to describe the complex or special operations. The match usage of TableGen and LLVM C++library realizes LLVM compiler to support NiosII backend processor. The experimental results indicate that backend-porting method which based on LLVM reduces the source lines of code (SLOC) and does not need to imitate the existing processors, and compared with backend-porting method based on GCC, the method greatly shortens the backend-porting period.
Secondly, in order to accelerate the backend-description speed of target processor, this thesis studies and implements the backend-description assistant system. Ascribe the existence of a great number of complex and repeated TableGen description which are text format in LLVM backend-porting architecture, this thesis designs a humanization and visualization backend-description assistant system. We input a few backend information of target processor, and the backend-description assistant system quickly generates the corresponding TableGen description files.
At last, this thesis takes paper-counting system as a starting point, in view of the heavy computation and the large loop count features of image-processing for paper, this thesis studies and implements the loop optimization function of LLVM compiler, and optimizes paper-counting system with it. The experimental results indicate that the image-processing speed of paper-counting system is improved by 10.1%～14.6%.
引文
[1]崔莹,辛晓晨等.基于UEFI的嵌入式驱动程序的开发研究[J].计算机工程与设计,2010,31(10)：2384-2387.
[2]The GNU Operationg System.GCC internal manual.http://www.gnu.org.2008. 05.16.
[3]任小西,李仁发等.一种基于多目标设计方法的嵌入式编译器技术[J].计算机应用,2004,24(2)：165-167.
[4]琚小明.面向媒体处理器可重定目标编译器设计研究[D].杭州：浙江大学,2004.
[5]朱少波.基于GCC开放C编译器的研究与实践[D].杭州：浙江大学,2003.
[6]蔡杰.GCC编译系统结构分析与后端移植实践[D].杭州：浙江大学,2004.
[7]苏斐琦.交叉编译系统的研究与实现[D].杭州：浙江大学,2003.
[8]冯钢.基于GCC的嵌入式系统编译器研究与开发[D].杭州：浙江大学,2004.
[9]杨川龙.基于GCC的嵌入式系统编译器的研究与开发[D].哈尔滨：哈尔滨工程大学,2006.
[10]裴晓航.基于龙芯处理器的GCC移植与优化[D].合肥：中国科学技术大学,2010.
[11]董峻峰.基于龙芯2号结构特征对GCC的分析与优化[D].北京：中国科学研究生院,2006.
[12]任小西.嵌入式系统编译器的快速生成方法研究[D].长沙：湖南大学,2004.
[13]曾楠.可重定向目标编译器辅助系统设计实现[D].厦门：厦门大学,2006.
[14]Jan Parthey.Porting the GCC-Backend to a VLIW-Architecture[D]. Chemnitz:Chemnitz University of Technology,2004.
[15]Jan Hubicka.Porting gcc to the amd64 architecture [D]. Prague:Charles University,2003.
[16]Hans-Peter Nilsson. Porting GCC for Dunces. http://gcc.gnu.org.2000.5.21.
[17]Hartmut E. Penner.Porting GCC to the IBM S/390 platform[C]. GCC Developers Summit, Ottawa,2003:195-212.
[18]Parthey J, Baumgartl R.Porting GCC to the TMS320-C6000 DSP Architecture[C]. Proceedings of GSPx'04, Santa Clara,2004:1-6.
[19]E. S.T. Fernandes. Microarchitecture modelling through ADL[C]. Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, California,1988:100-104.
[20]Prabhat Mishra, Aviral Shrivastava, Nikil Dutt. Architecture description language (ADL)-driven software toolkit generation for architectural exploration of programmable SOCs[C].ACM Transactions on Design Automation of Electronic Systems (TODAES), Florida,2006:626-658.
[21]Mishra, P. and Dutt, N. Architecture description languages for programmable embedded systems [J]. IEEE-Proceedings Comput Digital Techniques, 2005,152(3):285-297.
[22]郑建丹,张广泉.软件体系结构描述语言ADL[J].重庆师范学院学报(自然科学版),2000,17(4)：4-8.
[23]魏亮辉,李曦等.基于XP-ADL的重定向编译器后端设计[J].计算机辅助工程,2007,16(1)：60-64.
[24]徐步荣,李曦等.一种基于可重定向编译器的功耗优化框架[J].计算机仿真,2007,24(04)：306-309.
[25]林立峰.支援指令结构描述语言与GCC的结合技术[D].新竹：国立清华大学,2004.
[26]江盈宏ASIP的GCC移植工具[D].台北：国立台湾大学,2005.
[27]ZHU Xue-Yang, TANG Zhi-Song. A Temporal Logic-Based Software Archite-cture Description Language XYZ/ADL[J]. Journal of Software,2003,14(04):713-720.
[28]Schliebusch, O.,Hoffmann, A. Architecture implementation using the machine description language LISA[C]. Design Automation Conference, Bangalore,2002: 239-244.
[29]Chris Lattner, Vikram Adve. LLVM:A Compilation Framework for Lifelong Program Analysis & Transformation[J], Proceedings of the international symposium on Code generation and optimization, California,2004:75-92.
[30]Christoph Erhardt.Design and Implementation of a TriCore Backend for the LLVM Compiler Framework[D]. Friedrich:Friedrich-Alexander-University, 2009.
[31]C Lattner. LLVM:An Infrastructure for Multi-Stage Optimization[D]. Urbana-Champaign:University of Illinois,2002.
[32]David Anthony Terei.Low Level Virtual Machine for Glasgow Haskell Compiler[D]. Sydney:The University of New South Wales,2009.
[33]C Lattner.macroscopic data structure analysis and optimization[D]. Urbana-Champaign:University of Illinois,2005.
[34]Anders Alexandersson.RubyComp-A Ruby-to-LLVM Compiler Prototype[D]. Uddevalla:University of Uddevalla,2004.
[35]J Gorin. LLVM-based and scalable MPEG-RVC decoder[J]. JOURNAL OF REAL-TIME IMAGE PROCESSING,2010,6(1):59-70.
[36]BaojianHua, BoXu. Explicitly Typed Static Single-Assignment Form[C],2010 2nd International Conforence on Education Technology and Computer (ICETC), Shanghai, China,2010:43-47.
[37]Tilmann Scheller.Retargeting a C compiler to the HAPRA/FAPRA architecture[D]. Stuttgart:University of Stuttgart,2010.
[38]Vikram Adve,Chris Lattner. LLVA:A Low-level Virtual Instruction Set Architecture [C], Proceedings of the 36th annual ACM/IEEE international symposium on Microarchitecture, California,2003:205-216.
[39]Mattias Lundell.LLVM back-end for the Timber compiler[D]. Gothenburg:Chalmers University of Technology,2010.
[40]董峰LLVM编译系统结构分析与后端移植[D].上海：上海交通大学,2007.
[41]Lakulish Antani.Tricore Port for GCC[D].India:Indian Institute of Technology,2009.
[42]Alexandru Turjan, Dmitry Cheresiz. Porting GCC to Exposed Pipeline VLIW Processors[C],2009 GCC Developer's summit, Montreal, Quebec, Canada,2009:7-19.
[43]林凯伟.移植GCC的系统方法之研究[D].嘉义：国立中正大学,2008.
[44]Jan Parthey. Porting GCC to the TMS320-C6000 DSP Architecture[C], Proceedings of GSPx'04, Santa Clara,2004:20-26.
[45]Roel Trienekens. Porting the GCC Compiler to a VLIW Vector Processor[D]. Delft:Delft University of Technology,2009.
[46]王超.GCC编译器到Trimedia移植的研究和实现[D].上海：上海交通大学,2004.
[47]Jonas Paulsson. Retargeting GCC for a DSP architecture[D]. Scania:Lund University,2010.
[48]S.Kempf.Implementierung eines LLVM-Backends fur Jackal[D].Erlangen Nuremberg:Friedrich Alexander University,2008.
[49]Hans Wennborg. Emulator Speed-up Using JIT and LLVM[D]. Scania:LUND UNIVERSITY.2010.
[50]李兰英等Nios II嵌入式软核SOPC设计原理及应用[M].北京：北京航空航天大学出版社,2006.
[51]卢德良,周学功NIOSII处理器中定制指令的设计与实现[J].计算机应用与软件,2007,24(12)：3-5.
[52]蔡伟纲,Nios II软件架构解析[M].西安：西安电子科技大学出版社,2007.
[53]Alex K. Jones, Raymond Hoare. An FPGA-based VLIW processor with custom hardware execution[C], FPGA'05 Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, New York,2005:107-117.
[54]李顺新.基于纹理的纸张计数研究[D].武汉：武汉科技大学,2007.
[55]郑光,陈幼平.基于数学形态学的纸张计数算法的研究[J].微计算机信息,2007,23(7)：214-216.
[56]WU Yanxia, GU Guochang.Application-Specific Compiler for Reconfigur-able Architecture ASCRA[J]. Journal of Frontiers of Computer Science and Technology,2011,5(3):257-279.
[57]Denis Barthou, Sebastien Donadio. Loop Optimization using Hierarchical Compilation and Kernel Decomposition[C], Proceeding CGO'07 Proceedings of the International Symposium on Code Generation and Optimization, Washington,2007:3-16.
[58]N. V. Balashevich, R. Gabasov. Numerical Methods for Open-Loop and Closed-LoopOptimization of Linear Control Systems [J]. Computational Mathematics and Mathematical Physics,2000,40(6):799-819.
[59]Andrew Jeffery.Using the LLVM compiler infrastructure for optimized,asynchronous dynamic translation in Qemu[D]. Adelaide:University of Adelaide,2009.
[60]Adam Husar, Miloslav Trmac. Instruction Selection Patterns Extraction from Architecture Specification Language ISAC[C], Proceedings of the 16th Conference Student EEICT 2010,Brno, CZ,2010:166-170.
[61]OC Anderson.Compiler Optimizations for a Time constrained Environment [D]. Minnesota:Macalester College,2008.
[62]Arjun Jagadeesh Singri.Compile-Time Characterization of Recurrent Patterns in Irregular Computations[D]. Ohio State:The Ohio State University,2010.
[2]The GNU Operationg System.GCC internal manual.http://www.gnu.org.2008. 05.16.
[3]任小西,李仁发等.一种基于多目标设计方法的嵌入式编译器技术[J].计算机应用,2004,24(2)：165-167.
[4]琚小明.面向媒体处理器可重定目标编译器设计研究[D].杭州：浙江大学,2004.
[5]朱少波.基于GCC开放C编译器的研究与实践[D].杭州：浙江大学,2003.
[6]蔡杰.GCC编译系统结构分析与后端移植实践[D].杭州：浙江大学,2004.
[7]苏斐琦.交叉编译系统的研究与实现[D].杭州：浙江大学,2003.
[8]冯钢.基于GCC的嵌入式系统编译器研究与开发[D].杭州：浙江大学,2004.
[9]杨川龙.基于GCC的嵌入式系统编译器的研究与开发[D].哈尔滨：哈尔滨工程大学,2006.
[10]裴晓航.基于龙芯处理器的GCC移植与优化[D].合肥：中国科学技术大学,2010.
[11]董峻峰.基于龙芯2号结构特征对GCC的分析与优化[D].北京：中国科学研究生院,2006.
[12]任小西.嵌入式系统编译器的快速生成方法研究[D].长沙：湖南大学,2004.
[13]曾楠.可重定向目标编译器辅助系统设计实现[D].厦门：厦门大学,2006.
[14]Jan Parthey.Porting the GCC-Backend to a VLIW-Architecture[D]. Chemnitz:Chemnitz University of Technology,2004.
[15]Jan Hubicka.Porting gcc to the amd64 architecture [D]. Prague:Charles University,2003.
[16]Hans-Peter Nilsson. Porting GCC for Dunces. http://gcc.gnu.org.2000.5.21.
[17]Hartmut E. Penner.Porting GCC to the IBM S/390 platform[C]. GCC Developers Summit, Ottawa,2003:195-212.
[18]Parthey J, Baumgartl R.Porting GCC to the TMS320-C6000 DSP Architecture[C]. Proceedings of GSPx'04, Santa Clara,2004:1-6.
[19]E. S.T. Fernandes. Microarchitecture modelling through ADL[C]. Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, California,1988:100-104.
[20]Prabhat Mishra, Aviral Shrivastava, Nikil Dutt. Architecture description language (ADL)-driven software toolkit generation for architectural exploration of programmable SOCs[C].ACM Transactions on Design Automation of Electronic Systems (TODAES), Florida,2006:626-658.
[21]Mishra, P. and Dutt, N. Architecture description languages for programmable embedded systems [J]. IEEE-Proceedings Comput Digital Techniques, 2005,152(3):285-297.
[22]郑建丹,张广泉.软件体系结构描述语言ADL[J].重庆师范学院学报(自然科学版),2000,17(4)：4-8.
[23]魏亮辉,李曦等.基于XP-ADL的重定向编译器后端设计[J].计算机辅助工程,2007,16(1)：60-64.
[24]徐步荣,李曦等.一种基于可重定向编译器的功耗优化框架[J].计算机仿真,2007,24(04)：306-309.
[25]林立峰.支援指令结构描述语言与GCC的结合技术[D].新竹：国立清华大学,2004.
[26]江盈宏ASIP的GCC移植工具[D].台北：国立台湾大学,2005.
[27]ZHU Xue-Yang, TANG Zhi-Song. A Temporal Logic-Based Software Archite-cture Description Language XYZ/ADL[J]. Journal of Software,2003,14(04):713-720.
[28]Schliebusch, O.,Hoffmann, A. Architecture implementation using the machine description language LISA[C]. Design Automation Conference, Bangalore,2002: 239-244.
[29]Chris Lattner, Vikram Adve. LLVM:A Compilation Framework for Lifelong Program Analysis & Transformation[J], Proceedings of the international symposium on Code generation and optimization, California,2004:75-92.
[30]Christoph Erhardt.Design and Implementation of a TriCore Backend for the LLVM Compiler Framework[D]. Friedrich:Friedrich-Alexander-University, 2009.
[31]C Lattner. LLVM:An Infrastructure for Multi-Stage Optimization[D]. Urbana-Champaign:University of Illinois,2002.
[32]David Anthony Terei.Low Level Virtual Machine for Glasgow Haskell Compiler[D]. Sydney:The University of New South Wales,2009.
[33]C Lattner.macroscopic data structure analysis and optimization[D]. Urbana-Champaign:University of Illinois,2005.
[34]Anders Alexandersson.RubyComp-A Ruby-to-LLVM Compiler Prototype[D]. Uddevalla:University of Uddevalla,2004.
[35]J Gorin. LLVM-based and scalable MPEG-RVC decoder[J]. JOURNAL OF REAL-TIME IMAGE PROCESSING,2010,6(1):59-70.
[36]BaojianHua, BoXu. Explicitly Typed Static Single-Assignment Form[C],2010 2nd International Conforence on Education Technology and Computer (ICETC), Shanghai, China,2010:43-47.
[37]Tilmann Scheller.Retargeting a C compiler to the HAPRA/FAPRA architecture[D]. Stuttgart:University of Stuttgart,2010.
[38]Vikram Adve,Chris Lattner. LLVA:A Low-level Virtual Instruction Set Architecture [C], Proceedings of the 36th annual ACM/IEEE international symposium on Microarchitecture, California,2003:205-216.
[39]Mattias Lundell.LLVM back-end for the Timber compiler[D]. Gothenburg:Chalmers University of Technology,2010.
[40]董峰LLVM编译系统结构分析与后端移植[D].上海：上海交通大学,2007.
[41]Lakulish Antani.Tricore Port for GCC[D].India:Indian Institute of Technology,2009.
[42]Alexandru Turjan, Dmitry Cheresiz. Porting GCC to Exposed Pipeline VLIW Processors[C],2009 GCC Developer's summit, Montreal, Quebec, Canada,2009:7-19.
[43]林凯伟.移植GCC的系统方法之研究[D].嘉义：国立中正大学,2008.
[44]Jan Parthey. Porting GCC to the TMS320-C6000 DSP Architecture[C], Proceedings of GSPx'04, Santa Clara,2004:20-26.
[45]Roel Trienekens. Porting the GCC Compiler to a VLIW Vector Processor[D]. Delft:Delft University of Technology,2009.
[46]王超.GCC编译器到Trimedia移植的研究和实现[D].上海：上海交通大学,2004.
[47]Jonas Paulsson. Retargeting GCC for a DSP architecture[D]. Scania:Lund University,2010.
[48]S.Kempf.Implementierung eines LLVM-Backends fur Jackal[D].Erlangen Nuremberg:Friedrich Alexander University,2008.
[49]Hans Wennborg. Emulator Speed-up Using JIT and LLVM[D]. Scania:LUND UNIVERSITY.2010.
[50]李兰英等Nios II嵌入式软核SOPC设计原理及应用[M].北京：北京航空航天大学出版社,2006.
[51]卢德良,周学功NIOSII处理器中定制指令的设计与实现[J].计算机应用与软件,2007,24(12)：3-5.
[52]蔡伟纲,Nios II软件架构解析[M].西安：西安电子科技大学出版社,2007.
[53]Alex K. Jones, Raymond Hoare. An FPGA-based VLIW processor with custom hardware execution[C], FPGA'05 Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, New York,2005:107-117.
[54]李顺新.基于纹理的纸张计数研究[D].武汉：武汉科技大学,2007.
[55]郑光,陈幼平.基于数学形态学的纸张计数算法的研究[J].微计算机信息,2007,23(7)：214-216.
[56]WU Yanxia, GU Guochang.Application-Specific Compiler for Reconfigur-able Architecture ASCRA[J]. Journal of Frontiers of Computer Science and Technology,2011,5(3):257-279.
[57]Denis Barthou, Sebastien Donadio. Loop Optimization using Hierarchical Compilation and Kernel Decomposition[C], Proceeding CGO'07 Proceedings of the International Symposium on Code Generation and Optimization, Washington,2007:3-16.
[58]N. V. Balashevich, R. Gabasov. Numerical Methods for Open-Loop and Closed-LoopOptimization of Linear Control Systems [J]. Computational Mathematics and Mathematical Physics,2000,40(6):799-819.
[59]Andrew Jeffery.Using the LLVM compiler infrastructure for optimized,asynchronous dynamic translation in Qemu[D]. Adelaide:University of Adelaide,2009.
[60]Adam Husar, Miloslav Trmac. Instruction Selection Patterns Extraction from Architecture Specification Language ISAC[C], Proceedings of the 16th Conference Student EEICT 2010,Brno, CZ,2010:166-170.
[61]OC Anderson.Compiler Optimizations for a Time constrained Environment [D]. Minnesota:Macalester College,2008.
[62]Arjun Jagadeesh Singri.Compile-Time Characterization of Recurrent Patterns in Irregular Computations[D]. Ohio State:The Ohio State University,2010.