LLVM: AN INFRASTRUCTURE FOR MULTI-STAGE OPTIMIZATION阅读笔记

Abstract

看的出写这篇论文的动机，或者说写LLVM动机是提出新的编译框架来解决编译时间过长的问题。

LLVM的设计特点：

It is a low-level representation, but with high-level type information.

1. Introduction

This thesis describes the Low-Level Virtual Machine (LLVM), a compiler infrastructure which is well-suited for modern programming languages and architectures. LLVM is designed to achieve three critical goals:

1. Enable an aggressive multi-stage optimization strategy, providing maximum performance.
2. Serve as the host for leading edge research and development, providing a strong foundation for both current and future projects.
3. Operate transparently to the end-user (a developer), behaving identically to a standard system compiler (including realistic compilation times).

第一点不知道是不是就变成了现在的LLVM里的pass了。第二条看来是很有野心，但是我很想知道他如何能做到，如何为前沿研究服务呢？

LLVM is designed to address one simple observation: human patience is limited.

简单的说就是“懒，推动科技进步”，哈哈哈哈！🤣🤣🤣

1.1.1 Traditional Approaches to Link-Time Interprocedural Optimization

文章把当时的Link-Time Interprocedural优化（即在链接的时候，把尽可能多的程序聚集在一起，增大分析的范围，然后进行优化）分成两类，

1. 底层——机器码的层次

   优点：任何前端都可以（只要能编成正确的机器码）。缺点：缺乏高层信息用以帮助优化。

2. 高层——抽象语法树的层次即IR

   优点：机器码的层次的优化的缺点。缺点：不通用（很可能不开放），且非常费时。

1.1.2 Traditional Approaches to Run-Time Optimization

看文章的意思dynamic optimization和run-time optimization是同义词。

1. High Level Language Virtual Machines

   Run-time optimization和Just-In-Time compilation。

   These VMs often target very dynamic languages, such as SmallTalk [21], Self [44], Java [22], and C# [32], and use a machine-independent byte-code input which encodes these languages at a very high-level (effectively at the AST level).

2. Architecture Level Virtual Machines and Dynamic Translators

   即动态二进制翻译的工作。

1.1.3 Traditional Approaches to Compile-time Profile-Driven Optimization

5个步骤，

1. The first stage of compilation compiles the program, but inserts profiling instrumentation into the program to cause it to gather some form of profile information at run-time.

2. The second stage links these instrumented object files into an instrumented executable.

3. The third stage of profile-driven optimization requires the developer of the application to run the generated executable through a series of test runs, which are used to generate the profile information for the application.

4. Finally, the fourth and fifth stages recompile the program (often from source) and relink it, using the collected profile information to optimize the program.

缺点：profiling不一定准确，且麻烦。

1.2 Multi-stage Optimization with LLVM

这里详细表达了LLVM的设计理念：面对上述3类传统方法的劣势，LLVM选择的道路是给底层表示提供上层的类型信息。因此需要定义一个自己的虚拟指令集。原文如下，

The LLVM system architecture (described in Chapter 2) is designed to address these problems in traditional systems. Briefly, the static compilers in the LLVM system compile source code down to a low-level representation that includes high-level type information: The LLVM Virtual Instruction Set (described in Chapter 3). This allows the static compiler to perform substantial optimizations at compile time, while still communicating high-level information to the linker.

看到这里，更想去看看JAVA第一版里bytecode的设计了，想知道为什么JAVA的bytecode（反正不是bytecode的原因，这篇文章里有时也把LLVM IR叫做LLVM bytecode（应该是LLVM的存储形式）而是bytecode的设计）会是高层次的IR。注：为什么说“更”，因为之前在看 LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation 时也提到了JAVA虚拟机，详细见这篇文章的阅读笔记。

之后还提到LLVM静态链接的设计和运行时优化的设计，暂时不在我这次研究IR的范围内，就不赘述了。

1.3 Research Contributions of this Thesis

之前看文章好像没有看到过类似的把自己的文章的贡献列举出来的章节。挺有意思的，值得学习学习这个章节。这个章节能够让作者写文章时思路清晰，也能让读者对作者的工作一目了然。这篇文章整体的写作风格也值得学习。（相比华为的MAPLE IR（注：来自OpenArkCompiler项目的文档，即华为的方舟编译器的文档），这篇文章的可读性高多了！MAPLE IR里不知道是不是用的翻译软件翻译的，一堆奇怪的词，一堆奇怪的表达，然后就不想去看整体的行文逻辑了）

这里的第3点，提到了LLVM成功用于Illinois大学的advanced compilers class，文章还提到，

Students tend to be much less forgiving than researchers about a poor design, lack of documentation, buggy implementation, or poor extensibility, so this demonstrates a great deal of maturity.

在和学生的磨合中，让LLVM有很好的设计、丰富的文档和开放的接口。我想正是如此，LLVM才能走出校园，吸引众多的研究者和开发者不断加入LLVM的开发中，让LLVM不断壮大，以至于变为目前举世文明的编译系统吧。我觉值得学习的地方很多很多，等这周三的报告结束后，有时间再来好好研读研读被我跳过的和IR不太有关系的部分吧。

The key points of the high-level LLVM system design is that the LLVM virtual instruction set (described in more detail in Chapter 3) is used the communicate between the different tools, and the tools fit into a standard development framework. Operating on a common representation allows the transformations to be shared between the different components of the system.

2.2 Compile Time: Front-end & Static Optimizer

The primary job of the language front-end is to translate from the source language to the LLVM virtual instruction set, but it can also perform language-specific optimizations as well.

这里提到只适用于特定语言的优化，可以交给前端完成。（这里的前端是指把高级语言翻译成LLVM bytecode的部分）

Unlike high-level virtual machines, the LLVM type system does not specify an object model, memory management system, or specific exception semantics that each language must use. Instead, LLVM only directly supports the lowest-level type constructors, such as pointers, structures, and arrays, relying on the source language to map the high-level type system to the low-level one. In this way, LLVM is language independent in the same way a microprocessor is: all high-level features are mapped down to simpler constructs.

这里提到了LLVM IR低层次的特点。

第2章后面的内容都跳过了。

3. LLVM Virtual Instruction Set

3.1 Overview of the LLVM Virtual Instruction Set

The virtual registers are in Static Single Assignment (SSA) form ¹, a widely used representation for compiler optimization, as explained in Section 3.2.1.

这里提到了我想了解的SSA，并推荐了一片相关论文。

Note that LLVM is a virtual instruction set: it does not define runtime and operating system functions such as I/O, memory management (in particular, garbage collection), signals, and many others. These features are defined by runtime libraries and APIs that programs link against. On the other hand, the LLVM virtual instruction set is a first class language which has a textual, binary, and in-memory representation. The implications of this decision are discussed in Section 3.6.

LLVM IR不包括的内容如上。

🤔什么是first class language?看来就仅仅是“一流”的意思咯？

3.2 Three-Address Code

3.2.1 Static Single Assignment Form

A program is said to be in SSA form if each of its variables is defined exactly once, and each use of a variable is dominated by that variable’s definition. SSA form greatly simplifies many dataflow optimizations because only a single definition can reach a particular use of a value, and finding that definition is trivial. It also enables fast flow-insensitive algorithms to achieve many of the benefits of flow-sensitive algorithms without expensive dataflow analysis (sometimes referred to as the sparseness property).

SSA的关键是每个变量只定义一次（和高级语言的局部变量的概念相反，局部变量只需保证在一个区域里只有每个变量只有一个有效的定义）（这大概就是LLVM需要无限个寄存器的理由了）。于是又方便分析数据流的优势。

phi节点解决赋值语句可能有多个来源。

3.3 High-level Type Information

列举了所有类型，

primitive types (void, bool, signed and unsigned integers from 8 to 64 bits, floating-point values in single and double precision, and opaque) and constructive types (pointers, arrays, structures, and functions).

举例子如何把高举语言的结构映射到这些类型上去。

3.3.1 Type-safe Pointer Arithmetic with the getelementptr Instruction

3.4 Explicit Memory Allocation and Unified Memory Model

3.5 Function Calls and Exception Handling

3.6 Plain-text, Bytecode, and In-memory Representations

注：感觉3.3~3.6的内容[LLVM Assembly Language Reference Manual.html](LLVM Assembly Language Reference Manual.html) 和2004.LLVM-A_Compilation_Framework_for_Lifelong_Program_Analysis_Transformation.pdf 差不多，不过这篇文章的内容更详细。之后有需要再来这篇文章查询吧。