编译原理

一、 词法分析

关于IR

• IR：Intermediate Representation，中间表示，由编译器前端产生，被后端使用。
  • 树型IR：如语法分析树、抽象语法树。
  • 线性IR：如三地址码。
• 为什么要有IR？
  1. 统一编译成中间表示，从而分离开前端和后端，降低耦合
  2. 方便机器无关优化 （大量的优化 / 分析都在IR上进行）

串和语言

1. 字母表，一个有限的符号集合；
2. 串，字母表中符号组成的一个有穷序列；
3. 语言，给定字母表上一个任意可数的串的集合；
4. 前缀 / 后缀 / 子串
5. 真前缀 / 真后缀 / 真子串
6. 空串，$\varepsilon$

串的运算

• 连接：如$xy$
• 幂次：如$s^5=sssss,\ s^0=\epsilon$
• 翻转：如 $(abc)^R=cba$
• 长度：如 $|abc|=3,\ |\epsilon|=0$

语言的运算

• 语言本质上是一个集合，所以语言可以进行通用的集合运算如：交、并、差、补

• 语言的翻转：$L^R = {w^R : w \in L}$

• 语言的连接：$L_1 L_2 = {xy : x \in L_1, y \in L_2}$

• 语言的幂乘：
  ○ $L^n = L \cdots L$ (共$n$个$L$)；
  ○ $L^0 = {\varepsilon}$

• 星闭包：$L^* = {L^0 \cup L^1 \cup L^2 \cup \ldots}$

• 正闭包：$L^+ = L^* - {\varepsilon}$

• 例子：

{“ab”,”c”}* = { ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”, “ababab”, “ababc”, “abcab”, “abcc”, “cabab”, “cabc”, “ccab”, “ccc”, …}.

{“a”, “b”, “c”}* = { ε, “a”, “b”, “c”, “aa”, “ab”, “ac”, “ba”, “bb”, “bc”, “ca”, “cb”, “cc”, “aaa”, “aab”, …}.

语言：a language is any subset of 𝚺∗

P vs NP

• P问题 —— 确定性算法在关于输入规模的多项式时间内可解
• NP问题 —— 非确定性算法在关于输入规模的多项式时间内可解

正则表达式

• 正则表达式（Regular Expression, RE）是词法分析使用的工具。
• 正则表达式以代数形式描述了一个语言。（准确的说，是一个正则语言）

2.1.1 定义

定义 正则表达式 如下：

基础情况：

1. 如果 $a$ 是一个符号，那么 $a$ 是一个正则表达式，且 $L(a) = {a}$。
2. $\varepsilon$ 是一个正则表达式，且 $L(\varepsilon) = {\varepsilon}$。
3. $\varnothing$ 是一个正则表达式，且 $L(\varnothing) = \varnothing$。

递归情况：

1. 如果 $E_1$ 与 $E_2$ 是正则表达式，那么 $E_1 + E_2$ 也是一个正则表达式，且 $L(E_1 + E_2) = L(E_1) \cup L(E_2)$。（并）
2. 如果 $E_1$ 与 $E_2$ 是正则表达式，那么 $E_1 E_2$ 也是一个正则表达式，且 $L(E_1 E_2) = L(E_1)L(E_2)$。（连接）
3. 如果 $E$ 是一个正则表达式，那么 $E^$ 也是一个正则表达式，且 $L(E^) = (L(E))^*$。（星闭包）

运算符优先级

星闭包 > 拼接 > 并

2.2 有穷自动机 (Automaton)

• 两种有穷自动机：
  • DFA (Deterministic Finite Automaton)， 确定性有穷状态自动机
  • NFA (Nondeterministic Finite Automaton)， 非确定性有穷状态自动机
• 有穷自动机是一种能记忆有限量信息的形式系统，可用于接受或拒绝某一个特定的字符串，有穷自动机所有接受的字符串的集合就是它所定义的语言。
• 有穷自动机的关键是状态和转移

2.2.1 DFA和NFA的定义

这种逐一描述被定义对象的各个元素的形式化定义方式叫作 “声明式定义”

• NFA $A$ 是一个五元组 $A = (\Sigma, S, s_0, \delta, F)$：

  1. 字母表 $\Sigma$ ($\epsilon \notin \Sigma$)
  2. 有穷的状态集合 $S$
  3. 唯一的初始状态 $s_0 \in S$
  4. 状态转移函数 $\delta: S \times (\Sigma \cup {\epsilon}) \rightarrow 2^S$
  5. 接受状态集合 $F \subseteq S$
     • 接受状态也称为终止状态，一般在状态转换图中用双圈表示

• DFA $A$ 是一个五元组 $A = (\Sigma, S, s_0, \delta, F)$：

  1. 字母表 $\Sigma$ ($\epsilon \notin \Sigma$)
  2. 有穷的状态集合 $S$
  3. 唯一的初始状态 $s_0 \in S$
  4. 状态转移函数 $\delta: S \times \Sigma \rightarrow S$
  5. 接受状态集合 $F \subseteq S$

2.2.2 DFA和NFA的区别

• DFA的特点：
  • 一个字符只能转移到唯一确定的下一个状态。
  • 不支持空串$\epsilon$转移。
• NFA的特点：
  • 当前状态下，在一个字符的驱动下可以转移到两个（或多个）不同状态。
  • 允许使用$\epsilon$转移，即没有任何字符驱动也有可能转移。
• 二者区别：
  • DFA容易被计算机实现，但人类理解它较困难。
  • NFA 描述一个语言更容易被读懂；但是不用于实现词法分析器。

2.2.3 状态转换图

通常，我们用一张直观的图来表示有穷自动机，这就是状态转换图。

RE转化成NFA

NFA转化成DFA

DFA最小化

重要的转换图

• RE 到 NFA
  • Thompson 构造法
• NFA 到 DFA
  • 子集构造法
• DFA到 DFA 的自环
  • DFA 最小化
  • Hopcroft算法
• DFA 到 RE
  • Kleene 构造法

二、语法分析

定义 上下文无关文法（Context-Free Grammar） 为一个$G=(V,T,S,P)$四元组 ，其中：

• $T$ 是 CFG 所要定义的语言的字母表，称为 终结符(Terminals)；

• $V$ 是一个有限的具他符号的集合，每个符号代表了一个小语言，称为 变量(Variables) 或者 非终结符(Nonterminals)；

• $S$ 是代表 CFG 所要定义的语言变量，称为 起始符号(Start Symbol)；

• $P$ 是 产生式 (productions) （也译作：生成式/推导式）的集合，表示语言的递归定义，每个产生式形如
  $head \to body$，其中：

  • 产生式头 (head) 是一个变量；

  • 产生式体 (body) 是变量和终结符组成的字符串，可以是空串。

• 符号约定:

  • 习惯上，使用大写字母 $A, B, C, \ldots$ 和 $S$ 表示非终结符；而使用小写字母 $a, b, c, \ldots$ 来表示终结符。

• 例子:

  • $0^n1^n (n \geq 0)$，我们已知它不是正则语言，此时如果使用上下文无关文法描述它，就证明了它是上下文无关语言（上下文无关语言 (CFL) 是上下文无关文法 (CFG) 定义的语言）。

  • 做到这一点很简单，令$V = {S}, T = {0, 1}, S = S, P = {S \to 0S1 \mid \varepsilon}$即可。

推导

1. 如果 $A \rightarrow \gamma$ 是一个产生式，则称 $\alpha A \beta \Rightarrow \alpha \gamma \beta$ 为 $\alpha A \beta$ 推导（derive）出 $\alpha \gamma \beta$，这样就定义了一步推导。

2. 迭代推导（iterated derivation）：表示经过零步或者若干步推导，记作 $\Rightarrow^*$。

   • $\forall \alpha, ; \alpha \Rightarrow^* \alpha$（基础情况）
   • 若 $\alpha \Rightarrow^* \beta,; \beta \Rightarrow \gamma$，则 $\alpha \Rightarrow^* \gamma$（归纳情况）

3. 从起始符号推导得出的任意符号串称为句型（sentential form）。$\alpha$ 是一个句型当且仅当 $S \Rightarrow^* \alpha$。

   • 不含有非终结符的句型称为句子（sentence）。

4. 最左推导（leftmost derivations）：如果 $w$ 是由终结符构成的字符串，且 $A \rightarrow \beta$ 是一个推导式。称 $wA\alpha \Rightarrow_{lm} w\beta\alpha$ 为一个最左推导。定义
   $$
   \alpha \Rightarrow^_{lm} \beta
   $$
   表示 $\alpha$ 可以通过零步或者若干步*最左推导 $\Rightarrow_{lm}$ 变成 $\beta$。

5. 最右推导（rightmost derivations）：我们称 $\alpha Aw \Rightarrow_{rm} \alpha\beta w$，$\alpha\beta w$ 是一个最右推导，如果 $w$ 是由终结符构成的字符串，且 $A \rightarrow \beta$ 是一个推导式。定义
   $$
   \alpha \Rightarrow^_{rm} \beta
   $$
   表示 $\alpha$ 可以通过零步或者若干步*最右推导 $\Rightarrow_{rm}$ 变成 $\beta$。

6. 推导是一个建立语法分析树的过程。

7. 语法分析树（Parse Tree / Syntax Tree）：是一棵用某个特定的上下文无关文法中的符号对每个结点做标记的树：

   • 叶子结点：用终结符或者 $\varepsilon$ 标记；
   • 内部结点：用非终结符标记；
   • 子结点用父结点的推导式右边的符号标记；
   • 根结点：用起始符号标记。

8. 语法分析树的产出（yield）：按照前序遍历的顺序将叶子结点上的记号拼接起来得到的字符串称为语法分析树的产出。

   例子：产生式为 $Exp \rightarrow Integer \mid (Exp) \mid Exp * Exp \mid Exp + Exp$， 产出 $5 + (1 * 12)$ 的一棵语法分析树。

消除左递归

• 如果一个文法存在某个非终结符 $A$，使得存在推导 $A \Rightarrow^+ A\alpha$，则该文法是左递归的。

• 例子： $A \rightarrow A\alpha \mid \beta$ 是左递归的，可以转换为：

$$
A \rightarrow \beta A’ \
A’ \rightarrow \alpha A’ \mid \epsilon
$$

更一般地，对于：

$$
A \rightarrow A\alpha_1 \mid A\alpha_2 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_n
$$

可以转换为：

$$
A \rightarrow \beta_1A’ \mid \beta_2A’ \mid \cdots \mid \beta_nA’ \
A’ \rightarrow \alpha_1A’ \mid \alpha_2A’ \mid \cdots \mid \alpha_mA’ \mid \epsilon
$$

预测分析

• 预测分析器是没有回溯的递归下降分析器
• LL(1)
  • L：从左到右扫描输入
  • L：最左推导
  • 1：每一步只使用一个输入符号进行前瞻
• LL(1) 文法（无二义性！不是左递归！）
  • 足够丰富（Rich enough）可以覆盖大多数编程结构

First()

• $\mathrm{FIRST}(\alpha)$：

  • $\alpha$ 可能以哪些终结符开头的集合

  • 如果 $X$ 是终结符，$\mathrm{FIRST}(X) = { X }$

  • 如果 $X \rightarrow \epsilon$ 是一个产生式，则 $\epsilon \in \mathrm{FIRST}(X)$

  • 如果 $X \rightarrow Y_1 Y_2 \dots Y_k$，且 $\epsilon \in \bigcap_{j=1}^{i-1} \mathrm{FIRST}(Y_j)$ 且 $a \in \mathrm{FIRST}(Y_i)$，则 $a \in \mathrm{FIRST}(X)$

  • 若 $\epsilon \in \bigcap_{j=1}^{k} \mathrm{FIRST}(Y_j)$，则 $\epsilon \in \mathrm{FIRST}(X)$

  $$
  X \rightarrow Y_1 Y_2 \dots Y_k \rightarrow \epsilon
  $$

Follow()

• $\mathrm{FOLLOW}(\alpha)$:

  • $\alpha$右侧可以直接出现的终结符的集合

  • 若$S$为非终结符的开始符号，$$$作为字符串结尾标记，则$$ \in \mathrm{FOLLOW}(S)$

  • $A \rightarrow \alpha B \beta \implies \mathrm{FIRST}(\beta) \setminus {\epsilon} \subseteq \mathrm{FOLLOW}(B)$

  • $A \rightarrow \alpha B$ 或 $A \rightarrow \alpha B \beta$ 且 $\epsilon \in \mathrm{FIRST}(\beta)$，则$\mathrm{FOLLOW}(A) \subseteq \mathrm{FOLLOW}(B)$

  • 例如表格：

    $A$ or $\alpha B$	…

• 注意：重复上述过程直到不再变化为止（达到不动点）！

预测分析表（Predictive Parsing Table）

1. 基本原则

对于每个产生式 $A \rightarrow \alpha$，按如下规则填表：

• 对于每个 $a \in \mathrm{FIRST}(\alpha)$，令 $M[A, a] = A \rightarrow \alpha$
• 如果 $\varepsilon \in \mathrm{FIRST}(\alpha)$，则对每个 $b \in \mathrm{FOLLOW}(A)$，令 $M[A, b] = A \rightarrow \alpha$

---

2. 步骤详解

1. 计算所有非终结符的 FIRST 集和 FOLLOW 集。
2. 对于每个产生式 $A \rightarrow \alpha$：
   • 找出 $\mathrm{FIRST}(\alpha)$ 中的所有终结符 $a$，将 $A \rightarrow \alpha$ 填入 $M[A, a]$
   • 如果 $\varepsilon \in \mathrm{FIRST}(\alpha)$，则将 $A \rightarrow \alpha$ 填入 $M[A, b]$，其中 $b \in \mathrm{FOLLOW}(A)$

---

3. 表的含义

• 行表示非终结符，列表示输入符号（终结符或结束符号 $）。
• 每个单元格 $M[A, a]$ 指定了当栈顶为 $A$，输入符号为 $a$ 时应采用的产生式。
• 若单元格为空，表示语法分析出错。

---

4. 例子说明

以右上角文法为例：

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

表格含义解释

• 这个预测分析表用于 LL(1) 语法分析，也就是自顶向下的递归下降分析（没有回溯）。
• 解析时，分析器根据当前栈顶的非终结符和当前输入符号查表，选择相应的产生式进行推导。
• 若表格为空，则说明输入串与文法不匹配，发生语法错误。
• 红色说明：“根据表选择产生式，表格为空表示出错。”

例子

• 比如当前栈顶为 E，输入符号为 id，则查表得到 E → T E’，用此产生式替换 E。
• 如果当前栈顶为 E’，输入符号为 ) 或 $，查表得到 E’ → ε，表示可以推出空串。

预测分析表是实现 LL(1) 语法分析器的核心工具，通过 FIRST 和 FOLLOW 集进行自动化填表，指导语法推导过程。

通过 FIRST 集确定哪些输入符号能用该产生式推导，若能推出 $\varepsilon$，则还需结合 FOLLOW 集，确保所有归约和结束情况都被覆盖。

三、IR生成

三地址码（Three-Address Code）

• 提供一种标准表示方式，不如源代码灵活

• 每条指令右侧最多只有一个运算符

• 每条指令中最多包含三个地址/变量

  x = y op z
  

• 其中 x、y、z 可以是变量或常量；

• 变量可以来自源代码，也可以由编译器生成

源代码

do i = i + 1; while (a[i + 2] < v);

---

符号标签（Symbolic Labels）

L:   t₁ = i + 1
     i = t₁
     t₂ = i + 2
     t₃ = a[t₂]
     if t₃ < v goto L

---

数字标签（Numeric Labels）

100: t₁ = i + 1
101: i = t₁
102: t₂ = i + 2
103: t₃ = a[t₂]
104: if t₃ < v goto 100

---

Static Single-Assignment

• Feature 1: Every variable has only one definition

• Feature 2: Using φ to merge definitions from multi paths

  ⇒ Direct def-use chains

原始代码：

if (flag) x = -1; else x = 1;
y = x * a;

SSA 形式：

if (flag) x₁ = -1; else x₂ = 1;
x₃ = φ(x₁, x₂);
y = x₃ * a;

主支配关系（Dominance Relations）

• A dom B

  • 如果从入口（Entry）到 B 的所有路径都经过 A

• A post-dom B

  • 如果从 B 到出口（Exit）的所有路径都经过 A

• 严格（Strict）(后)支配（dominance）
  A (后)支配 B，但 A ≠ B。

• 直接（Immediate）支配（dominance）
  A 严格支配 B，并且不存在 C，使得 A 严格支配 C，且 C 严格支配 B。

支配前沿（Dominance Frontier）

• DF(B) = { … }，对于基本块 B

  • 由 B 支配的基本块的直接后继
  • 但这些后继不是被 B 严格支配的

• DF(𝔅) = { … }，对于基本块集合 𝔅

  • $DF(𝔅) = ⋃_{B∈𝔅} DF(B)$

迭代支配前沿（Iterated Dominance Frontier）

• 一个基本块集合 𝔅 的迭代支配前沿（Iterated DF）：
  • DF₁ = DF(𝔅)；𝔅 = 𝔅 ∪ DF₁
  • DF₂ = DF(𝔅)；𝔅 = 𝔅 ∪ DF₂
  • ……
  • 直到达到不动点！（即 DFₙ = DFₙ₋₁）

数据流分析（Data Flow Analysis）

• IN[B]/OUT[B]

  • 一个基本块前后的数据流事实($facts$)集合

• 约束条件（Constraints）

  • OUT[B] = f_B(IN[B]) = gen_B ∪ (IN[B] - kill_B)
  • IN[B] = ∧_P∈preds(B) OUT[P] = ∪_P∈preds(B) OUT[P]

• 要进行数据流分析，需定义

  • 每个语句/基本块的传递函数 f
  • 在多条路径的连接点处的合并函数 ∧
  • 每个基本块的初始数据流事实集合

• 数据流分析产生

  • IN[B]/OUT[B]，包含了程序某一点的数据流事实
  • 所得到的数据流事实在程序执行过程中始终为真

工作表算法（The Worklist Algorithm）

ForEach 基本块 B: 初始化 IN[B] 和 OUT[B]; EndFor

worklist = 所有基本块的集合;

While (!worklist.empty()) Do

B = worklist.pop();

IN[B] = ∧_P∈preds(B) OUT[P]; OUT[B] = f_B(IN[B])

If OUT[B] 发生变化: worklist.push(所有 B 的后继节点); EndIf

EndWhile

到达性定义（Reaching Definitions）

• 一个定义 $d$ 可能到达程序的某一点，如果存在一条从 $d$ 到该程序点的路径，使得 $d$ 没有在这条路径上被杀死（killed）。
• OUT[B] = f_B(IN[B]) = gen_B ∪ (IN[B] - kill_B)
• IN[B] = ∧_P∈preds(B) OUT[P] = ∪_P∈preds(B) OUT[P]

可用表达式（Available Expressions）

• 一个表达式 x + y 在某点 p 是可用的，如果：

  • 从入口节点到 p 的每条路径都对 x + y 进行了计算，并且

  • 在到达 p 之前最后一次计算之后，没有对 x 或 y 进行任何赋值操作。

    $$\text{OUT}[B] = e_gen_B \cup (\text{IN}[B] - e_kill_B)$$
    $$\text{IN}[B] = \bigcap_{P \text{ a predecessor of } B} \text{OUT}[P].$$

活跃变量分析（Live Variable Analysis）

• 我们希望知道在程序点 p 处的变量 x 的值是否可以在从 p 开始的路径上被使用。

对于代码$x=y+z$

• 在这一点上，变量 $y$ 和 $z$ 是活跃的（live），因为我们可以在下一条语句中使用它们。
• 在这一点上，变量 $x$ 是死亡的（dead），因为 $x$ 将被重新定义，旧值不能再被使用。
• use[B]：在程序点B中被引用的变量的集合。
• def[B]：在程序点B中被定义的变量的集合。

$$\text{IN}[B] = use_B \cup (\text{OUT}[B] - def_B)$$
$$\text{OUT}[B] = \bigcup_{S \text{ a successor of } B} \text{IN}[S]$$

应用：寄存器分配

• 死亡值（A dead value）
  • 在变量被修改后，其之前的值（在寄存器中）就死亡了
  • 我们需要从内存重新加载它的值到寄存器中
• 活跃值（A live value）
  • 变量没有被重新定义
  • 将值加载到寄存器后，寄存器中的值是有效的
  • 不需要从内存重新加载值

	到达性定义（Reaching Definitions）	活跃变量（Live Variables）	可用表达式（Available Expressions）
域（Domain）	定义集合	变量集合	表达式集合
方向（Direction）	前向（Forwards）	后向（Backwards）	前向（Forwards）
传递函数（Transfer function）	$gen_B \cup (x - kill_B)$	$use_B \cup (x - def_B)$	$e_gen_B \cup (x - e_kill_B)$
交汇（Meet）(∧)	∪	∪	∩
初始化（Initialize）	OUT[B] = ∅	IN[B] = ∅	OUT[B] = U

符号执行（Symbolic Execution）

• 路径敏感性（Path Sensitivity）
• 流敏感性（Flow Sensitivity）
• 上下文敏感性（Context Sensitivity）

路径敏感性（Path Sensitivity）

路径敏感性是指程序分析能够区分不同程序执行路径的能力。一个路径敏感的分析会考虑条件语句（如if-else、switch等）对程序状态的影响，并分别对不同的执行路径进行分析。

例如，在以下代码中：

if (x > 0) {
    y = 5;
} else {
    y = 10;
}
z = y * 2;

路径敏感分析会分别追踪两条执行路径：

1. x > 0 时，y = 5，z = 10
2. x ≤ 0 时，y = 10，z = 20

这种分析方法能够更精确地检测出可能只在特定路径上出现的问题，但通常计算成本较高，可能面临”路径爆炸”问题。

流敏感性（Flow Sensitivity）

流敏感性是指程序分析能够考虑语句执行顺序的能力。流敏感分析会按照程序控制流的顺序处理语句，并且能够捕获变量在不同程序点的不同值。

例如，考虑以下代码：

x = 5;
y = x;
x = 10;

流敏感分析会理解在第二行时x的值是5，而在第三行后x的值变成了10。这种分析能够精确地追踪变量值随程序执行过程的变化。

相比之下，非流敏感分析会将x视为可能是5或10，而无法区分执行顺序的影响。

上下文敏感性（Context Sensitivity）

上下文敏感性是指程序分析能够区分函数或方法在不同调用上下文中执行情况的能力。当一个函数在程序的不同位置被调用时，上下文敏感分析会分别分析每个调用点的具体情况。

例如：

function double(x) {
    return x * 2;
}

a = double(5);   // 上下文1
b = double(10);  // 上下文2

上下文敏感分析会区分double函数在这两个调用点的不同行为，分别分析得出a=10和b=20的结果，而不是简单地认为函数返回值可能是任何x*2的结果。

这种分析对于准确理解库函数在不同情况下的行为、检测特定上下文中的安全漏洞特别有用，但同时也会增加分析的复杂度和计算成本。

这些敏感性概念在静态代码分析、符号执行、漏洞检测等领域都有重要应用，可以提高程序分析的精度，但通常也会增加分析的复杂度和计算成本。

• 路径爆炸（Path Explosion）
• 约束求解（Constraint Solving）
• 外部函数调用（External Function Call）

每个输入变量都与一个符号相关联，例如，int i → $\alpha_i$

• 每个程序语句生成关于输入符号的公式，例如，i * 2 + 5 → $2 * \alpha_i + 5$

• 程序路径 => 路径约束（$Path\ Constraint$）

  if (i < 10)
  

  路径#1	路径#2
  $\alpha_i < 10$	$\alpha_i \geq 10$

1.    void foobar(int a, int b) {
2.        int x = 1, y = 0;
3.        if (a != 0) {
4.            y = 3 + x;
5.            if (b == 0)
6.                x = 2 * (a + b);
7.        }
8.        assert(x - y != 0);
9.    }

$\sigma = {a \rightarrow \alpha_a ; b \rightarrow \alpha_b ; \boxed{x \rightarrow 1}; \boxed{y \rightarrow 0}};$
$\pi = true$

$\sigma = {a \rightarrow \alpha_a ; b \rightarrow \alpha_b ; x \rightarrow 1; \boxed{y \rightarrow 4}};$
$\pi = \alpha_a \neq 0$

$\sigma = {a \rightarrow \alpha_a ; b \rightarrow \alpha_b ; \boxed{x \rightarrow 2(\alpha_a+ \alpha_b)}; y \rightarrow 4};$
$\pi = \alpha_a \neq 0 \wedge \alpha_b = 0$

check: $\pi \wedge \neg(2(\alpha_a+ \alpha_b) - 4 \neq 0)$
可满足 => 错误

$\sigma$: 符号存储，将每个变量映射到符号表达式。
$\pi$: 路径约束。初始时，$\pi = true$。

求解路径约束（Solving Path Constraints）

• 我们如何检查约束的可满足性？

  $α_a ≠ 0 ∧ α_b = 0 ∧ ¬(2(α_a + α_b) - 4 ≠ 0)$

• 约束求解器

  • 可满足（Satisfiable）=> 存在可能的解
  • 不可满足（Unsatisfiable）
  • 未知（Unknown）（由于超时）

逻辑

• 逻辑只是一种形式语言（就像正则语言等）
• (1) 语法：什么是该语言的合法句子？
• (2) 语义：句子的含义是什么？

命题逻辑（PL）($Propositional\ Logic$)

• 命题逻辑的语法，即，什么是命题逻辑的合法句子？($legal\ sentences\ of\ PL$)
• (1) 真值符号（$b$）：⊤ 和 ⊥（真和假）
• (2) 命题变量（$v$）：$p$, $q$, $r$, …

（1）和（2）都是原子（$Atoms$)

• (3) 字面量（$l$）：原子或其否定
• (4) 公式（$F$）：$l$ | $\neg F$ | $F_1 \vee F_2$ | $F_1 \wedge F_2$ | $F_1 \Rightarrow F_2$ | $F_1 \Leftrightarrow F_2$

“$\vee$”是或的意思，“$\wedge$”是且的意思

可满足性和有效性($Satisfiability\ \ and\ \ Validity$)

• 命题逻辑中公式 $F$ 的解是一个映射 $I$，它将每个变量映射到 ⊤ 或 ⊥

• 命题逻辑中的公式 $F$ 是可满足的，当且仅当存在 $I$：$I \models F$ (语义蕴涵)

• 命题逻辑中的公式 $F$ 是有效的，当且仅当对所有 $I$：$I \models F$

定理 [可满足性和有效性的对偶性]
对于命题逻辑中的所有公式 $F$，$F$ 是有效的当且仅当 $\neg F$ 不可满足。

范式

• 范式是对公式形式的语法限制
• 范式结构化了搜索空间并简化了决策过程

否定范式（NNF）

• 否定范式不允许蕴含式，并且只允许变量被否定
  • (1) 真值符号（$b$）：⊤ 和 ⊥（真和假）
  • (2) 命题变量（$v$）：p, q, r, …
  • (3) 字面量（$l$）：原子或其否定
  • (4) 公式（$F$）：$l$ | $\neg F$（不允许） | $F_1 \vee F_2$ | $F_1 \wedge F_2$ | $F_1 \Rightarrow F_2$（不被允许） | $F_1 \Leftrightarrow F_2$（不被允许）

析取范式（DNF）

• 析取范式中的公式是连接字面量的析取式

$$\bigvee_i \bigwedge_j l_{ij}$$

合取范式（CNF）

• 合取范式中的公式是析取字面量的合取式

$$\bigwedge_i \bigvee_j l_{ij}$$

例子：哪些公式是CNF？

• $(p \wedge q) \Rightarrow (p \vee \neg q)$
• $(\neg p \vee \neg q) \wedge (p \vee \neg q)$
• $\neg p \vee \neg q \vee p \vee \neg q$

1. (¬p∨¬q)∧(p∨¬q)： 这个公式是CNF形式，因为它是两个析取子句的合取：
   • 第一个子句：(¬p∨¬q)
   • 第二个子句：(p∨¬q) 每个子句都是字面量的析取，整个公式是这些子句的合取。
2. ¬p∨¬q∨p∨¬q： 这个公式也是CNF形式，尽管它只有一个子句。它是单个析取子句，可以看作只有一个子句的合取。 这个公式包含字面量：¬p、¬q、p、¬q的析取。

两个公式 $F_1$ 和 $F_2$ 是等可满足的，当且仅当：
$F_1$ 可满足 $\Leftrightarrow$ $F_2$ 可满足

Tseitin转换

• $(r \Rightarrow p) \Rightarrow (\neg(q \wedge r) \Rightarrow p)$

$x_1 \wedge (x_1 \Leftrightarrow (x_2 \Rightarrow x_3))$
$\wedge x_2 \Leftrightarrow (r \Rightarrow p)$
$\wedge x_3 \Leftrightarrow (x_4 \Rightarrow p)$
$\wedge x_4 \Leftrightarrow \neg x_5$
$\wedge x_5 \Leftrightarrow q \wedge r$

定理 [高效CNF编码]
对于命题逻辑中的所有公式$F$，存在一个等可满足的CNF公式，其大小最多比$F$大一个常数因子。

SAT问题

• 判断命题逻辑中公式$F$的可满足性

• 寻找一个解使得我们可以将$F$重写为真

• 步骤1: 使用Tseitin转换将$F$转换为CNF

• 步骤2: 调用DPLL算法

DPLL

• $(p \vee q \vee \neg r) \wedge (p \vee q \vee r) \wedge (p \vee \neg q) \wedge \neg p$

• 目标：找到一个解来满足输入公式

• 重复以下步骤:

  • (1) 选择一个变量，$p$，给变量赋值为真或假
  • (2) 传播$p$的值

定理 [消解]

$(a_0\vee a_1 \vee \cdots\vee a_n \vee c) \wedge (b_0\vee b_1 \vee \cdots \vee b_m \vee \neg c)$

可以被简化为

$(a_0\vee a_1 \vee \cdots\vee a_n \vee b_0 \vee b_1 \vee \cdots \vee b_m)$

• $(p \vee q \vee \boxed{\neg r}) \wedge (p \vee q \vee \boxed{r}) \wedge (p \vee \neg q) \wedge \neg p$

• $(p \vee \boxed{q}) \wedge (p \vee \boxed{\neg q}) \wedge \neg p$

• $p \wedge \neg p$ (假！不可满足！)

bool DPLL (F, I) {
    if (F == false) return UNSAT;
    if (F == true) return SAT;
    
    p = choose(F);
    bool ret = DPLL(F[p→true], I[p→true]);
    if (ret == SAT) return SAT;
    
    return DPLL(F[p→false], I[p→false]);
}

一阶逻辑（First-Order Logic）

PL	FOL
PL假设世界由事实组成，这些事实成立或不成立，即真或假	FOL假设世界由对象和关系组成

• 一阶语言由以下定义：
  • (1) 对象的符号，例如，$a, b, c, …$ （Each symbol is a bit vector of a fixed width.)
  • (2) N元谓词（返回真/假的关系），例如，$p(t_1, t_2, …, t_n)$ (Relational/Logic operations between bitvectors, e.g., slt, ult, ∧, ∨ …)
  • (3) N元函数（关系），例如，$f(t_1, t_2, …, t_n)$ (Arithmetic operations, e.g., +, -, *, /, %, etc)
  • (4) 公式 $(F)$: $\top$ | $\bot$ | $t$ | $\neg F$ | $F_1 \vee F_2$ | $F_1 \wedge F_2$ | $F_1 \Rightarrow F_2$ | $F_1 \Leftrightarrow F_2$ | $\forall x. F$ | $\exists x. F$
• 一阶语言通常与定义符号和关系的”理论“一起使用

模理论中的可满足性(Satisfiability Modulo Theories)

• 对于位向量理论
  • 步骤1: 字级预处理
  • 步骤2: 位爆炸（从FOL到PL）
  • 步骤3: DPLL/CDCL

步骤1示例：

$α_a ≠ 0 ∧ α_b = 0 ∧ ¬(2(α_a+ α_b) - 4 ≠ 0) \stackrel{\text{步骤 1}}{\longrightarrow} α_a ≠ 0 ∧ α_b = 0 ∧ α_a = 2\stackrel{\text{步骤 1}}{\longrightarrow} α_b = 0 ∧ α_a = 2$

步骤2示例：

$x = [a_7, a_6, …, a_0]$, $y = [b_7, b_6, …, b_0]$ 和 $z = [c_7, c_6, …, c_0]$ 是三个8位比特向量

$x | y = z \stackrel{\text{步骤 2}}{\longrightarrow} \bigwedge_{i=0}^{7}((a_i \vee b_i) \Leftrightarrow c_i)$

$x >u 0 \stackrel{\text{步骤 2}}{\longrightarrow} \bigvee{0}^{7} a_i$ $x >s 0 \stackrel{\text{步骤 2}}{\longrightarrow} \neg a_7 \wedge \bigvee{0}^{6} a_i$

(u表示无符号比较，s表示有符号比较)

指针分析（Pointer Analysis）

• y = &x（取地址）

• y = x（赋值）

• *y = x（存储语句）

• y = *x（加载语句）

• pts(x) — x的指向集

  • pts(x) = { y, z } — x可能指向y或z

安德森算法

基于包含关系的指针分析

语句	约束	简写
y = &x	pts(y) ⊇ {x}
y = x	pts(y) ⊇ pts(x)
*y = x	∀ v ∈ pts(y): pts(v) ⊇ pts(x)	pts(*y) ⊇ pts(x)
y = *x	∀ v ∈ pts(x): pts(y) ⊇ pts(v)	pts(y) ⊇ pts(*x)

p = &a;         pts(p) ⊇ { a };         pts(p) = { a, b };
q = p;    =>    pts(q) ⊇ pts(p);   =>   pts(q) = { a, b };      过度近似！
p = &b;         pts(p) ⊇ { b };         pts(r) = { a, b };      结果安全！
r = p;          pts(r) ⊇ pts(p);        pts(a) = pts(b) = { };

安德森算法作为图闭包

• 每个图节点 $x$ 表示指向集 $pts(x)$
• 通过动态传递闭包解决集合约束

Steensgaard算法

基于包含关系（Inclusion-based）的指针分析（Andersen算法）

语句	约束	简写
y = &x	pts(y) ⊇ {x}
y = x	pts(y) ⊇ pts(x)
*y = x	∀ v ∈ pts(y): pts(v) ⊇ pts(x)	pts(*y) ⊇ pts(x)
y = *x	∀ v ∈ pts(x): pts(y) ⊇ pts(v)	pts(y) ⊇ pts(*x)

基于合一（Unification-based）的指针分析（Steensgaard算法）

语句	约束	简写
y = &x	pts(y) ⊇ {x}
y = x	pts(y) = pts(x)
*y = x	∀ v ∈ pts(y): pts(v) = pts(x)	pts(*y) = pts(x)
y = *x	∀ v ∈ pts(x): pts(y) = pts(v)	pts(y) = pts(*x)

• 指向图：x → y 表示 y ∈ pts(x)。

Steensgaard	Andersen
Sound（可靠）	Sound（可靠）
接近线性（更高效）	接近三次方
基于合一（精度较低）	基于包含关系

Datalog-Based DFA

• Datalog是Prolog的一个子集
  • 所有Datalog程序都会终止
  • 规则的顺序无关紧要
  • 不是图灵完备的

谓词/原子

• 谓词是N元关系

  • predicate(x, y, z)

• 示例

  • rainy(“Nanjing”)
  • rainy(“Beijing”)
  • cold(“Beijing”)
  • brother(x, y) – x是y的兄弟
  • speaks(x, a) – x说语言a

• Datalog程序是Horn子句的数据库

  • h是真的，如果假设l₁ l₂ … lₙ同时为真
  • if — 充分但非必要条件

h :- l₁ l₂ ... lₙ

• 示例：

  • rainy(“Nanjing”)
  • snowy(c) :- rainy(c), cold(c)

• 所有规则对其变量的任何实例都成立

  • snowy(c) :- rainy(c), cold(c) 适用于所有城市，如南京、北京等…

• 任何未声明的内容都不为真

• 规则的顺序不影响结果（Prolog与Datalog的区别）

• 规则可以是递归的

  • reachable(a, b) :- edge(a, b);
  • reachable(a, c) :- edge(a, b), reachable(b, c)

• 否定在假设中是允许的

  • more_than_one_hop(a, b) :- reachable(a, b), ¬edge(a, b)

• 所有规则必须是良构的。不良规则的例子：

  • more_than_one_hop(a, b) :- ¬edge(a, b)

  • 不良：左侧的a, b在右侧的正谓词中没有出现

  • 目标：确保终止

通过Datalog实现的到达定义分析

• def(B, N, X)
  • 在块B中的第N个语句可能定义变量X。

• succ(B, N, C)

  • 块C是块B的后继，且B有N个语句。

• rd(B, N, C, M, X)

  • 在块C的第M个语句中对变量X的定义到达了块B中的第N个语句。

• rd(B, N, B, N, X) :- def(B, N, X)
• rd(B, N, C, M, X) :- rd(B, N-1, C, M, X), def(B, N, Y), X ≠ Y
• rd(B, 0, C, M, X) :- rd(D, N, C, M, X), succ(D, N, B)

指令

• 三类指令

• 加载/存储

  • LD R0, addr
  • LD R0, R1
  • LD R0, #500
  • ST addr, R0

• 计算

  • OP dst, src₁, src₂
  • 例如，SUB R0, R1, R2

• 跳转

  • BR L/addr
  • Bcond R, L/addr
  • 例如，BLTZ R, L

寻址模式

• 什么是寻址模式？

• 寻址模式

  • LD R1, a(R2)
  • LD R1, 100(R2)
  • LD R1, *R2
  • LD R1, *100(R2)
  • LD R1, #100

寻址模式：如何计算地址

• LD R, addr
• ST addr, R

假设a是一个元素为8字节值(比如实数)的数组。再假设a的元素的下标从0开始。我们可以通过下面的指令序列来执行三地址指令 b = a[i]：

LD  R1, i          // R1 = i
MUL R1, R1, 8      // R1 = R1 * 8
LD  R2, a(R1)      // R2 = contents(a + contents(R1))
ST  b, R2          // b = R2

这里的第二步计算8i；而第三步把a的第i个元素的值放到R2中，这个元素位于离数组a的基地址8i个字节的地方。

类似地，三地址指令a[j] = c所代表的对数组a的赋值可以实现为：

LD  R1, c          // R1 = c
LD  R2, j          // R2 = j
MUL R2, R2, 8      // R2 = R2 * 8
ST  a(R2), R1      // contents(a + contents(R2)) = R1

Register Allocation

为什么要寄存器分配？

• 减少溢出（Spill）
• 少用寄存器

溢出（Spilling）：

• 将寄存器中的值保存到内存中
• 这样寄存器就可以用于存储其他值
• 当需要时，可以从内存中将溢出的值重新加载回寄存器

局部寄存器分配（Local Register Allocation）

• 在一个基本块内进行寄存器分配

• MAXLIVE：每条指令处同时存活的值的最大数目

  • MAXLIVE ≤ k —— 分配是平凡的（容易分配）
  • MAXLIVE > k —— 必须将部分值溢出到内存中

对于代码：

1. LD   R1, #1028        // R1 <- 1028
2. LD   R2, *R1          // R2 <- contents(R1)，假设为y
3. MUL  R3, R1, R2       // R3 <- 1028 * y
4. LD   R4, x            // R4 <- x
5. SUB  R5, R4, R2       // R5 <- x - y
6. LD   R6, z            // R6 <- z
7. MUL  R7, R5, R6       // R7 <- z * (x - y)
8. SUB  R8, R7, R3       // R8 <- z * (x - y) - 1028 * y
9. ST   *R1, R8          // contents(R1) <- z * (x - y) - 1028 * y

存在以下MAXLIVE的分析：

1. LD   R1, #1028        // R1
2. LD   R2, *R1          // R1 R2
3. MUL  R3, R1, R2       // R1 R2 R3
4. LD   R4, x            // R1 R2 R3 R4
5. SUB  R5, R4, R2       // R1    R3    R5
6. LD   R6, z            // R1    R3    R5 R6
7. MUL  R7, R5, R6       // R1    R3          R7
8. SUB  R8, R7, R3       // R1                   R8
9. ST   *R1, R8          // 

MAXLIVE = 4

如果 $k \geq 4$，例如 $k = 4$，则寄存器分配是简单的。

如果 $k \leq 4$，例如 $k = 3$，则需要溢出。

全局寄存器分配（Global Register Allocation）

• 局部寄存器分配无法捕捉跨多个基本块的值复用

• 全局分配通常采用**图着色（graph-coloring）**范式

  • 构建一个冲突/干涉图（conflict/interference graph）
  • 为该图寻找一个k-着色（k-coloring），或者将代码转化为一个更容易着色的近似问题
  • 在几乎所有假设下，该问题是**NP完全（NP-complete）**的，因此需要启发式方法（heuristics）

K-着色（K-Coloring）

• 顶点着色（Vertex Coloring）：为每个顶点分配一种颜色，使得没有边连接两个相同颜色的顶点。

• K-着色（K-Coloring）：一种最多使用k种颜色的着色方法。

• 将图的顶点映射到虚拟寄存器

• 将颜色映射到物理寄存器

• 由活跃区间构造冲突图（conflict graph）

• 给图着色，使得没有两个相邻节点具有相同的颜色

• 如果图需要多于 $k$ 种颜色，则发生溢出（Spilling）

冲突图（Conflict Graph）

• 顶点（Vertex）：虚拟寄存器；
• 边（Edges）：活跃区间有重叠的虚拟寄存器之间存在边。

• 顶点的度是可着色性的一个宽松上界
• 度小于 $k$ 的顶点总是可以 $k$-着色

Chaitin 算法

• 顶点的度是可着色性的一个宽松上界
• 度小于 $k$ 的顶点总是可以 $k$-着色
• 将这些顶点移除并压入栈，直到图为空（稍后再着色）

• 左侧是一个例子冲突图，其中 $k = 3$。

• 中间为一个栈，用于存储被移除的顶点。

• 右侧为三种可用颜色的示意。

• 颜色：红、绿、蓝分别代表三种可用颜色。

由于a的度为2，小于3，所以先入栈，并删去a的两条边；随后b和c入栈；随后e和d入栈

全部入栈后从栈顶依次出栈并分配不同的颜色

当算法达到所有顶点的度都大于等于 $k$ 时：

• 立即选择一个顶点进行溢出（spill）
  • 将该顶点加入溢出列表
  • 从图中移除该顶点
  • 继续将度小于 $k$ 的顶点从图中移除并压入栈
• 如果溢出列表不为空，插入溢出代码，重建冲突图，并重新分配寄存器

插入溢出代码，重建冲突图并重新分配寄存器：

Chaitin-Briggs 算法

• 当 Chaitin 算法达到所有顶点的度都大于等于 $k$ 时

• 立即选择一个顶点进行溢出（spill）

  • 将该顶点加入溢出列表
  • …

• Briggs:

  • 顶点的度是可着色性的一个宽松（loose）上界
  • 度小于 $k$ 的顶点总是可以 $k$-着色（always k-colorable）
  • 度大于等于 $k$ 的顶点也可能（may also be）可以 $k$-着色

指令调度（Instruction Scheduling）

为什么要调度（Why Scheduling?）

• 每一个现代高性能处理器都能在一个时钟周期内执行多个操作。

为什么编译器很重要（Why Compilers Matter?）

• 硬件只能执行已被取指（fetch）的指令

• 硬件用于缓存停滞操作的空间有限

• 编译器能够将独立操作尽量靠近放置，从而提升硬件利用率

调度约束（Scheduling Constraints）

• 真依赖（True Dependence，也称为读后写依赖，Read-After-Write Dependence）

• 存储（伪）依赖 (Fake Dependence)—— 通过重命名消除
  • 反依赖（Antidependence，写后读依赖，Write-After-Read） 和 输出依赖（Output dependence，写后写依赖，Write-After-Write）

依赖图（Dependence Graph）

• 节点（Node）：指令（Instructions）
• 边（Edge）：真依赖（True Dependence，读后写依赖（Read-After-Write Dependence））

注意用重命名消除假依赖！

表示出各个指令所需要的时间（圆圈），计算出每个指令一共需要的时间长度（方框）

列表调度（List Scheduling）

• 检查每一个时钟周期
• 指令准备好时进行调度
• 当多条指令可被调度时，检查它们的优先级（priority）
  • 最长延迟路径（最大深度，max depth）
  • 使用最多资源
  • …