## ==⚡ Compilers Architecture 编译器构架

• - [Programming Language Pragmatics 4th, Morgan Kaufmann Michael L. Scott](https://booksite.elsevier.com/9780124104099/)

• - [Stanford CS143: Compilers](http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/)

• - [CPEG 421/621 Compiler Design](https://www.capsl.udel.edu/courses/cpeg421/2012/)

• - [CSc 453: Compilers and Systems Software](http://www2.cs.arizona.edu/classes/cs453/fall14/)

• - [CMU 15-411 Compiler Design](https://www.cs.cmu.edu/~fp/courses/15411-f08/)

• - [CS 6120: Advanced Compilers](https://www.cs.cornell.edu/courses/cs6120/2022sp/)

经典编译器工作流程如下：

- Front end : machine independent phases

    - Lexical Analysis

    - Syntax Analysis

    - Semantic Analysis

- Middle end

    - Intermediate code generation

    - Some code optimization

- Back end : machine dependent phases

    - Final code generation

    - Machine-dependent optimizations

一种语言的 compiler 或 interptreter 通常需要两个基本步骤，前端与中端作为一个部分，后端负责机器码的生成（合成），高度依赖具体的硬件系统：

- Read the source program and discover its structure.

- Process this structure, e.g. to generate the target program.

Lex 和 Yacc，Flex 和 Biion 这些工具可以完成前面的代码结构分析工具，并细分为两步操作流程：

- Split the source file into tokens (Lex).

- Find the hierarchical structure of the program (Yacc).

编译前端流程工作内容：

- Lexical Analysis (Scanner) 分析输入的源代码字符序列得到 Tokens；

- Syntactic Analysis (Parser) 解析器分析 Tokens 序列得到 AST，确定语法结构并检查部分语法错误；

- Semantic Analysis 语义分析器检查语法树可能出现的语义错误，例如 *float d = "x"*，还包含类型检查、对象绑定等；

为了加强理解 Programming Language Pragmatics 4th 书中第一章有一道习题，尝试使用熟悉的一种命令式语言，如 C/C++，去触发不同阶段的错误：

(a) A lexical error, detected by the scanner

(b) A syntax error, detected by the parser

(c) A static semantic error, detected by semantic Analysis

(d) A dynamic semantic error, detected by code generated by the compiler

(e) An errorthat the compiler can neither catch nor easily generatecode to

catch (this should be a violation of the language definition, not just a

program bug)

现代的编译器增加了中间代码表示层，IR - Intermediate Representations，像 LLVM - “Low Level Virtual Machine” 这种编译工具，因为增加 IR 层带来的灵活性而取得了巨大的成功。

参考 Stanford CS143: Compilers 提供的现代编译器工作流程图：

●  Lexical Analysis (Scanning): Identify logical pieces of the description.

●  Syntax Analysis (Parsing): Identify how those pieces relate to each other.

●  Semantic Analysis: Identify the meaning of the overall structure.

●  IR Generation: Design one possible structure.

●  IR Optimization: Simplify the intended structure.

●  Generation: Fabricate the structure.

●  Optimization: Improve the resulting structure.

参考 CPEG 421/621 Compiler Design 提供的 LLVM 工具链示意图：

通过实现编译器前端与后端的分离构架，LLVM 就可以使用 IR 灵活地处理各种言语分析并生成的中间代码，中间表示也称为 LLVM ASM，然后通过后端生成各种硬件平台依赖的机器码，无论是 ARM、x86、PowerPC 架构都可以，只需要根据不同的语言实现相应的前端编译器即可。

LLVM IR 是一种基于*静态单一赋值*的表示法，Static Single Assignment (SSA) 特性提供类型安全性、底层操作、灵活性，以及清晰地表示所有高级语言的能力。

SSA philosophy:

    definitions == variables

    instructions == values

    arguments == data flow graph edges

SSA 理念：

- 每个变量被赋值一次，每次赋值定义一个新变量；

- 这样做获取的好处是，变量引用指向唯一的定义，同名变量拥有相同值；

- 形式上等价于 Continuation-Passing Style (CPS) IR；

SSA 属于控制流分析技术，所以相关的概念有控制流图、控制树、直接控制和真控制，参考康奈尔大学的 CS 6120: Advanced Compilers 或卡内基梅隆大学 CMU 15-411 Compiler Design 课程资源。

Clang 项目就是 LLVM 的前面编译器，目前提供了大量流行语言的编译能力：

● Compiler Front end for LLVM.

● Compiles C, C++, Objective-C, and Objective-C++ into LLVM IR.

● Using Clang in conjunction with LLVM replaces the GCC stack.

参考 LLVM 文档，LLVM: An Infrastructure for Multi-Stage Optimization，Figure 2.1: LLVM system architecture diagram。

当前编译系统主要有以下编译优化方法：

● Traditional Approaches to Link-Time Interprocedural Optimization

    1. Very Low Level - Machine Code

    2. Very High Level - Abstract Syntax Trees (AST)

● Traditional Approaches to Run-Time Optimization

    1. High Level Language Virtual Machines, Run-time optimization and Just-In-Time (JIT) compilation

    2. Architecture Level Virtual Machines and Dynamic Translators

● Traditional Approaches to Compile-time Profile-Driven Optimization

● Multi-stage Optimization with LLVM 

    1. Compile Time: Front-end & Static Optimizer

    2. Link Time: Linker & Interprocedural Optimizer

    3. Run Time: Profiling & Reoptimization

    4. Gathering Profile Information at Run Time

    5. The LLVM Approach to Run Time Optimization

    6. Idle Time: Offline Reoptimizer 

得益于前后分离的编译系统构架，LLVM 可以在多个阶段提供编译优化时机，可以为优化提供 Optimizing Linker、Runtime Optimizer、Offline Reoptimizer 实现。

参考 Programming Language Pragmatics by Michael L. Scott，对于 Python 这类使用解释器运行的脚本语言，或者 Java 这种使用虚拟机运行的语言，编译器与解析器的结构简化表达如下：

虽然，Python 并没有虚拟机的实现，但是脚本运行流程基本是类似的，依然会将脚本转译为字节码，然后再通过字节码解析器运行。

最早的 Java 实现完全基于字节码解析器运行程序，byte-code interpreters，经过发展优化后，现代的 Java 实现了 JIT - Just-in-Time compiler，在程序即将执行之前，它会将字节码转译为机器语言：