鉴释课堂丨编译器技术入门知识一网打尽

近 10 年，摩尔定律逐渐失效，芯片性能已经摸到了天花板。功率消耗与优化的基石——编译器技术再次进入了人们视野，我们请到了鉴释静态代码分析工具爱科识（Xcalscan）研发负责人赖建新，通过通俗的语言与示例带大家走近编译器技术。

这次分享将分为共六个问题向大家介绍:

1. 什么是编译器技术？
2. 初学编译器技术的开发者需要具备哪些基础？
3. 当今现代编译器的关键挑战是什么？
4. 编译器中哪个部分最重要？
5. 编译器技术除了生成代码在进程或 VM 中执行之外，是否还有其他领域使用编译器技术？
6. 为什么数据流分析在发现程序问题（包括错误、安全漏洞等）方面更有效？

一、什么是编译器技术？

编译器技术与高级语言程序设计技术一同诞生，狭义的编译器技术是指将高级语言翻译成机器码。但倘若没有编译器的存在，那么程序员只能用机器码，这些由 0 和 1 组成的数字代码来编写程序，在如今庞大的软件体量里，这几乎是不可能完成的任务。

所以千万不要小看编译器，它自下而上贯穿了程序开发的全过程，从硬件到应用全都有它的存在。

除了常见的高级语言到机器码的编译器外，编译器技术还广泛应用于领域特定语言（Domain Specific Language， DSL）到通用编程语言的源到源编译器（例如区块链中智能合约编译器，Web 开发中各种高级语言到 JavaScript 的编译器），高级语言解释器（例如 Python）和虚拟机（例如 Java VM 和 WebAssembly VM），以及二进制翻译（Binary Translation，例如 Apple Silicon M1 上的 Rosetta 2）等领域。

随着现代软件规模不断增大，技术栈日趋复杂，只有充分利用编译器技术，才能在程序的正确性、稳定性、安全性、性能，代码的可读性、可维护性、可移植性和开发人员的开发效率等多方面取得更好的平衡。

二、初学编译器技术的开发者需要具备哪些基础？

熟悉 C 语言与 C++，以及常见的数据结构，特别是树和图的构建、查找、遍历和变换算法是必须的敲门砖

进阶编译器技术开发还需要对源语言、目标语言或指令集和微架构有深刻的理解。

三、当今现代编译器的关键挑战是什么？

从第一个高级语言 FORTRAN 发明以来，编译器技术就随着高级语言和计算机技术的发展而不断发展。早期的编译器侧重于高级语言到机器码的代码生成技术，主要解决的问题是指令选择和寄存器分配。

随着高级语言的抽象层次不断提高以及现代处理器和存储系统日益复杂，编译器优化技术的重要凸显出来。编译优化技术一般可分为机器无关优化和机器相关优化。

• 前者能够帮助消除高级语言抽象引入的额外开销同时提升程序员的开发效率，增加程序的可读性、可维护性、可移植性。
• 后者能帮助程序充分利用现代处理器和存储系统的资源和特点以提高程序运行性能。

随着开源软件和云计算的到来，软件开发逐渐从原来封闭的完全内部开发转为开放的基于开源软件组装或者集成开发；从使用单一编程语言的单机环境，到使用两种语言的服务器/客户端环境，再到使用多种语言云-边缘-端复杂环境开发。这些给编译器带来了新的挑战。例如:

• 如何优化编译器本身以更好的支持超大规模软件系统（例如 Android，Chromium）的构建和优化？
• 在代码生成之外，如何将编译器技术应用到开发过程中，能够提升程序员开发效率，解决代码质量问题？
• 在混合语言开发或者三方库集成中，如何利用编译器技术防范跨越语言边界或三方库边界出现的 bug？

这些问题都是今天的编译器面临的关键挑战。

四、编译器中哪个部分最重要？

首先我们看一下编译器的整体架构：

编译器前端的职责是将源语言转换为中间表示，包括词法分析、语法分析、语法检查和中间代码生成。

• 词法分析和语法分析都是基于文法和自动机理论，在 1970 年代已经发展成熟。
• 语法检查遍历语法分析产生的抽象语法树(Abstract Syntax Trees，AST)，检查树的节点和层次关系是否符合源语言规范。
• 中间代码生成是将抽象语法树简化和规范化后生成编译器定义的中间表示（Intermediate Representation，IR)。

编译器后端的职责是将中间表示经过编译分析和编译优化后生成汇编代码或目标代码的过程。

• 预链接阶段是过程间分析的必备步骤，它使用和最终链接阶段相同的链接规则和顺序确定全局函数和变量的访问目标并以此为基础构建函数调用图(Call Graph)。
• 编译分析主要包括函数内的控制流分析(Control Flow Analysis)，数据流分析(Data Flow Analysis)，函数调用的上下文分析(Context Analysis)和别名分析(Alias Analysis)。这些分析为后续的优化和代码生成提供优化依据和策略。
• 机器无关优化包括过程间优化(Inter-Procedure Optimization)，循环优化（Loop Optimization）和标量优化（Scalar Optimization）等，它的优化目标和依据和具体的处理器架构无关。
• 机器相关优化包括指令选择和调度，寄存器分配和针对特定硬件结构的优化等。
• 代码生成阶段将完成寄存器分配的中间表示通过内置或外置的汇编器产生出目标代码。目标代码最终通过链接器链接产生可执行文件或可加载模块。

在上述的编译器各个部分中，编译分析的重要性越来越大。编译分析不仅对编译优化至关重要；对新兴的编译器应用场景，如代码静态扫描，更是最为关键的步骤。函数内的控制流分析技术和数据流分析技术已经发展成熟并在各编译器实现里广泛使用，而别名分析和上下文分析仍面临巨大挑战。

从这个角度而言，别名分析和上下文分析成为编译器中最重要的部分：

——— 别名分析 ———

别名分析用于确定两个指针或引用所指向的内存或对象是完全重叠、部分重叠或者相互独立。部分重叠的情形存在于 C/C++这类允许联合体（Union）数据类型或允许指针算术操作的语言中。

别名分析的难点：

一方面在于在函数调用的每一个上下文和函数执行的每一条可能路径上跟踪指针变量的定义-使用链非常困难，其算法复杂度是指数级的；

另一方面在于对于存放在数组等可随机访问或递归数据结构（如链表、树和图）中的指针的别名分析几乎没有精确的结果。

别名分析对优化和静态扫描非常重要，我们用 C 语言举例如下，假定 a、b、c、d 均为整型变量，p 和 q 为整型变量指针：

——— 上下文分析 ———

上下文分析将函数放进函数调用点的上下文环境中，确定调用前参数和全局变量的取值情况后分析函数行为以确定函数调用结束后返回值和全局变量的变化情况。

上下文分析的难点：

• 一是完全上下文敏感分析的算法复杂度是指数级的，例如假设函数 A 在 3 个不同位置调用函数 B，函数 B 也在 3 个不同位置调用函数 C，此时函数 C 有 9 个不同的上下文需要分析；
• 二是随着软件规模增大及模块化软件设计强调函数功能单一化后函数数量和调用点数量激增，上下文数量可能膨胀到无法分析的情况；
• 三是由于函数递归调用导致难以进行精确的上下文分析结果。

上下文分析同样对优化和静态扫描很重要：

五、编译器技术除了生成代码在进程或 VM 中执行之外，是否还有其他领域使用编译器技术？

除了上述领域，编译器技术目前还能被应用在：

• 静态扫描工具，即利用编译分析技术查找程序中存在的 bug 或者不符合规约的代码。
• 基于抽象语法树的用于提高程序可读性和可维护性性的格式化工具、代码重构工具和代码规范检查工具；
• 与 IDE 集成的程序分析工具，可为程序员提供智能提示，并自动修复代码中的拼写错误；
• 源到源的编译技术则应用于各种领域特定语言（Domain Specific Language，DSL）的处理；
• 软件成分分析工具，即利用编译技术分析大型软件可能引用了哪些第三方组件，各三方组件是否有已知安全漏洞、兼容性问题和许可证问题等，从而在开发早期阶段就避免或修复此类问题。

六、为什么数据流分析在发现程序问题 (包括错误、安全漏洞等）方面更有效？

以另一种广泛使用的基于抽象语法树（Abstract Syntax Trees，AST）的检查为比较对象，基于 AST 的检查工具通常用于检查输入源语言的词法、语法检查和基于模式匹配的规则检查。

例如，对于类似 int x = y / 0;这样的语句，AST 检查器能检查出语句包含一个除数为零的错误；但如果代码是 int x = y / z; 如果 z 在程序的某处会被赋值为 0 且该赋值语句能到达做除法的这条语句，程序执行同样会产生除数为零的错误。AST 检查器因为难以跟踪变量的定义使用和值传播情况而无法检测后面这种错误。

类似的，在跨越函数边界传递指针时，通常会约定由调用函数或者被调用函数检查空指针。在软件有很多不同组织开发的模块或者开源模块集成时，不同模块间的调用约定不一致时会因重复检查而导致性能问题，或遗漏检查而导致程序错误和安全问题。

由于相关的函数调用语句和空指针检查语句处于不同的抽象语法树中，这样的检查也很难在 AST 检查器中实现。而结合数据流分析和上下文分析就能很好检测这类错误。

程序中常见的错误或安全漏洞往往可以归纳为源（Source）-汇（Sink）模型，即引起错误或安全漏洞的数据来自一个有问题的源，经过一系列的流动（Flow，例如被复制到另一个变量，写入内存再读出，等）后最终在汇的地方引发程序错误。

以安全漏洞中最常见的释放后使用（Use After Free）为例，从指针所指向的内存被释放的语句（Source）开始，如果指针或其别名指针进过一系列的数据流操作后能到达指针被解引用的语句（Sink），即会触发一个释放后使用的错误。对于这类问题，可以给特定的语句或变量（Source）打上特定标签，利用数据流分析技术复制和传播这个标签，随后在可能引起程序错误的语句或变量（Sink）上检测是否存在特定标签，即可高效准确的检测此类问题。

编译器技术自诞生至今已经过去几十年，主要的分析和优化技术都诞生于上世纪 70 年代到 90 年代。进入二十一世纪后，编译相关技术已经不是学术界或工业界研究热点，但仍有不少技术人员持续深耕该领域，希望做出拥有行业影响的优秀产品。

例如鉴释自主开发的代码分析工具爱科识（Xcalscan）通过编译器技术，于软件生命周期的早期就在后端位置检查代码漏洞、优化代码质量，赋能企业提高开发效率、降低开发成本，至今已经与人工智能芯片、无人驾驶、智能家居等领域的头部企业展开合作。

看完了文章，您是否已经对编译器技术有了更深刻的认识呢？未来鉴释也将带来更多技术干货，敬请期待！

本文作者：赖建新，鉴释研发负责人，毕业于清华大学计算机系，有着丰富的编译器优化和高级程序静态分析的经验。