第 3 章 编译系统 ..3.1编译系统概述 第一台计算机出现在20 世纪40 年代,它使用由0、1序列组成的机器语言 编程,这个序列明确地告诉计算机以什么样的顺序执行哪些技术。人们就开始 了机器语言的程序设计:指定数据区编制一条条指令。由于任何人也无法记住 并自如地编排二进制码(只有1和0的数字串), 所以用八进制、十六进制数写程 序,输入后转换为二进制。因此,要在智能芯片上运行智能算法,需要先把开发 者的高级语言编译成汇编指令,再通过汇编器最终生成二进制机器码,才能使 程序在芯片上运行,在这个过程中主要是靠编译器来完成。 机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指 令集合,如图3. 1所示是一个机器语言例子。 图3.机器语言 1 机器语言的缺点是可读性很差,难以理解。编程人员要首先熟记所用计算 机的全部指令代码和代码的含义,编程困难并且效率低,缺少移植性。不同型 号的计算机其机器语言是不同的。 汇编语言用字母和数字表示对应的0、1串指令及数据。如用“MOVA, 16”表示“0000,0000,00000010000”;汇编语言和机器语言一一对应,比机器语 言可读性好、编程效率高、调试性好。但汇编语言仍不具有移植性,且与人类语 言差异很大。 因此,计算机公司提出了多种高级语言,从而便于开发人员开发程序,常见 的开发语言有C、C++、Python和Java等。而如何把高级语言对应到汇编语言 和机器语言这些低级语言,就需要编译器来完成。 编译器可以把高级语言编译成目标文件,并通过连接器把多个目标文件连 接起来,从而产生出可执行文件,2所示。 如图3. 第3章编译系统45 图3.2编译器产生出可执行文件 ..3.2编译器 3.2.1编译器流程说明 高级语言编译生成可以在芯片上运行二进制机器码的过程如图3.3所示。 图3.编译器流程图 3 (1)编译器(Compiler):将源语言翻译成目标语言。重要任务是在翻译过程中发现 源语言中存在的错误。相比于解释器,目标语言执行的速度快。 编译器逐行扫描高级语言程序源程序,编译的过程如下。 ①词法分析(LexicalAnalysis)。识别关键字、字面量、标识符(变量名、数据名)、运 算符、注释行(给人看的,一般不处理)、特殊符号(续行、语句结束、数组)等6类符号,分别 归类等待处理。 ②语法分析(SyntaxAnalysis)。一个语句看作一串记号(Token)流,由语法分析器 进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部 46智能系统及其应用 格式保存,否则报错。直至检查完整个程序。 ③语义分析(SemanticAnalysis)。语义分析器对各句子的语法做检查:运算符两边 类型是否相兼容;该做哪些类型转换(例如,实数向整数赋值要“取整”);控制转移是否到 不该去的地方;是否有重名或者使语义含糊的记号,等等。如果有错误,则转出错处理,否 则可以生成执行代码。 ④中间代码生成。中间代码是向目标码过渡的一种编码,其形式尽可能和机器的汇 编语言相似,以便下一步的代码生成。但中间码不涉及具体机器的操作码和地址码。采 用中间码的好处是可以在中间码上做优化。 ⑤优化。对中间码程序做局部优化和全局(整个程序)优化,目的是使运行更快,占 用空间最小。局部优化是合并冗余操作,简化计算,例如x:=0可用一条“清零”指令替 换。全局优化包括改进循环、减少调用次数和快速地址算法等。 ⑥代码生成。由代码生成器生成目标机器的目标码(或汇编)程序,其中包括数据 分段、选定寄存器等工作,然后生成机器可执行的代码。 (2)解释器(Interpreter):利用用户的输入执行源程序中指定的操作。相比于编译 器,错误诊断效果好,解释器是逐条语句执行。 第一步先作词法分析,建立内部符号表;再作语法和语义分析,并进行类型检查(解释 语言的语义检查一般比较简单,因为它们往往采用无类型或动态类型系统)。完成检查后 把每一语句压入执行堆栈,并立即解释执行。因为解释执行时只看到一条语句,无法对整 个程序进行优化。但是解释执行占用空间很少。 操作系统的命令、VisualBasic、Java、JavaScript都是解释执行的(其中有些语言也可 以编译执行)。解释器不大,工作空间也不大,不过,解释执行难于优化、效率较低,这是这 类语言的致命缺点。 (3)预处理器(Preprocesor):把源程序聚合在一起,把宏的缩写转换为源语言的语 句。预处理器是由特殊的预处理器命令行控制的,例如在C语言中它们是以“#”符号开 头的源文件行。预处理器的一般操作:从源文件中删除所有的预处理器命令行,并在源 文件中执行这些预处理器命令所指定的转换操作。 (4)汇编器(Asembler):将汇编语言程序处理后生成可重定位的机器代码。汇编 语言是一种以处理器指令系统为基础的低级语言,采用助记符表达指令操作码,采用标识 符表示指令操作数。 (5)连接器(Linker):解决外部内存地址问题。将多个可重定位的目标文件以及库 文件连接到一起,形成真正在机器上运行的代码。 高级语言源程序经编译后得到目标码程序,还不能立即装入机器执行,因为程序中如 果用到标准函数(它们生成的目标码已存放在模块库中),还需对编译后得到的目标模块 进行连接。连接程序(Linker)找出需要连接的外部模块,然后到模块库中找出被调用的 模块,调入内存并连接到目标模块上,形成可执行程序。 (6)加载器(Loader):把所有的可执行目标文件放到内存中执行。 执行时,把可执行程序加载到内存中合适的位置(此时得到的是内存中的绝对地址) 即可执行。 第3章编译系统47 传统的三段编译器设计中,前端负责解析源码、检查源码错误以及建立抽象语法树来 生成编译中间件(IR);优化器负责将中间件进行逻辑重组以及优化;后端负责按照代码 运行环境生成机器码并进行连接优化,libc参与静态库连接以及运行时的动态库调用,如 图3.4所示。 图3.4三段式编译器架构 3.2.2连接过程说明 连接过程是将多个可重定位的目标文件以及库文件连接到一起,形成真正在机器上 运行的代码。 1.目标文件 以Linux系统为例,目标文件有如下几类。 (1)可重定位文件。如.o文件,包含代码和数据,可以被连接成可执行文件或共享 目标文件,静态连接库属于这一类。 (2)可执行文件。如/bin/bash文件,包含了可以直接执行的程序,一般没有扩展名。 (3)共享目标文件。如.o文件,包含代码和数据,可以跟其他可重定位文件和共享 目标文件连接产生新的目标文件,也可以跟可执行文件结合作为进程映像的一部分。 目标文件由许多段组成,其中主要的段如下。 s (1)代码段(.et)。保存编译后得到的指令数据。 tx (2)数据段(data)。保存已经初始化的全局静态变量和局部静态变量。 (3)只读数.rodata)。保存只读变量和字符串常量,有些编译器会把字符串常 量放到“.aa”段。据段((.) dt (4)BSS段(. s)。保存未初始化的全局变量和局部静态变量 。 (5)重定位表 b 。连接器在处理目标文件时,需要对目标文件中某些部位进行重定位, 即代码段和数据段中那些绝对地址的引用位置,这些重定位信息记录在重定位表里。每 个需要重定位的代码段或数据段都会有一个相应的重定位表,如.rel.ext是针对“text” 段的重定位表,.aa”是针对“dt”段的重定位表。t..re(“) ldt.aa 2.静态连接 几个目标文件进行连接时,每个目标文件都有其自身的代码段、数据段等,连接器需 要将它们各个段合并到输出文件中,具体有两种合并方法。 (1)按序叠加。将输入的目标文件按照次序叠加起来。这种方法会产生很多零散的 段,而且每个段有一定的地址和空间对齐要求,会造成内存空间大量的内部碎片。所以这 个方法现在较少用。 48智能系统及其应用 (2)第二种方法分为两个步骤进行。 ①空间与地址分配。扫描所有输入的目标文件,获得各个段的长度、属性和位置,收 集它们符号表中所有的符号定义和符号引用,统一放到一个全局符号表中。此时,连接器 可以获得所有输入目标文件的段长度,将它们合并,计算出输出文件中各个段合并后的长 度与位置并建立映射关系。 ②符号解析与重定位。经过步骤①后,输入文件中的各个段在连接后的虚拟地址已 经确定了,连接器开始计算各个符号的虚拟地址。各个符号在段内的相对地址是固定的, 连接器只需要给它们加上一个偏移量,调整到正确的虚拟地址即可。 3.可执行文件的装载 可执行文件只有被装载到内存以后才能运行,最简单的办法是把所有的指令和数据 全部装入内存,但这可能需要大量的内存。为了更有效地利用内存,根据程序运行的局部 性原理,可以把程序中最常用的部分驻留内存,将不太常用的数据放在硬盘中,即动态 装入。现 在大部分操作系统采用的是页映射的方法进行程序装载,将内存和所有硬盘中的 数据和指令按页为单位划分成若干个页,以后所有的装载和操作的单位就是页。 4.动态连接 静态连接有如下缺点。 (1)浪费内存和磁盘空间。在多进程操作系统下,每个程序内部都保留了公用的库 函数及其他数量可观的库函数及辅助数据结构,浪费大量空间。 (2)程序开发和发布困难。一个程序如果使用了很多第三方的静态库,那么程序中 一旦有任何库的更新,整个程序就要重新连接并重新发布给客户,非常不方便。 动态连接可以解决空间浪费和更新困难的问题,程序运行时才对目标文件进行连接。 使用了动态连接之后,系统会首先加载该程序依赖的其他的目标文件,如果其他目标文件 还有依赖,系统会按照同样方法将它们全部加载到内存。当所需要的所有目标文件加载 完毕之后,如果依赖关系满足,系统开始进行连接工作,包括符号解析及地址重定位等。 完成之后,系统把控制权交回给原程序,程序开始运行。此时如果运行第二个程序,它依 赖于一个已经加载过的目标文件,则系统不需要重新加载目标文件,而只要将它们连接起 来即可。 ..3.3 常见编译器 3.1 GCC编译器介绍 3. GCC(GNUCompilerColection,GNU编译器套件)是由GNU开发的编程语言编译 器。GNU编译器套件包括C、C++、Objective-C、FORTRAN 、Java、Ada和Go语言前 端,也包括了这些语言的库(如libstdc++ 、libgcj等)。 第3章 编译系统 49 GCC 编译器是Linux系统下最常用的C/C++ 编译器,大部分Linux发行版中都会 默认安装。 GCC最基本的用法是:gcc[options][filenames]。其中,options就是编译器所需 要的参数,filenames给出相关的文件名称。 -c,只编译,不连接成为可执行文件,编译器只是由输入的.c等源代码文件生成扩展 名的目标文件,通常用于编译不包含主程序的子程序文件。 -ooutput_filename,确定输出文件的名称为output_filename,同时这个名称不能和 源文件同名。如果不给出这个选项,gcc就给出预设的可执行文件a.out。 -g,产生符号调试工具(GNU 的gdb)所必要的符号信息,要想对源代码进行调试,我 们就必须加入这个选项。 -O,对程序进行优化编译、连接,采用这个选项,整个源代码会在编译、连接过程中进 行优化处理,这样产生的可执行文件的执行效率可以提高,但是,编译、连接的速度就相应 地要慢一些。 -O2,比-O 更好的优化编译、连接,当然整个编译、连接过程会更慢。 -Idirname,将dirname所指出的目录加入到程序头文件目录列表中,是在预编译过 程中使用的参数。 GCC编译器可以在x86平台上面运行,也可以在ARM 和RISC-V 平台上应用,其编 译的指令如下。 在x86 平台上: gcc main.c -o main 在ARM 平台上:arm-linux-gcc main.c -o main 在RISC-V 平台上:riscv-gcc main.c -o main 以上若只有一个文件,可直接用后缀-o生成可执行文件main;但若是几个文件时,需 要先单独编译各个文件,然后再通过连接产生出可执行文件main,如下。 gcc -o a.o -c a.c gcc -o main.o -c main.c gcc -o main a.o main.o GCC也支持华为公司的openEuler操作系统,GCC 针对openEuler支持基于开源 GCC-10.3版本(https://gcc.gnu.org,2021年4月发行)开发,并进行了优化和改进,实现 软硬件深度协同优化,挖掘OpenMP、SVE向量化、数学库等领域极致性能,是一种Linux 下针对鲲鹏920处理器的高性能编译器。GCC 针对openEuler默认使用场景为TaiShan 服务器、鲲鹏920处理器、ARM 架构,操作系统为CentOS7.6、openEuler20.09等。GCC 是一个单一的可执行程序编译器,前段、IR和后端没有明确的分界,耦合严重,难以独自 发展,在整个编译过程中,中间诸多信息都无法被其他程序重用。 3.3.2 LLVM 编译器介绍 LLVM(http://llvm.org/)是构架编译器的框架系统,用C++编写而成,用于优化以 50智能系统及其应用 任意程序语言编写的程序的编译时间、连接时间、运行时间以及空闲时间,对开发者保持 开放,并兼容已有脚本。LLVM核心库提供了与编译器相关的支持,可以作为多种语言 编译器的后台来使用。能够进行程序语言的编译期优化、连接优化、在线编译优化、代码 生成。LLVM的项目是一个模块化和可重复使用的编译器和工具技术的集合。LLVM 是伊利诺伊大学的一个研究项目,计划启动于2000年,提供一个现代化的、基于SSA的 编译策略,能够同时支持静态和动态的任意编程语言的编译目标。目前LLVM已经被苹 果公司iOS开发工具、XilinxVivado、Facebook、Google等各大公司采用。 LLVM在继承了传统三段式设计的情况下,将优化器的输入输出接口、数据进行归 一,即不同语言的前端解析后生成相同语法规则的中间件,经过优化后输出通用的代码给 不同的后端进行目标代码生成。由于代码目标运行平台有限,后端相对固定,前端的输入 格式固定,所以对于一门新语言的编译器开发,LLVM具有方便快捷的集成能力,同样还 有多种的前端作为开发的样例和对比,进而推动了LLVM框架的繁荣发展。LLVM相 对GCC编译器有着较快的编译速度,目标程序有着较好的性能表现,在编译错误上也有 着更加友好的提示。 前端:LLVM最初被用来取代GCC中的代码产生器,许多GCC的前端已经可以与 其运行,LLVM 目前支持Ada、C语言、C++、D语言、FORTRAN、Haskell、Julia、 Objective-C、Rust及Swift的编译,它使用许多的编译器,有些来自4.0.1及4.2版本 的GCC。 中间端:LLVM的核心是中间端表达式(IntermediateRepresentation,IR),是一种 类似汇编的底层语言。IR是一种强类型的精简指令集(ReducedInstructionSet Computing,RISC),并对目标指令集进行了抽象。例如,目标指令集的函数调用惯例被抽 l 和rt指令加上明确的参数。另外, 象为caeIR采用无限个数的暂存器,使用如%0 、%1 等形式表达。LLVM支持3种表达形式:人类可读的汇编,在C++中对象形式和序列化 后的bitcode形式。 后端:LLVM已经支持多种后端指令集,包括ARM 、QualcommHexagon、MIPS 、 NVIDIA(LLVM 中称为NVPTX )、PowerPC 、AMDTeraScale、AMDGPU 、SPARC 、 SystemZ 、RISC-V、WebAsembly、x86 、x86-64和XCore。 3.3 TVM 编译器 3. 有关深度学习编译器框架,近年有名的是华盛顿大学陈天奇提出的TVM(Tensor VirtualMachine)框架,它旨在缩小以生产力为中心的深度学习框架与以性能和效率为中 心的硬件后端之间的差距。TVM与深度学习框架合作,为不同的后端提供端到端编译。 TVM与LLVM的架构非常相似。TVM针对不同的深度学习框架和硬件平台,实现了 统一的软件栈,以尽可能高效的方式,将不同框架下的深度学习模型部署到硬件平台上。 TVM的设计目的是分离算法描述、调度和硬件接口。该原则受到Halide的计算/调度 分离思想的启发,而且通过将调度与目标硬件内部函数分开而进行了扩展。这一额外分 离使支持新型专用加速器及其对应新型内部函数成为可能。TVM具备两个优化层:一 个是计算图优化层,用于解决第一个调度挑战;另一个是具备新型调度基元的张量优化 第3章编译系统51 层,以解决剩余的3个挑战。通过结合这两个优化层,TVM从大部分深度学习框架中获 取模型描述,执行高级和低级优化,生成特定硬件的后端优化代码,如CPU 、GPU和基于 FPGA的专用加速器。实现了如下功能。 (1)构建了一个端到端的编译优化堆栈,允许将高级框架(如Cafe 、MXNet、 PyTorch、Cafe2、CNTK)专用的深度学习工作负载部署到多种硬件后端上(包括CPU 、 GPU和基于FPGA的加速器)。 (2)提供深度学习工作负载在不同硬件后端中的性能可移植性的主要优化挑战,并 引入新型调度基元(Scheduleprimitive)以利用跨线程内存重用、新型硬件内部函数和延 迟隐藏。 (3)在基于FPGA的通用加速器上对TVM进行评估,以提供关于如何最优适应专 用加速器的具体案例。 3.方舟编译器 3.4 方舟编译器改变了系统及应用的编译和运行机制,直接将高级语言编译成机器码,让 手机能直接听懂“高级语言”,消除了虚拟机动态编译的额外开销,提升了手机运行效率。 同时,方舟编译器还能够理解程序特征、使用适合的指令来执行程序,因此能够极大程度 地发挥出芯片的能力。目前,方舟编译器聚焦在Java代码性能上,未来,方舟编译器将覆 盖多种编程语言(包括C/C++、JS等),多种芯片架构(包括CPU 、GPU 、IPU等),覆盖更 广的业务场景。 方舟编译器主要有如下特点。 ava/C/C+ (1)方舟编译器将手机开发中的多种语言J+实现了统一的中间表示IR, 将Java/C/C++等混合代码一次编译成机器码直接在手机上运行,告别Java的JNI额外 开销,使得不同语言代码在开发者环境中能够统一编译成同一套可直接执行的机器码,从 而彻底消除混合语言互相调用的开销。 (2)方舟编译器直接将代码优化从手机环节搬到了开发者环境,利用开发者环境更 强大的算力,可以实现更先进和精细的优化算法,来达到更强大的优化效果。 (3)方舟编译器采用了引用计数法(ReferenceCounting,RC)来进行内存的实时回 收,并且配合使用了专门的消除环算法(消除对象互相引用带来的无法回收问题),来避免 Android虚拟机集中式回收带来的系统卡顿。相比Android虚拟机集中式内存回收,方 舟编译器的内存回收是实时的而非集中式的,且不需要暂停应用进程,这样便大大消除了 卡顿。 方舟编译器整体架构分为编译器输入、编译器处理和编译器输出。编译器处理采用 了目前业界主流的三阶段设计。方舟编译器的整体架构如图3. 5所示。 方舟编译器(OpenArkCompiler)是为支持多种编程语言、多种芯片平台的联合编译、 运行而设计的统一编程平台,包含编译器、工具链、运行时等关键部件,并在htps:// gie.om/pnrcier网站进行开源。 tcoeakompl Operomplr2.主要提供对Jv nAkCie0 aa、C语言的编译和运行支持,代码仓为 htps:ie.om/peakomplreromplr。 //gtconrcie/OpnAkCie 52 智能系统及其应用 图3.5 方舟编译器的整体架构 OpenArkCompiler3.0主要结合OpenHarmony和HarmonyOS面向多设备开发和 运行的多语言应用的需求,新增对JavaScript/TypeScript语言、平台无关的应用分发格 式、跨设备轻量级运行时的支持。目前在OpenHarmony开放的代码仓如下。 运行时公共组件:https://gitee.com/openharmony/ark_runtime_core。 JavaScript运行时:https://gitee.com/openharmony/ark_js_runtime。 JavaScript/TypeScript前端编译器:https://gitee.com/openharmony/ark_ts2abc。 3.3.5 毕昇编译器 毕昇编译器是华为编译器实验室针对鲲鹏等通用处理器架构场景,打造的一款高性 能、高可信及易扩展的编译器工具链,增强和引入了多种编译优化技术,支持C/C++/ FORTRAN 等编程语言。 毕昇编译器基于开源LLVM 开发,并进行了优化和改进,LLVM 是一种涵盖多种编 程语言和目标处理器的编译器,毕昇编译器聚焦于对C、C++、FORTRAN 语言的支持, 利用LLVM 的Clang作为C和C++的编译和驱动程序,Flang作为FORTRAN 语言的 编译和驱动程序。 毕昇编译器的运行平台是鲲鹏920硬件平台,支持的操作系统有openEuler21.03、 openEuler20.03(LTS)、CentOS7.6、Ubuntu18.04、Ubuntu20、麒麟v10和UOS20。 使用毕昇编译器,例如编译运行C/C++程序,命令如下。 clang [command line flags] main.c -o main.o clang++ [command line flags] main.cpp -o main.o 毕昇编译器的默认选项:支持LLVM 的所有优化等级(O0/O1/O2/O3/Ofast),支 持Clang 的默认编译选项和Flang 的默认编译选项,支持fsanitize=address/leak/ memory等选项。 毕昇编译器除LLVM 通用功能和优化外,对中端及后端的关键技术点进行了深度优 化,并集成Autotuner特性支持编译器自动调优。初始编译阶段发生在调优开始之前, 第3章编译系统53Autotuner首先会让编译器对目标程序代码做一次编译,在编译的过程中,毕昇编译器会 生成一些包含所有可调优结构的YAML文件,告诉我们在这个目标程序中哪些结构可 以用来调优,例如文件(Module)、函数(Function)、循环(Loop)。例如,循环展开是编译 器中最常见的优化方法之一,它通过多次复制循环体代码,达到增大指令调度的空间,减 少循环分支指令的开销等优化效果。若以循环展开次数(Unrollfactor)为对象进行调 优,编译器会在YAML文件中生成所有可被循环展开的循环作为可调优结构。当可调 优结构顺利生成之后,调优阶段便会开始:①Autotuner首先读取生成好的可调优结构的 YAML文件,从而产生对应的搜索空间,也就是生成针对每个可调优代码结构的具体的 参数和范围;②调优阶段会根据设定的搜索算法尝试一组参数的值,生成一个YAML格 式的编译配置文件(Compilationconfig),从而让编译器编译目标程序代码产生二进制文 件;③最后Autotuner将编译好的文件以用户定义的方式运行并取得性能信息作为反 馈;④经过一定数量的迭代之后,Autotuner将找出最终的最优配置,生成最优编译配置 文件,以YAML的形式存储。