LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation
TL;DR 精炼摘要
LLVM(低级虚拟机)是一个编译框架,旨在支持对任意程序进行透明的、终身的分析与转换。它通过提供高级信息来优化编译、链接、运行及空闲时间的计算过程。论文展示了LLVM的设计和评估,包括其类型系统和针对编译效率的多种特性,使其在编程语言中的应用具有重要意义。
摘要
This paper describes LLVM (Low Level Virtual Machine), a compiler framework designed to support transparent, lifelong program analysis and transformation for arbitrary programs, by providing high-level information to compiler transformations at compile-time, link-time, run-time, and in idle time between runs. LLVM defines a common, low-level code representation in Static Single Assignment (SSA) form, with several novel features: a simple, language-independent type-system that exposes the primitives commonly used to implement high-level language features; an instruction for typed address arithmetic; and a simple mechanism that can be used to implement the exception handling features of high-level languages (and setjmp/longjmp in C) uniformly and efficiently. The LLVM compiler framework and code representation together provide a combination of key capabilities that are important for practical, lifelong analysis and transformation of programs. To our knowledge, no existing compilation approach provides all these capabilities. We describe the design of the LLVM representation and compiler framework, and evaluate the design in three ways: (a) the size and effectiveness of the representation, including the type information it provides; (b) compiler performance for several interprocedural problems; and (c) illustrative examples of the benefits LLVM provides for several challenging compiler problems.
思维导图
论文精读
中文精读
1. 论文基本信息
1.1. 标题
LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation (LLVM: 一个用于终身程序分析与转换的编译框架)
1.2. 作者
Chris Lattner 和 Vikram Adve,均来自伊利诺伊大学厄巴纳-香槟分校 (University of Illinois at Urbana-Champaign)。
1.3. 发表期刊/会议
该论文发表于 2004 年。虽然论文本身没有明确指出具体的会议或期刊名称,但从其内容和影响力来看,这通常是计算机体系结构或编程语言领域顶级会议的出版物(如 PLDI, ASPLOS, MICRO 等)。LLVM 项目本身在计算机科学领域具有极高的声誉和影响力。
1.4. 发表年份
2004 年。
1.5. 摘要
本文描述了 LLVM (Low Level Virtual Machine,低级虚拟机),一个旨在通过在编译时 (compile-time)、链接时 (link-time)、运行时 (run-time) 以及两次运行之间的空闲时间 (idle time) 向编译器转换提供高级信息,从而支持对任意程序进行透明的、终身 (lifelong) 程序分析与转换的编译器框架。LLVM 定义了一个通用的、低级代码表示 (code representation),采用静态单赋值 (Static Single Assignment, SSA) 形式,并具有几个新颖的特性:一个简单、独立于语言的类型系统 (type-system),它暴露了实现高级语言特性常用的基本操作;一个用于类型化地址算术 (typed address arithmetic) 的指令;以及一个可以统一高效地实现高级语言异常处理 (exception handling) 特性(以及 C 语言中的 setjmp/longjmp)的简单机制。LLVM 编译器框架和代码表示共同提供了一系列关键能力,这些能力对于实用、终身的程序分析与转换至关重要。据作者所知,目前没有其他编译方法能提供所有这些能力。本文描述了 LLVM 表示和编译器框架的设计,并通过三种方式评估了其设计:(a) 表示的大小和有效性,包括其提供的类型信息;(b) 编译器针对几个过程间问题 (interprocedural problems) 的性能;以及 (c) LLVM 为几个具有挑战性的编译器问题带来的益处示例。
1.6. 原文链接
/files/papers/6944c996742e302e037d058b/paper.pdf (请注意,这是一个相对链接,通常需要与基础 URL 结合使用才能访问,例如 https://llvm.org/files/papers/6944c996742e302e037d058b/paper.pdf)
发布状态:已正式发表。
2. 整体概括
2.1. 研究背景与动机
现代应用程序的规模日益增长,其行为在执行过程中会显著变化,支持动态扩展和升级,并且常常包含用多种不同语言编写的组件。传统编译模型通常在编译时或链接时完成大部分优化,这难以适应这些现代应用的需求。
论文试图解决的核心问题是:如何实现对程序透明的、贯穿整个生命周期的(从编译到运行再到空闲时间)高效分析和优化,以最大化程序的效率和灵活性?
这个问题在当前领域是重要的,原因有以下几点:
-
应用复杂性增加: 现代软件的规模和复杂性不断攀升,传统的静态编译优化不足以应对所有场景。
-
动态行为和多语言: 程序在运行时行为可能动态变化,且常由多种语言混合编写,这使得单一的编译时优化难以捕捉所有潜在的性能瓶颈和互操作性问题。
-
硬件演进: 处理器架构不断演进,需要程序能够灵活地适应新硬件,而遗留应用程序也需要在新系统上高效运行。
-
新应用场景: 除了性能优化,程序分析也广泛应用于静态调试、内存泄漏检测、安全强制等领域,这些应用往往需要跨越整个程序的生命周期进行。
现有研究存在的挑战或空白包括:
-
信息丢失: 传统的编译过程会将高级语言信息逐渐丢失,导致后续优化阶段(如运行时)缺乏足够的信息进行深度分析和转换。
-
碎片化优化: 不同的优化阶段(编译时、链接时、运行时)通常使用不同的中间表示或工具,导致优化效果不连贯,且难以进行全局性优化。
-
透明性不足: 许多优化技术要求开发者或用户手动干预,缺乏对程序员透明的自动化机制。
这篇论文的切入点或创新思路是提出一个通用的、低级的、但在整个程序生命周期中都能保留高层语义信息的中间表示 (Intermediate Representation,
IR),并围绕此IR构建一个统一的编译器框架。这个IR足够低级以支持任意语言和系统级代码,但又足够丰富以支持高级分析。
2.2. 核心贡献/主要发现
论文最主要的贡献是提出了 LLVM (Low Level Virtual Machine) 这一编译器框架和其核心的低级代码表示。这个框架旨在提供五个关键能力,而作者声称现有编译方法无法同时提供这些能力:
-
持久的程序信息 (Persistent program information): LLVM 表示在应用程序的整个生命周期中都得以保留,允许在所有阶段(包括运行时和运行间空闲时间)进行复杂的优化。
-
离线代码生成 (Offline code generation): 即使保留了高级表示,也能够使用昂贵的代码生成技术离线编译出高效的原生机器码,这对于性能关键的程序至关重要。
-
基于用户的分析与优化 (User-based profiling and optimization): LLVM 框架在运行时收集代表实际用户行为的性能分析信息,并在运行时和空闲时间利用这些信息进行性能分析指导的转换。
-
透明的运行时模型 (Transparent runtime model): 系统不强制指定任何特定的对象模型、异常语义或运行时环境,从而允许任何语言(或多种语言组合)通过它进行编译。
-
统一的全程序编译 (Uniform, whole-program compilation): 语言独立性使得所有构成应用程序的代码(包括特定语言的运行时库和系统库)在链接后能够以统一的方式进行优化和编译。
论文得出的关键结论或发现包括:
- LLVM 的
IR(即LLVM语言) 能够有效地捕获 语言程序中的类型信息,即使在允许类型转换的语言中,平均68%的内存访问也能获得可靠的类型信息。这使得 LLVM 能够安全地执行许多传统上只在类型安全语言中才尝试的激进转换。 - LLVM
IR的大小与X86机器码相当,平均比RISC机器码小约25%,尽管它捕获了更丰富的类型信息和SSA形式的无限寄存器集。 - LLVM 表示支持极快的过程间优化 (interprocedural optimizations),其优化时间远少于
GCC编译器在单一模块编译时所花费的时间。 - LLVM 框架已成功应用于多个挑战性的编译器问题,如
SAFECode(安全低级代码表示) 和V-ISA(虚拟指令集架构) 设计,证明了其通用性和强大功能。
3. 预备知识与相关工作
3.1. 基础概念
为了理解 LLVM 论文,初学者需要了解以下核心概念:
3.1.1. 编译器 (Compiler)
概念定义: 编译器是一种计算机程序,它将用一种编程语言(称为源语言)编写的源代码转换成另一种编程语言(称为目标语言)的代码。通常,目标语言是机器码或另一种更低级的中间表示,可以被计算机直接执行或进一步处理。 目的: 主要目的是将人类可读的高级代码转换为机器可执行的低级代码,并在此过程中进行优化以提高程序性能。
3.1.2. 编译阶段 (Compilation Phases)
一个典型的编译过程通常包含以下几个阶段:
- 前端 (Front-end): 负责分析源代码的语法和语义,生成中间表示 (Intermediate Representation,
IR)。它通常包括词法分析、语法分析、语义分析。 - 中间表示 (Intermediate Representation,
IR): 编译器在不同阶段之间使用的、介于源代码和目标代码之间的一种数据结构。IR的设计对于编译器的灵活性、可移植性和优化能力至关重要。LLVM 的核心贡献之一就是其独特的IR。 - 优化器 (Optimizer): 对
IR进行各种转换,以提高目标代码的性能(如速度、大小)或资源利用率。优化可以在不同的粒度上进行,如局部优化、全局优化和过程间优化。 - 后端 (Back-end) / 代码生成器 (Code Generator): 将优化后的
IR转换成特定目标机器的机器码。这包括寄存器分配、指令选择和指令调度。 - 链接器 (Linker): 将编译好的多个目标文件(包含机器码和元数据)以及所需的库文件组合成一个可执行文件。
3.1.3. 静态单赋值 (Static Single Assignment, SSA) 形式
概念定义: SSA 是一种 IR 的特性,其中每个变量在程序文本中只被赋值一次。如果一个变量在原始程序中被多次赋值,SSA 形式会引入新的“版本”变量来区分这些赋值,并使用特殊的 (phi) 函数来合并来自不同控制流路径的值。
目的: SSA 形式极大地简化了数据流分析和优化算法的设计,因为它使得变量的定义-使用链 (def-use chains) 变得非常明确。例如,在 SSA 形式下,一个变量的值在任何一点上都只有一个明确的来源。
例子:
原始代码:
x = 1;
if (...) {
x = 2;
} else {
x = 3;
}
y = x + 4;
SSA 形式:
x1 = 1;
if (...) {
x2 = 2;
} else {
x3 = 3;
}
x4 = φ(x2, x3); // φ函数合并来自不同路径的值
y1 = x4 + 4;
3.1.4. 控制流图 (Control Flow Graph, CFG)
概念定义: CFG 是程序的一种抽象表示,它将程序分解为基本块 (basic blocks) 和它们之间的控制流路径。一个基本块是一系列指令,其中控制流只能从第一个指令进入,并只能从最后一个指令离开,且块内没有分支。图中的节点是基本块,边表示控制流的可能转移。
目的: CFG 是编译器进行许多代码优化和分析(如数据流分析)的基础。
3.1.5. 过程间优化 (Interprocedural Optimization)
概念定义: 过程间优化是指在分析和优化程序时考虑多个函数(或过程)之间的相互作用,而不仅仅是单个函数内部的优化。 目的: 它能够发现并利用跨函数边界的优化机会,例如函数内联、死代码消除、过程间常量传播等,从而实现更强大的全局优化。
3.1.6. 链接时优化 (Link-Time Optimization, LTO)
概念定义: LTO 是一种在程序的链接阶段进行的优化。在 LTO 中,编译器将程序的所有模块(通常是编译为 IR 格式而不是机器码)收集起来,然后对整个程序执行优化,就像它是一个单一的源文件一样。
目的: LTO 能够实现比传统编译时优化更深度的过程间优化,因为它可以看到整个程序的代码。
3.1.7. 运行时优化 (Run-Time Optimization, RTO) / 动态优化 (Dynamic Optimization)
概念定义: RTO 是在程序执行期间进行的优化。通常由即时编译器 (Just-In-Time Compiler, JIT) 完成,它会在程序运行时将热点代码(经常执行的代码路径)编译成优化后的机器码,甚至根据运行时数据进行专门的优化。
目的: 能够利用实际的运行时信息(如输入数据、分支预测、内存访问模式)来执行更激进、更有效的优化,这些优化在编译时是无法进行的。
3.1.8. 配置文件引导优化 (Profile-Guided Optimization, PGO)
概念定义: PGO 是一种编译技术,它利用程序在一次或多次执行中收集到的性能配置文件(profile data)来指导后续的优化过程。这些配置文件包含代码执行频率、分支跳转概率、函数调用模式等信息。
目的: 编译器可以根据这些“真实世界”的使用模式来做出更明智的优化决策,例如将最常执行的代码放在一起以改善缓存局部性,或者更激进地内联热点函数。
3.1.9. 透明性 (Transparency)
概念定义: 在编译器或系统设计中,透明性意味着用户(通常是程序员)不需要了解或介入底层实现细节,系统会自动处理这些细节。 目的: 提高用户体验和开发效率,使程序员可以专注于高级逻辑,而不必担心底层优化或资源管理。
3.2. 前人工作
论文在第 5 节“相关工作 (Related Work)”中详细讨论了 LLVM 与现有系统的异同。以下是作者提及的关键先前研究类别及其特点:
-
高级语言虚拟机 (High-level Virtual Machines,
HVMs):- 示例: SmallTalk [18]、Self [43]、JVM [32]、Microsoft's CLI [33]。
- 特点: 这些系统通常具有特定的对象模型和运行时系统,并提供高级类型信息。它们主要关注支持与其设计匹配的语言(如
Java和C#)。为了支持移动代码,通常要求代码是类型安全的,并且在运行时之前需要进行字节码验证,这限制了编译前可进行的优化量。 - 与 LLVM 的区别: LLVM 没有类、继承或异常处理语义等高级概念,也不指定运行时系统或对象模型。它不保证类型安全或内存安全,这使得它能够支持任意语言和非类型安全的低级系统代码。LLVM 专注于终身优化,而
HVMs更侧重于运行时优化和平台无关性。
-
类型化汇编语言 (Typed Assembly Languages,
TALs):- 示例: TAL [35]、LTAL [10]、SafeTSA [3]。
- 特点: 这些研究主要目标是在编译和优化过程中保留高级类型信息并保证类型安全。
SafeTSA结合了类型信息和SSA形式,旨在提供比JVM字节码更高效的表示。 - 与 LLVM 的区别: LLVM 的虚拟指令集不试图保留高级语言的类型安全或直接强制代码安全。它的目标是实现超越静态编译时的复杂分析和转换。LLVM 的类型系统是为了暴露实现细节以供优化,而不是为了强制类型安全。
-
统一、通用中间表示 (Unified, Generic Intermediate Representations):
- 示例: UNCOL [42] (未实现)、ANDF [4] (使用有限)。
- 特点: 这些尝试旨在通过包含所有支持源语言的特性来在
AST(抽象语法树) 级别描述程序。 - 与 LLVM 的区别: LLVM 的野心小得多,它更像一种汇编语言,使用一小组类型和低级操作,高级语言特性的“实现”通过这些低级类型来描述。LLVM 更像一个严格的
RISC架构。
-
链接时或动态优化系统 (Link-Time or Dynamic Optimization Systems):
- 链接时优化器:
- 示例: 商业编译器中的链接时优化器 [21, 5, 26]。
- 特点: 这些系统在链接时进行过程间优化,通常通过导出
IR或注解。 - 与 LLVM 的区别: 这些系统不尝试支持在软件安装到现场后的运行时或离线优化。
- 透明二进制运行时优化系统:
- 示例: Dynamo [6]、Transmeta 处理器中的运行时优化器 [16]。
- 特点: 这些系统透明地优化原生二进制代码。
- 与 LLVM 的区别: 它们直接在机器码上操作,这限制了它们能执行的优化类型,并且它们无法提供 LLVM 所拥有的类型、数据流 (
SSA) 和显式CFG信息。它们通常只在运行时进行有限的优化,不支持链接时、安装时或离线优化。
- 链接时优化器:
-
配置文件引导优化 (Profile-Guided Optimization,
PGO):- 特点: 为静态语言提供
PGO的系统通常需要多阶段编译过程,且其配置文件是静态的,可能无法代表最终用户的实际使用模式或适应动态变化的行为。 - 与 LLVM 的区别: LLVM 的
PGO能够利用最终用户在现场运行时收集的配置文件信息,并在空闲时间进行离线重优化,甚至可以根据不断变化的使用模式多次重优化。
- 特点: 为静态语言提供
3.3. 技术演进
编译技术从最初的静态编译(编译时和链接时优化)发展而来,主要目标是生成高效的机器码。随着软件复杂性增加和硬件多样化,人们开始探索在更晚的阶段进行优化:
-
链接时优化 (
LTO) 出现,以实现跨模块的全局优化。 -
即时编译 (
JIT) 和 运行时优化 (RTO) 在虚拟机(如JVM)中流行,以利用运行时信息和适应性优化。 -
配置文件引导优化 (
PGO) 允许编译器利用实际的程序行为数据进行更有效的静态优化。 -
二进制转换/优化 尝试在机器码层面进行优化,但往往会丢失高级语义信息。
本文的工作
LLVM处于这一技术演进的交汇点,它试图融合并超越这些方法,通过引入一个独特的低级IR,使得所有这些优化阶段(编译时、链接时、运行时、空闲时间)都能获得足够的高级信息,从而实现一种“终身”的程序分析和转换能力。
3.4. 差异化分析
LLVM 的核心创新在于其 IR 和围绕该 IR 构建的多阶段、透明、终身优化框架。与现有方法相比,其核心区别和创新点在于:
-
统一的低级但信息丰富的
IR:- 与
HVMs不同,LLVM 的IR是低级的、语言独立的,不强制特定运行时模型,因此可以支持任意语言(包括非类型安全的 )和系统级代码。 - 与
Omniware或二进制优化系统不同,LLVMIR虽然低级,但保留了丰富的类型信息、显式的SSA形式数据流和CFG,这使得它可以进行高级分析,而不会丢失原始程序的语义。 - 与
TALs不同,LLVM 不强制类型安全,而是提供工具(如DSA)来验证和利用类型信息,这提供了更大的灵活性。
- 与
-
透明的终身优化模型: LLVM 是第一个同时提供以下所有能力的系统:
- 持久的程序信息:
IR在整个程序生命周期中都保留。 - 离线高效代码生成: 可以生成高质量的原生代码。
- 基于用户的配置文件优化: 能够在最终用户系统上收集配置文件并进行优化。
- 透明的运行时模型: 不强制特定语言运行时。
- 统一的全程序编译: 可以优化所有组件,包括系统库。
现有系统要么侧重于一个或几个阶段(如
LTO仅到链接时,JIT仅在运行时),要么在支持任意语言或保留高级信息方面存在局限。LLVM 试图打破这些限制,提供一个真正统一的优化基础设施。
- 持久的程序信息:
4. 方法论
本节将详细拆解 LLVM 的技术方案,包括其独特的代码表示和编译器架构。
4.1. 程序表示 (Program Representation)
LLVM 的代码表示是其区别于其他系统的关键因素。它旨在提供程序所需的高级信息,以支持复杂的分析和转换,同时又足够低级以表示任意程序并允许广泛的静态编译器优化。
4.1.1. LLVM 指令集概述
LLVM 指令集捕获了普通处理器的关键操作,但避免了机器特定的约束,例如物理寄存器、流水线和低级调用约定。
- 虚拟寄存器: LLVM 提供无限数量的类型化虚拟寄存器 (typed virtual registers),可以保存基本类型(布尔、整数、浮点数和指针)的值。
- SSA 形式: 虚拟寄存器采用静态单赋值 (
SSA) 形式,这意味着每个虚拟寄存器只被一个指令写入,并且对寄存器的每次使用都由其定义所支配。 - 加载/存储架构 (Load/Store Architecture): 程序通过使用类型化指针的加载 (load) 和存储 (store) 操作,在寄存器和内存之间传输值。LLVM 的内存模型将在后续小节中描述。
- 精简的指令集: 整个 LLVM 指令集仅包含
31个操作码。这是因为:- 避免了同一操作的多个操作码。
- 大多数操作码都是重载的(例如,
add指令可以操作任何整数或浮点操作数类型)。 - 大多数指令(包括所有算术和逻辑操作)采用三地址形式:它们接受一个或两个操作数并产生一个结果。
phi指令: LLVM 指令集包含一个显式的phi指令,它直接对应于SSA形式的标准(非门控) 函数,用于合并来自不同控制流路径的值。- 显式控制流图 (
CFG): LLVM 在表示中明确了每个函数的CFG。一个函数是一组基本块 (basic blocks),每个基本块是一系列 LLVM 指令,以一个终止指令(branches,return,unwind, 或invoke)结束。每个终止指令都明确指定其后续基本块。 - 内存的 SSA 形式例外: 内存位置在 LLVM 中不采用
SSA形式,因为通过指针的一次存储可能修改许多可能的位置,这使得为这些位置构建合理紧凑、显式的SSA代码表示变得困难。
4.1.2. 语言无关的类型信息、类型转换和 GetElementPtr
LLVM 的一个基本设计特征是包含了语言无关的类型系统。
-
严格类型规则: 每个
SSA寄存器和显式内存对象都具有关联的类型,并且所有操作都遵循严格的类型规则。 -
类型信息的作用: 这种类型信息与指令操作码结合使用,以确定指令的确切语义(例如,浮点加法与整数加法)。它还支持对低级代码进行广泛的高级转换,并有助于检测优化器错误。
-
原始类型: LLVM 类型系统包括预定义大小的源语言无关原始类型(
void、bool、8到64位的有符号/无符号整数,以及单精度和双精度浮点类型)。 -
派生类型: LLVM 只包括四种派生类型:
pointers(指针)、arrays(数组)、structures(结构体) 和functions(函数)。作者认为大多数高级语言数据类型最终都通过这四种类型的某种组合来表示其操作行为。例如,具有继承的 类使用结构体、函数和函数指针数组来实现。 -
捕获分析所需信息: 这四种派生类型捕获了复杂、语言无关的分析和优化所需的类型信息。例如,字段敏感的指向分析 (field-sensitive points-to analyses) [25, 31]、调用图构建 (call graph construction)、聚合体的标量提升 (scalar promotion of aggregates) 和结构体字段重排 (structure field reordering) 转换 [12] 仅使用指针、结构体、函数和原始数据类型。
-
cast指令: LLVM 的cast指令用于将一个类型的值转换为另一个任意类型,并且是执行此类转换的唯一方式。这使得所有类型转换都显式化,包括类型强制转换、物理子类型 (physical subtyping) 的显式转换以及非类型安全代码的重解释转换。一个不含cast的程序在没有内存访问错误的情况下,必然是类型安全的。 -
getelementptr指令: 这是 LLVM 系统用于执行指针算术的指令,它既保留了类型信息,又具有机器无关的语义。- 目的: 给定一个指向某种聚合类型对象的类型化指针,此指令以类型保留的方式计算对象子元素的地址(相当于 LLVM 的组合
.和[]运算符)。 - 例子: C 语言语句 可以转换为一对 LLVM 指令:
这里假设 是结构体%p = getelementptr %xty* %X, long %i, ubyte 3 store int 1, int* %p;X[i]中字段编号为3的字段,并且该结构体是%xty类型。 - 重要性: 使所有地址算术显式化非常重要,以便将其暴露给所有 LLVM 优化(最重要的是重关联 (reassociation) 和冗余消除 (redundancy elimination));
getelementptr在不模糊类型信息的情况下实现了这一点。load和store指令接受单个指针,不执行任何索引操作,这使得内存访问的处理简单而统一。
- 目的: 给定一个指向某种聚合类型对象的类型化指针,此指令以类型保留的方式计算对象子元素的地址(相当于 LLVM 的组合
4.1.3. 显式内存分配和统一内存模型
- 内存分配指令: LLVM 提供了类型化内存分配指令。
malloc指令:在堆上分配特定类型的一个或多个元素,返回一个指向新内存的类型化指针。free指令:释放通过malloc分配的内存。alloca指令:类似于malloc,但它在当前函数的栈帧 (stack frame) 中分配内存,并在函数返回时自动释放。所有栈驻留数据(包括“自动”变量)都使用alloca显式分配。
- 统一内存模型: 在 LLVM 中,所有可寻址对象(“lvalues”)都显式分配。全局变量和函数定义一个符号,该符号提供对象的地址,而不是对象本身。这提供了一个统一的内存模型,其中所有内存操作,包括调用指令,都通过类型化指针发生。没有隐式内存访问,简化了内存访问分析,并且表示不需要“取址 (address of)”运算符。
4.1.4. 函数调用和异常处理
call指令: 对于普通函数调用,LLVM 提供了call指令,它接受一个类型化的函数指针(可以是函数名或实际的指针值)和类型化的实际参数。这抽象了底层机器的调用约定,简化了程序分析。- 异常处理机制 (
invoke和unwind): LLVM 最不寻常的特性之一是它提供了一个显式的、低级的、机器无关的机制来实现高级语言中的异常处理。这个机制也支持 C 语言中的setjmp和longjmp操作。-
invoke指令: 行为类似于call,但它指定了一个额外的基本块,该基本块指示异常处理器 (unwind handler) 的起始块。当程序执行unwind指令时,它逻辑上解开栈 (unwinds the stack),直到移除由invoke创建的激活记录 (activation record)。然后,它将控制权转移到invoke指定的基本块。 -
unwind指令: 用于抛出异常或执行longjmp。 -
暴露异常控制流: 这两个指令在 LLVM 的
CFG中暴露了异常控制流。 -
实现 异常的例子: 以下是原文 Figure 1 的代码片段,展示了一个 中需要生成“清理代码”的例子:
{ AClass Obj; // Has a destructor func(); // Might throw; must execute destructor }如果
func()调用抛出异常, 保证Object对象的析构函数会被运行。为了实现这一点,使用invoke指令来停止解开栈,运行析构函数,然后使用unwind指令继续解开栈。 以下是原文 Figure 2 所示的生成的 LLVM 代码:; Allocate stack space for object: %Obj = alloca %AClass, uint 1 ; Construct object: call void %AClass::AClass(%AClass* %Obj) ; Call "func()": invoke void %func() to label %OkLabel unwind to label %ExceptionLabel OkLabel: ; ... execution continues... ExceptionLabel: ; If unwind occurs, excecution continues ; here. First, destroy the object: call void %AClass::~AClass(%AClass* %Obj) ; Next, continue unwinding: unwind -
与运行时库结合: 异常处理模型非常复杂。LLVM 通过语言前端生成对简单运行时库的调用来支持这些语义。运行时库处理所有实现细节(如为异常分配内存)并操纵异常处理运行时的线程局部状态。
-
以下是原文 Figure 3 所示的 异常
throw 1的 LLVM 代码片段:
该图像是一个代码片段,展示了LLVM代码在运行时库中分配异常对象和处理异常的过程。代码首先调用 %__llvm_cxxeh_alloc_exc(uint 4) 分配异常对象,并将整数值抛出,随后进行栈的卸载。相关的操作通过简单的注释解释,并利用了控制流的特点。这个例子说明了 LLVM 如何利用运行时库来处理特定语言的复杂异常语义,同时通过
invoke和unwind指令在CFG中显式暴露异常控制流,让优化器能够进行分析。
-
4.1.5. 纯文本、二进制和内存表示
LLVM 表示是一种头等 (first class) 语言,它定义了等效的纯文本、二进制和内存(即编译器的内部)表示。指令集旨在有效地用作持久的离线代码表示和编译器内部表示,两者之间不需要语义转换。能够在这些表示之间无损地转换 LLVM 代码,使得调试转换变得更简单,易于编写测试用例,并减少了理解内存表示所需的时间。
4.2. 编译器架构 (Compiler Architecture)
LLVM 编译器框架的目标是实现链接时、安装时、运行时和空闲时间的复杂转换,通过在所有阶段操作 LLVM 表示的程序。同时,它必须对应用程序开发人员和最终用户透明,并且足够高效以用于实际应用。
4.2.1. LLVM 编译器框架的高级设计
以下是原文 Figure 4 所示的 LLVM 系统架构图:
该图像是LLVM系统架构示意图,展示了编译器前端、链接器、库及代码生成模块之间的关系。图中涵盖了包括CPU和JIT的运行时优化器及离线重优化器,说明了LLVM在程序分析与转换中的结构与流程。
LLVM 系统的高级架构如上图所示。简而言之:
-
静态编译器前端 (Static Compiler Front-ends): 将源代码程序编译成 LLVM 表示。
-
LLVM 链接器 (LLVM Linker): 将多个 LLVM 模块组合在一起,并执行各种链接时优化,特别是过程间优化。
-
原生代码生成 (Native Code Generation): 结果 LLVM 代码随后在链接时或安装时翻译成给定目标的原生代码,并且 LLVM 代码与原生代码一起保存。
-
即时编译器 (Just-In-Time Translator): 也可以在运行时使用
JIT翻译器来翻译 LLVM 代码。 -
运行时优化 (Runtime Optimization): 原生代码生成器插入轻量级插桩 (instrumentation) 来检测频繁执行的代码区域(当前是循环嵌套和跟踪,但可能也包括函数)。
-
离线重优化器 (Offline Reoptimizer): 运行时收集的配置文件数据代表最终用户的运行情况,可以由离线优化器在空闲时间在现场进行激进的配置文件引导优化,以适应特定目标机器。
这种策略提供了五个优势:
-
持久的程序信息 (Persistent program information):
IR在整个生命周期保留。 -
离线代码生成 (Offline code generation): 可以生成高质量原生代码。
-
基于用户的配置文件优化 (User-based profiling and optimization): 利用最终用户数据进行优化。
-
透明的运行时模型 (Transparent runtime model): 不强制特定运行时。
-
统一的全程序编译 (Uniform, whole-program compilation): 统一优化所有代码。
4.2.2. 编译时:外部前端和静态优化器
- 前端任务: 外部静态 LLVM 编译器(即前端)将源语言程序转换为 LLVM 虚拟指令集。每个静态编译器可以执行三个关键任务:
- 执行特定语言的优化(可选),例如优化高阶函数中的闭包。
- 将源程序翻译成 LLVM 代码,尽可能合成有用的 LLVM 类型信息,特别是暴露指针、结构体和数组。
- 在模块级别调用 LLVM 通道 (passes) 进行全局或过程间优化(可选)。LLVM 优化被构建为库,方便前端使用。
- SSA 构建: 前端不必执行
SSA构造。相反,变量可以在栈上分配(非SSA形式),然后使用 LLVM 的栈提升 (stack promotion) 和标量扩展 (scalar expansion) 通道来有效地构建SSA形式。栈提升将栈分配的标量值转换为SSA寄存器,如果它们的地址未逃逸当前函数,则必要时插入 函数。标量扩展在此之前进行,尽可能将局部结构体扩展为标量,以便它们的字段也可以映射到SSA寄存器。
4.2.3. 链接器和过程间优化器
链接时是编译过程中大多数程序可用于分析和转换的第一个阶段。因此,链接时是执行激进过程间优化的理想场所。LLVM 中的链接时优化直接作用于 LLVM 表示,利用其包含的语义信息。
- LLVM 包含的分析和转换: LLVM 目前包括多项过程间分析,例如上下文敏感的指向分析 (
Data Structure Analysis[31])、调用图构建 (call graph construction) 和Mod/Ref分析。以及过程间转换,如内联 (inlining)、死全局消除 (dead global elimination)、死参数消除 (dead argument elimination)、死类型消除 (dead type elimination)、常量传播 (constant propagation)、数组越界检查消除 [28]、简单结构体字段重排 (structure field reordering) 和自动池分配 (Automatic Pool Allocation) [30]。 - 加速过程间分析: LLVM 的编译时和链接时优化器设计允许使用一种加速过程间分析的常用技术:在编译时为程序中的每个函数计算过程间摘要 (interprocedural summaries),并附加到 LLVM 字节码。链接时过程间优化器可以直接处理这些摘要,而无需从头计算结果。这大大加速了增量编译。
4.2.4. 离线或 JIT 原生代码生成
在执行之前,代码生成器以两种方式之一将 LLVM 转换为目标平台的原生代码(当前支持 Sparc V9 和 x86 架构)。
- 静态代码生成: 代码生成器在链接时或安装时静态运行,为应用程序生成高性能的原生代码,可能使用昂贵的代码生成技术。如果用户选择使用链接后(运行时和离线)优化器,程序的 LLVM 字节码副本会包含在可执行文件中。此外,代码生成器在程序中插入轻量级插桩以识别频繁执行的代码区域。
- 即时执行引擎 (
JIT Execution Engine): 另一种选择是使用JIT执行引擎,它在运行时调用适当的代码生成器,一次翻译一个函数进行执行(如果原生代码生成器不可用,则使用可移植的 LLVM 解释器)。JIT翻译器也可以插入与离线代码生成器相同的插桩。
4.2.5. 运行时路径分析与重优化
LLVM 项目的目标之一是开发一种新的通用应用程序运行时优化策略。
- 热点路径识别: 随着程序执行,通过离线和在线插桩的组合来识别最频繁执行的执行路径。离线插桩(由原生代码生成器插入)识别代码中频繁执行的循环区域。当在运行时检测到热点循环区域时,运行时插桩库会插桩正在执行的原生代码,以识别该区域内频繁执行的路径。
- 轨迹优化: 一旦识别出热点路径,LLVM 将原始 LLVM 代码复制到一条轨迹 (trace) 中,对其执行 LLVM 优化,然后将原生代码重新生成到软件管理的轨迹缓存 (trace cache) 中。然后,在原始代码和新的原生代码之间插入分支。
- 优势: 这种策略结合了:
- 原生代码生成可以提前进行,使用复杂的算法生成高性能代码。
- 原生代码生成器和运行时优化器可以协同工作,因为它们都属于 LLVM 框架。
- 运行时优化器可以利用 LLVM 表示中的高级信息执行复杂的运行时优化。
4.2.6. 基于最终用户配置文件信息的离线重优化
由于 LLVM 表示被永久保留,它使得在最终用户系统上利用空闲时间进行透明的离线应用程序优化成为可能。这种优化器只是链接时过程间优化器的修改版本,但更侧重于配置文件引导和目标特定的优化。
- 关键优势:
- 可以使用从最终用户运行应用程序中收集的配置文件信息,甚至可以多次重优化以响应随时间变化的使用模式。
- 可以将代码定制到单个目标机器的详细特性,而传统的二进制代码分发通常必须在许多不同机器配置上运行。
- 可以执行比运行时优化器更激进的优化,因为它是在离线运行的。
5. 实验设置
本节将评估 LLVM 设计的三个方面:表示的特性、编译器执行全程序分析和转换的速度,以及 LLVM 如何解决一些具有挑战性的编译器问题。
5.1. 数据集
实验主要使用了以下数据集:
- SPEC CPU2000 C 基准测试 (SPEC CPU2000 C benchmarks): 这是一套广泛用于评估处理器和编译器性能的基准程序集合。
- 特点: 包含一系列真实的、计算密集型的 C 语言程序,涵盖了各种应用领域。
- 选择原因: 它们代表了业界和学术界公认的、具有挑战性的真实世界应用程序,可以有效验证 LLVM 在通用 C 程序上的表现。
- Olden 和 Ptrdist 基准测试: 这两套基准测试程序以其结构化良好的指针使用和类型行为而闻名。
- 特点: 这些程序通常以更规范的编程风格编写,对类型的使用更加严格。
- 选择原因: 用于展示在“更规范”的程序中,LLVM 捕获类型信息的有效性。
5.2. 评估指标
论文使用了多种指标来评估 LLVM 的设计。
5.2.1. 类型化访问百分比 (Typed Accesses Percentage)
- 概念定义: 这个指标量化了在程序的所有静态内存加载 (load) 和存储 (store) 操作中,有多少比例的访问能够通过分析(如
DSA)获得可靠的类型信息。一个高百分比表明IR能够有效保留并允许编译器推断出重要的类型信息,即使在允许类型不安全的语言中。 - 数学公式:
- 符号解释:
- :能够被
DSA证明其访问对象类型是可靠的静态内存访问指令(load或store)的数量。 - :程序中所有静态内存访问指令(
load或store)的总数。
- :能够被
5.2.2. 代码大小 (Code Size)
- 概念定义: 衡量编译后的 LLVM
IR文件在磁盘上的大小,与原生机器码进行比较。较小的IR大小意味着存储和传输效率更高,对于终身保留程序信息至关重要。 - 数学公式: 无特定数学公式,通常直接以字节 (Bytes) 或千字节 (KB) 为单位进行报告。
- 符号解释: 直接反映了
IR的存储开销。
5.2.3. 过程间优化时间 (Interprocedural Optimization Timings)
- 概念定义: 衡量 LLVM 编译器执行各种过程间分析和转换所需的时间。此指标直接反映了 LLVM
IR支持高效优化的能力,尤其是在链接时和运行时等对性能敏感的阶段。 - 数学公式: 无特定数学公式,直接报告以秒 (seconds) 为单位的执行时间。
- 符号解释:
DGE(Dead Global variable and function Elimination,死全局变量和函数消除) 的耗时、DAE(Dead Argument and return value Elimination,死参数和返回值消除) 的耗时、inline(函数内联) 的耗时。
5.2.4. 编译器性能 (Compiler Performance)
- 概念定义: 指的是 LLVM 编译器本身执行编译和优化任务的速度,而不是生成代码的运行时性能。这个指标对于衡量编译框架的实用性至关重要,特别是在需要快速反馈的场景(如
JIT编译或增量优化)。 - 数学公式: 无特定数学公式,以秒 (seconds) 为单位报告。
- 符号解释: 在
Table 2中,GCC列代表了GCC 3.3编译器在-O3优化级别下编译整个程序所花费的总时间,作为一个参考基线。
5.3. 对比基线
在不同的评估维度上,LLVM 与以下系统或数据进行了对比:
- 代码大小对比:
- X86 机器码: 一种
CISC架构,指令集密度较高,指令长度可变。 - 32 位 SPARC 机器码: 一种传统
RISC架构,指令长度固定。 - 选择原因: 这些是两种代表性的主流硬件架构的机器码,用于评估 LLVM
IR在存储效率方面的相对表现。
- X86 机器码: 一种
- 优化时间对比:
- GCC 3.3 编译器 (
-O3优化级别): 一个广泛使用的静态编译器。 - 选择原因: 作为
GCC在进行其自身优化(不进行跨模块优化或很少的过程间优化)时的总编译时间的参考,以展示 LLVM 过程间优化的效率。
- GCC 3.3 编译器 (
- 能力集合对比(引言和相关工作部分):
- 传统源级编译器: 如
GCC。 - 链接时过程间优化器: 商业编译器中常见的系统。
- 高级虚拟机 (HVMs): 如
JVM,CLI。 - 透明二进制运行时优化系统: 如
Dynamo。 - 配置文件引导优化 (PGO) 系统: 针对静态语言的
PGO。 - 选择原因: 用于论证 LLVM 在其声称的五个关键能力(持久信息、离线代码生成、用户配置文件优化、透明运行时、统一全程序编译)上超越了所有现有系统。
- 传统源级编译器: 如
6. 实验结果与分析
6.1. 核心结果分析
6.1.1. 类型信息提供价值
LLVM 的关键设计之一是其语言无关的类型系统。通过 Data Structure Analysis (DSA) [31],LLVM 能够从代码中提取和验证内存对象的类型信息。
以下是原文 Table 1 的结果,展示了 SPEC CPU2000 C 基准测试中可证明为类型化的加载和存储操作的比例:
| Benchmark Name | Typed Accesses | Untyped Accesses | Typed Percent |
|---|---|---|---|
| 164.gzip | 1654 | 61 | 96.4% |
| 175.vpr | 4038 | 371 | 91.6% |
| 176.gcc | 25747 | 33179 | 43.7% |
| 177.mesa | 2811 | 19668 | 12.5% |
| 179.art | 572 | 0 | 100.0% |
| 181.mcf | 571 | 0 | 100.0% |
| 183.equake | 799 | 114 | 87.5% |
| 186.crafty | 9734 | 383 | 96.2% |
| 188.ammp | 2109 | 2598 | 44.8% |
| 197.parser | 1577 | 2257 | 41.1% |
| 253.perlbmk | 9678 | 22302 | 30.3% |
| 254.gap | 6432 | 15117 | 29.8% |
| 255.vortex | 13397 | 8915 | 60.0% |
| 256.bzip2 | 1011 | 52 | 95.1% |
| 300.twolf | 13028 | 1196 | 91.6% |
| average | 68.04% |
分析:
- 高比例的类型化访问: 即使对于 C 语言程序(它不鼓励严格的类型使用),许多基准测试(如
164.gzip,175.vpr,179.art,181.mcf,183.equake,186.crafty,256.bzip2,300.twolf)仍然显示出令人惊讶的高比例(87.5%到100%)具有可靠类型信息的内存访问。这对于进行激进优化(如内存管理优化)至关重要。 - 影响类型信息丢失的原因:
- 自定义内存分配器: 在
197.parser,254.gap,255.vortex中,自定义分配器的使用是导致类型信息丢失的主要原因。 - 非类型安全编程构造: 在
176.gcc,253.perlbmk,254.gap中,在不同地方对同一对象使用不同的结构体类型,以及 转换等 C 语言技巧,导致类型信息难以验证。 - DSA 的不精确性: 在
177.mesa和188.ammp中,DSA自身的局限性导致了部分不精确性。
- 自定义内存分配器: 在
- 总体结论: 尽管存在这些挑战,
DSA平均仍能验证68%的内存访问的类型信息。这表明 LLVM 的IR和相关分析能够从低级代码中提取出足够的高级信息,以支持通常只在类型安全语言中才安全进行的激进转换。这验证了 LLVM 在保留高级语义信息方面的有效性。
6.1.2. 高级特性到 LLVM 的映射
论文通过 语言作为示例,说明了其复杂的高级特性如何清晰地映射到 LLVM IR,从而允许有效的分析和优化:
-
隐式调用和参数: 如复制构造函数和
this指针,在 LLVM 中都被显式化。 -
模板: 在生成 LLVM 代码之前由 前端完全实例化。
-
基类: 扩展为嵌套结构体类型。例如,具有多重继承的 类,LLVM 类型会包含所有基类的成员。
-
虚函数表 (vtable): 表示为全局的、常量函数指针数组,以及类的
type-id对象。这使得 LLVM 优化器可以有效地执行虚方法调用解析。 -
C++ 异常: 转换为
invoke和unwind指令,将异常控制流暴露在CFG中,允许链接时进行过程间分析以消除未使用的异常处理器。这表明 LLVM 虽然是低级的,但其设计允许前端将高级语言特性以一种对优化友好的方式映射过来,从而保留了足够的语义信息。
6.1.3. LLVM 表示的紧凑性
由于编译后的程序代码在整个生命周期中都以 LLVM 表示存储,因此其大小不宜过大。
以下是原文 Figure 5 所示的 LLVM、X86 和 Sparc 可执行文件大小对比图:
分析:
- 与 X86 相当: LLVM 代码的大小与原生
X86可执行文件(一种更密集的、可变大小指令集)大致相同。 - 小于 SPARC: LLVM 代码明显小于
SPARC(一种传统的32位RISC机器)可执行文件,平均小约25%。 - 令人满意的结果: 考虑到 LLVM 编码了无限寄存器集、丰富的类型信息、控制流信息和数据流 (
SSA) 信息(这些是原生可执行文件不具备的),这个结果是非常好的。 - 未来改进空间:
- 当前,大型程序编码效率较低,因为它们在任何一点上都有更多的可用寄存器值,使得指令更难适应
32位编码。当指令不适合32位编码时,LLVM 会回退到64位或更大的编码。 - 通用的文件压缩工具(如
bzip2)能够将字节码文件大小减少到未压缩大小的约50%,这表明仍有很大的改进空间。
- 当前,大型程序编码效率较低,因为它们在任何一点上都有更多的可用寄存器值,使得指令更难适应
6.1.4. LLVM 的执行速度
LLVM IR 的低级特性、统一的指令集、显式的 CFG 和 SSA 表示,以及精心实现的数据结构,使得分析和转换非常高效。这种速度对于编译过程后期(链接时或运行时)的使用至关重要。
以下是原文 Table 2 的结果,展示了几个过程间优化的运行时长(单位:秒):
| Benchmark | DGE | DAE | inline | GCC |
|---|---|---|---|---|
| 164.gzip | 0.0018 | 0.0063 | 0.0127 | 1.937 |
| 175.vpr | 0.0096 | 0.0082 | 0.0564 | 5.804 |
| 176.gcc | 0.0496 | 0.1058 | 0.6455 | 55.436 |
| 177.mesa | 0.0051 | 0.0312 | 0.0788 | 20.844 |
| 179.art | 0.0002 | 0.0007 | 0.0085 | 0.591 |
| 181.mcf | 0.0010 | 0.0007 | 0.0174 | 1.193 |
| 183.equake | 0.0000 | 0.0009 | 0.0100 | 0.632 |
| 186.crafty | 0.0016 | 0.0162 | 0.0531 | 9.444 |
| 188.ammp | 0.0200 | 0.0072 | 0.1085 | 5.663 |
| 197.parser | 0.0021 | 0.0096 | 0.0516 | 5.593 |
| 253.perlbmk | 0.0137 | 0.0439 | 0.8861 | 25.644 |
| 254.gap | 0.0065 | 0.0384 | 0.1317 | 18.250 |
| 255.vortex | 0.1081 | 0.0539 | 0.2462 | 20.621 |
| 256.bzip2 | 0.0015 | 0.0028 | 0.0122 | 1.520 |
| 300.twolf | 0.0712 | 0.0152 | 0.1742 | 11.986 |
分析:
- 优化速度快: 在所有情况下,LLVM 执行过程间优化(
DGE:死全局变量和函数消除,DAE:死参数和返回值消除,inline:函数内联)所需的时间都大大少于GCC编译器在-O3级别编译程序所需的总时间。 - 对比优势:
GCC尽管是强大的编译器,但它没有进行跨模块优化,并且在单个翻译单元内进行的过程间优化也很少。LLVM 在整个程序层面执行这些优化,却能以更快的速度完成。 - 线性扩展性: 过程间优化时间与执行的转换数量大致呈线性关系。例如,
DGE从255.vortex中消除了331个函数和557个全局变量,DAE从176.gcc中消除了103个参数和96个返回值,而inline在176.gcc中内联了1368个函数。 - 结论: 这些结果表明 LLVM
IR和其框架能够支持极其高效的全程序分析和转换,这对于在链接时、运行时甚至离线空闲时间进行深度优化至关重要。
6.2. 利用 LLVM 终身分析和优化能力的应用
论文通过几个例子说明了 LLVM 的能力如何解决各种编译器问题。
6.2.1. 将 LLVM 作为通用编译器基础设施
- 数据结构分析 (
DSA) 和自动池分配 (Automatic Pool Allocation) [30]: 这些技术在 LLVM 中实现,用于分析和转换程序的逻辑数据结构。它们受益于 LLVM 的几个特性:- 链接时可用性: 这些技术只有在程序大部分可用时(即链接时)才有效。
- 类型信息: 指针和结构体等类型信息对其有效性至关重要。
- 源语言无关: 这些技术独立于源语言。
- SSA 形式:
SSA显著提高了DSA的精度。
- 其他研究者应用: 其他研究人员也积极使用 LLVM 作为:
- 二进制到二进制转换的中间表示。
- 支持基于硬件的轨迹缓存和优化系统的编译器后端。
- 网格程序 (Grid programs) 运行时优化和适应的基础。
- 新型编程语言的实现平台。
6.2.2. SAFECode:一个安全的低级表示和执行环境
- 目标:
SAFECode旨在通过静态分析在SAFECode表示中强制执行内存安全,使用自动池分配的变体代替垃圾回收 [19],并通过广泛的过程间静态分析来最小化运行时检查 [28, 19]。 - LLVM 能力的利用:
- 代码表示: 直接使用 LLVM 代码表示来分析 和 程序,这对于嵌入式软件、中间件和系统库至关重要。
- 类型信息: 依赖 LLVM 中的类型信息(无需语法更改)来检查和强制类型安全。
- 数组类型信息: 依赖 LLVM 中的数组类型信息来强制数组边界安全,并通过过程间分析在许多情况下消除运行时边界检查 [28]。
- 链接时框架: 利用链接时框架进行过程间安全检查技术,保留了单独编译的优势。
6.2.3. 虚拟指令集计算机 (Virtual Instruction Set Computers) 的外部 ISA 设计
- 概念: 虚拟指令集计算机 [40, 16, 2] 是一种处理器设计,使用两个不同的指令集:一个外部可见的虚拟指令集 (
V-ISA) 作为所有软件的程序表示,以及一个隐藏的实现特定指令集 (I-ISA) 作为实际的硬件ISA。一个与硬件共同设计的软件翻译器透明地将V-ISA代码转换为I-ISA执行。 - LLVM 在其中的作用: 作者认为扩展版 LLVM 指令集可以作为这种处理器设计的外部
V-ISA的良好选择 [2]。- 低级但信息丰富: LLVM 代码表示足够低级以表示任意外部软件(包括操作系统代码),但又提供了足够丰富的信息来支持翻译器中的复杂编译器技术。
- 离线和在线翻译: 能够进行离线和在线翻译,这被
OS无关的翻译策略所利用。
7. 总结与思考
7.1. 结论总结
本文描述了 LLVM 这一开创性的编译框架,它旨在实现对程序的透明、终身程序分析与转换。LLVM 的核心是其独特的低级、类型化、基于 SSA 的指令集作为程序的持久表示,同时不强加特定的运行时环境。这种表示方式是语言独立的,使得应用程序的所有代码,包括系统库和用不同语言编写的部分,都能够被统一编译和优化。LLVM 编译器框架被设计为在软件生命周期的所有阶段都允许优化,包括广泛的静态优化、利用 LLVM 代码信息进行的在线优化,以及利用从现场用户那里收集的配置文件信息进行的空闲时间优化。目前的实现包括一个强大的链接时全局和过程间优化器、一种用于运行时优化的低开销轨迹跟踪技术,以及即时 (JIT) 和静态代码生成器。
实验证明,LLVM 即使对于 语言程序也能提供广泛的类型信息,这使得安全地执行许多传统上只在类型安全语言的源级编译器中才尝试的激进转换成为可能。LLVM IR 的大小与 X86 机器码相当,平均比 SPARC 代码小约 25%,尽管它捕获了更丰富的类型信息和 SSA 形式的无限寄存器集。此外,LLVM 上的全程序优化效率极高。
7.2. 局限性与未来工作
论文作者指出了以下局限性:
-
语言特定优化: 语言特定的优化必须在前端生成 LLVM 代码之前完成,因为 LLVM 并不直接表示源语言类型或特性。
-
复杂运行时系统语言的适用性: 对于需要复杂运行时系统的语言(如
Java),LLVM 是否能直接受益尚不明确。未来可能的研究方向:
-
探索 LLVM 是否能有效地实现像
JVM或CLI这样的高级虚拟机。 -
进一步研究和优化 LLVM 的编码效率,特别是对于大型程序,以减少
IR文件大小。 -
持续改进
DSA和其他分析技术的精度,以在更多程序中获得更可靠的类型信息。 -
完善运行时优化策略,使其能与离线重优化协调工作,以确保实现最高性能。
7.3. 个人启发与批判
7.3.1. 个人启发
这篇论文提供了一个极具前瞻性和影响力的编译框架设计。对我而言,最主要的启发在于:
- “终身”优化理念: 将优化视为一个贯穿程序整个生命周期的持续过程,而非仅仅停留在编译阶段,这极大地拓展了优化的可能性和效果。这种理念在现代软件开发中愈发重要,因为软件部署环境和使用模式日益多样。
IR设计的重要性: LLVM 的成功充分证明了IR设计在编译器中的核心地位。一个好的IR必须在“低级通用性”和“高级语义保留”之间找到平衡点。LLVM 的IR既足够低级以支持任意语言和系统代码,又通过SSA、显式CFG和语言无关的类型系统保留了足够的高级信息,这正是其成功的基石。- 模块化与可扩展性: LLVM 框架的模块化设计(前端、链接器、优化器、代码生成器等分离)以及优化作为库的提供,使其极具可扩展性。这使得 LLVM 能够被广泛应用于各种研究和工业项目中,成为一个通用的编译器基础设施。
- 实际效益: 论文通过实验数据(如类型信息提取、代码紧凑性、优化速度)有力地证明了其设计的实际效益,而不仅仅是理论上的创新。
7.3.2. 批判与潜在问题
尽管 LLVM 框架非常出色,但仍有一些可以探讨的潜在问题或可以改进的地方:
-
类型信息的局限性: 尽管
DSA能提取相当多的类型信息,但 语言的本质特性(如指针的随意转换、底层内存操作)决定了总会有部分内存访问无法获得可靠的类型信息。这限制了某些激进优化(如严格的内存安全检查)的普适性。对于追求极致性能和安全的应用,如何在这些“Untyped Accesses”上做出权衡,或开发更强大的类型推断/验证技术,仍是一个挑战。 -
JIT编译的延迟: 论文中提到JIT可以在运行时翻译函数。虽然JIT能利用运行时信息进行优化,但其本身的编译开销可能会引入启动延迟,这对于某些对启动时间敏感的应用程序可能是一个问题。如何平衡JIT的优化收益和运行时开销,特别是对于短生命周期的程序,是一个持续的研究领域。 -
配置文件的代表性问题: 配置文件引导优化 (
PGO) 依赖于收集到的用户配置文件。如果训练运行 (training run) 的模式与最终用户的实际使用模式不符,优化效果可能会下降,甚至可能适得其反。LLVM 提出在空闲时间进行重优化,但如何确保收集到的配置文件具有高度代表性,并能适应用户行为的长期演变,仍然是一个开放问题。 -
与高级语言运行时系统的集成: 论文提到正在探索将
JVM和CLI等高级虚拟机构建在 LLVM 之上。这确实是一个有前景的方向,但这些高级运行时系统有其自身的垃圾回收、线程模型、安全沙箱等复杂特性,如何将这些特性高效地映射到 LLVM 的低级IR,并在性能和语义上保持一致,将是巨大的工程挑战。 -
调试复杂性: 尽管 LLVM
IR具有纯文本表示,有助于调试优化过程,但在JIT和多阶段优化(尤其是运行时重优化)的复杂环境中,程序的实际执行路径可能会动态变化,这可能给传统的调试工具和技术带来新的挑战。总而言之,这篇论文为现代编译器设计奠定了坚实的基础,并提出了许多富有远见的理念。LLVM 的成功实践证明了其设计的卓越性,但其中提出的许多问题也为未来的研究指明了方向。
相似论文推荐
基于向量语义检索推荐的相关论文。