编译器优化（二）

编译器优化（二）数据流分析与编译器前端

1 学习目标

本次讲座的核心目标包括：

• 完成 Snake 语言的程序分析与优化：探讨可能值分析（Possible values）以及断言消除（Assertion removal）。
• 将活跃变量分析（Liveness analysis）和可能值分析推广到更为通用的数据流分析（Dataflow analysis）概念中。
• 开始探讨编译器前端，特别是词法分析（Lexical analysis）。

2 代码分析与断言消除 (Assertion Removal)

在动态类型语言中，编译器会在程序中加入大量的运行时断言（Runtime assertions），以确保操作数的类型正确。 例如，给定以下代码：

let x = f() in
let y = x + 2 in
let z = y * x in

当前的编译方式会默认所有的输入都是整数，并在中间代码（SSA 形式）中插入相应的类型断言：

x = f()
assertInt(x)
y = x + 2
assertInt(y)
assertInt(x)
y2 = y >> 1
z = y2 * x
...

为了优化程序性能，我们需要回答一个关键问题：何时可以正确地移除这些断言？ 答案是：当确信该断言必然成功时。以 assertInt(x) 为例，如果在运行时能够确定 x 必然是一个（带有标签的）整数，该断言就可以被安全移除。

2.1 可能值分析 (Possible Values Analysis)

为了进行断言消除，编译器需要找出变量在运行时可能取到的值。这就需要执行一种程序分析，计算出在程序的每个节点处，每个变量可能的取值集合。 根据莱斯定理（Rice's Theorem），计算出绝对精确的取值集合是不可能的，因此必须进行近似（Approximation）：

• 下溢近似（Underapproximate）：生成真实可能值的子集，但可能会遗漏某些实际上可能发生的值。
• 超溢近似（Overapproximate）：生成真实可能值的超集，包含所有真实可能值，但也可能包含实际上永远不会发生的值。

对于断言消除，必须采用超溢近似。如果生成的可能值集合（作为真实可能值的超集）仅仅包含带标签的整数，那么可以绝对肯定运行时的值必定是带有标签的整数。虽然这种方法可能会导致漏掉一些本可以消除的断言（因引入了不可能发生的状态而导致保守退让），但这在理论上是不可避免的妥协。

2.2 SSA 层面的可能值与状态爆炸问题

在 SSA（静态单赋值）层面，一个值就是一个 64 位的整数。初步构想是将可能的 SSA 值集合表示为 Rust 中的 HashSet<i64>。 但在遇到类似 x = f() 的外部函数调用时，如果不对外部函数 f 内部行为进行假设，x 可能取得任何值。表示这个全集需要一个极其庞大的集合；在一般情况下，表示 i64 的任何可能子集需要 $2^{2^{64}}$ 位，这在计算机的空间消耗上是完全不可行的。

3 抽象解释 (Abstract Interpretation)

为了将分析所需的内存空间控制在可管理的范围内，需要采用一种不同于精确集合的表示方式。这不可避免地会导致精度的进一步损失，但大多被舍弃的状态集在我们的分析中根本不会出现，足以满足优化需求。 我们设计一个**抽象域（Abstract domain）**来近似表示可能值的集合。为了单纯地消除 assertInt 断言，可以采用一个仅包含三个元素的简单抽象域：

• Any（或称 Top，⟙）：表示所有可能的 64 位整数集合。
• Even（或称 TaggedInt）：表示所有偶数 64 位整数集合（在标签系统中，偶数代表纯整数）。
• None（或称 Empty 或 Bottom，⟘）：表示绝对的空集。

3.1 流函数 (Flow Functions)

在每一个程序执行点，编译器会为每个变量关联一个关于其可能值的近似信息。对于每条具体指令，我们定义一个“流函数”（Flow function），用于描述执行该操作会如何改变相关变量可能值的集合。 例如，对于加法指令 x = y + z，流函数需要基于 y 和 z 的可能值，推导 x 的最精确可能值状态： Poss(x) = Flow[+](Poss(y), Poss(z)) 加法指令对应的流函数定义如下：

• Flow[+](Any, Any) = Any
• Flow[+](Any, Even) = Any
• Flow[+](Even, Any) = Any
• Flow[+](Even, Even) = Even
• Flow[+](None, Q) = None
• Flow[+](P, None) = None 这是非常自然的结果。当任意输入为空集（None）时，说明该执行路径不可能发生，其运算结果的集合必定也为空集。

对于位移指令 x = y << n （其中 n >= 1）：

• Flow[<< n](Any) = Even （任何数字左移后必然是偶数，这就过滤掉了一部分 Any 状态）。
• Flow[<< n](Even) = Even （这里损失了精度，因为偶数左移必然是4的倍数，但在当前仅有三个状态的抽象域中，只能粗略表示为 Even）。
• Flow[<< n](None) = None

对于乘法指令 x = y * z：

• 只要有一个操作数是 Even，且另一个操作数不是 None，相乘结果必然是 Even。即 Flow[*](Any, Even) = Even。

对于断言指令 assertInt(x)：

• Flow[assertInt](Any) = Even
• Flow[assertInt](Even) = Even
• Flow[assertInt](None) = None

4 标签检查分析与控制流分析

将流函数扩展到所有 SSA 操作后，就可以对直线型代码（Straightline code）进行简单的从上至下分析。但实际上的计算机程序总是包含条件分支、循环和函数调用的。

4.1 处理基本块和函数

对于一个具有参数的块或函数 f(x)，要确定其参数 x 的初始可能值信息，需要收集所有跳转到 f 的调用方（前驱节点，即控制流图中的入边）的信息，并将它们取并集（Union/Join）。 对于 main 函数，存在一个隐式的特殊前驱节点（即程序的入口点）。由于我们设定程序的输入是一个不可预知的数组类型，所以入口点会将输入变量初始化为最宽松的 Any。

4.2 处理循环与迭代求解

由于程序中存在循环结构，函数或基本块在控制流图中可以是其自身的前驱节点。这就产生了与活跃变量分析中遇到的类似的循环依赖问题。 解决方案非常清晰：首先将所有节点的信息初始化为最小状态（在这种分析中为 None / Bottom，唯独 main 函数入口点参数例外），然后不断迭代地应用流函数和并集规则更新内部节点信息。直到经历完整的一轮更新后，所有节点的信息都不再发生任何变化，此时我们就说分析达到了不动点（Fixed point）。

5 通用数据流分析框架 (General Dataflow Analysis Framework)

通过对比活跃变量分析和可能值分析，我们会发现两者具有高度相似的模式，这些模式可以被高度抽象为一个通用的数据流分析框架。

5.1 两种分析的异同比较

• 共同点：
  • 两者都在程序的每个操作点附加上特定“域（Domain）”的信息：活跃变量的域是程序变量集合，而可能值分析的域是变量名到可能值抽象集的映射。
  • 两者都定义了各自的流函数，用于根据特定程序的汇编/中间代码操作来更新这些信息。
  • 两者都在控制流的边界处进行信息聚合：活跃变量在条件分支处获取后继节点集合的并集；可能值分析在基本块或函数入口处获取所有前驱节点信息的并集。
  • 两者都遵循“从不正确的基础信息出发，迭代至状态不再改变（达到不动点）”的执行逻辑。
• 差异点（信息传播方向）：
  • 活跃变量分析是向后的（Backwards）：如果一个变量在当下被使用，这意味着该变量在之前的程序点必须是处于活跃状态的。
  • 可能值分析是向前的（Forwards）：如果在当下推断出了某个变量的值，那么该变量在后续的代码路径上的状态也是已知的。

5.2 形式化前向数据流分析

一个标准的前向数据流分析可以由以下几个基本要素进行形式化刻画：

1. 一组用于描述信息状态的数据流值的域 L。
2. 一个聚合运算符，用于组合控制流图（CFG）边缘汇合处的信息状态。
3. 对于每个 CFG 节点 n 绑定的专门的流函数 Fn : L -> L。

通用迭代算法框架：

for all n, in[n] := ⟘, out[n] := ⟘
repeat until no change
  for all n
    in[n] := ⨆ (n’∈pred[n]) out[n’]
    out[n] := Fn(in[n])

在这个框架中，⟘ (Bottom) 代表拥有“最精确”的约束信息（例如不可能的值或绝对确定的常数）。由于“更精确”的底层信息能够为编译器支持更多的优化，整个迭代的过程实际上就是不断暴露不一致性、放宽状态限制，从最精确逐渐向“不太精确”甚至悲观结果退却并收敛的过程。

5.3 域的结构：偏序集与晶格 (Lattice)

数据流域具有反映其中所含信息“数量”的内生结构。部分数据流值天生比其他值更具信息量和优化价值：

• 在数学上我们使用记号 ℓ1 ⊑ ℓ2 来表示 ℓ1 提供的信息不亚于 ℓ2（即 ℓ1 信息量更大，更有利于开启代码优化）。
• 这种偏序关系 ⊑ 是自反的、传递的和反对称的。
• 在这种偏序中，合并操作 ⨆ 称为“连接（Join）”，它负责构造最小上界（Least Upper Bound）。即 ℓ1 ⊑ ℓ1 ⨆ ℓ2，并且不存在比它还要小的公共上界。
• 与之对偶的，还有“交集（Meet）”操作 ⨅ 用于构造最大下界。 这种具备上述连接和交集操作元素的偏序集结构，在数学上构成了晶格（Lattice）。 在数据流分析的晶格中，最底部元素是 ⟘（None），最顶部元素是信息量最贫乏的 ⟙（Any）。

5.4 单调性与终止性 (Monotonicity & Termination)

• 在算法迭代求解时，我们真正希望找到的是一个最小不动点（Minimal fixpoint），因为它包含了最为充分和严苛的优化条件信息。
• 为了使整个分析过程在逻辑上有意义，并能够从理论上保证算法必然终止，所有的流函数都必须具备单调性（Monotonicity）：这意味着如果进入某节点的信息变得更为宽泛/缺乏约束（即在晶格中向着更高的方向移动），那么输出的信息也必定会变得同样宽泛或保持不变。形式化的数学表述为：若 ℓ1 ⊑ ℓ2，则必然有 Fn(ℓ1) ⊑ Fn(ℓ2)。
• 只要流函数具备单调性，且我们所设计的晶格高度是有限的，整个数据流分析就注定会停机（终止计算）。

基于相同框架，还可以实现常量传播（Constant Propagation）等其他优化机制，其晶格结构中，⟙ 代表一个变量拥有多个不可预测的值，中间层是各种平铺的具体的常量整数（如 -2, -1, 0, 1, 2 等），而底部的 ⟘ 则表示未定义或永远不会执行到达的空状态。

6 编译器前端：词法分析入门 (Compiler Frontend: Lexical Analysis)

编译器前端的核心任务是读取作为纯字符串的源代码并进行结构化：

1. 验证它是否是一个形式良好、符合语法规范的程序。
2. 输出抽象语法树（AST，Abstract Syntax Tree），这是一种更便于编译器后端（如中间代码生成、优化器）进行后续操作的中间表示。 编译器前端通常分为三个递进的阶段：词法分析（Lexical Analysis）、语法分析（Syntactic Analysis）和语义分析（Semantic Analysis）。

6.1 词法分析的任务 (Lexing)

词法分析的第一步也是最基础的一步，是将原始的字符序列转化为一个个结构化的“词法单元（Tokens）”。例如将一行代码 if (b == 0) a = 0; 转换为逻辑序列： IF; LPAREN; Ident("b"); EQEQ; Int(0); RPAREN; LBRACE; Ident("a"); EQ; Int(0); SEMI; RBRACE

Token 是用于表示代码中不可分割的最基础文本块的数据类型，常见的 Token 包括：

• 标识符（Identifiers）：如变量名、函数名，例如 a, y11, _100 等。
• 关键字（Keywords）：保留给语言语法的词汇，如 if, else, while。
• 字面量（Literals）：代码中硬编码的常数数据，包括整数（200, -500）、浮点数（2.0, 1e5）、字符串文本（"He said"）。
• 符号（Symbols）：如各种数学运算符、位运算符和括号（+, *, {, <<）。
• 注释（Comments）及空白符（在 C/Java 等多数语言中空白会被直接忽略，但在部分语言如 Python 或 Haskell 中，空白或缩进是具有强语义意义的，因此相应的空格也会被视作 Token 解析）。

6.2 词法分析器的构建途径

• 手工编写词法分析器（Hand-written Lexer）：要求工程师直接编写底层状态机代码来逐个读取字符并进行繁杂的分支判断归类。这条路径的开发极其枯燥且充满痛苦，主要困难在于需要异常精确地界定和验证所有可能的 Token 边界、同时并行匹配验证多个相似的 Token 规则。
• 词法分析器生成器（Lexer Generators）：这是业界主流做法，开发者利用生成器（如 Lex, Ocamllex 等），只需要提供一种用于描述 Token 字符串集合规范的领域专用规则语言，系统就能自动演算和生成具备高性能扫描功能的底层机器代码。

6.3 形式语言与正则表达式

为了通过生成器描述极其复杂的 Token 格式，我们必须借助于形式语言（Formal Languages）理论。

• 我们首先要固定一个基础支持字符的“字母表（Alphabet）” $\Sigma$（例如 0-255 范围的 ASCII 字符集，或者庞大的 Unicode 字符集）。
• 所谓的“字符串”，即是由选定字母表中的字符所拼合而成的有限长度序列。
• “形式语言”，简单来说，就是全体字符串集合的某个特定子集。
• 正则表达式（Regular Expressions）：这是词法分析器表达中最为有力的描述工具，常用于精准定义不同类别 Token 的接受模式。以常见的匹配规则为例：
  • 精确匹配独立关键字：直接写 "if"
  • 匹配单一数字位：['0'-'9']
  • 匹配带可选符号的完整整数常量：'-'?['0'-'9']+
  • 匹配标准格式的变量标识符（通常要求字母开头，后跟任意字母数字下划线）：(['a'-'z']|['A'-'Z'])(['0'-'9']|'_'|['a'-'z']|['A'-'Z'])*

通过在脚本中给特定的正则表达式片段赋予别名，开发者可以如同搭积木一般清晰且模块化地构建出整个编程语言的完备词法规范。而在面临匹配歧义时（例如面对字符串 ifx = 0 时，它是应该被拆解为一个 if 关键字和一个变量 x，还是应当合并理解为一个名为 ifx 的变量），目前几乎所有的主流编译器语言都强制遵循**“最长匹配（Longest match）”**法则，并通过优先遵守规则的声明次序（例如硬性规定优先解析出的 Keyword 压制 Identifier）来最终消解冲突。