LLVM：用于终身程序分析与翻译的编译框架外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

LLVM：用于终身程序分析与翻译的编译框架

摘要

本文介绍了 LLVM（底层虚拟机），这是一个编译器框架，旨在通过在编译时，链接时，运行时，以及多次运行之间的空闲时间向编译器转换提供高级信息来支持对任意程序的透明的终身程序分析和转换。LLVM 定义了静态单赋值（SSA）形式的公共低级代码表示，其具有几个新特征：简单的，语言无关的类型系统，该类型系统提供了通常用于实现高级语言特性的原语；用于带类型的地址算术的指令以及可以用来实现高级语言的异常处理功能（以及 C 语言中的 setjmp / longjmp）的简单机制。LLVM 编译器框架和代码表示是支持程序的终身分析和转换重要的关键因素。据我们所知，没有任何现有的编译方式提供所有这些功能。我们将描述 LLVM 表示和编译器框架的设计，并以三种方式评估设计：(a) LLVM 表示的大小与效率，以及它提供的类型信息；(b) 几个过程间问题的编译器性能和 (c) LLVM 为几个具有挑战性的编译器问题提供的益处的说明性示例。

1. 简介

现代应用程序的规模不断增加，在运行时自我修改，支持动态扩展和升级，并且通常使用多种不同语言编写的组件。一些应用程序的热点部分较小，其它程序则均匀分布。为了最大限度地提高所有这些程序的效率，我们认为程序分析和转换必须在程序的整个生命周期中执行。这种“终身代码优化”技术包括链接时施行的过程间优化（以保留分离编译的好处）、在每个系统上安装时的机器相关的优化、运行时的动态优化以及在多次运行之间的空闲时间利用从终端用户收集性能分析信息进行的分析导向优化。

程序优化不是终身分析和转换的唯一用途。静态分析基本上也是基于过程间的，因此在链接时执行最为方便（例如静态调试，静态泄漏检测和内存管理转换）。一些复杂的分析与转换技术正在被研究用于保证程序安全性，但是这些技术只能在软件的安装或加载时使用。允许程序的终生再优化给予了架构演进处理器的能力，并且允许以更灵活的方式暴露接口，从而使旧程序在新系统上依旧运行良好。

这篇论文介绍了 LLVM —— 底层虚拟机 —— 一种编译器框架，旨在以一种透明的方式对任意软件做终身程序分析及转换。LLVM 通过两方面来做到这一点：(a) 有着多种全新功能的代码表示。该代码表示作为分析、转换和代码分布的通用表示； 和 (b) 编译器设计。其利用这些代码表示来提供前所未有的功能组合。

LLVM 的代码表示使用一种抽象的类 RISC 指令集来描述程序，但是其具有关键的高级信息，以用来实现高效的分析。高级信息包括类型信息、显式控制流程图以及一个显式的数据流表示（其在 SSA 种使用一种无限的、强类型的寄存器集合）。在 LLVM 代码表示中，有几个非常重要的特性：(a) 底层、语言无关的类型系统，其可以用来实现高级语言中的数据类型与操作，并且可以将它们的实现行为暴露给优化的所有阶段。这个类型系统包括一些复杂的技术（语言无关的）用到的类型信息，例如指针分析、依赖分析以及数据转换算法；(b)能够在执行类型转换以及底层地址算术计算保留类型信息的指令；(c) 2 个底层的异常处理指令，用于实现语言特定的异常语义，并且将异常控制流暴露给编译器。

LLVM 所使用的代码表示是源语言无关的，其原因有二：第一，其使用的较为底层的指令集以及内存模型仅仅稍微比汇编语言丰富一点，并且其类型系统允许其代码表示带有少了的类型信息。第二，它不对程序施加任何特定的运行时需求或语义。尽管如此，重要的是要注意，LLVM 不是一个通用的编译器 IR。具体地来说，LLVM 并没有直接表示高级语言的特性（所以它不能被用于一些语言特定的转换），也没有依赖机器相关的特性和后端代码生成器使用的代码序列（当然它最后还是会被降低到这一层）。

由于不同的目标与表示，LLVM 是对高级虚拟机（例如，Small-Talk、Self、JVM、微软的 CLI 等）的补充，而不是这些系统的替代品。LLVM 与上述高级虚拟机有三个主要不同。第一，LLVM 没有像类、继承、异常处理语义等高级设施，即使是在编译有这些设施的源语言时。第二，LLVM 没有指定运行时或某个特定的对象模型：LLVM 足够底层，甚至可以用 LLVM 实现某个语言的运行时。实际上，LLVM 可以用来实现高级虚拟机。第三，LLVM 不保证类型安全、内存安全，与除了与汇编之外的语言之间的互通性。

LLVM 编译框架利用它的代码表示来同时提供 5 种功能，我们认为这些功能对于支持终身程序分析很重要。总的来说，很难同时实现这些功能，但是 LLVM 还是实现了： (1) 持久的程序信息：LLVM 的编译模型在程序的整个生命周期都保留了 LLVM 的代码表示，从而允许在所有阶段执行复杂的优化，包括运行时间和运行之间的空闲时间。 (2) 离线代码生成：离线时将程序编译成高效的机器码是可行的：可以使用不适合运行时代码生成的昂贵代码生成技术将程序编译为离线的高效本地机器代码。这对于在乎性能的程序至关重要。 (3) 基于用户的分析和优化：LLVM 框架在运行时收集分析信息以便它可以代表实际用户，并且可以在运行时和空闲时间将其应用于配置文件引导的转换。 (4) 透明的运行时模型：系统不指定任何特定的对象模型，异常语义或运行时环境，从而允许使用它来编译任何语言（或语言组合）。 (5) 统一的全程序编译：语言的独立性使得可以以统一方式（包括链接之后）优化和编译包括应用程序的所有代码，包括特定于语言的运行时库和系统库。

我们认为没有以前的系统同时提供上述五个属性。源级编译器提供 #2 与 #4，但是没有尝试去提供 #1, #3 和 #5。于商业级编译器常见的链接时过程间优化器多提供了 #1 和 #5，但是仅仅是链接时。用于静态语言的配置导向的优化器提供了 #2，但是失去了透明性，而且最重要的是它们不支持 #3。高级虚拟机（如 JVM 和 CLI）提供了 #3 并且部分提供了 #1 和 #5，但是没有打算提供 #4，并且不提供 ＃2 或不提供 ＃1 或 ＃3。二进制运行时优化系统提供了 #2、#4 和 #5，但是仅仅以有限的形式于运行时提供 #3，并且最重要的是，没有提供 #1。我们将在第 3 节更详细地解释这些。

我们通过三个问题来评估 LLVM 系统的效率：(a) LLVM 表示的大小和效率，这其中包括为 C 程序提取有用类型信息的能力; (b)编译器的性能（而不是取决于特定代码生成器或者使用的优化序列的生成的代码的效率以及 (c) 展示 LLVM 为若干具有挑战性的编译器问题提供关键能力的具体例子。

我们的实验结果表明，在 SPECINT 2000 C 基准测试中，LLVM 编译器可以为测试中所使用的静态存储器访问指令的 68% 提供可靠类型信息，在其它更严格的程序中，甚至可以做到近乎 100%。基于我们的经验我们还讨论了 LLVM 捕获的类型信息是如何支撑一系列比较激进的变换的，这些变换原来只会在类型安全的高级语言的源级编译器中的进行。代码大小的测量表示，尽管捕获了更丰富的类型信息以及使用了 SSA 形式的无限寄存器集合，LLVM 表示与 X86 机器代码（CISC 架构）大小相当，并且平均比 RISC 代码小约 25％。最后，我们提出示例时序，以显示 LLVM 表示支持极快的进程间优化。

我们目前的 LLVM 实现支持 C 与 C ，二者目前是完全静态编译的。我们目前正在探索实现类似 JVM 与 CLI 的动态运行时是否会带来好处。LLVM 是免费的，并且使用了无限制的协议。本文的其余部分安排如下。第 2 节描述了 LLVM 代码表示。第 3 节介绍了 LLVM 编译器框架的设计。第 4 节，如上文提到的，讨论 LLVM 系统的评估。第 5 节比较 LLVM 和以前的类似的系统。第 6 节对本文进行总结。

2. 程序表示

LLVM 与其他系统的关键区别就是 LLVM 的代码表示。该代码表示旨在为复杂的分析与转换提供其必要的信息，同时足够低级来表示任意程序以及允许在静态编译器中进行大量优化。本节概述了 LLVM 指令集，并描述了其与语言无关的类型系统，内存模型，异常处理机制以及离线与其在内存的内存表示。 该表示法的详细语法和语义在 LLVM 参考手册中定义。

2.1 LLVM 指令集概述

LLVM 指令集捕获普通处理器的关键操作，但避免机器特定的约束，例如物理寄存器，管线和低级调用约定。 LLVM 提供了一组无限的类型化虚拟寄存器，它们可以保存基本类型（布尔值，整数，浮点和指针）的值。虚拟寄存器采用静态单赋值（SSA）形式。 LLVM 是一种加载/存储架构：程序只能使用类型化指针通过加载和存储操作在寄存器和存储器之间传输值。 LLVM 内存模型在第 2.3 节中描述。

整个 LLVM 指令集只包含 31 个操作码。之所以这么少，是因为，首先，我们避免多个操作码用于相同的操作。再者，LLVM 中的大多数操作码都是重载的（例如，add 指令可以对任何整数或浮点操作数类型的操作数进行操作）。大多数指令，包括所有的算术和逻辑操作，都是三地址形式：它们取一个或两个操作数并产生一个结果。

LLVM 使用 SSA 形式作为其主代码表示，即，每个虚拟寄存器只会被一条指令写入，并且其定义决定其使用。LLVM 中的内存位置不是以 SSA 形式，因为通过指针的内存写可能会改变许多内存地址，使得难以为这样的位置构造足够紧凑的，显式的 SSA 代码表示。 LLVM 指令集包括显式 phi 指令，其直接对应于 SSA 形式的标准 phi; 函数。SSA 形式提供了一个紧凑的 def-use 图，简化了许多数据流优化算法，使得一些快速的、不基于流的算法也可以在不使用昂贵的数据流分析的情况下获得基于流的算法的优势。SSA 形式的非循环变换被进一步简化，因为它们不会遇到对 SSA 寄存器的输出依赖。非内存的变换也被大大简化，因为（与 SSA 无关）寄存器不能 'alias'。

LLVM 还将每个函数的控制流图（CFG）显式表示在其代码表示中。函数是一组基本块，每个基本块是一串 LLVM 指令，以一个终止指令结束（分支，return，unwind 或 invoke。后两个将在后面解释）。每个终结指令明确指定其后继的基本块。

2.2 语言无关的类型信息、转换和 GetElementPtr

LLVM 的基本设计特征之一就是包含了一个与语言无关的类型系统。每个 SSA 寄存器和显式内存对象都有与其关联的类型，并且所有操作都遵守严格的类型规则。 该类型信息与指令操作码共同确定指令的确切语义（例如，浮点与整数加法）。这种类型信息使得能够在低级代码上进行大量的高级转换（例如，参见第 4.1.1 节）。此外，类型的不匹配对于检测优化器的漏洞非常有用。

LLVM 的类型系统包括具有预定义大小（void，bool，8 到 64 位的有符号/无符号整数，以及单精度和双精度浮点类型）的源语言无关的基本类型。这使得可以使用这些类型写出可移植的代码，尽管不可移植的代码也可以直接表示。LLVM 还（仅）包括四种派生类型：指针，数组，结构和函数。我们认为，大多数高级语言的数据类型最终在其操作行为上使用这四种类型的某种组合来表示。例如，使用结构，函数和函数指针数组来实现具有继承的 C 类，如第 4.1.2 节所述。

同样重要的是，上述四种派生类型捕获了用于复杂的语言无关分析和优化的类型信息。 例如，字段敏感的指向分析，调用图构造（包括如 C 等面向对象语言），聚合的标量提升和结构字段重排序转换，它们只需要使用指针，结构，函数和原始数据类型。而数组依赖分析和循环变换则还需要数组类型。

因为 LLVM 是语言无关的并且必须要为弱类型语言提供支持，所以在合法的 LLVM 程序中声明的类型信息可能并不可靠。相反，必须使用一些指针分析算法来区分哪些指针指向的类型是可靠的，哪些是不可靠的。 LLVM 支持这种分析，并描述于 4.1.1 节。我们的结果表明，尽管允许值被转换为其他任意类型，但是还是可以从编译到 LLVM 的 C 程序中的大部分的内存访问中获取可靠的类型信息。

LLVM的 cast 指令用于将一种类型的值转换为另一种任意类型的值，并且这是执行这种转换的唯一方法。因此，cast 指令使得所有的类型转换都变成了显式，包括隐式类型转换（在 LLVM 中没有混合类型的操作），显式转换用于子类型，以及非类型安全代码的重新解释的转换。没有使用 cast 指令的程序必然是类型安全的（在没有内存访问错误的情况下，例如，数组溢出）。

保存低级代码的类型信息的关键困难是实现地址算术。LLVM 中的 getelementptr 指令用来以保留类型信息和具有机器无关语义的方式执行指针算术。给定一个聚合类型的对象的类型化指针，该指令在保存类型信息的情况下计算该对象的子元素的地址。（实际上是 LLVM 中 . 与 [] 运算符的组合）。例如 C 语句 X[i].a = 1; 可以翻译成两条 LLVM 指令：

%p = getelementptr %xty* %X, long %i, ubyte 3;

store int 1, int* %p;

其中，我们假设 a 在 X[i] 结构中偏移为 3 的地方，该结构体类型为 %xty。使所有地址算术显式是重要的，以便暴露给 LLVM 的全部优化（最重要的是，重关联和冗余消除）; getelementptr 在不失去类型信息的情况下实现了这一点。加载和存储指令接收单个指针并且不执行任何索引，这使得存储器访问的处理变得简单和一致。

2.3 显式内存分配与统一的内存模型

LLVM 提供了类型化的内存分配指令。 malloc 指令在堆上分配特定类型的一个或多个元素，返回指向新内存的类型化的指针。free 指令释放通过 malloc 分配的内存。 alloca 指令类似于 malloc，但是它在当前函数的栈帧中分配内存，而不是堆，并且在从函数返回时自动释放内存

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138819]，资料为PDF文档或Word文档，PDF文档可免费转换为Word