编译原理课程笔记（All-in-One速通版）

Cubic Y^3

2024-04-14 (Updated: 2024-06-24)

Course Notes › Compiler Construction Principles

Compiler, Computer Science, On Going

views

Word count: 44.4k (~168 mins to read) Last updated: 2024-06-24 23:59:10

编译原理`Speed-run any%`

以快速复习为目的，尽可能对缺乏动机(intuition)的一些概念提供课堂外的例子以简明解释。
如果读者能通过这些例子意会到某种 sense 就最好不过了。

包含浙江大学编译原理课程课改后新增部分。
标题中使用*标记的部分为考试不考察的内容。

文中大部分图片来自于姚老师(ZJU, pyaoaa at zju.edu.cn)，在此表示感谢。
建议阅读本笔记时配合老师课件/讲义作为参照。
如果忘记了某个术语的意思，还请活用Ctrl+F调用网页搜索功能。

Part 0: 课程信息

使用教材：Modern Compiler Implementation in C, Andrew W. Appel （A.K.A. 虎书）

复习要点 / Cheat Sheet

重点关注 编译器前端部分（课改前已有的教学内容）。
大部分都考过，粗体为侧重点。
重要概念包括但不限于：
- lexer=scanner, parser
- derivation, reduction
- semantic action
- AST, APT
- stack, heap
  - data段，text段
- 解析树，二义性，结合性，左递归文法
- sentential form, sentence, language, Chomsky form
- reduce-reduce conflict, shift-reduce conflict
- leaf procedure
- activation record, stack frame, frame-resident variable
- temporary, formals, 虚拟寄存器
- static link, lambda lifting, display
- interference graph
- escape, spill
- liveness, live-in, live-out, use of…, def of…
- canonical form, canonical tree
- basic block, trace, covering set of traces
- commute , side-effect
- optimum tiling V.S. optimal tiling
- maximum V.S. maximal
- internal fragmentation, external fragmentation
- dominance, loop-invariant
- imperative, functional
提高涉及各算法的计算题熟练度与概念辨析能力。可能题型包括但不限于：
- 计算 First, Follow, Nullable 集
- 构造各个文法的状态图/预测分析表，并据此判断给定的文法（一些产生式）是否属于该文法（i.e. 判断有无 conflict）
  - 不排除会考 LALR(1) 大题
- 实现块结构（嵌套函数）的不同方法：static link, display, ~~lambda-lifting~~
  一些快速判断方法：
  - 利用文法的包含关系快速判断
  - 有左递归/左公因子 -> 不是LL(1)
  - ……
- Liveness analysis: 算出每个指令的in[n] out[n]
- 根据 liveness analysis 的结果画出 interference graph
  - 同时存在的变量之间两两连边
  - MOVE操作时，对t:=s中的t和s连虚边
- 对 IR Tree 进行树覆盖：使用 Maximal Munch / 动态规划，并且转为代码
  - 将各个 tile 分别转写为一块代码，而后按自底向上的顺序，把每块代码拼接成整个程序
- Mark-and-Sweep, Reference count, Copying collection (Stop-and-Copy) 各自的垃圾回收流程
  - 三种方式的优缺点比较：
    - Fragmentation 问题
    - Cache 友好性
    - 能/不能清理哪种垃圾
- Briggs / George 各自的 coalesce 策略
- Do actual spill 时具体如何 rewrite 代码
- Do actual spill 时通过计算 $ \frac{循环外 use/def 次数 + 循环次数 \times 循环内 use/def 次数}{节点度数} $ 计算哪个节点需要被spill
  - 该判据的值越小则越优先被 spill
- 给定功能需求写出NFA/DFA 或给定 NFA/DFA 描述其功能
  - 识别能被5整除的二进制数：5个状态表示 mod 5 余数
- 寄存器分配图染色全过程（build, simplify, coalesce, freeze, spill, select, rewrite）
- Thumpson构造法：RE->NFA
  - 如果题目 明确表示需要用 Thumpson 构造法 ，只需要注意不要自作主张省去一些 ε-move 与状态即可。
  - 如果题目没有明确说明，可以直接手动构造，可以省略一些 ε-moves.
- Frame-resident variables: 必须放置到内存上的变量
  - 对象过大
  - 数组
  - Spill
  - 寄存器被特殊需要
  - 变量逃逸
  - ……
- 变量逃逸(escape)的三种情况：引用、取地址、嵌套函数访问
- Yacc / Bison 语义动作和文法的对应关系
  - 例如：
    1
    2
    3
    factor : '(' expr ')' { $$ = $2; }
    | NUMBER { $$ = atoi(yytext); }
    ;
- 判断给定的树是否为 Canonical tree
- 给定程序，写出对应的 Tiger IR
- Statements 和 expressions 之间判定两两是否 commutes
- 构造 basic blocks 和 traces, 并找出最长的 trace
- Maximum 和 Maximal 的区别
- Tree grammar 的作用：描述各个 tile, 详见正文
- 循环优化部分 dominance, loop-invariant 的概念定义
- 子集构造法：NFA->DFA, 使用状态转换表
- Hopcroft’s algorithm: 简化 DFA
- 各个文法识别字符串的过程，判断是否被接受
- 符号表的不同实现方式（ imperative or functional ）以及优势劣势
- 函数调用时活动记录/栈帧的布局变化，FP/SP 的变化
- IR Tree 线性化为 canonical trees, 组装成 basic blocks, 排序为 traces, 最后生成目标机器代码的全过程
- Deutsch-Schorr-Waite (DSW) pointer reversal 流程？估计不考
- 循环优化：外提变量的前提
确保掌握作业题：和历年大题重复度高，可能出现升级版题甚至“原题”
- 可以找不同班级的同学要一下作业题

Part 1: 简介

基本概念：

中间代码=Intermediate Code
词法分析=Lexing/Scanning/LexicalAnalysis
语法分析=Parsing/SyntaxAnalysis
中间表示=IR=Intermediate Representation
树型中间表示=IR Tree
前端，后端

Part 2: 词法分析

词法分析概述

使用分词器(parser / tokenizer)将输入字符串切割、识别为有意义的子串（把基本单元划分好）。

记法(notation)：(单词(token), 词素(lexeme)(可选) )

e.g.: (IF, ) (ELSE, ) (BINARY_OP, >=) (UNARY_OP, &)

正则表达式

读者应当已经在前置计算理论课程中掌握了该部分内容。

Regex Expression = RE
运算：连接concatenation + 幂Power
e.g.: $ ab(a|b)^3c^* $

有穷自动机

读者应当已经在前置计算理论课程中掌握了该部分内容。

词法分析器自动生成

DFA最小化（->状态最小的DFA，在同构意义下唯一）
可区分状态：存在串s使其分别从状态s、t出发，一个接受串s，一个拒绝串s，则s与t可区分
步骤：
1. 初始等价类，仅由接受状态集合和非接受状态两个集合构成
2. 用所有可能的输入ai应用于各个集合（走一步）
  - 只有集合G的每个状态读入同一字符后，都落入（包含在）相同的某个集合，该集合G在这一步才不用细分
  - 否则集合G要被细分：落入不同集合的对应状态需要被分割进不同集合
3. 不断重复2直到不动点（任一集合分别对所有输入ai都不可细分）
4. 此时等价类中的每个集合即对应最小DFA的一个状态。在其上可以轻松构建min-DFA，该过程是trivial的（可以每个组中选择一个状态作代表）。
示例：

Lex工具

通常和Yacc一起使用，生成编译器的前端。

声明部分
- 常量：常数标识符
- 正则规则定义
转换规则模式{动作}
- 模式=正则表达式
- 动作=识别到相应模式时应调用的处理函数（一般以C语言代码表示）
辅助函数：动作中使用的函数

解决冲突：最长匹配，较前规则优先

Part 3: 语法分析 - CFG & Parsing

分析 lexer(scanner) 得到的 token 序列，判断是否合乎语法。

语法分析器概述

从词法分析器获得Token序列，确认该序列是否可以由语言的文法生成

对于语法错误的程序，报告错误信息
对于语法正确的程序，生成语法分析树(简称语法树) e.g. 抽象语法树AST

实现：手动 or 自动(使用Parse generator={Yacc, Bison, ANTLR, mehir…})

上下文无关文法CFG

CFG = Context Free Language

$$ G=(T,N,P,S) $$
T：终结符集合(Terminals)
N：非终结符集合(Non-terminals)
P：产生式集合(Productions) $ A\rightarrow a, A \in N, a \in (T \cup N)^*$
S：开始符号(Startsymbol): $ S \in N $

📕“上下文无关”体现在：产生式左侧只有一个非终结符，因此类似 $xAy\rightarrow xay$这样，需要关心符号前后别的符号是什么才能应用的产生式是不能在CFG里的。

特殊符号：$ =end of file(EOF)
添加一个新符号S’与一条新规则以表明必须在尾部：
- $ S’ \rightarrow S$ $
产生式缩写：左侧一样的产生式可以把右侧使用”|”合并。例如 $E\rightarrow E+E|(E)|id$

推导Derivation和规约Reduction

例如有产生式 $A\rightarrow \gamma$，可以有这样的变换： $\alpha A \beta \Rightarrow \alpha \gamma \beta$
那么我们说：

$\alpha A \beta $ 直接推导到 $ \alpha \gamma \beta$
$\alpha \gamma \beta $ 直接规约到 $ \alpha A \beta$
不言而喻的多步推导记号：$\Rightarrow^5$ $\Rightarrow^+$ $\Rightarrow^*$
分别代表五步推导，至少一步推导，0次或更多次推导
推导=从文法生成语言里的句子，规约=识别句子成分并逐渐规约到开始符号

最左推导Left-most Derivation
- 最左推导=每步代换最左边的非终结符。逆过程为最右规约
- 类比可得出最右推导、最左规约的定义
- 在自顶向下的分析中，总是采用最左推导；在自底向上的分析中，总是采用最左归约
句型句子语言
- 句型(Sentential form) = 文法G下可能推导出的一个符号序列：可能包含终结符/非终结符，可为空
- 句子(Sentence) = 不含非终结符的句型（仅含终结符）
- 语言(Language) = 文法G可产生的所有句子的集合
正则文法(RE) 与上下文无关文法(CFG)
- 上下文无关语言L(G) := CFG产生的所有句子的集合
- 正则语言L(r) := RE产生的所有句子的集合
  - RE = Regex Expression = 正则表达式
  - 正则表达式r定义正则语言L(r)
  - $ L(r) \in L(G) $：因为正则对产生式限制更大，必须为( $A,B \in N, a \in T\cup {\epsilon} $ )：
    - 左线性文法：形如 $A\rightarrow aB$ 或 $A\rightarrow a$
    - 右线性文法：形如 $A\rightarrow Ba$ 或 $A\rightarrow a$
  - 正则语言可用于词法分析，上下文无关语言可用于语法分析（语言描述能力、复杂性决定的）
Chomsky范式（计算理论课程内容）:
- 0型文法=短语结构文法递归可枚举
- 1型文法=上下文有关文法
- 2型文法=CFG
- 3型文法=RE

CFG的分析树Parse Tree

分析树性质
- 根节点=文法初始符号
- 叶节点=终结符
- 内部节点=非终结符
- 父节点→{叶节点}=产生式
语法分析(Parsing)中的挑战
核心目标：对于终结符号串x，要么从S推导出x，要么设法将x规约到S
- 自顶向下(Top-down) S->x, 从根节点开始构造Parse Tree
- 自底向上(Bottom-up) x->S, 从叶节点开始构造Parse Tree
作为搜索问题：搜索空间大->空间大小受文法产生式限制。
- 无限制文法：时间复杂度 $O(n^3)$
- 上下文无关语言CFL 的子集需要的典型时间为 $O(n)$，例如
  - Predictive parsing using LL(1) grammars
  - Shift-Reduce parsing using LR(1) grammars
  - …

编程语言的文法设计

核心：无二义性

二义性来源：某些句子存在不止一棵分析树=有两个不同的最左推导=多种可选推导处于文法同一层
例如：$$E \Rightarrow E*E \Rightarrow id*E \Rightarrow id*E+E$$ 与 $$E \Rightarrow E+E \Rightarrow E*E+E \Rightarrow id*E+E $$
对于”3*4+5”，前者给出3*(4+5)=27（错误），后者给出3*4+5=17（正确）。
解决办法：
- 确保只有一种最左推导=将同一层文法分层
- 规定符号优先级（”*“” > “+”,”-“）
  - 越接近开始符号S的文法符号优先级越低
- 规定符号结合性（左结合/右结合）
  - 递归非终结符（也就是这个终结符在产生式左部右部都出现）在终结符（也就是这个运算符，比如*,+）左边，运算就左结合
- 修改方法示例：
判定CFG二义性：不可判定问题
但可以通过给定充分条件（无二义文法）确保无二义性：
- 自顶向下：LL(1)
- 自底向上：LR(1), LALR(1)

grammars

Part 4: 语法分析 - 自顶向下

自顶向下每一步的推导都需要做出两个选择：

替换哪个非终结符？
应用哪个（左侧为该终结符的）产生式替换？

递归下降分析Recursive-Descent Parsing

自顶向下语法分析的一种通用解决方案。
只有 LL(k) 文法能使用该方法。

从根节点开始，尝试应用一个产生式，从而产生一个句型（例如S->(S)）；
递归下降到下一层：对句型中非终结符也尝试应用一个产生式；
发生错误（例如发现产生的句型((S))不可能匹配给定的字符串(a)）就尝试另一个产生式；
如果所有产生式都错误，则失败，需要回溯让上层选择其他产生式。
问题：太慢！
- 该过程类似NFA，能否构造类似DFA的分析方法？

LL(1)和预测分析法

预测分析法(Predictive parsing)：接受LL(k)文法

第一个L: “left to right” 从左到右扫描
第二个L: “left-most derivation” 最左推导
k: 向前看k个token确定推导选用的产生式（一般不明确说k就是k=1）

接下来需要添加约束使其无需回溯。我们先引入几个概念：

First集和Follow集

给定 $ G=(T,N,P,S),\alpha \in (T\cup N)^* $
记空串为$\epsilon$
- First集：可从$\alpha$推导得到的串的首个终结符的集合（也就是说，$\alpha$自己推导出的第一个终结符可能是什么）
  $$ \text{First}(\alpha)={a| \alpha \Rightarrow^*a…\ ,a\in T} $$
- Follow集：从S出发，可能在推导过程中跟在A右边的终结符号集
  $$ \text{Follow}(A)={a|S\Rightarrow^*…Aa…\ ,a\in T} $$
  - 例如: $ S\rightarrow \alpha\ A a\ \beta $，终结符号 $ a\in \text{Follow}(A) $ （仔细区分a和α）
至此可以使用两个条件保证产生式的选择是唯一的：
对于产生式 $ A\rightarrow \alpha|\beta $ ,
1. $ \text{First}(\alpha)\cap \text{First}(\beta)= \emptyset $ （α和β推导不出以同一个单词为首的串）
  - 意义：显然的。这样看终结符是哪个就知道应该用哪个产生式。
2. 若$\beta \Rightarrow^* \epsilon$，那么$\alpha \nRightarrow^* \epsilon$，且 $ \text{First}(\alpha) \cap Follow(A) = \emptyset $ （α和β不能同时推出$\epsilon$;First(α)不应在Follow(A) 中）
  - 意义：其实就是考虑如果可以推导出空串时，后继终结符因为是空串所以暂时还没法确定，得从Follow集中寻找（再向后看），最终做出哪个产生式的选择。
  - 在满足这条要求的情况下，假设下一个输入是b,且$\beta \Rightarrow^* \epsilon$
    - 如果b∈First(α)，则选择A → α(属于上面1的情况)
    - 如果b∈Follow(A)，则选择A → β ,这对应A最终到达了$\epsilon$而且后面紧跟着终结符b的情况
应试建议：直接列出LL(1)分析表并检查是否有冲突（见下文）。

接下来我们会看到具体的LL(1)预测分析实现方式。
三步走：计算First,Follow->构造预测分析表->预测分析

计算First, Follow
- Nullable集
  由于刚刚提到了空串，我们需要引入一个简单的新定义：Nullable集={可推导出空串的符号}。
  定义是递归的：
  - Base Case: 如果有产生式 $ X\rightarrow \epsilon$, 那么X当然是Nullable的
  - Inductive Case: 如果有产生式 $ X\rightarrow Y_1 Y_2 Y_3 … Y_n$, 且 $Y_1,Y_2,Y_3,…,Y_n$每个都能推导出空串，则X是Nullable的
  - 对于每个产生式，我们可以循环用它们不断更新Nullable集直到不动点。这同样适用于First集与Follow集。
- First集：
  - Base Case: 如果X是终结符terminal: First(X)={X}
  - Inductive Case: 如果有产生式 $ X\rightarrow Y_1 Y_2 Y_3 … Y_n$
    - 首先，$\text{First}(X) \cup = \text{First}(Y_1)$ ($ a\cup = b$意为$ a \leftarrow a\cup b$，也就是把b并进a里)
    - 如果$Y_1 \in \text{Nullable}: $$\text{First}(X) \cup = \text{First}(Y_2)$
    - 如果$Y_1,Y_2 \in \text{Nullable}: $$\text{First}(X) \cup = \text{First}(Y_3)$
    - …
    - 直到某个$Y_i \notin \text{Nullable}$则停止
  - 对于每个产生式，我们可以循环用它们不断更新First集直到不动点。
- Follow集：
  - Base Case: $ \text{Follow}(A)=\emptyset $
  - Inductive Case: 如果有产生式 $ B\rightarrow s_1 A\ s_2 $
    - $\text{Follow}(A) \cup = \text{First}(s_2)$
    - 如果$s_2 \in \text{Nullable}$, $\text{Follow}(A) \cup = \text{Follow}(B)$
  - 对于每个产生式，我们可以循环用它们不断更新Follow集直到不动点。
Tips(不要求掌握):Tiger book algorithm 3.13指出他们可以同时计算，感兴趣可以看看。
应试技巧：可以把 Nullable 合并到 First 中：如果X是 Nuallbale 的，则 First 中有ε. Follow 不准出现ε, 但可以有$代表句子结束.
构造预测分析表
- ~~打开网站即可LL(1) Parser Generator~~ 不过这个网站确实对于理解第三步中PDA相关过程很有帮助。
- 回顾自顶向下推导的两个选择题：
  - Q: 替换当前句型中的哪个非终结符? A: “Left-most”一词说明：总是选择每个句型的最左非终结符进行替换。
  - Q: 用该非终结符的哪个产生式进行替换? A: 构建二维表M, 通过当前非终结符和看到的终结符决定选取何种产生式。
- 定义并构造M：
  - 每一行A对应一个非终结符
  - 每一列a对应某个终结符或输入结束符$
  - 表中的某一格M[A,a]表示：针对当前非终结符A，下一个输入Token为终结符a时，可选的产生式集合
  - 构造过程：对于每个产生式 $X\rightarrow \gamma$
    - 如果 $ t\in \text{First}(\gamma)$, 插入产生式 $X\rightarrow \gamma$ 到M[X,t]
    - 如果 $ \gamma \in \text{Nullable} $ 且 $t \in \text{Follow}(X)$, 插入产生式 $X\rightarrow \gamma$ 到M[X,t]
  - 如果某一格存在多个产生式，就说明无法确定选取哪个产生式（也即：产生了冲突），也就说明不是LL(1)文法！

预测分析

递归下降

例如对于文法：

S -> E $
E -> E + T
E -> E – T
E -> T
T -> T * F
T -> T / F
T -> F
F -> id
F -> num
F -> ( E )

形如：

void S(void) { E(); eat(EOF); } 
void E(void) {
  switch(tok) { 
    case ?: E(); eat(PLUS); T(); break;
    case ?: E(); eat(MINUS); T(); break;
    case ?: T(); break; 
    default: error();
  }
}
// 问号处内容由预测分析表M决定，读者有兴趣可以帮忙验证一下这个文法是否LL(1)

非递归下降（无需掌握）
- 本质上还是递归下降，只是改写成Pushdown Automata所以相当于模拟一个栈
- 如果栈顶是非终结符A：利用预测分析表,选择产生式A -> a（也就是将栈顶的非终结符A替换成串a）
- 如果栈顶是终结符a：将栈顶记号a和输入中的Token匹配并出栈
- 初态：压入初始符号
- 终态：输入读取完毕，栈空，此时接受

消除左递归、提左公因子

LL(1)文法的部分性质
可用于判定问题。
- LL(1)文法是无二义的
- LL(1)文法是无左递归的
- LL(1)文法是无左公因子的
左递归(left-recursive)文法:
- 有非终结符A使得 $A \Rightarrow^* A\alpha$
- 形如 $S\rightarrow Sa$ 的称为直接/立即左递归
- 问题：这会导致递归下降分析进入无限循环
  - $S\rightarrow Sa|b$ 分析 $baaaa$
  - 可能永远卡在”a”里而没机会考虑”b”: $ S \Rightarrow Sa \Rightarrow Saa \Rightarrow Saaa \Rightarrow Saaaa …$
- 解决办法：通过文法变换消除（详见龙书）
  比如可以将这一文法：
  1
  A -> A a | b (a,b不以A开头，a不为空)
  转为右递归：
  1
  2
  A -> b A'
  A' -> aA' | ε
左公因子的(left-factored)文法:
- $ P \rightarrow \alpha \beta | \alpha \gamma$
- 问题：同一非终结符的多个候选式存在共同前缀，可能导致回溯
- 解决办法：限制文法或文法变换
  - 例如可以提取左公因子来“推迟决定”，这样可以在读入更多token后进行决策：
    把
    $$ P \rightarrow \alpha \beta | \alpha \gamma $$
    变换为
    $$ P \rightarrow \alpha Q \\ Q \rightarrow \beta | \gamma $$

*错误恢复

该部分内容不要求掌握。

错误：表M中对应格是空格，没有任何可取的产生式
我们不希望遇到错误直接全盘放弃，而是令Parser报错后，尽可能从错误中恢复并继续工作，这样可以一次性尽可能报出程序里全部错误。

可以通过以下几种方式恢复：

删除：例如，可以一直跳过token直到遇到当前非终结符对应Follow集中的token
插入：例如，如果左右括号不匹配，我们可以插入一个括号，暂时假装它是匹配的
替换：例如，变量名错误可以替换为最相近的变量名

我们之后会细讲错误恢复的策略。

Part 5: 语法分析 - 自底向上

从串w归约为文法开始符号S的过程。规约时，一个与某产生式体（->右侧）相匹配的特定子串被替换为该产生式头部（->左侧）的非终结符号。

问题：

何时归约(归约哪些符号串)？
归约到哪个非终结符号？

回顾LL(1)的优势劣势：

+ 运行高效(线性时间)
+ 递归实现符合文法结构、适合手动构造&自动生成
- 能分析的文法类型受限

我们提出新文法：LR(k)

表达力: Every LL(k) grammar is also LR(k)
不要求无左公因式
可以处理左递归文法
被广泛采用(Yacc, Bison, …)
“L”: left-to-right scanning 自左向右扫描
“R”: right-most derivation in reverse 最右推导的逆
“k”: 向前看的字符的个数(k省略时取1)
子集（详见该图）：LR(1), LALR(1), SLR, LR(0), …

移进-规约 Shift-Reduce

这是LR(k) Parsing 的一般模式。

核心思想：将字符串一分为二，

右侧是未被parser检查过的
左侧包含终结符与非终结符
我们接下来会使用”|”标记分割点。

例如，考虑该文法： $ E \rightarrow E+(E) | \text{int} $

显然并非LL(1)的：存在左递归

我们考虑处理字符串”int+(int)+(int)”，则过程如下：
shift reduce

可见LR分析采用最右推导的逆过程：最左规约。因此LR分析的每一步都是最右句型。
一般实现方式：采用栈进行Shift-Reduce

栈：包含左侧字符串
输入流：包含剩余未处理的右侧字符串
操作：
- Shift: 从输入读入一个Terminal压入栈
- Reduce: 栈顶的几个元素满足某条产生式的RHS(Right hand side), 则pop这些元素并压入产生式的LHS(Left hand side)
- Error: 爆！留待后文讨论。
- Accept: shift “$” 并且栈中只剩下文法的开始符号
需要解决的问题：何时shift? 何时reduce?
- 表驱动的LR分析：类似LL文法的表，但行列意义不同，且这个表一般很大（详见后文）

几个文法的包含关系（仍然是详见该图）:
$ LR(0) \in SLR(1) \in LALR(1) \in LR(1) $

LR(0) Parsing

核心思想：因为需要凑出产生式RHS，维护栈顶内容对于所有产生式右侧的“进度”。
项(Item):= 一个产生式加上在其中某处的一个点。

例如产生式 $A\rightarrow XYZ$ 有4个 items:

$A\rightarrow \bullet XYZ $
$A\rightarrow X\bullet YZ $
$A\rightarrow XY\bullet Z $
$A\rightarrow XYZ \bullet $

Item 的含义：

$ A\rightarrow \alpha \bullet \beta$: 已扫描/归约到了α，并期望在接下来的输入中经过扫描/归约得到β，然后把αβ归约到A
$ A\rightarrow \alpha \beta \bullet$: 已扫描/归约得到了αβ，此时已经可以把αβ归约为A

Item类似一个有穷自动机的状态!

一个项读入一个符号后可以转变为另一个项：例如$A\rightarrow \bullet XYZ $ 读入X就可以转为 $A\rightarrow X\bullet YZ $
显然项的数量是有限的。
这样的有穷自动机被称为LR(0)自动机。

LR(0)Parsing的NFA:

⚠ NFA只能识别正则语言RE，然而RE<LR(0). 所以这里的NFA只是用于辅助记录栈顶识别进度。

新增开始符号S’，并加入产生式” S’->S$ “
NFA起始状态：$S’\rightarrow \bullet S$ $
NFA终结状态：$S’\rightarrow S\bullet$ $
转移：
- $A\rightarrow \bullet XY $ 读入X就可以转为 $A\rightarrow X\bullet Y $
- 对于产生式 $ X\rightarrow \alpha Y \beta $ 与 $Y\rightarrow \gamma$ 那么 $ X\rightarrow \alpha \bullet Y \beta $ 可以直接转换（ε-move）到 $ Y \rightarrow \bullet \gamma$ （相当于递归下降法里进入下一层递归，从而分析当前产生式内部的非终结符）

我们更希望能转为DFA. 当然可以使用子集构造法转换，但事实上可以直接构造DFA.
lr-nfa2dfa

LR(0)Parsing的DFA与分析表：

DFA构造：
- 项集闭包CLOSURE:= a set of items, 记为I
- 任意符号记为X
- 对任意项集Closure(I)求法（其实就是ε-closure）：
  Closure(I) =
  1
  2
  3
  4
  5
  6
  repeat
  for any item A→ α•Xβ in I
  for any production X→ γ
  I ← I + {X→ •γ}
  until I does not change.
  return I
  TL;DR: 如果”·”的右边是非终结符X，就把X为LHS的产生式对应的初始项加入。注意这是递归的：加入的新初始项如果也有这个情况还得接着加。
- 接下来的构造方式通过类比NFA->DFA的子集构造法是显然的：
  GOTO(I,X):= I是一个项集，X是一个文法符号，则GOTO(I,X)定义为I中所有形如 $A\rightarrow \bullet X \beta$ 的项所对应的新项 $A\rightarrow X \bullet \beta$ 构成的新集合生成的闭包（I是状态，X是转移，I里符合要求（也就是下一个符号是X）的产生式前移一位越过X加入转移到的新状态，不符合的被丢弃；当然考虑到ε-moves要再求一遍新状态的闭包）
DFA到分析表
分析表T类似LL(1)中的表M，但是行列的含义与内容都发生了很大变化。
- Action表项：
  - 每一行对应一个状态i
  - 每一列对应一个终结符t
  - 表中的一格T[i,t]代表要做的操作action，有以下几种可能：
    - $s_n$ = shift n := 从状态i经过终结符t转移到状态n. 步骤：
      1. 从输入流中取一个终结符t压入状态栈
      2. 将n压入状态栈
    - $r_k$ = reduce k := 确定使用第k个产生式进行规约（此时状态i没有出边）。步骤：
      1. 弹出状态栈顶的几个状态（数量对应产生式#k的RHS长度）
      2. 符号栈压入产生式#k的LHS，也即一个非终结符X
      3. 查询Goto表（见下文）T[i,X]将对应的下一个状态压入状态栈
    - accept := 该状态包含 $S’\rightarrow S \bullet $ $, 接受字符串，运行完毕
- Goto表项：
  - 每一行对应一个状态i
  - 每一列对应一个非终结符X
  - 表中的一格T[i,X]表明经过非终结符X下一个状态是什么
  - 格中的$g_n$ = goto n := 从状态i经过非终结符X转移到状态n
- LR实际实现只有状态栈，符号信息可从相应状态中获取
- 一个例子：

如何理解”LR(0)”中的”0”:

Item中没有Lookahead terminal等信息，不关心后面的token
是否规约/使用何产生式规约完全取决于栈顶状态

局限性：由于只要有产生式能规约就立刻规约，很容易产生冲突（也就是表中一格有多个$s_n$,$r_n$，不知道应该直接规约还是需要接受更多符号来完成另一个产生式，这被称作shift-reduce conflict）
我们引入新的文法，放宽一些限制。

SLR(1) Parsing

SLR(1) = Simple LR(1)

我们说过k省略时默认为1，所以称为SLR文法即可。其实就是LR(0)稍微改改。

考虑每次规约，都会使用一个产生式 $E\rightarrow \alpha$
“LR分析是最右推导的逆过程”，因此每步归约都应该满足：
$$ t \in \text{Follow}(E) $$其中t指的是输入流中下一个token, E指的是用于此规约用到的产生式的左部(LHS).
因此对于SLR文法来说，SLR的DFA和LR(0)一样；但LR(0)的分析表中有一些$r_n$是非法的，需要删去。
在生成分析表的具体步骤上：

LR(0)的某些状态包含可规约的Item，那么这个状态I在对应的Action表中T[I,_]这一行的每一个格子（无论终结符t是什么）无论如何都会有对应的$r_n$项
SLR会关心后面的终结符是什么，因此如果t不在Follow集中，这不能是一个合法的规约，Action表对应的t列就不会有这个$r_n$

例如，图中被划去的部分即为从LR(0)分析表到SLR分析表的变化：
SLR分析表：删去了部分规约项

规约的条件更严格，也就“自动”消除了一些冲突，也就允许了更多语言被纳入该文法，因此 $\text{LR(0)} \in \text{SLR}$

局限性：显然不能消除所有shift-reduce冲突。如果产生冲突对应的终结符t恰好在Follow集里，就无法消除。例如考虑如下文法：

S' -> S $
S -> L = R
S -> R
L -> id
L -> * R
R -> L

由最后两条规则L -> * R R -> L可以看出Follow(R)与Follow(L)两个集合互相包含，即相等，即Follow(R)=Follow(L)
然而’=’在Follow(L)={=,$}中，因此我们遇到’L=…’时仍然不知道应该接受等于号进行shift(这样就可以进一步在S->L=R这个产生式中前进)，还是直接使用R->L进行reduce.
slr-conflict
slr-conflict-table

需要更多、更精确的限制才能进一步降低冲突的可能。

LR(1) Parsing

包含更多信息（后继token）来消除一些归约动作。
相当于“分裂”一些LR(0)状态，精确指明何时应该归约。

LR(1)项(item)的形式：$ A \rightarrow \alpha \bullet \beta,\ a$

逗号后的a是 向前看符号(lookahead symbol) 即表明向前看一个终结符，可以是$.
和LR(0)对比，处理ε-move时记录合法的向前看符号w.

各种计算：

计算Closure
对于状态I中的一个item $$A\rightarrow \alpha \bullet X \beta,\ z$$ 以及一个产生式 $$X\rightarrow \gamma$$
我们递归地寻找所有 $w\in \text{First}(\beta z)$ 然后加入I：$I\cup={(X\rightarrow \bullet \gamma,\ w) | \forall w\in \text{First}(\beta z) }$（直到不动点为止）
起始状态是 $S’\rightarrow \bullet S \$,\ ?$ 的闭包
- 我们不关心”?”处是什么，因为永远不会移进$.
  所以一种可行的表示是把$都移到产生式外部，而非真的要产生一个$符号： $S’\rightarrow \bullet S,\ \$$）
  或者你也可以直接写作：$S’\rightarrow \bullet S\$,\ ?$ （推荐）
计算Goto表
基本和LR(0)算法保持相同，移入动作不考虑向前看符号z
也就是对于转移X，转移前后项的变换是：
$$A \rightarrow \alpha \bullet X \beta,\ z \ \ \Rightarrow\ \ A \rightarrow \alpha X \bullet \beta,\ z$$
计算Action表：Reduce操作

规约操作是变换较大的部分。
在LR(1)中，Action表项中Reduce操作形如$(I, z, A\rightarrow \alpha)$
- I: 代表状态I对应的行
- z: 代表向前看符号
- $ A\rightarrow \alpha $ 为规约所采用的产生式
  这就限制了从某个可规约项规约时，必须向前看一个符号以确保它是lookahead symbol.

局限性：这样的文法限制过少，过于灵活，导致状态数量过多，状态表过于庞大。
lr1 con
lr1 dfa

注：话虽如此，文法仍然可能因为R-R冲突与S-R冲突从而导致其不属于LR(1)！这样的例子可以在LR(k)且k>1的文法中大量找到。

因此我们在SLR(1)=Simple LR(1)与LR(1)之间折中，可以得到一个新文法LALR(1).

LALR(1) Parsing

LALR = Look-Ahead LR

动机：发现很多LR(1)中的状态都只有lookahead symbol的区别。能否合并？

LALR(1): 把LR(1)中只有lookahead symbol不同的item合并。

定义：把LR(1)中item的集合里所有lookahead symbol去掉，剩下的称为核(core)
把LR(1)中所有核相同的状态两两合并为一个状态。每次合并都删除两个旧状态，新增一个新状态，入边出边的连接方式是显然的，直接接在新状态上即可。
新状态的item是两个旧状态的item的并（其实就是把每个item的lookahead symbol合并一下）。

lr1 to lalr1

这样得到的表将会小很多：与SLR的分析表一样大！通常状态数只有LR(1)的十分之一。付出的微小代价：规约-规约冲突(reduce-reduce conflict)
例如对于如下文法：

S -> a E c
   | a F d
   | b F c
   | b E d
E -> e
F -> e

在LALR分析表中有两个状态会被合并成一个。而之后的下个字符将会出现歧义。这个冲突对应的状态：

1 2	E -> e, {c,d} F -> e, {c,d}

LR(1)分析器：将产生两个不同的状态(图中的状态#6与#9)，不会产生冲突：
LALR(1)分析器：只会产生一个状态，产生冲突
- 若下个输入字符为c或d，可以归约成E或F

因此，上述文法对于LALR(1)是二义的。
但这是可以接受的：LALR(1)足以处理绝大部分程序设计语言。

Part 6: 语法分析杂项

语法分析器的生成器：YACC

Yacc = yet another compiler-compiler:

基于LALR(1)
BNF(Backus Naur Form)范式
GNU版本名为Bison
流程：
1. Yacc源程序(*.y) >> Yacc Compiler >> C语言实现的LALR分析器(y.tab.c)
2. y.tab.c >> C Compiler >> 分析器可执行文件(.exe/.out)
3. 输入 >> 分析器可执行文件 >> 输出

Lex
- 一种词法分析器的生成器，将词法转化为词法解析器yylex()
- Yacc生成的yyparse()可以接受yylex()进而生成语法分析器

Yacc源程序结构

声明
- C语言的声明
- 词法单元的声明
翻译规则
- 产生式
- 产生式相关语义动作（例如编译时计算）
辅助性C语言例程
- 直接拷贝到生成的*.tab.c中
- 可以在语义动作中调用
- Lex生成的yylex()就是其中之一，可以返回词法单元

例如，对于示例文法：

exp → exp addop term | term
addop → + | -
term → term mulop factor | factor
mulop → *
factor → ( exp ) | number

有示例程序：

%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
int yyerror (char * s);
%}
%token NUMBER
%%
command: exp {printf("%d\n", $1);};
exp: exp '+' term {$$ = $1 + $3;}
  | exp '-' term {$$ = $1 - $3;}
  | term {$$ = $1}
;
term: term '*' factor {$$ = $1 * $3;}
    | factor {$$ = $1;}
;
factor: NUMBER {$$ = $1;}
      | '(' exp ')' {$$ = $2;}
;

其中翻译规则Rule的格式为 Rule {Action Code}，使用规则规约后Action Code就会被执行
语义动作形如 $$ = $1 + $3

$$ 表示和产生式头(LHS)相关的属性值
$i 表示产生式体中第i个文法符号（终结符/非终结符）的属性值

消除二义性与解决冲突
- 消除二义性：
  - 指定运算符优先级：先出现的优先
  - 指定运算符结合律：%left（左结合，例如乘法加法） %right（右结合，例如一元运算符负号）
- 冲突解决
  - 规约-规约冲突：先出现的产生式优先采用
  - 移进-规约冲突：移进优先采用
- 更通用的方法：通过改写文法，可以在消除冲突的同时减少二义性

*错误恢复（续）

该部分内容不要求掌握。

动机：一次性报告所有错误，而非遇到第一个就停下。

局部错误恢复：调整Parse过程的栈，使其恢复到正常从而继续进行Parsing
全局错误恢复：删除/插入尽可能少的字符，使得源字符串成为合法的字符串

局部错误恢复
Yacc中的一个方法：使用特殊的error符号（终结符）控制恢复过程。
例如：
1
2
exp -> ( error )
exp -> error ; exp
于是通过这样的产生式，我们可以把错误的影响范围控制在右括号处/分号处。如果语法处理时遇到错误，可以一路跳过直到右括号和分号，然后继续处理。
分号、右括号这样的符号就被叫做synchronizing token.

当语法分析器遇到错误时：
- 不断弹出栈中状态，直到栈顶状态包含项 $ A \rightarrow \bullet error\ \alpha$
- 分析器将error移入栈中
- 如果α为空，分析器直接执行归约，并调用相关的语义动作；否则跳过一些符号，找到可以归约为α的串为止
流程示例：
全局错误恢复

Burke-Fisher 错误恢复: 对于在发生错误处之前的K个token，每一处都允许插入/删除/修改一个token，直到修复成功。
优势：
- 不引入新产生式，不改变文法
- 也不改变分析表
如何判定修复是否成功：修复后，在报告错误处继续Parsing直到下一个错误发生的距离最长（一般来说，修复后能从本来由于错误卡住的地方继续前进4个token就算成功了）。

实现：维护K个token前的旧栈，以及K个token组成的队列。遇到错误后基于旧栈和增删改后的token队列（不一定是K个了）试图parse. 尝试不同的增删改方案直到修复成功：

语义动作需要延迟到进入旧栈中（进入旧栈说明在解析流程中已经确定了）再进行
- 否则如果遇到错误，错误恢复发现原来的parsing方式不对时，文法符号的属性已经按照错误的方式运算了，回天乏术。

语法分析小结：文法对比

SLR 与 LR(0)

	SLR	LR(0)
移进	$ A\rightarrow \alpha \bullet a \beta \in I_i \\ \text{Goto}(I_i,a)=I_j \\ \text{Action}[i,a]=s_j $	$ A\rightarrow \alpha \bullet a \beta \in I_i \\ \text{Goto}(I_i,a)=I_j \\ \text{Action}[i,a]=s_j $
—	—	—
规约	$ A\rightarrow \alpha \bullet \in I_i \\ \alpha \in \text{Follow}(A) \\ \text{Action}[i,a]=r_j$	$ A\rightarrow \alpha \bullet \in I_i \\ \text{Action}[i,a]=r_j $

可见唯一的区别就是SLR在规约时要求后继token是在Follow集里的。

LL(1) 与 LR(1)

	LR(1)	LL(1)
建立分析树	自底而上	自顶而下
归约or推导	规范归约(最右推导的逆)	最左推导
分析表（行x列）	状态×文法符号，大	非终结符×终结符，小
分析栈	状态栈，信息更多	文法符号栈

LL(1): 对于多个可选产生式 $A\rightarrow \alpha_1|\alpha_2|…$ 向前看下一个输入根据First,Follow确定使用哪条产生式推导
LR(1): 对于多个可选产生式 $A\rightarrow \alpha,\ B\rightarrow \alpha,… $ 在识别出整个$\alpha$后，再往前看1个符号，然后确定使用哪条产生式归约

LL(1) LR(1) SLR

grammar-compare

Part 7: 抽象语法

编程语言 = 语法（识别一个合法的程序） + 语义（这个合法的程序对应的实际行为）

语法：已经在之前章节讨论过。
语义：
- 操作语义：如何执行程序？
- ~~公理语义：可以证明程序的那些性质？~~ （该部分不在本课讨论）
- 指称语义：程序是做什么的？

属性文法Attribute Grammar

属性文法=上下文无关文法+属性+属性计算规则

属性:= 描述文法符号的语义特征，比如表达式E的值可以记为E.val
属性计算规则(语义规则):= 与产生式相关联、反映文法符号属性之间关系的规则，比如在乘法表达式中左侧的E.val要如何计算
- 仅表明属性间“抽象”关系，不涉及计算次序等具体实现细节
应用：
- “推导类”：例如很多语言的编译期求值
- “生成类”：生成AST，中间代码等
- …
实现：例如在先前章节中Yacc等Parser生成器的语义动作

语义动作Semantic Action

我们可以给产生式绑定一个语义动作，使得按照这个产生式规约时/推导时完成特定操作。

每个token都可能有独属于自己的 语义值(Semantic Value) 。每种token的语义值类型可以不同，我们把A的语义值的类型称为“A的关联类型”。
例如对于产生式 $A\rightarrow B\ C\ D$

语义动作返回值必须是A的关联类型
这个值可以通过B C D各自的语义值进行运算得出

例如通过如下语义动作可以在编译期直接evaluate表达式的值：

E->E1 + T   { E.val= E1.val + T.val }
E->E1 – T   { E.val= E1.val - T.val }
E->T        { E.val= T.val }
T->(E)      { T.val= E.val }
T->num      { T.val= num.val }

在递归下降法中，语义动作体现为每个符号对应的parsing函数。这里我们同时关心函数的返回值与副作用。
因此假设T和F两个token的关联类型都是int，对于表达式 $T\rightarrow T * F$ 可以如此实现语义动作：

int a= T();
eat(TIMES); // '*'
int b= F();
return a*b;

而对于Parser生成器来说，其实现方式有所不同，以Yacc为例：

用一个栈储存语义值，这个栈和状态栈是同步的
当进行规约操作时，需要执行相应的语义动作（C语言实现）
- 可能用到的值一定可以通过多次pop语义值栈获得（和状态栈pop同步）
- pop完毕后运算得到的新值压入该栈（和状态栈压入新状态同步）

抽象解析树APT

APT = Abstract Parse Tree 是语义动作的一种应用。

⚠和抽象语法树(Abstract Syntax Tree)的区别请参阅https://stackoverflow.com/questions/5026517/whats-the-difference-between-parse-trees-and-abstract-syntax-trees-asts

能否通过描述语义动作直接实现整个编译器？可以，但是难以维护，且必须保证这些语义值的计算顺序和Parsing顺序完全一致。

考虑分离语法解析（Parsing）和语义动作：一个可行方案是Parsing得到树，而后遍历以进行语义相关的操作。

我们可以很容易得到一棵树：叶节点对应输入的token，内部节点对应一个语法规则。这被称为concrete parse tree.
concrete-pt

缺点：太“啰嗦”。例如括号相关产生式只是为了解析顺序正确才有的，没必要放进树里。

抽象语法树AST

AST = Abstract Syntax Tree
可以提供一个干净的（不包含Parsing的那些繁文缛节）接口用于后续编译流程的实现或优化（编译器后端）。

生成方式：用具体语法（Parser生成器能懂的）为抽象语法（我们想要的、更可读的）生成抽象语法树：
AST

实现：

为每一个非终结符定义一个类型声明，用于表示其关联类型。
产生式统一放进一个union（如果是Rust就是Option直接解决，~~C语言太坏了~~）里，每一个产生式就是union里的一个结构体，这个结构体用于储存其子节点：
为每个产生式定义一个函数，除了计算需要的语义值返回以外，还将申请空间、分配新的树节点并设置好其子节点：
以Yacc为例，把这些函数放入对应产生式的语义动作块中即可在规约时自动调用。随着Parsing的逐步推进，每次规约都可以产生一个新的内部节点，最终逐步构建出整颗AST。

此外，通过遍历AST还能做很多：

通过一些“变形”缩小树的规模，减少最终代码的大小
通过一些“变形”优化树的结构，提高最终代码的性能
代码内联优化
静态分析，编译期推导值
类型系统检查等安全检查
翻译到中间表示，虽然AST也常被视作一种“中间表示”

位置Position

在one-pass编译器中，词法分析、语法分析、语义分析是同步进行的。而错误发生时，词法分析器lexer的位置可以用来作为错误发生位置的合理估计反馈给用户。所以，lexer存有一个全局变量维护当前位置信息。

然而，对于使用AST的编译器，词法分析结束后才开始语法分析，因此这是不可行的。
解决方案：AST每个节点记录自己在源文件中的位置，标记自己是具体哪几个字符派生而来的。

lexer把每个token的起始位置、结束位置传递给parser

parser维护位置栈与语义值栈，这样语义操作就知道位置信息了

不是所有的Parser生成器都可以做到这一点：例如Bison可以但Yacc不行
对于Yacc等无法直接实现的，可以引入新的非终结符pos（其语义值包含需要的位置信息）并改写文法。例如可以如此改写PLUS表达式以利用位置信息：

%{ extern A_OpExp(A_exp, A_binop, A_exp, position); %}

%union {
    int num;
    string id;
    position pos;
    ...
};

%type <pos> pos

pos: { $$ = EM_tokpos; }

exp: exp PLUS pos exp { $$ = A_OpExp($1, A_plus, $4, $3); }

Part 8: 语义分析

语法正确并不足够，还需要保证语义信息的正确。可以使用英语类比：

I apple eat. 语法错误。
I eat water. 语法正确，但语义错误。
I eat apple. 语法正确，语义正确。

语义分析的任务无法在之前语法分析的过程中完成，根本原因是存在上下文(context).
同一个 token 的含义会随着上下文不同改变：没有上下文，我们无法知道变量v是局部变量还是全局变量。

注意到：上述的属性文法等内容只适用于上下文无关文法CFG.
然而CFG有很多不足，例如不可能完成：

检查数组引用的维度是否匹配
检查数组越界
确定变量应储存于栈上还是堆上
…

这是因为，这些检查和值有关（涉及语义），而非语法本身。
因此我们需要通过检查、遍历 程序表示(Program Representation) 来完成 （广义的）语义分析。
常用的程序表示：

abstract syntax tree (AST)
control flow graph (CFG)
programdependence graph (PDG)
valueflowgraph (VFG)
single static assignment (SSA)

然后我们就可以：

类型检查
代码生成
去除dead code
寄存器分配
…

本课重点关注的（狭义的）语义分析指的是通过检查AST获知程序的静态属性，包括：

作用域(Scope)与变量可见性
变量、函数、表达式的类型
以及将AST转为中间代码(Intermediate Code)

符号表Symbol Table

Binding:= 把类型、值等信息绑定到一个identifier上
Environment:= 一些绑定的集合，体现了程序当前环境下已声明的一些变量/函数/…

符号表就是Environment的一种实现方式。我们在遍历AST的过程中可以维护一个符号表用于语义分析。
符号表中的重要组成部分就是各个局部变量及其作用域。当退出作用域时，自然就需要丢弃内部的一些binding.
变量在scope内重新定义时需要覆盖（屏蔽）掉更大作用域的，退出时则还原。
因此可见我们需要为符号表实现的接口包括：

insert: 将名称绑定到相关信息(type, value, …), 且将覆盖已有的绑定关系（如果存在）
lookup: 用名称查找信息
beginScope: 进入作用域
endScope: 退出作用域，将符号表恢复到进入之前的状态

在Java等语言中，可能有多个环境同时活跃（对应不同的module, class等），他们都需要一个符号表。这被称为多符号表。

符号表的实现：
绑定时，如果遇到了符号已经存在的情况，有两种策略：
- Imperative Style: 直接覆盖旧的绑定，这样就不可能lookup到旧的信息。当这个新的绑定不再有效时，需要复原旧的绑定。
  - 如何快速lookup且支持删除和复原(restore): 使用哈希表套链表储存每对binding. 我们称哈希表中的元素为bucket.
  - insert: 直接插入对应bucket的链表头。如果已经存在，由于这使得新的binding关系更靠前，这样做可以成功覆盖。
  - restore: 对应bucket的链表头弹出头部的一些元素。
  - 我们会发现需要维护一些必要的额外信息（比如scope变化时应该要弹出几次）。
- Functional Style: 永远保留旧的绑定，只是查询时做一些额外处理找到当前的绑定（可以理解为只是一种 renaming）。这样退出 scope 时还原更简单。
  - 直接使用BST（红黑树等）实现查找。
  - 可以使用可持久化数据结构完成删除、复原等操作，进一步降低单次操作的时空复杂度，非常方便。

两种方法均可使用。

Tiger编译器符号相关的实现

在哈希表中的链表进行lookup时，不断进行字符串比较是很耗时的。

解决办法：使用新的数据结构将符号对象关联到一个整数上（哈希值）

Tiger编译器的environment是destructive-update的。也就是说，有两个函数：

S_beginScope: 记下当前符号表的状态
S_endScope: 恢复到最近的、还未被恢复的S_beginScope记下的状态

我们引入一个 辅助栈(Auxiliary stack) 来维护上文提到的必要的额外信息:

符号入栈时，会将binding联动地插入对应bucket的链表头
弹出栈顶符号时，对应bucket的链表头也会联动地被移除
beginScope: 压入一个特殊标记到辅助栈中
endScope: 一直弹出符号直到弹出了一个特殊标记
- 可以由此标记推断：此次因为退出scope引发的restore操作可以就此结束

类型检查

类型系统

类型限定了变量的取值范围以及部分运算规则。
可以大致把编程语言分为：
- 类型化的(typed): C/C++ Java Go
- 非类型化的(untyped): LISP JavaScript
  - 注意：不是没有类型，而是类型可变
类型系统作用：
- 提高开发效率（高层抽象&指称语义）
- 提高运行性能（指导编译优化）
- 提高安全性（内存安全等）
- …
事实上，可以理解为每引入一种类型就能完全消除某一类特定错误。

形式化的类型系统可用于数学领域，参见Coq以及LEAN
Tiger的类型系统
包含：
- 原始类型(primitive type): int和string
- 构造类型(constructed type): record（类似结构体）和array
根据不同的判别法，类型等价这一关系分为：
- Name equivalence (NE): 必须声明是同一个类型才是同一类型
- Structure equivalence (SE): “长得一样”（内部结构一样）就是同一类型
显然前者被广泛采用，Tiger语言也不例外。
Tiger存在两个独立的命名空间，不同命名空间的同名identifier不会互相遮蔽(hide)对方：
- Types
- Functions and variables
Tiger的类型检查

Tiger的语义分析需要两个环境：
- Type: 把类型符号映射到其表示的具体类型对应的数据结构
  - 初始时包含primitive type对应的映射 int $\mapsto$ Ty_int, string $\mapsto$ Ty_string
- Value: 把变量名映射到具体类型，把函数名映射到(参数类型, 返回值类型)（也就是函数签名）
  - 初始时包含Tiger中预定义的一些函数定义
semant 模块包含类型检查等语义分析相关操作。类型检查分为两部分：
- Type-checking expressions
  - transExp可以在给定的两个环境下将输入的表达式标记上type（如果发现非法则报错）
- Type-checking declarations
  - 在Tiger语言中声明只可能在let语句中出现
  - 变量声明：如果提供了变量类型，则检查初始化表达式类型是否匹配；否则直接通过初始化表达式类型获得变量类型
  - 类型声明：递归地获取类型别名对应的实际类型。
    - Q: 如何处理递归声明 type list = {first: int, rest: list}？A: 不使用one-pass而是two-pass: pass#1: 记录声明头部（左侧）放入环境；pass#2: 完成
    - 不允许类型的直接循环引用(type a=b;type b=a)：必须通过record或array完成(type a=b;type b={i:a})
  - 函数声明：检查形参、返回值与函数体
    - Q: 如何处理递归声明？A: 不使用one-pass而是two-pass: pass#1: 记录函数声明（签名）放入环境；pass#2: 处理函数体

!!!以上所有内容为期中考覆盖范围

Part 9: 活动记录Activation Record

其实Activation Record就是栈帧Stack Frame

Why & How

编译过程需要区分代码（由PC寄存器指向）与数据。

高地址向低地址增长：栈Stack
低地址向高地址增长：堆Heap
低地址：静态数据（代码+全局变量）

递归/调用子函数时需要在栈帧存放当前函数的上下文信息：

调用的参数
局部变量
子函数执行完毕后的返回地址
…

主要寄存器：

Frame Pointer/Base Pointer 基址寄存器
Stack Pointer 栈顶寄存器
例如f()中调用g():

然后g()执行完毕返回f()继续执行：

所以子函数是通过基址寄存器向高地址，越过返回地址获取自己的参数。

思考：为什么不开启优化的时候如下的写法可以“返回”值？

#include<bits/stdc++.h>
using namespace std;
int foo(int num) {
 int var=num+1;
 // no return!
} 
int main() {
 int a = foo(114514);
 cout<< a <<endl; // 114515
}

答案：如果有return语句，返回值会被push到栈帧。
但是这里并没有return语句，所以本来是返回值的位置就被栈帧里最后一个（也是唯一一个）局部变量var给“冒充”了。
当然这是UB, 不能保证这种行为的可重复性（例如开启高优化级别时，这个现象很容易就被优化坏了，只留下一个0）。

总结

基址寄存器=FP
栈顶寄存器=SP
如果f调用g(a1, a2, …):

SP指向第一个参数a1
SP减去栈帧大小（向低地址增长）得到FP
进入g:
将旧的FP压入栈
令新的FP=SP
g可以基于FP向高地址获取参数，或向低地址压入/查询局部变量
从g退出：
返回值拷贝至特殊寄存器
SP=FP（释放g的栈帧）
从栈上取回旧的FP值到FP中

Part 10: 寄存器与变量

Intuition: 内存太慢了，使用层次化的储存提高速度(Regs-L1-L2-L3-Mem-Disks…)
所以其实并不是所有参数/局部变量都要放栈上，有时直接通过寄存器传参/保存局部变量即可。
Tiger语言：默认按值传递，函数内部改变不影响外部值
注：函数/过程这两个词可以混用，是一个含义。

局部变量

调用函数需要保护现场：因为寄存器的值可能会被子函数改变，返回时“现场已经被破坏”。为此部分寄存器的值需要在栈上进行备份。分为以下两种：

Caller-saved: 也被称为易失(volatile)寄存器。例如t系列临时寄存器。调用者如果用到则需要自己保存，子函数可以任意修改
Callee-saved: 例如FP/SP, 由子函数负责保存与恢复（进入子函数时push到栈，退出时从栈里pop），调用者无需关心

参数传递

函数调用传参：大部分现代编译器对于前几个参数直接通过寄存器传递，多余的则仍然通过栈完成传递。
但是物理寄存器的数量是有限的：假设有如下调用链f(x)->g(y)->h(z), 如果所有函数都通过寄存器r1接收参数，则f调用g(y)时要备份r1，再将r1设为要传给g的参数y.
因此，每个函数都要将r1在栈上备份，带来额外的内存traffic。
优化策略：

从变量生命周期入手：如果寄存器对应的变量/参数在当前函数不再使用，子函数覆盖了自然也无妨
全局寄存器分配策略：每个函数使用不同的一组寄存器传参
优化叶过程(Leaf Procedure)：如果某函数不调用任何其他过程，自然也不需要为（不存在的）子过程备份传入的参数
寄存器窗口Register Windows: 每次调用函数时，尽可能利用尚未用到的寄存器，然后为子函数分配新的一套可用的寄存器（SPARC采用该策略）

返回值与返回地址

返回地址:
Tl;DR: 函数调用call指令地址为a，则函数调用完毕应返回至地址a+1
现代机器基本将该地址保存在一个指定(designated)寄存器中。非叶过程需要在调用时把该值写入栈上，叶过程则不必。
返回值：
- 如果可以则放置在指定寄存器中（例如X86-64使用rax）。
- 如果不可以（如：返回对象太大），一般来说调用者会在自己栈帧开一个临时空间，然后将地址作为一个隐藏的参数传递给被调用函数。这样被调用方可以直接在这个空间上储存返回值，最后用寄存器（比如eax/rax）把返回值所在地址告诉调用者。

关于局部变量、表达式中间值如何尽可能地利用寄存器储存，尽量减少内存traffic，以后会在寄存器分配部分详细阐述。

Frame-Resident Variables

寄存器并非万能：有时，在栈上分配空间（实体化）是不可避免的。例如：

对象过大，无法放在寄存器中
数组对象，需要通过地址偏移访问
寄存器被特殊需要，例如上文提到可能用于传参
太多中间值/局部变量，有限的寄存器放不下
- 称为 “Spill” 了, 在寄存器分配部分会展开讨论
变量 “逃逸(escape)” 了（也就是脱离了当前scope/无法确定变量有效的生命周期）：
- 引用传参：需要内存地址（虽然对于现代语言经过优化并不总是需要一个地址）
- 显式地取变量地址（C语言等）
- 被嵌套函数访问（Tiger语言不需要考虑）

这些变量就是 frame-resident 的，也就是它们不得不被分配在栈帧上。

Part 11: 块结构Block Structure

Intuition: 在允许函数嵌套定义的语言（比如Tiger）中，内部函数可能使用外部函数中的局部变量。
nested-funcs
变量可以通过FP访问（因为定义的变量内存地址在编译时未知，但相对当前函数的FP偏移值(offset)是已知的）。

在编译时，如何使得内部函数访问非局部定义的外部变量呢？有以下几种方法：

静态链接Static Link: 当内部函数g被调用时，调用者f传入一个指针指向f的栈帧（或者说活动记录）
- 这种情况下，我们说”f statically encloses g“
- 如果多次嵌套，嵌套次数为N，这些指针会构成一个长为N的单向链表串联起栈帧
- 每个函数记录自己的嵌套深度n
- 如果访问了在深度m的变量，只需沿着该链向上n-m次就可以找到该变量所在的栈帧
- 优缺点：Overhead小，但是因为要通过链表向上经过多层速度较慢
- 注意：有时f中嵌套的函数g不直接引用外部变量，而更里面的函数h可能才会；这时h的static link可以越过g
Lamda lifting: 从最深的一层叶过程开始，把所有g(a1)用到的外部变量o1 o2改写为真正传入的参数，于是变为g(o1, o2, a1). 如此逐渐向上改写每一层即可。
Display数组：一个全局数组，记录当前每个嵌套深度i对应的栈帧地址。这样不需要经过链表即可直接找到变量对应的栈帧。

Part 12: Tiger语言：一个例子

Tiger语言的栈帧布局(Layout)

layout

incoming parameters: 调用者传入
return address: 返回CALL指令
local variables: 部分必须在栈帧中放置的局部变量
saved registers: 该函数保存的一些寄存器值，为其他用途腾出寄存器
out-going arguments: 调用其他函数时传递的参数
static link: 如上所述
FP/SP: 指向基址/栈顶

Tiger语言编译器的栈帧实现

~~看起来就不是什么会详细考的部分~~

formals = formal-parameters (不包括static link之类隐藏的参数)

记录变量在寄存器中还是在栈帧中
记录变量是否逃逸(escape)
…

进入被调用函数的上下文=新的栈帧=“视角切换(view shift)”, 这是不同机器/指令集的实现需要完成的。
view-shift

💡本质上，我们在做的事和Lab3里为每一个参数分配地址，把一切读写放在内存里是一样的。
只是为了效率，有时这个“地址”并不存在而是储存在寄存器中；此外有的变量会逃逸。
因此需要实现访问的接口，对在寄存器的变量或者会逃逸的变量进行一些额外处理。

其他trivial话题：

Temporary: 局部变量的抽象名，代表一些暂存在寄存器中的值
- 本质上是为不同scope里的相同变量名进行重命名，类似我们在lambda演算时做的重命名等价变换： $ \lambda x.x \equiv \lambda y.y$ 所以 $\lambda x.\lambda x.x \equiv \lambda x.\lambda y.y$, 然后才能无歧义地带入x, y
Label: 标记还不能确定的机器静态的、物理的地址

总结：两层抽象

2 layers: abstraction

frame.h temp.h 封装了机器无关的变量视角，我们无需关心是在内存还是在寄存器中
Translate模块用于在上述封装的基础上将高级语言翻译为有层次的、用static link连接起来的各个函数，维护函数间的层次关系；找到跨层次的、对外部变量的访问，并把每个访问定位到具体某一层函数的某一个变量上。
- 这里，我们让Static link这一指针“伪装”成一个传给嵌套函数的参数

Part 13: 中间表示(IR)

概述

IR = Intermediate Representation

编译流程划分：

前端：源代码->词法分析->语法分析->语义分析->
中端：IR1->IR2->…->IRn->
- 这个过程可做一些机器无关优化（比如循环展开）
后端：指令选择->寄存器分配->指令调度->机器码
- 这个过程可做一些机器相关优化

为何需要IR

更模块化，更可迁移（跨平台）
- 考虑n个语言和m种平台，如果没有IR则需要n*m个编译器；引入一个IR后先统一翻译成IR，则只需要n+m个编译器
多层的：分层应用不同的分析和优化（i.e. 变换）
- 例如GCC, LLVM, Rust…
可能丢失少部分机器特定的细节，但不会损失太多

一个好的IR应该简单，然后将复杂的AST翻译为IR代码，最后组合不同代码块。

*IR杂项

不要求掌握。

IR分类：
- 高层IR: 提供语言特性的检测（例如borrow checking）
- 中层IR
- 低层IR: 贴近目标语言，易于生成
表示方式：
- 结构化
  - 基于图（树、无环图……）
- 线性Linear: 储存布局是线性的
  - 栈（虚拟）机、三地址码……
- 混合Hybrid: 节点内线性，节点间图形化
  - 经常见到的控制流图(CFG)就是一种
三地址码：
- 是一种线性的IR
- 格式：x = y op z
- 每个指令至多一个算符op, 至多三个操作数（地址）x y z
- 地址可以为：
  - 源程序中显式的变量名
  - 常量、字面量
  - 编译器生成的临时中间变量
- 也可以记为一个四元组：(op, x, y, z) (unary_op, x, y, _) …
*静态单赋值SSA:

Lab3实现过但不要求掌握。
SSA是特殊的三地址码：每个变量只能被赋值一次
加速分析优化，被广泛应用（如LLVM）

Tiger语言的IR Tree及其指令

许多现代语言采用多层IR: AST->IR1->IR2->…->IRk->机器码
Tiger只使用单个IR, 也就是IR Tree: AST->IR Tree->汇编->机器码

IR Tree是一种特殊的树形IR。指令列举如下：

表达式（有值，可能有副作用）：

Syntax	Description
CONST(i)	The integer constant i
NAME(n)	The symbolic constant n (e.g. a label is a name representing a address)
TEMP(t)	Temporary t.
BINOP(o, e1, e2)	The application of binary operator o to operands e1, e2. The integer arithmetic operators are PLUS, MINUS, MUL, DIV; the integer bitwise logical operators are AND, OR, XOR; the integer logical shift operators are LSHIFT, RSHIFT; the integer arithmetic right-shift is ARSHIFT.
MEM(e)	The contents of wordSize bytes of memory starting at address e. When MEM is used as the left child of a MOVE, it means “store”, but anywhere else it means “fetch”.
CALL(f, l)	A procedure call: the application of function f to argument list l.
ESEQ(s, e)	Statement s is evaluated for side effects, then e is evaluated for the result.

语句（无值，有副作用）：

Syntax	Description
MOVE(TEMP t, e)	Evaluate e and move it into temporary t.
MOVE(MEM(e1) e2)	Evaluate e1, yielding address a. THEN evaluate e2, and store the result into wordSize bytes of memory starting at a.
EXP(e)	Evaluate e and discard the result.
JUMP(e, labs)	Transfer control (jump) to address e. The destination e may be a literal label, as in NAME(lab), or it may be an address calculated by any other kind of expression.
CJUMP(o, e1, e2, t, f)	Evaluate e1, e2 in that order, yielding values a, b. Then compare a, b using the relational operator o. If the result is true, jump to t; otherwise jump to f.
SEQ(s1, s2)	The statement s1 followed by s2.
LABEL(n)	DEFINE the constant value of name n to be the current machine code address.

每个指令都对应IR Tree的一颗子树。指令为根，操作数为其子节点。

在这种中间表示中，我们假定有无数个寄存器。

重要指令：ESEQ(s, e):

首先，s被执行(evaluate), 可能带有副作用(side effect).
而后，e被执行作为指令的值。

例如，ESEQ(a=5, a+5)会返回值10, 同时副作用是a的值变为 5.

❗副作用=更新了内存单元或更改了寄存器的值

从AST生成IR Tree

~~这部分看看就行~~

总览
Tiger语言并不区分语句(statement)和表达式。
AST中的表达式(expression)可以分为：
- 返回数值的，记为Ex.
- 不返回数值的，记为Nx.
- 返回布尔值：用于条件跳转，记为Cx.
  加上一些辅助函数unEx unNx unCx用于在不同类型之间转换。
- 例如flag:= (a>b | c<d), 右侧是Cx没有返回值，要转换成Ex.
  - 表达式上下文不同，含义也不同，因此需要我们在这一步根据情况像这样进行转换。
  - 说到底，IR翻译是上下文有关问题，不便用CFG刻画。
变量翻译
- 普通变量
  - 相对FP的偏移是固定的。假设偏移量为k，则内存中变量的值为：MEM(BINOP(PLUS,TEMP fp, CONST k))
  - 注意，对于一些常见的操作（例如加法）有如下简写：BINOP(PLUS, a, b) = +(a, b)
  - 因此若变量a在内存中为InFrame(k), 则F_Exp(a,T_Temp(F_FP())翻译为MEM(BINOP(PLUS,TEMPFP,CONST(k)))
  - 而如果变量b在寄存器中为InReg(t_832), 则直接翻译为TEMP(t_832)
- 数组变量
  - 其实就是一种固定的指针，只是没法直接拷贝（这一点取决于具体语言有所不同，Pascal就可以）
  - Tiger语言提供Record类型，类似结构体。本质上还是指针，可以（浅）拷贝
左值与右值
初略的理解：
右值：可以出现在赋值语句右侧，不能出现在左侧
左值：可以出现在赋值语句左侧和右侧

🤭当然C++作为一门博大精深的语言把左值、右值、纯右值、将亡值的定义和用法给玩出花来了。左值和将亡值合称泛左值(generalized lvalue=glvalue)，纯右值和将亡值合称右值(right value=rvalue)。

左值/右值各自又分为两种：
- 标量(scalar): 只有一个元素（比如单个的变量名）
- 结构化的(structured): 例如C中的结构体和数组
  - 在这种情况下，从内存中取值的指令MEM(addr)要修改为MEM(addr, size)
  - 当然Tiger语言并不需要：因为在Tiger语言中所有变量和左值都是标量（Tiger的数组和record本质上只是指针）。
杂项

对于这部分内容，如果认真写过Lab3: 实现AST->IR的应该可以直接无视。

下标索引与field选择
- 数组：考虑a[i], 其实际地址为(i-l)*s+a, 其中a为基地址，s为元素大小，l为最小索引值（l取0时即为i*s+a）。
- Record: a.f地址自然是offset(f)+a, 其中offset(f)代表该field在Record中的固定偏移量
内存安全

内存漏洞普遍存在且危害大。
部分解决方法：
- 插入额外的指令动态检查数组越界或空指针
  - 性能↓↓↓
- 静态检查：例如borrow checker
运算符与条件语句

二元运算符的翻译是显然的。
一元运算符可以由等效的二元运算符表达式代替：-a = 0-a …
条件表达式可以转写为条件跳转，同时还能实现短路功能。
If, While, For

通过多个LABEL和条件跳转完成。
结构：
- If(cond): cjump(cond,:TRUE,:FALSE) :TRUE then :FALSE else
- While(cond): :TEST cjump(cond,...) body :DONE
  - 遇到break则跳转到:DONE, 遇到continue则跳转到:TEST
- For(init;cond;each): 转写为While即可。不过要记得及时跳出循环，因此在开头和执行each前都要判断cond是否成立。
函数调用

显然的。但是记得在参数列表开头加入static link:
CALL(NAME :LABEL_f,[SL, e1, e2, ..., en])
类型、变量与函数定义
- 丢弃类型定义（毕竟只是别名）
- 确定变量相对函数frame的偏移
- 把变量初始化值转为赋值语句，插入初始化处
- 函数定义分为三部分：
  - prologue:
    - 函数入口的LABEL标记
    - 更改栈帧的FP/SP以创建新栈帧
    - 保存不逃逸的参数到可用寄存器
    - 保存逃逸的参数到栈帧（包含Static link）
    - 保存callee-saved的寄存器到栈帧（例如返回地址）
  - body: 翻译的函数体
  - epiloge:
    - 保存返回值到寄存器（或栈上某地址）
    - 从栈帧中恢复callee-saved的寄存器
    - 回退到调用者的栈帧（更改FP/SP）
    - Return指令
    - 【可选】伪指令（标记函数在此结束）
重定位

对于条件跳转或其他跳转指令的目的地址有可能在此时没法直接确定。例如C语言的编译单元是每个.c .h文件，并不知道其他文件存在，所以可能遇到如下情况：
- 需要函数入口/变量的绝对地址，但目前只知道相对地址。
- 需要访问在外部定义的函数/变量，但尚未进行链接。
如果都能直接通过偏移找到位置，那么就是 “位置无关代码(PIC)” 了。
我们维护一个表记录需要待确定、需要在之后被填入的地址在哪些位置，留待日后使用。
参考ELF的.rel.text

Part 14: 基本块与traces

轨迹 = trace

注：这里的许多概念都是针对Tiger语言的，承接上文。
在将IR的AST翻译为机器码的过程中，不可避免地需要解决将“树形的”AST转换到“线性的”机器码这一问题。
例如：一个包含ESEQ子节点的BINOP树代表一个二元运算符表达式。但由于ESEQ有副作用，这个表达式的值取决于ESEQ先求值/后求值，是存在歧义的。
解决方法：将IR Tree变换为 正规形式(canonical form) ，而内部存在很多 正规树(canonical tree) （详见下文）.

正规形式Canonical Form

就是某个事物（树/代码）经过规范化后的形式。
例如经过 canonicalization 的树是一种 canonical form.

对比 IR Tree 与 canonical form:

IR Tree:
- 容易从源码AST生成
- 难以直接翻译为机器码
Canonical form:
- SEQ节点都在最右侧一路向下：
- 一个函数就是一个大SEQ序列：SEQ(s1,s2,s3...)
- 可以直接生成机器码

IR Tree 的 canonicalization 需要如下三步：

IR树被转化/重写，或者说线性化为一些正规树。
线性化：消除ESEQ以及把CALL向上挪。最后把树中的SEQ删去，这棵树就会“破碎”成很多正规树。
正规树被组装成一些基本块(basic block), 内部不包含LABEL与跳转语句。
这句话很别扭，更人体工程学的说法应该是“LABEL和跳转语句把代码（或这些树）分割成了不同基本块。”
基本块被排序成一些trace, trace 中的CJUMP指令后紧跟着条件不成立需要跳转到的false标签。
这是因为在IR Tree中CJUMP条件为真/假分别跳转至两个不同标签，但事实上机器码可以顺着执行下去(fall-through), 只有条件为真才需要跳转到远处，否则直接不跳转往下继续运行即可。

所以我们并没有真的“生成”一颗叫 canonical form 的树：我们生成的是等价的、接近机器语言、能用于后续指令选择的代码。
Canonical tree, canonical form 这两个概念有点乱，不过最主要的还是知道 canonical tree 的性质以及 canonicalization 的具体步骤（见下）。

正规树Canonical Tree

一种中间体，从 IR Tree 线性化而来。
不要太纠结这个概念本身。正规树，不过是因为要重排一些指令，不得不破碎原来的树为森林后，为这些树起的一个过于术语化的名字。

Canonical tree 的性质：

根节点为 语句(statement) ，所以正规树就对应IR中的一个语句，也就是IR Tree中的一个子树。
- 只不过这些额外约束，所以子树可能需要经过变换，结构会改变。
其他所有节点都是表达式。
不存在SEQ或者ESEQ。
- SEQ: 用于分割出这些canonical tree, 自然被删了不存在。
- ESEQ: 被变换成SEQ然后也被删了（详见下文）。
每个CALL节点的父节点即为canonical tree的根节点，且只能为EXP或MOVE.
- 事实上至多只能有一个CALL节点，因为我们规定EXP或MOVE只能包含一个CALL.
  这是因为实现上返回值在指定寄存器里保存，如果有两个CALL就会导致覆写，需要引入新的临时寄存器保存值（详见下文）。

Stage 1: 线性化为正规树

线性化 = linearization
如果没有特别限定，本部分的“树”指的就是IR Tree.

消除ESEQ
首先要去除原先树中所有的ESEQ. 总的来说是不断向上“提升”ESEQ直到它可以转为SEQ.
部分规则如下：

Expression	Transforms to
ESEQ(s1, ESEQ(s2, e))	ESEQ(SEQ(s1, s2), e)
BINOP(op, ESEQ(s, e1), e2)	ESEQ(s, BINOP(op, e1, e2))
MEM(ESEQ(s, e1))	ESEQ(s, MEM(e1))
JUMP(ESEQ(s, e1))	SEQ(s, JUMP(e1))
CJUMP(op, ESEQ(s, e1), e2, l1, l2)	SEQ(s, CJUMP(op, e1, e2, l1, l2))
BINOP(op, e1, ESEQ(s, e2))	ESEQ(MOVE(TEMP t, e1), ESEQ(s, BINOP(op, TEMP t, e2)))
CJUMP(op, e1, ESEQ(s, e2), l1, l2)	SEQ(MOVE(TEMP t, e1), SEQ(s, CJUMP(op, TEMP t, e2, l1, l2)))
MOVE(ESEQ(s, e1), e2)	SEQ(s, MOVE(e1, e2))
CALL(f, a)	ESEQ(MOVE(TEMP t, CALL(f, a)), TEMP(t))

这些变换的成立性是容易验证的，
在这之中，要注意副作用的问题，也就是语句执行顺序对结果有影响的情况：例如对于BINOP(op, e1, ESEQ(s, e2))（e1先求值，而后执行s）：

如果s会影响e1的值，那么不能调换二者的执行顺序。
也就是说不一定能变形为ESEQ(s, BINOP(op, e1, e2))（s先执行，而后对e1求值）
解决方法：使用临时变量保存e1值。这种情况下则变形为ESEQ(MOVE(TEMP t,e1), ESEQ(s, BINOP(op, TEMP t, e2)))

可见，取决于s是否会影响e1值，有不同的变形策略。
事实上，“会不会影响取值”是一种称为“可交换性(commutativity)”的属性：

如果s不影响e1值，那么我们说s, e1 commute
如果s会影响e1值，那么我们说s, e1 do NOT commute

如果能判断两者是否commute, 就可以最大限度避免引入新的临时变量，使得目标代码尽可能短小、高效。遗憾的是由于内存读写等原因，这一判定问题是困难的。不过我们只需要进行保守近似即可。也就是说，如果我们的保守近似策略判定二者commute, 那么他们一定commute; 否则如果策略无法确信二者commute, 则保守地认为他们互相有可能影响（不commute）。

一种年轻，简单，有时幼稚(naïve)的策略是：

常量和所有语句commute
空语句和所有语句commute
其他情况均假定为not commute

当然，如果能进行别名分析(alias analyses)以判断某个内存地址是否会被两个不同指针指向, 就能确认更多的对象间commute, 得到更精确的近似。

移动CALL到顶层
常见的现代编译器都使用指定寄存器保存函数返回值。因此形如BINOP(PLUS, CALL(…), CALL(…))有多个CALL子节点的表达式虽然结构正确，但在实现中存在对该寄存器的使用冲突。
解决方法也很简单：对于多余的CALL(fun, args)直接转化为ESEQ(MOVE(TEMP t, CALL(fun, args)), TEMP t), 也就是使用临时变量保存返回值。
重排并消除SEQ
在执行完上述步骤后，整个树可能形如SEQ(SEQ(SEQ(..., sx), sy), sz).
现在需要把SEQ变为父节点的最右儿子（类似平衡树的旋转）。这只需要无脑应用SEQ(SEQ(a, b), c) => SEQ(a, seq(b, c))即可。
然后树就变成了：SEQ(s1, SEQ(s2, ..., SEQ(sn-1,sn)...))（也就是让SEQ集中在树的“右上”部分）

接下来把SEQ全部去除，只留下这些s1 … sn: 每个都是一颗不含SEQ/ESEQ的正规树！
至此第一阶段任务完成。

Stage 2&3: 处理条件跳转

大部分机器不具备CJUMP的两个分支跳转到两个不同块这种功能。通常来讲是一个分支是继续顺序向下执行，另一个分支进行跳转。
因此需要重排树，让CJUMP后紧接的就是一个label, 对应其中一个分支跳转到的块。
这需要以下两步：

Stage 2: 组装为基本块(basic block)
基本块指的是一串代码，进入则一路执行到块末尾。性质：
- 开头是一个 label 伪指令（入口唯一！）
- 最后一个指令是跳转、条件跳转或返回等terminator
- 中间不包含其他 label/terminator （出口唯一！）
本质上，如果没有跳转指令，程序只会一路向下执行。
正是跳转指令（JUMP/CJUMP/RET/…）令程序在执行中途跳出，而跳转的目标地址（也就是LABEL）令程序在执行中途跳入，才把原本的代码分割为了多个基本块。
控制流图(Control-Flow Graph = CFG)中的节点就是基本块，边就是跳转指令。~~打开IDA反编译立刻就能见到。~~

生成的过程是显然的：找到一个LABEL就新起一块；找到一个JUMP/CJUMP/RET/…就结束当前块并新起一块。有的块缺少LABEL或者terminator则补上一个。
Stage 3: 生成轨迹(trace)
基本块如何排列并不影响程序执行结果。
然而我们需要进行一些优化，尽可能减少跳转或提高跳转的效率。例如：
- 对于CJUMP(cond, true, false), 将false label对应的块紧挨着放置在CJUMP指令后，这样执行时就可以fall through
- 尝试将无条件跳转JUMP的目标label对应的块直接放在JUMP后
- 如果可以，甚至可以直接删除部分JUMP, 例如将函数内联
- 优化缓存命中率:
- …
在此定义几个相关概念:
- 轨迹trace
  - 一个可以被按顺序执行完毕的指令序列
  - 说人话：几个连接在一起的基本块构成一个trace
  - CFG图中的一条链就是一个trace
- covering set of traces
  - 一个集合，元素是许多无环trace
  - 每个基本块在且恰好在一个trace中（i.e. 集合能覆盖整个CFG图）
有一个比较显然的构建方法：从源节点（不叫根节点是因为这只是个图，大概率不是棵树）开始跑一次DFS即可。
每次从一个未被染色的节点开始，递归地对于每个后继节点，如果还未染色则加入当前trace。
重复该过程直到整个图都被染色。

通过这种方式可以去掉不少跳转。
这是因为现在可以转变思维：原先的跳转指令似乎毫无关联，而现在则是把其中一些连在一起成为traces，然后默认代码执行是在一个trace上走到底的。于是只有要切换trace时才需要一个跳转。
可见，其实我们希望被经常执行的一段代码序列要自己成一个trace，这样就可以尽量减少跳转，增加性能。
在某个判据(criteria)下最好的一些trace就可以被称为 “optimal traces” .
例如如果我们的判据是“最少的跳转指令”，对于While语句，通过合理的重排就可以去掉一个跳转达成：

IR->机器码：小结

一共四步：

把IR Tree转成一些canonical trees
重排这些canonical trees为traces, 使得CJUMP(cond, :true, :false)后紧跟着LABEL(:false)
指令选择：从 canonical trees 产生伪汇编代码
对伪汇编代码进行寄存器分配：确定哪些值可以放置在寄存器中
指令调度（不在本课程中）：通过重排等操作优化代码、实现指令级并行

其中后 3 步将在后文展开阐述。

Part 15: 指令选择

回顾现代编译器架构：指令选择 开始是编译器的后端部分。
LLVM支持用tblgen描述后端，从而自动生成指令选择器。

指令选择概述

任务： 把IR转化为 抽象汇编代码。

抽象汇编代码=

具有有限个寄存器的汇编代码；
为中间结果创造新的临时寄存器；
在之后的流程中，会把这些寄存器映射到物理寄存器。

指令选择要解决的问题：IR的一个语句有多种可能的实现方式，需要确定为其中“最好”的一种。
最好= 最快/最小/最省电……这个判据取决于具体需求。总之需要综合考虑操作数/结果的访存需求，指令本身的代价等。

例如对于MOVE(TEMP(t1), TEMP(t1) + MEM(TEMP(FP)+4)), 既可以翻译为：

mov t2, rbp
add t2, 4
mov r3, [t2]
add t1, t3

，也可以翻译为：

1	add t1, [rbp + 4]

指令选择一种可能的实现方式：对IR进行模式匹配，一个模式匹配一些IR片段，转化为机器指令
IR Tree 是一种 tree-oriented IR, 自然需要在树上进行模式匹配。例如基于动态规划(DP)的匹配。
同理对于线性IR，就需要一些字符串匹配。例如纯文本匹配。
当然，匹配器(matcher)都是因地制宜相差甚远的，我们不需要当一个分类学家。

接下来把重心放在树形IR上。

指令选择算法：基于树覆盖

这里的覆盖意指：显然的，整棵 IR Tree 需要被完全覆盖才能完成翻译流程。
为了方便起见，接下来假设目标机器码是一个简单的架构（指令集）：Jouette架构。它基本上就是RISC-V的子集。我们约定：

寄存器r0永远为0
数据/地址能直接在寄存器中放得下
每时钟周期只有1个指令执行
每个指令延迟1时钟周期（但内存-内存数据拷贝使用的MOVEM指令除外）

有如下翻译方式：

宏展开/模板匹配
- 公式化地，把每条IR直接展开成一或多条机器指令
- 缺点：缺乏优化
  - 只能1->1或1->N, 但多条IR指令有时明明可以合并(N->1)
  - 盲目的，缺乏上下关联
通过寻找树上的模式(tree patterns)
- 将在下文详细研究。
- Tree Pattern: IR Tree的某个片段如果长得符合某个树形的模式(tree pattern)，就可以把这部分对应到一条机器码。
  - 这种模式匹配出来的 IR Tree 片段被叫做 tile.
  - tile 是模式匹配到的一个实例。
- 比如LOAD ri <- M[rj+c]对应的模式就可以是MEM(BINOP(PLUS, _expr_, CONST(_expr_)))
- 目标：没有重叠地覆盖整棵IR Tree. 这个过程称为tiling
- 把机器码转为对应的 tree patterns (注意可能有多种模式都可以翻译到这种机器码)。以Jouette架构为例：
  - 接下来只需找到一种方式让各种机器指令的 tree pattern 能够覆盖整颗 IR Tree, 就任务完成了。
    X86的例子：
    
    Jouette的例子，其中a数组每个元素占据4个储存地址，因此要翻译的IR指令是M[a+i*4]:=x：

现在要做的是找到一种方法，使得生成的机器代码跑的比香港记者还快。
注：以下讨论隐含的前提是每个指令速度一致。但是对于RISC指令集（见下一节）来说并非如此，有的指令可能耗费高达数十时钟周期。好消息是Jouette指令集不仅单发射还固定延迟，所以指令少即是跑得快。

每个Tile对应一个代价(cost), 反应了生成的目标机器指令运行的代价（功耗/延迟/速度……取决于你）。

可以用很多小的tile轻松覆盖整棵树，但是大量tile对应大量目标代码，很长很慢；
也可以用一些大块的tile进行覆盖，这样tile量少对应目标代码也较小，跑得快（但是这使得覆盖问题本身变得困难）。

为此我们需要区分如下两个概念：

Optimum tiling
- 全局最优：所有tiles总代价最小
Optimal tiling
- 局部最优：没有相邻的tile可以被合并成一个tile了

显然全局最优一定局部最优，但反之则不然。

接下来就是不同的指令选择算法（划重点！）：

Maximal Munch: 寻找optimal tiling (局部最优的)
- 自顶向下
- 用可用的最大tile覆盖当前节点
- 递归地对（那些根节点）还未被覆盖的每个子树应用该算法
- 把所有tile对应的指令按照覆盖顺序的逆序收集起来即为目标机器码
  - 为何逆序？考虑一个简单的BINOP(PLUS, 1, 5), 该算法会先用加法指令对应的tile覆盖，然后再对操作数表达式（1和5）递归生成对应的tile. 但显然要先有操作数表达式的值，才能对他们执行加法指令。
- 运用贪心思想：更大的tile=>更精确的模式匹配=>更多指令中的信息被运用=>更优的代码
动态规划(dynamic programming, DP): optimum tiling (全局最优的)
- 自底向上
- 每个节点x都有一个代价，是代价最小的覆盖方案的代价。
  而每个可用于覆盖节点x的tile都对应一种方案，该方案的代价为该tile的子树代价之和，加上这个tile T固有的代价：
  $ cost(x)=\underset{\forall \text{tile } T \text{ that can cover node } x}{min} (cost_T + \underset{\forall \text{child } y \text{ of tile } T}{\sum} cost(y)) $
  例如，假设ADD指令对应两种tile,
  - 第一种，对应最原始的模式BINOP(PLUS, _expr1_, _expr2_)，如果使用这个 tile, 该节点的代价自然就是表达式1（左子树）的代价+表达式2（右子树）的代价+1;
  - 第二种，操作数都是常数可以直接优化为常值，对应模式为BINOP(PLUS, CONST(num), CONST(num))，那么以该节点为根的子树立刻被完全覆盖，该节点代价就是固定值1 !
  如果这两种tile都可用的话，显然应该选择第二种。
- tile 的子树的代价均已知，在可用于覆盖当前节点的tiles中，采用一个使得该节点代价最小的进行覆盖即可。
- 正确性：使得某节点代价最小的 tile, 其子树必然也以代价最小的tile覆盖。否则子树可以替换为更优的覆盖方式，结果一定不会更劣。
- 时间复杂度：线性（因为可用 tile 数与IR Tree节点数量都是已知常数）。
- 步骤：
  1. 自底向上，递归地求出所有子树的代价
  2. 尝试所有在当前节点可用的tile, 每种tile对应一个覆盖方案
  3. 找到代价最低的一个方案，记录所用的 tile 和代价在该节点上
  4. 根节点的最小代价被找到，意味着整棵树的optimum tiling已完成，开始指令发射(instruction emission).
    也就是从根节点开始，递归地，先发射该节点 tile 子树的指令，而后发射该节点 tile 的指令。
    例如：
    1. 寻找CONST 1与CONST 2的最小代价与tile（略）
    2. 寻找+的最小代价与 tile, 方案2被采用：
    3. 寻找MEM的最小代价与 tile, 方案3被采用：
    4. 发射指令：

这里需要特别注意：tile 的子树不是指该节点的子树，而是用 tile 覆盖该节点以及部分子节点后，那些没被覆盖到的子树。
例如下图中红色的 tile 对应的子树并非两个MEM子树（因为被这个tile覆盖在内），而是两个PLUS子树：

树语法Tree Grammar

tree grammar 是一种上下文无关文法。
可以用 tree grammar 描述这些 tile.

需要记录：

pattern: 模式是什么样的
replacement: 这个pattern被替换之后，原来的位置要用什么代替（比如一个加法指令被替换后，要用加法结果所在的寄存器替换该表达式）
cost: tile 的固有代价
template: 生成的目标代码模板

pattern->replacement	cost	template
+(r1,r2) -> r2	1	add r1,r2
store(r1,load(r2)) -> DONE	5	movem r2,r1

CISC vs. RISC

CISC
- Complex Instruction Set Computer = 复杂指令集计算机
- 可能有多个寄存器类，有的指令只能使用一部分
- 指令不等长
- 计算指令可用内存作为操作数
- 内存寻址方式多样
- 指令可能有副作用
- …
- 难以使用tree pattern-based tiling建模！
RISC
- Reduced Instruction Set Computer = 精简指令集计算机
- 寄存器只有一类
- 指令等长（例如32bit）
- 计算指令只能用寄存器作为操作数
- 内存寻址方式少
- 指令没有副作用（WYSIWYG）
- …

CISC 引入了一些问题：

较少的寄存器：用一些临时节点代替，让寄存器分配器干活
要求操作数/结果放在不同寄存器：多显式 move 即可
使用2地址码，但IR是3地址码：t1<-t2+t3可转为t1<-t2; t1<-t1+t3;. 然后让寄存器分配器干活
操作数使用了内存值：先放进寄存器即可
有副作用（比如某种自增计数器）：无视/改写/换一套算法然后改用DAG模式匹配……

对于CISC, IR Tree中的多个指令可能只需要一个机器指令就能解决，此时 optimal 和 optimum 区别巨大；
对于RISC, 很多时候二者没有什么区别，因此只需要最简单的 tiling 算法。

现代编译器还需要额外考虑以下问题：

多级流水中指令可以同时发射执行，因此多指令的执行时间并非简单加和即可
cost只是一种不错的估计，而不能反应全貌。
- 例如，指令顺序可能影响流水线的 stall 频率从而影响 CPU 的 IPC, 指令间复杂的羁绊显然无法通过cost这一简单数字反应……

Part 16: 活跃变量分析

*编译器优化

不要求掌握。

例如GCC的 -O 系列编译选项。

优化可以分为：

空间优化
时间优化
能耗优化

优化可以是：

本地的：一个basic block里
全局的（过程内）：在整个过程（函数/方法）中
全程序的（跨过程）：多个过程（函数/方法）之间，甚至整个程序，甚至多个通过链接器连接起来的源程序间（参见LTO, link time optimization）

常见优化（闲的话可以在lab里实现一下）：

编译期常量求值：常量折叠、常量传播
减少计算代价：代数简化、强度折减(strength reduction)
消除重复计算：拷贝传播、值编号、消除公因子
向量化：超字级并行(superword-level parallelism, SLP)、循环向量化
循环优化：循环不变代码外提、循环展开、合并拆分、代码提升(code hoisting)
减少函数调用开销：内联、尾递归优化
控制流优化：死代码消除、if语句简化

这些优化需要一些对代码的分析：

控制流分析：基本块之间的跳转关系
- 例如：死代码消除
数据流分析：数据依赖、引用关系，活跃情况
- 例如：向量化
别名分析：寻找可能指向同一地址的指针

数据流分析Dataflow Analysis

CFG = Control-Flow Graph
- 节点代表一个语句
  - 一般来说，我们会将多个相邻的不包含跳转指令，也不是跳转指令目的地的多个语句组合为一个基本块
- 有向边代表一个可能的跳转

我们可以从CFG（或其他类型的中间表示）中静态（i.e. 不需要真的运行程序）推导出一些程序的行为信息。
这其中就包括马上要研究的话题：变量的活跃性。

活跃性分析Liveness Analysis

定义变量的liveness: 我们说变量x在执行到一个语句s时是活跃(live)的，当且仅当：

存在某个语句s'使用了x
存在一个执行路径，能从s执行到s'
在某个这样的路径上，x没有被重新赋值/定义过

简单粗暴的理解：活跃变量=还有用的变量，需要留着备用；不活跃变量=没有用的变量=死变量，不再使用，对应的寄存器可以释放。

为什么要进行活跃性分析呢？因为从Low level IR到机器码的翻译过程中，需要把有限但很多的抽象寄存器对应到物理寄存器上，也就是寄存器分配。
如果能识别不需要使用的变量（i.e. 不活跃变量），那么其对应的虚拟/物理寄存器就可以被释放，再次用于分配。

可以把活跃变量分析理解为一种特殊的生命周期分析，只不过除了显式的变量，还要考虑那些中间值，统称 temporaries.
temporaries 其实经常指的就是 IR 中的那些虚拟寄存器。

活跃性分析用途：

指导/优化寄存器分配，减少寄存器使用
例如对于：
1
2
3
4
1: a = 1; // a lives in out[1]->in[2]
2: b = a + 2; // b lives in out[2]->in[3]
3: c = b + 3; // c lives in out[3]->in[4]
4: return c;
我们会发现他们的 活跃区间(live range) 并不重叠，可以映射到同一个物理寄存器r，并据此重写代码：
1
2
3
4
r=1;
r=r+2;
r=r+3;
return r;
消除多余代码：例如删去未被使用的变量
优化 IR 生成
提高安全性：检查未初始化的变量
…

活跃性分析：数据流方程

首先要明确一点：不可能精确知道一个变量在某处是否活跃，所以我们要做的只是保守估计（i.e. 标记为不活跃的变量一定不活跃，但反之则不然）。
这是因为对于代码片段int x=10; f(); return x;:
如果能判断x是否在定义并初始化之后依旧活跃，就等于能判断f()是否停机。而众所周知停机问题不可判定，so sad.

在本节中，我们需要分析的是活跃变量。
而变量在CFG上，通过有向边“流向”各个节点。
所以我们将通过数据流分析，找到每个节点可能会有哪些变量“流过”；换言之，找到每个节点可能会有哪些变量在其上是活跃的。

一些CFG上的术语定义（可能很抽象，往后看就行）：

node/节点：在本文中均指只包含一个语句的
out-edges: 出边，指向后继节点
in-edges: 入边，来自前驱节点
pred[n]: 节点n的前驱节点们
succ[n]: 节点n的后继节点们
fact: 从CFG中能推断出的一些结论/信息/事实，这些结论是“绑定”在有向边上的
- 例如现在要研究的 变量活跃性(liveness) 就是一个fact.
- 变量是否活跃这一信息是通过这些有向边传递的。
- 后文不会用到这个概念。
in[n]: 入口活跃集合，包含节点n的入边(in-edges)上的所有facts
- 对于本节来说，我们要求的是变量的liveness, 所以为在节点n内 live-in(定义见下文) 的变量。
  - 也就是 the live-in set of node n
  - 也就是 the variables that are live-in at node n
  - 可以简单理解为：在节点n中的代码执行前，哪些变量处于活跃状态，有可能在当前节点n或未来被用到。
- 稍后会详细解释该集合的含义，以及如何计算它。
out[n]: 出口活跃集合，包含节点n的出边(out-edges)上的所有facts
- 对于本节来说，我们要求的是变量的liveness, 所以为在节点n内 live-out(定义见下文) 的变量。
  - 也就是 the live-out set of node n
  - 也就是 the variables that are live-out at node n
  - 可以简单理解为：在节点n中的语句执行后，哪些变量处于活跃状态，有可能在未来被用到。
- 稍后会详细解释该集合的含义，以及如何计算它。
transfer function: 传递函数，定义一个节点上的信息如何通过传递给另一个节点
- 比如稍后会得到的两个in/out的求解方程（等式）。
- 后文不会用到这个概念。
use: 如果一个语句的右侧(RHS)出现了变量x, 我们说这个语句use了x
- 这意味着变量x中储存的值被使用了，引入了一个数据依赖。
use of a variable x: 所有use了x的节点集合
def = define: 对x赋值即为 define 了x
- 注意：这里的 IR 没有类似 C 语言变量定义的语句，而初次赋值其实就是一种“变量定义”，或者叫 define。
- 为何后续再次对x赋值也是define？这是因为我们如果以一种比较函数式的视角来看，我们并非是“把值val储存到x中”，而是将“名字x绑定到值val上”。
  这不难理解：我们关心的是数据之间的依赖性（数据流），x只是对某个值的一个指代/一个记号/一个名字。
  x=1; x=x+1; return x; 与 x=1; y=x+1; return y; 是完全等价的。
  也就是说，每次对x的赋值都是一个“重绑定”：原来的旧x已经死了，新的x只是恰好名字也叫x, 但它已经是全新的一个变量了。
def of a variable x: 所有define了x的节点集合
def of a node N: 节点N定义的变量集合
x is live on an edge: 存在一条以这条有向边(edge)开始的路径，终点指向一个use of x, 且中间经过的节点不包含任何def of x
- 这意味着：x可能在之后被使用；而且在被使用前没有被重定义/赋值过（这表明数据确实可能存在依赖：那个 use 必须真的使用现在这个x储存的值）。
live-in: 如果x live on 节点的任意一个入边，那么我们说x live-in 该节点
live-out: 如果x live on 节点的任意一个出边，那么我们说x live-out 该节点

活跃变量分析是数据流分析的冰山一角。关于传递函数等概念感兴趣可以查看编译原理-代码优化3.

可以把每个节点n理解为一个工厂，in[n]是工厂需要购买的材料，out[n]是工厂需要提供的材料。
工厂有时会自己生产新的材料给下游使用（def[n]），有时会消耗上游提供的材料（use[n]），其他时候可能只是把上游的材料原封不动地转交给下游工厂（in[n]和out[n]的交集*）

*严格来说不考虑重绑定，或者说静态单赋值的情况下是in[n]和out[n]的交集。
如果有重绑定就会有重名的情况：比如对于下图中的节点 3, 由于该节点进行了赋值操作（define）， in[3]中的c和out[3]中的c看似在交集中，但其实值已经被改变，已经是两个不同的变量了，只是“恰好”名字一样。

cfg example
例如对于上图：

如下信息可以直接获得：
- 5的出边有2条，分别指向2和6
- 4只有一条入边，来自3
- pred[3]={2}
- succ[5]={2, 6}
- def(a)={1, 4}
- use(a)={2, 5}
- def(3)={c}
- use(3)={b, c}
如下信息蕴含在图中，但无法直接获得，需要进一步求解：
- in[1]={c}, out[2]={a, c}
- in[2]={a, c}, out[2]={b, c}
- in[6]={c}, out[6]={}

记住：CFG 中的一个节点是一段代码，但是为了方便起见我们都假设只有一个语句在里面。所以其实你可以很简单地合并一串连续的代码（变成基本块）。我们说“执行某个节点”，指的就是执行节点里的代码。

接下来的重点就是找到一种方式计算in/out集合。
事实上可以迭代地不断计算、更新in[n]以及out[n], 直到他们在某次迭代后不再改变变（i.e. 到达了这个算法的不动点）。

要计算 in[n] 与 out[n], 需要用到以下几个规则(rule)：

If $ a \in in[n] $, then $ \forall m \in pred[n], a \in out[m] $
- 解释：每个前驱节点都可能是在该节点执行前的节点（我们在静态分析，无法确定到底是从何处执行到n的）。
  如果某个节点n要求执行前a是活跃的，我们想要确保无论是从pred[n]中的哪个前驱节点跳转而来，前驱节点执行完毕时a都是活跃的（因为我们在做保守估计）。
If $ a \in use[n] $, then $ a \in in[n] $
- 解释：如果某个节点n直接使用了变量a, 那当然要求a在节点执行前是活跃的。
If $ a \in out[n] $ and $ a \notin def[n] $ , then $ a \in in[n] $
- 解释：如果现在已知某个变量a必须在节点n执行完毕时活跃，但是n自己并没有定义a, 那显然a是从之前的前驱节点继承而来。
  因此，要求a在节点n执行之前就是活跃的。

从这些规则可以导出如下两个方程（等式），可直接用于迭代计算并更新 in[n] 与 out[n] 这两个集合:

$ in[n] = use[n] \cup (out[n]-def[n]) $
- 解释：节点n需要向前驱节点索取的活跃变量包括自己需要使用的use 并上后续别的节点需要使用的out. 不过如果节点自己定义了一些变量，则不需要向前驱节点索要，所以挖去def
$ out[n] = \underset{s \in succ[n]}{\cup} in[s] $
- 解释：后继节点要什么就给什么，后继节点的总需求就是该节点n需要供给的活跃变量。

解方程(equations)

应用这两个方程可以给出如下算法求解出in/out：

for each n
  // init. to empty sets, which is a very rough approximation:
  in[n] ←{}; out[n] ←{} 
repeat:
  for each n
    in'[n] ← in[n]; out'[n] ← out[n]
    
    // `⋃` stands for "union"

    // use/def is easy to obtain at the very beginning
    in[n] ← use[n] ⋃ (out[n] − def[n]) 

    out[n] ← ⋃{ in[s], where s in succ[n] }

until in'[n] = in[n] and out'[n] = out[n] for all n 
// i.e. until no update can be made

每次迭代中集合总会单调地变大。
对于刚刚的这个 CFG, 其求解流程如下，在7步后收敛：
calc-liveness-forward

似乎每一步能更新的很少。但事实上想要加速收敛的技巧就藏在for each n这一句中：只需要反转一下每次迭代遍历节点的顺序即可！

我们原先是顺着CFG中的有向边方向进行更新（1->6, in->out）。
然而考虑信息在节点间的传递是通过 $ out[n] = \underset{s \in succ[n]}{\cup} in[s] $ 完成的，其方向是从后向前的。
所以我们可以在每次迭代中，都按照逆序（6->1, out->in）进行计算：
calc-liveness-backward

只需要 3 次迭代就收敛。

本质上，liveness问题是“需求决定供给”的：后续的节点有对变量的使用需求，之前的节点才可能需要提供一个活跃的变量。
liveness 就是一种 fact.
迭代更新顺序也应遵循这些 facts 的流动方向。而在活跃性分析中，liveness 反向流过这些 CFG 的有向边，并且是先影响 out 再进而影响 in.
因此我们迭代的过程也要遵从这一规律，使得一次迭代中，某一个 use 引入的需求能够迅速传遍整个 CFG, 而非每次只影响附近的个别节点，

关于迭代方向的重要性，可以类比一下冒泡排序：如果现有数组2 3 4 5 6 7 1需要排序，那么可以看出1自然的流动方向就是从右到左。
冒泡排序每次迭代会按顺序检查相邻的数字并交换逆序对。
如果从右到左，第一次迭代就可以完成排序：1连续被交换，迅速“上浮”至第一的位置；
如果非要从左到右，那么每次迭代1都只能被交换一次，上浮一位，需要多达6次迭代才能完成！

最终， out[n]会被用于寄存器分配：毕竟最终要决定的是执行语句之后需要保留哪些变量 （供给侧）。

活跃性分析杂项

把多个相邻的节点尽可能合并为基本块可以加速。
根据变量多少，视具体情况用 bitmap 或有序列表等方式储存集合可以更快。
实践中也可以每次专门求解某一变量x的数据流（in/out），因为大部分中间临时值的 live range 很短。
这一算法最差的时间复杂度可能为 $ \Omega (N^4)$, 其中N为节点个数。好在这一上界很难达到……
算法求解的是“最小不动点”：极端情况下，你当然可以让所有变量都是live的，这也是个不动点，但不是我们想要的。
进一步优化算法：可以用队列记录有可能需要被进一步更新的节点（类似BFS）。
变量活跃性可以分为：
- 动态的dynamic liveness: 运行时判断，显然是一种under-approximation, 因为不能覆盖所有可能执行路径。
- 静态的static liveness: 像刚刚做的一样在编译期判断，显然是一种over-approximation, 因为估计得很保守，而事实上有些路径不可能被执行到。

Part 17: 寄存器分配

我们当然希望一切储存访问都尽可能通过寄存器完成，因为寄存器的速度远快于内存的速度。
之前，在 IR 中可以有任意多的虚拟寄存器，但我们在物理架构上不可能有任意多的寄存器。
因此他们中的一些势必要被移动到内存中。

寄存器分配算法的任务：

将 IR 中大量的虚拟寄存器（储存变量或者运算的中间临时结果，统称 temporaries）分配到固定数量的 k 个物理寄存器上，保证代码使用不超过 k 个寄存器
使得内存访问、储存尽可能少
使得内存上用于储存 spilled 值的空间尽可能小
算法需要尽可能高效
- 典型的复杂度：O(n) 或 O(nlogn)

在工程实践中，算法的实现大致分为两种：

图染色： 效果好，但是慢
- “传统派”：GCC等采用
线性扫描： 效果也很好，接近图染色的效果；运行速度快
- “维新派”：LLVM等采用

不同的分配策略：

Naïve register allocation: 变量（广义的变量，也就是虚拟寄存器储存的 temporaries）一股脑全塞内存里！
局部寄存器分配：在 basic block 里进行，无法应对跨越多个块的对寄存器的复用。
全局寄存器分配：在函数内进行，经常基于图染色：
1. 建立一个干扰图/相交图 。
  - 这是一个无向图，每个边都代表两端的 temporary 同时存在过，不能被分配到同一个寄存器里。我们马上会详细阐述。
2. 对于 k 个物理寄存器，找到这个图的 k-coloring(k染色)：也就是边连接的相邻节点不被染为同一个颜色的情况下，用 k 种颜色染色所有节点。
  - 如果染色成功：每种颜色对应一个物理寄存器，分配完成
  - 如果染色失败：说明这个图并非 k-colorable，需要修改代码(原文：change the code to a nearby)。
    - 会在后文详细阐述。

干扰图Interference Graph

相交图 = 干扰图 = interference graph = conflict graph

如果两个虚拟寄存器a和b因为某种约束限制，使得它们无法被分配到同一个物理寄存器中，我们就说a与b之间存在 干扰(interference) ，或者说他们”interfere”。
这些约束包括但不限于：
- live range 有重叠（最主要的原因！）：某个时刻a和b都是活跃的，值需要得到保留，我们自然无法在同一个寄存器中同时保存a和b；
- 产出/使用a这个值的指令比较特殊，不能使用某些特定寄存器（比如r1），那么a和r1也 interfere 了。
  - 读者可能会疑惑r1不是物理寄存器吗？其实我们不用太纠结这个：最终都是为了让图染色算法能够“感知”到有这样一个约束存在，所以大可以把物理寄存器添加到虚拟寄存器中，图只要改一改就行。
    说到底，现在要禁止a染上r1对应的颜色：
    试图 ban 掉某种颜色：可以在一开始就把 k 个物理寄存器加入图中，对应 k 个节点 r1 r2 … rk, 并在他们之间建立全连接（注意！更高效的做法参见后文 预染色 部分），
    这将强迫图染色器为他们分配 k 种不同的颜色。
    建立干涉图的过程中，如果a和r1 interfere 了，只需要在图中连接a与对应的节点r1即可。
节点：一个节点就是 IR 中的一个虚拟寄存器，或者说一个 temporary.
无向边：一条边代表一个 interference, 边连接的两个节点不能被分配到同一个物理寄存器。

建图步骤：基本上就是在同时存在的变量之间连边。在变量t被定义（赋值也是定义）时，把它和所有其他的、当前活跃(live)的变量vi连边 (b, vi) 即可：
例如对于如下程序（由于这里是一串线性指令，上一条指令的 live-out 就是下一条指令的 live-in, 因此把活跃变量写在指令中间）：

Inst.	Live vars	Operation
	a	-
b=a+2
	a, b	link b-a
c=b*b
	a, c	link c-a
b=c+1
	a, b	link b-a (duplicated)
return b*a

最终得到：
interference graph example

需要特别处理（或者说优化）涉及MOVE指令的情况：
如果通过MOVE执行了t:=s这样的移动操作，由于MOVE后t和s储存的值是相同的，其实暂时可以不添加 (s, t) 这条边，而是采用同一寄存器。
1
2
3
4
5
6
t := s (MOVE)
...
x := ... s ... (use of `s`)
...
// `t` can still be stored in the same register as `s` !
y := ... t ... (use of `t`)
换言之，此时t只是s的一个别名。
……直到t被重定义（非MOVE）时，如果s此时还 live, 才不得不添加 (s, t) 这条边。
如果最终s和t在整个分配流程后被证明确实可以使用同一个寄存器，那么这个自己拷贝到自己的MOVE指令会自然在生成机器码的过程中被我们优化掉。
这对于单静态赋值SSA这种存在大量MOVE的 IR 来说是一个很大的优化。
- 这种关系被称为移动关联(move-related)，在干扰图中可以用虚线表示。
绝大部分情况下不需要考虑可以无视的函数调用处理：
- （被调函数要用到的）Caller-saved 寄存器需要放在CALL指令的 def 处。这是因为子函数可以随便修改。
- 传参用的寄存器需要放在CALL指令的 use 处。这是显然的。
- Return指令的 def 为空。这是显然的。
- Return指令的 live-in / live-out / use 包含返回值和（调用者要用到的）callee-saved 寄存器。

关于如何加边，总结如下 （有点抽象，可以直接跳过，不会有任何问题） （请记得每次赋值、每个运算指令都是一种“定义”；out[n]即为 live-out 集合，定义在 CFG 部分，有疑惑可以回顾一下）：

对于定义了t的非MOVE指令n，我们有out[n]={b1, b2, ..., bj}, 则添加边(t, b1), (t, b2), …, (t, bj).

对于MOVE指令n, 记作t:=s, 有out[n]={b1, b2, ..., bk}, 则添加上述边(t, b1), (t, b2), …, (t, bj)中的一部分。具体而言，如果这些边都记作 (t, bi), 我们要求bi不是s，也不是某个s的别名.
换言之，如果bi是s或是某个s的别名，储存的值和s一样，那么现在就不需要在图上连边 (t, bi).

例如：

Inst.	Live vars	Operation
	a, b	link a-b (assume no aliasing)
t=a
	a, b, t	MOVE: link t-b, but not link t-a
a=a*2
	a, b, t	link a-b(dup), a-t
t=b
	a, b, t	MOVE: link t-a(dup), but not link t-b(though linked)
return a*t+b

图染色概述

vertex coloring: 对所有节点进行染色，且对于任何边，两个端点节点的颜色都不一样。
k染色(k-coloring): 最多使用 k 种颜色的 vertex coloring.

著名的四色定理指出：对于任意 “平面图” ，至多只需要 4 种颜色即可完成染色，也就是说所有平面图都是 4-colorable 的。
——温馨提示：这个定理和我们的课程内容八竿子打不着边。

在得到干扰图后，我们对其进行k染色。
染色完毕后，每一种颜色对应一个物理寄存器，节点颜色即为节点所对应的寄存器。
当然也有可能染色失败：这意味着需要超过k种颜色才能染色成功。
如果需要的颜色种数超过物理寄存器个数，说明 spilling （部分临时寄存器分配不到物理寄存器，不得不“溢出”到内存上）是必要的。

任务： 找到最小的 k, 使得染色可以成功。-> NP-hard!
对应的判定问题：检查图是否 k-colorable. -> NP-Complete!
所以其实并不需要找到“最小”的k，只需要“较小”的结果即可。也就是需要实现一个近似算法，以及一些启发式的想法。
换句话说，可以容忍找到的k不是最小的，或是误判一个事实上 k-colorable 的图无法被k染色。

接下来引入一种线性时间的算法，能给出不错的结果。大体分为4个部分：

Build: 建图（刚刚已经完成了）
Simplify: 对干扰图进行简化
Spill: 处理被挤出的寄存器
Select/Color: 进行节点染色操作

我们将在下文详细介绍并改进该算法。

请注意：我们提到的“变量”“temporary”“虚拟寄存器”“节点”其实基本上是同一个东西。
temporary 是更广义的变量，包含运算的中间值。IR 里的 temporary 有时也用“变量”称呼。
在 IR 里的这些 temporary 之后要进行寄存器分配。所以现在先假设有无数虚拟的寄存器，每个 temporary 都存在一个虚拟寄存器里。
而干扰图上的节点就代表这些虚拟寄存器。

一个简单的图染色算法

首先，考虑一个简化版本的、很粗糙的近似算法，用于判断图是否 k-colorable, 并给出染色方案：

Build: 建图，已经完成了。
Simplify:
- 如果从图G中存在一个节点n，其度数（i.e. 相邻节点数量）小于k, 令图G'为从G中移除该节点得到的图。
  那么如果G'是 k-colorable 的，则原来的图G也是。
  - 这是显然的：给定一个图G'的k染色方案，由于相邻节点数量不够多，一定有剩余的颜色分配给n.
    因此把G的k染色问题简化为了G'的k染色问题。
- 这就引出一个自然的启发式的算法：
  不断地从图中删除度数少于k的节点（并放入栈中）。
  可以保证，每次删除的这个节点都有剩余的、可用的颜色分配给他。
  如此重复删除下去，有机会直接把图简化成空图！这样就能直接宣告整个染色过程结束了。
Spill: 暂时留白，什么也不做。
Select: 接下来要从这个空图重建原图。每次从栈顶取出一个节点，一定有剩余的、可用的颜色能用于染色。
- 每次简化删除一个节点时，都保证如果删除后颜色够用，那么删除前颜色也够用。
- 因此对于每次删除，有删除后的k染色方案，就能推出一个删除前的k染色方案。
- 显然，空图是 k-colorable 的。因此如果图被删空了，我们就可以归纳地推出原图的k染色方案。
- 显然，删除顺序的逆序=归纳推理的顺序=算法找到的合法的染色顺序（所以使用的是栈）。

coloring-k2
coloring-rebuild

这个算法跑的很快（线性），但很容易误伤无辜：毕竟这只是个近似算法。
如果一个近似算法 fail 了，这个图事实上可能还是 k-colorable 的，只是这个算法能力不足以找到可行解。
对于现在这个简单的算法来说，fail 就意味着在某一步，所有节点的度数都>=k（或者说图中的节点度数都是 significant 的）.

此时不得不考虑如何实现刚刚留白的第三步，也就是处理 spilling: 也就是选择图中的一些节点，把他们放在内存（而非寄存器）中。

挤出Spilling

如果上述算法在某一步无法继续下去，也就是说图中所有节点的度数都>=k, 无法继续简化。
这就意味着染色失败了吗？其实并不一定：相邻节点数量少于k一定能染色成功；但这不代表邻居超过k个就一定失败。
如果相邻节点重复使用了部分颜色，那么该节点依旧可以使用剩下的。所以可以当作无事发生，继续删除该节点并压入栈中，该算法继续运行。

这就是 Chaitin-Briggs 提出的乐观染色(optimistic coloring): 如果遇到有 spill 可能的节点（i.e. 度数>=k）ns时，先乐观地假设它其实可以被染色成功，不会 spill, 依旧删除并压入栈中，继续该算法。
不过这就使得后续的 select 部分需要做出修改：

染色成功：把ns弹出栈时，邻居使用的颜色种数少于 k, 有剩余的颜色分配给ns. 这说明刚刚作出的乐观假设确实成立，万事大吉
染色失败：把ns弹出栈时，邻居已经使用了 k 种颜色, ns无法染色成功。这说明刚刚的乐观假设过度乐观了，需要进行 spill 操作
- 此时不为ns染色，也不终止这个算法，而是继续进行 select 直到所有像ns这样无法被染色成功，需要 spill 的节点都找出来。

现在，改进版的染色算法如下：

Build: 建立干扰图。
Simplify: 不断执行简化，如果找到可能 spill 的节点（度数>=k）则标记，并按照乐观染色策略继续进行，直到简化为空图。最终，我们就标记了许多无法被染色的节点。
Select: 当 select 算法运行一轮后，我们会发现：
- 这些无法被染色的节点中的一部分确实 spilled, 需要 do actual spills, 也就是改写和这部分变量读写相关的代码，继续执行第4步↓
- 不发生 actual spill, 染色成功！算法结束。
Rewrite: 改写代码，将每个 spilled 变量(actual spilled variables)移动到内存上：
1. 为 spilled 变量f分配内存地址fa(一般在栈帧上，除非太大或者有什么别的情况)
2. 引入新的fx系列 temporaries: f1 f2 … fn, 用于在每次使用/定义f时临时储存f的值。这些临时变量的 live range 较短，减少了 interference.
3. 在所有使用f的指令前加入fx:=load fa（读的时候先从内存载入）。
4. 在所有定义f的指令后加入store fx, fa（写的时候需要写进内存）。
使用改写后的代码，返回步骤1进行 Rebuild. 由于引入了一系列 temporaries, 需要重建干扰图。在 spilling 后，这个干扰图相比原先的会更简化，更容易被染色成功。

这个循环一般来说只需要一到两次就能结束。
下面来看一个例子，假设有4个物理寄存器（i.e. k=4）：
coloring k4
图中虚线代表MOVE.

入栈顺序：g h k d j e f b c m
染色：

Node	Color
m	1
c	3
b	2
f	2
e	4
j	3
d	4
k	1
h	2
g	4

coloring-k4-result

合并Coalescing

现在要进一步改进这个算法：在 simplify 后合并部分节点。

之前，我们说到对于t:=s这样的MOVE指令需要特殊处理：并不立刻为(t, s), (t, s1), (t, s2)…（其中s1, s2, … 代表目前活跃的 s 的别名，保存的值和 s 相同）这些点对添加边。因为此时 t 只是 s 的又一个别名，可以共享一个寄存器。
等到某个定义改变了其中一方的值，破坏了这种别名关系时，才真正连边。
而如果整个算法运行完毕后，发现MOVE指令对应的这些点对之间确实还没有边，就说明这些节点事实上可以被 合并(coalesce) 为同一个节点。
coalescing

好处👍：可能使得原图更容易染色，例如合并的这两个节点共用大部分的相邻节点
坏处👎：可能使得原图无法染色：极端情况下，合并后的节点的度数可能是合并前两个节点度数之和！

在此引入保守合并策略。当某些条件成立时才合并节点a和b.

有如下的策略可用：

Briggs: 确保合并出的新节点ab的相邻节点中，significant 节点（i.e. 度数>=k的节点） 数量少于 k 个。
- 避免创造新的 significant 节点。
- 这样在执行 simplify 时，ab相邻节点中的 non-significant 节点被去掉后，ab自己也成为 non-significant 节点。因此不会降低可染色性。
George: 对于a的每个相邻节点t, 要么t是 non-significant 节点，要么t和b之间本来就有 interference 边。
- non-significant 的邻居会被 simplify 掉。
- (a, t)与(b, t)合并得到新边(ab, t), 不会增加任何节点的度数。

冻结Freeze

要明确一点：合并操作是一把双刃剑。合并的不止是寄存器，还有节点对应 temporaries 的 live range. 新的节点，也就是新的 temporary 能“活更久”，对寄存器分配造成更大压力。如果因此造成了更多 spill, 那么得不偿失：与其进行内存读写，还不如不要自作主张“优化”掉MOVE指令。

如果 simplify 和 coalesce 都无法进行，我们寻找MOVE指令引入的低度数节点（也就是 non-significant 节点），或者说找一些低度数的 move-related 节点。
我们将这些节点“冻结”，也就是去除这些节点相关的移动关联(move-related)关系（i.e. 把虚线直接去掉），不再试图让这些节点参与合并。

一开始，这些 move-related 节点不能参与 simplify. 在进行 freeze 后这些节点的 move-related 关系被去除，从而得以参与 simplify, 此时就可以再次尝试 simplify 和 coalesce 了.

可参阅：图着色寄存器分配 - anna - 博客园

图染色总结

引入了一些新东西，因此算法许多部分都有些微调。
最终梳理一下我们的算法。包含如下几个模块↓

Build: 建图
- 建立干扰图
- 标记节点是否是移动关联(move-related)节点（i.e. MOVE的源/目标）
Simplify: 简化图
- 每次去除一个 non-significant 的非移动关联节点。
Coalesce: 合并MOVE引入的移动关联节点
- 进行保守合并，得到的新节点标记为非移动关联节点，可用于下一次 simplify.
Freeze: 冻结部分移动关联节点，放弃合并
- simplify 和 coalesce 交替进行。如果两者都无法进行，则尝试放弃合并部分 non-significant 移动关联节点。
- 放弃合并的节点不再视为 move-related 节点。
Spill: 处理需要挤出到内存的变量
- 万策尽：确实存在需要 spill 的 temporaries, 找到所有这样的一起进行 spilling.
- Do actual spilling: 改写 IR 代码以把它们移动到内存中，重新开始整个算法。
Select: 不断弹栈，为出栈节点分配可用颜色，直到只剩下预染色节点（见下文）。

全流程：
coloring-algo-full
coloring-algo-full-book

图中可以看出，simplify 和 coalesce 交替进行直到图为空或无法继续后，再进行 freeze 等操作。

课件上有一个很好的例子，展示了如何把一个程序在一个 3 个寄存器(2 caller-saved + 1 callee-saved)的机器上进行编译。
有条件的同学建议参阅课件： ch11. 寄存器分配第124页。

图染色杂项

预染色(pre-colored) 节点：
- 栈顶指针寄存器、参数寄存器等 special purposed 寄存器不是通用的。
- 可以把这些物理寄存器一一对应成虚拟寄存器，或者说为每个 special purposed 寄存器分配一个专属 temporary / node.
- 需要通过预先染色，以告诉染色器这种一一对应的关系：
  - 每个 pre-colored node 的颜色是唯一的
  - pre-colored nodes 之间互相两两 interfere （不一定需要真的全连接，也可以特殊处理）
- 预染色节点不能被 simplify 掉。
- 预染色节点不能被 spill 到内存上。
- 预染色节点能参与合并(coalescing).
- 普通的 temporary / node 可以使用预染色的颜色（只要不 interfere）
  - 例如，calling-convention register 可以在函数里当作临时寄存器使用。使用时，这个临时值(temporary)对应的节点颜色即为 calling-convention register 对应的预染色节点的颜色
- 编译器前端需要保证预染色 temporary 的 live range 足够短：多多使用MOVE
  最佳实践：
  - temporary 的 live range 如果不需要跨越某个函数调用，最好放置在 caller-saved 寄存器中
  - temporary 的 live range 如果需要跨越某个或多个函数调用，只能放置在 callee-saved 寄存器中
受限的(constrained)节点：如果两个节点之间同时有移动关联（虚线边）又有冲突（实线边），那么需要忽略这个移动关联关系。
- 某个变量被多次MOVE进不同的值，合并后就会这样。
- 例如上文这个程序：
  
  如果a和t合并为at, 就不能和b共用寄存器。
  同理，如果b和t合并为bt, 就不能和a共用寄存器。
划重点！需要 spilling 时如何选择节点进行 spill 呢？优先选择：
- 较少使用的 temporary ：例如在循环外的。
- 高度数的节点：它们是“罪魁祸首”，我们应当“擒贼先擒王”。
- 可以通过计算如下判据决定（假设每个循环运行 10 次）：

Part 18: 垃圾回收

运行时Runtime

运行时 = Runtime = (Language) Runtime System = 程序默认的、不在编写时描述的builtin 方法等运行时环境信息。可能有：

POSIX 信号处理
任务智能分配到多核 CPU 的不同核心
虚拟机（比如 JVM）
智能内存管理
- 比如：垃圾回收

内存管理概述

手动内存管理带来许多安全隐患，是最主要的漏洞来源之一。可能的问题：
- 内存泄漏：不再使用的内存未释放，可用内存越来越少，消耗系统资源。
- Double-free: 重复释放同一块内存。可能导致程序崩溃，或是被攻击者以此误导 glibc 等实现未授权的内存写入。
- Use-After-Free(UAF): 使用已经被释放的内存区域（例如通过悬空指针）。如果在释放后这块区域被攻击者修改了，之后再次使用时可能误导程序做出恶意行为。
内存管理需要平衡性能、安全以及开发难度。
内存区域划分：
- Static area
  - 编译期分配
  - 全局变量、字符串字面量等
- Runtime stack
  - 也就是栈，储存许多栈帧 / 活动记录(activation record)
  - 包含局部变量、函数调用返回地址等信息
- 堆(heap)
  - 通过malloc new 等方式在程序中动态分配的对象
  - 如果这些对象不再使用则称之为 垃圾(garbage)
垃圾回收(garbage collection, GC)：自动清理不被使用的垃圾。
- 是运行时的一部分。
- 在 LISP 里第一个应用。
- 两个阶段：
  1. garbage detection: 检测已经成为垃圾的内存对象
  2. garbage reclamation: 释放这些垃圾对象
理想的垃圾回收器：
- 安全：不会回收还没成为垃圾的对象 （必须）
- 完善(Complete)：应回收尽回收
- Low overhead: 时空占用小
- Fast: short pause time(程序为了等待垃圾回收时阻塞的时间) + 并行化
- 实现简单：现在是，幻想时间……
- ……

如何判断一块内存M之后是否会被继续使用？考虑程序/* here */ Call P; Use M;:
如果能在here处判断M是否会被继续使用，就意味着能判定P是否停机……这是个不可判定问题！

因此，我们需要再次使用保守估计的策略，只回收那些确信是垃圾的对象，确保垃圾回收器是安全的。
我们通过判断内存对象的可达性(reachability)来找出哪些对象可以 / 无法通过指针，或是指针链访问到。不可达的对象一定不可用。

接下来的任务：使用某种方式获取内存对象的可达性信息。方法：

引用计数Reference Count: 统计每个内存单元被引用的次数
- 直接追踪哪些内存单元是活跃的。
- 分配堆上空间时，GC 介入。
- 无法检测所有垃圾。
Tracing
- 当分配堆上空间失败时，GC 介入并检测活跃的内存单元。
- Mark-sweep
- Copying collection / Stop-and-copy
其他现代方法：generational GC 等。

接下来我们会详细讨论这些方法。

基础数据结构：有向图

对象间的引用关系构成一个有向图。

点：
- 变量/寄存器：在图中是一些指向内存对象的 “根节点”。
- 内存对象（例如一个 struct / record）：被指向，也可能指向其他内存对象。
有向边：指针，a储存了指向b的指针，则对应一条有向边a->b

directed-graph

在图上，我们可以更好地描述可达性：

无法从任一“根节点”r出发，通过一条链r->a->b->c->...->x到达的内存对象x，就是不可达的对象。
例如，如果内存对象x的入度为0, 则x一定不可达（但反之不然）。

Mark-and-Sweep

一种朴素的垃圾回收方式。有如下两步：

Mark: 从各个根节点出发，搜索并标记能到达的全部节点。
Sweep: 线性扫描整个堆，把未被标记的节点（不可达节点）链接到 freelist 中, 最后清除标记。

graph-marks
图中蓝色的节点即为未被标记的节点。
图中的·即为变量或是 record 中的字段。如有出边，则代表它是个指针，指向一个 record.

freelist: 储存所有可用的(free)内存块，是一个链表。程序开始运行，没有进行任何堆内存分配时，这个链表自然包含了程序内存中的所有块。

当程序需要在堆上分配一个 record 时，从 freelist 中取出一块。
如果此时 freelist 空了或是不足以满足 record 的空间需求，则重新进行一次 Mark-and-Sweep 尝试找到垃圾并回收入 freelist, 然后再分配.
如果找不到任何垃圾回收，或是回收后 freelist 仍空间不足，则分配失败。

Mark-and-Sweep 方案的代价分析：

H: 堆的总块数
R: 可达的数据块数
时间花费：
- Mark: 遍历可达对象，代价为 $ c_1 R $.
- Sweep: 遍历整个堆，代价为 $ c_2 H $.
- 填充 freelist, 大小变为 H-R:
  - 长期来看，分配对象数=回收对象数。
  - 摊还后的代价 = 单次代价/回收对象数 = $ (c_1 R + c_2 H)/(H-R) $.
  - 如果堆一直接近满（H接近R），则时间花费极大！

该方案的问题与改进：

问题：遍历可达对象时如果直接 DFS, 在极端情况下容易递归过深爆栈。
- 解决方法：使用显式的栈(explicit stack)进行 DFS: 手动模拟一个栈，初始时压入所有 roots; 每次弹出栈顶节点t，标记t, 把t指向的所有节点压入栈中；重复执行直到栈空。
问题：即使如此，栈的大小太大了
- 解决方法（了解即可！）：Deutsch-Schorr-Waite (DSW) pointer reversal
  - 不使用显式的栈，而是复用图中的元素（节点与边），把栈“放在”图中：在图中用指针串起来一连串节点，也可以充当栈！
    当搜索某个节点（也就是内存中的一个对象，或者说 record）x时：
    1. 标记x.
    2. 如果发现有x的某个 field x.fi 储存了一个指针，并且指向一个未标记的子节点y：临时篡改x.fi,让它指向x的父节点t: y:=x.fi; x.fi:= t.
    3. 递归地，搜索、标记子节点y(对应地更新t:= x; x:= y)。
    4. 搜索完毕后，退回父节点(对应地更新y:= x; x:= t; t:= x.fi)，然后恢复这个被临时篡改的指针：x.fi:= y。
  - 伪代码如下：
    - 对所有变量（“根节点”）v执行DFS(v)
    - # of ... = the number of ...
    - x: 全局指针，指向当前处理的节点
    - t: 全局指针，指向当前处理节点的“父节点”
    - y: x的某个子节点
    - done[r]: 记录r这个 record 中,已被检查/搜索过的 fields 是那些。例如若done[r]=3:
      - 说明r.f0 r.f1 r.f2已经被处理过，现在下一个要处理的子节点是 r.f3 (如果r.f3是指针)。
      - 之后，如果r.f3指向子节点，搜索前篡改r.f3为t.
      - 最后，如果子节点搜索处理完毕回退到r, 程序就可以知道需要恢复的、之前被篡改的 field 就是r.f3.
    课件示例拼接：
Mark-and-Sweep 优缺点总结：

+ 垃圾数量较少时很高效
+ 可以回收循环引用（A->B->C->A...）
+ 对象在内存中不需要移动，也就是其位置不需要更改（有时影响程序正确性：参考隔壁 Rust 的 std::pin）

- 垃圾数量多时很低效
- GC 过程会阻塞程序运行，程序必须暂停以回收垃圾
- 容易导致堆的碎片化，尤其是会产生许多内存（外部）碎片

关于 内存碎片 这一概念，我们会在该部分的最后进行说明。

引用计数Reference Count

核心思想：在释放对象时就进行垃圾回收，而不是等到申请内存时发现空间不足才试图回收垃圾。

尽管不能确定被指针指向的对象是不是垃圾，但是我们能知道的是没有任何指针指向的对象一定是垃圾。

使用引用计数的垃圾回收，简而言之就是：

维护每个对象x被几个指针引用（指向），这个值记作rc.
在删除指针时，x的rc:= rc-1;.
如果此时发现rc变为0了，立刻进行垃圾回收，释放x.
- 如果x也包含指向其他对象的指针，则在释放x前，需要递归地删除指针（意味着可能递归地触发 GC）

具体而言，

当执行x.fi:= p时，我们需要维护 RC(reference count) 值：
- p的 RC 值+=1 .
- x.fi之前指向的对象 RC 值-=1 .
如果此时发现某个对象r的 RC 值变为 0, 也就是无人指向它时：
- 将r加入 freelist.
- r的各个 fields 指向的对象 RC 值-=1 .
- 这可能会使得其他对象 RC 值也下降到 0, 从而触发一连串回收过程。

其实很多语言都有类似的设计，例如 C++ 中的智能指针就利用 RC 避免了裸指针带来的许多内存安全问题。

Reference Count 优缺点总结：

+ GC 带来的开销(overhead)是渐进式的：不需要专门为了进行 GC 暂停程序执行，而是融合到程序执行过程中（无需 stop-and-collection）
+ 实现简单
+ 可以和手动内存管理并存（例如同时使用裸指针和智能指针）
+ 内存局部性好：RC 值和对象储存在一起
+ 垃圾能被立即回收（而不是等待直到下一批统一回收）

两个严重问题：
- 不能回收循环引用（A->B->C->A...）。相互引用可能导致它们的 RC 值都不为 0, 成为一个永远不可达的”孤岛“
- 增加/减少 RC 值是非常频繁的，带来非常昂贵的开销
- 增加/减少 RC 值需要在目标代码中加入大量指令

Copying Collection

也叫做 Stop-and-Copy.
核心思想：用两个 heap space, 用完一个就切换到另一个。

from-space: 程序使用的
to-space: 在进行垃圾回收前不使用
GC 流程：每个 heap space 有next和limit指针，分别表示可分配空间的起点；可分配空间的终点。如果 from-space 用完了，就开始进行 GC:
1. 遍历 from-space 并把其中可达的对象一一拷贝到 to-space, 占据 to-space 开头一段连续的空间，这个过程中next指针不断移动，使其始终指向可用空间的起点。
2. 这样一来，不可达的垃圾自然就留在原先的 from-space 中被无视并抛弃了。
3. 拷贝完毕，此时新空间中next指针紧跟在这些拷贝过来的对象后。如果程序在之后的运行中需要分配新的内存空间，就从next开始分配，并根据分配空间大小移动。
4. 然后，自然地， from-space 和 to-space 角色互换。

此外，我们还需要进行 指针转发(pointer forwarding) . 这是因为我们移动了一些对象，改变了其内存地址，因此原先指向这些对象的指针地址也需要相应地被修改。
……但这样做需要在找到、储存每个对象对应的新地址，开销太大了，因此我们在每次拷贝时，直接把新对象x'的地址储存在 from-space 已经用不到的对象x开头：x.f1:= &x'
然后在拷贝时，每次访问指针p时，通过forward(p)翻译到真实地址：

p指向 to-space 中：这就是真实地址，直接返回p
p指向 from-space 中：
- 如果p->f1指向 to-space: 这是对象被拷贝后转发后的指针，返回p->f1
- 如果p->f1指向 from-space: 对象还未被拷贝，
  - 拷贝p指向对象的所有 fields: p->f1 p->f2 …
  - 拷贝p指向的对象*p到next处
  - 在 from-space 记录转发的指针：p->f1:= next
  - 移动next指针
  - 返回新地址p->f1

利用这个函数，我们可以导出一个 from-to 拷贝的算法。

Cheney’s Algorithm: 使用 BFS 遍历可达对象并拷贝。
简而言之，就是：

初始时，拷贝根变量(roots)指向的内存对象，这些对象进入 copied 队列。
处理 copied 队列中对象内部的指针，这些对象指向的内存对象被拷贝，进入 copied 队列；这些对象本身成为 copied-and-scanned 对象，移出队列。
重复以上两步直到队列空。

把 to-space 切割成三个连续段，依次为：
- copied and scanned: 包含的对象已经复制，且对象中的指针被检查/转发过了。
- copied: 包含的对象已经复制，但还没检查过对象内部的指针。
  - 其实这段空间就是 BFS 过程的待处理 copied 队列。
- empty: 可用空间。

scan ← next ← beginning of to-space

for each root r
  r ← Forward(r)

while scan < next
  for each field fi of record at scan
    scan.fi ← Forward(scan.fi)
  end

  scan ← scan + size of record at scan
end

然而，

BFS算法的内存局部性较差：x中的指针x.fi指向的对象可能地址离x很远！这导致无法很好的利用虚拟内存，也会造成许多 cache misses.
DFS算法的内存局部性较好，但需要 pointer-reversal, 也很慢，且麻烦。

因此我们可以提出一种混合式(hybrid)算法：复制对象时使用 BFS, 但是复制时顺带使用 DFS 递归地检查对象内部的指针，如果有还未被拷贝的对象则拷贝。
换句话说就是 BFS 的过程中，每次复制对象x时，顺带把一条路径（x->某个叶子）上的对象也复制了。
hybrid-algo

Copying Collection 优缺点总结：

+ 实现简单：无需用栈或 pointer-reversal
+ 跑得比香港记者快，时间复杂度优秀：和活跃对象数量成正比
+ 可用的 free space 在内存上连续：每次 GC 时自动进行了“压缩”，去除了内存碎片
+ 是更新的一些算法的基础范式，起到了示范作用

- 高达一半的空间被浪费了
- 内存局部性差：Cheney's algorithm 
- 需要精确的类型信息标出所有指针（如果不知道某个 field 是否为指针，就无法在移动对象后转发该指针）

编译器：实现快速分配

虽然在本部分开头指出“GC 属于 runtime”, 但这不意味着编译器不能参与该过程。

编译器可能通过如下方式和垃圾回收器进行交互：
- 在内存上分配 records
- GC 时，为垃圾回收器描述 roots 变量有哪些
- 描述内存布局（例如指出某个 record 各个 field 的大小）
- 读写屏障(barrier)，防止 GC 造成条件竞争
- ……
其中，内存分配是最为重要的环节：
- 函数式编程语言不鼓励更新，而是创建新的不可变对象
- 内存密集型程序在循环中可能需要访问几乎所有内存对象一次
- 经验告诉我们平均每条指令在内存上分配 1/7 word

为了高效分配内存，我们可采用 Copying Collection: 可分配空间连续，且起始位置(next)、区域末尾(limit)已知。
每次在内存上分配一个大小为N的 record 时，有如下开销与对应优化：

~~Call the allocate function~~
- 通过内联展开，可消除函数调用
Test next + N < limit ? (If the test fails, call GC)
Move next to result
- 可以和 A(见下)合并：Move next into some computationally useful place
~~Clear M[next], M[next+1], …, M[next + N - 1]~~
- 可以通过和 B(见下)合并消除（或者干脆不初始化）
next <- next + N
~~Return from the allocate function~~
- 通过内联展开，可消除函数调用

以及如下不属于分配过程的开销：
~~A. Move result into some computationally useful place~~ (Done in step#3)
B. Store useful values into the record

综合分析：

如果保持next和limit在寄存器中，step#2 和 step#5 可以在 3 条指令内完成。
每次分配的总开销通过这些优化方式降低到大约 4 条指令。

编译器的 GC 接口

编译器需要为垃圾回收器提供部分信息。

编译器的任务：
- 为不同类型的 record 提示长度信息，用于 scan 阶段
- 为不同类型的 field 提示类型信息（是/不是指针），用于 Forward 函数
- 对于 Tiger, Pascal 等静态类型语言，或 Java 等 OOP 语言，可以在每个对象开头放置一个指针，指向一个特殊类型 type-descriptor 的 record.
  - 对象总大小
  - 指针 field 的地址
  - ……
- 为 GC 提示哪些根变量包含指针，从而作为每次 GC 的起点：
  - 根变量可能是栈上的指针，或是 callee-saved 寄存器中的指针
  - approximate GC: 栈上看起来像指针的就当作指针，尽管可能会把一些整数当作指针
  - Tiger 语言的解决方法：使用 pointer map, 编译期就能知道哪些 temporary 是指针。
    - 如果垃圾回收器在分配时调用：在执行每次分配 record 的指令前生成 pointer map
    - 递归调用时：每次调用函数CALL前生成 pointer map
    - 由于我们调用函数CALL前生成 pointer map, 所以通过每个返回地址可以索引到下个（被调用函数）栈帧的 pointer map.
    - 垃圾收集器通过从栈顶向下扫描调用栈,依次处理每个栈帧。每处理完一个栈帧,就可以通过该栈帧的返回地址来获取下一个栈帧的 pointer map, 识别出栈帧中的指针。
    - 需要特殊处理 callee-saved 寄存器：考虑调用链 f->g->h, g 在调用 h 前，对于这些 callee-saved 寄存器，必须在 pointer map 中额外记录哪些是 g 自己使用的，哪些是从 f “继承”来的。
Derived Pointer:
- 有的指针可能指向某个 record 中间，或者根本不指向一个 record.
- 例如，假设我们需要在循环中访问a[i-2024], 则该地址可以表示为M[a-2024+i]:
  1
  2
  3
  t1 <- a-2000
  t2 <- t1+i
  t3 <- M[t2]
  而编译器可能会把t1提升(hoist, 见后文循环优化章节)到循环外避免重复计算。
  如果循环中有分配指令触发了 GC 操作，垃圾回收器可能会错误地以为t1不引用对象；或是以为t1指向了某个别的对象（如果运气不好）。
- 在刚刚的那个例子中，我们就称t1是从基(base)指针派生(derived) 出的指针。
- pointer map 必须识别出每个 derived pointer 并把信息“告诉” base pointer:
  - 如果a的地址在 GC 过程中发生了改变，则t1的地址也需要被修正；
  - a至少要比t1活得久（参见 Rust 中引用(references)的生命周期控制）；否则在 GC 时 pointer map 就无法有足够的信息修正 derived pointer.

GC 杂项

内存碎片：意味着浪费了内存中的空间，内存不是“最密堆积”的。
有两种内存碎片：
- 外部碎片(external fragmentation): 当程序要求分配一块内存时，尽管堆中看起来可用空间足够，但由于这些可用空间零散、碎片化地分布在各个位置，成为了外部碎片，我们找不到足够大的一段连续内存分配给程序，分配失败。
- 内部碎片(internal fragmentation): 当程序要求分配一块内存时，由于地址对齐等原因，内存管理管理器可能返回一块比要求的更大的内存，用不完的部分即为内部碎片，将不可避免地被浪费。
内存分配方式：
- Linear allocation:
- Freelist allocation:
总结：GC 有代价，但可以通过优化减少开销。
阅读 Appel 第13章，文中对不同 GC 机制进行了分析、比较。

Part 19: 面向对象(OOP)

面向对象语言= object-oriented language = OO language = class-based language
- （几乎）所有值都是对象(object)（例如 Python）
- 对象属于某个类，或者说对象是某个类的实例(instance)
- 对象封装了状态（也就是成员变量 fields）与行为（也就是成员方法 methods）
重要概念：
- 继承(inheritance) : 派生类继承基类的特性（例如假设基类Rocket具有方法fire(), 则子类Spaceship自然也有fire()方法）
- 封装(encapsulation) : 隐藏不该被外部接触到的接口
- 多态(polymorphism) : 对象可以以不同形态呈现（例如，由于Cat继承自Animal，一个Cat实例也可以被看作是一个Animal实例）

Tiger 语言中的类

语法：class B extends A {...}
- 子类B继承自父类A, 或者称派生(derived)类B继承自基类A. 出于避免偏见的目的，建议使用后者。
  - 传递性：如果C继承了B, B继承了A, 我们可以说C继承了A.
- B隐式地继承A的所有 fields(成员变量) 和 methods(成员方法).
- B可以重写(override) 部分 methods. 注意和重载(overload) 区分：
  - 重写(override): 函数名相同，且函数签名必须一致；派生类重写某个 method 以添加和基类不同的实现。
  - 重载(overload): 函数名相同，且函数传入参数必须不同；可以为某个函数在不同传参下的多个版本、多个实现。
- fields 不能被重写(override). 派生类中定义的所有 fields 都是在派生类中新定义的.
  - 例如基类A有一个 field name, 而派生类B也有一个 field name, 则实际上它们是不同的 fields A.name 与 B.name. 并非重写基类的 field!
- 所有类都是预定义的Object类的派生类，Object类没有 field 或 method.
  - 这被称为 singly rooted class hierarchy, Python 和 Java 都采用了，但 C++ 并不。
关于self: 在 Tiger 中不是关键字，而是每个 method 都有的隐式的参数。在运行时自动传入，指向当前实例，用以引用当前实例对应的 fields 和 methods。

使用例：

let
  Class Car extends Vehicle { // declaration
    …
    method await(/*self: Car,*/ v: Vehicle) {
      if (v.position < position)
      then v.move(position – v.position) // access a field "position"
      else self.move(10) // access a method "move"
    }
  }

  var c := new Car // instantiate a new instance called "c" with type "Car"
in
  c.move(60); // equals to: move(c, 60);
end

类的层次结构

可以用图表示继承关系（这里就不画了）。主要分为两种：
- 单继承single-inheritance(SI): 每个类最多只能继承一个基类，因此继承关系图是一棵树。
  - 例如 Python
- 多继承multiple-inheritance(MI): 每个类可以继承多个基类，因此继承关系图是有向无环图(DAG).
  - 例如 C++, Perl, Python
  - 实现起来更 tricky
在 Tiger 中实现类需要解决如下问题：
- Field layout: 某个类的各个 fields 在内存中如何放置、访问？换句话说，如何确定某个实例的 field 内存地址相对这个实例初始地址的偏移量？
- Method dispatch: 调用某个实例的方法时，如何找到正确的方法位于何地址？是派生类的实现，还是基类的实现，还是基类的基类的实现，……？
- Membership test: 如何检查给定实例是否是给定类的实例？例如 Java 中的 instanceof.

单继承Single-Inheritance

每个类最多只能继承一个基类。
单继承下的部分实现会相对容易一些。

Field layout: 使用 prefixing

派生类新增的 fields 跟在基类的后面。
这使得我们可以正确处理多态：例如把Cat当作Animal看待，访问Animal的 fields 时相当于屏蔽了新增的 fields; 基类的各个 fields 偏移量不会因为这是个派生类实例发生变化，仍然是已知的。
这避免了不安全的内存访问。
Method dispatch:
- 每个 method 编译成一段代码（称为 method instance），编译方式和普通函数几乎无异。
  - 比如A中的f()就编译为一段代码，可用A_f这样 label 标记函数地址。
- 机器码中，函数起始地址使用一个LABEL标出。
- 每个类都对应一个 class decriptor, 里面包含了描述这个类的一些必要信息：
  - 一个指向基类的指针
  - 一个列表，包含这个类所有的 method instances
- 对于 static method 的调用x.f(), 编译器将会：
  1. 找到对象x对应的类，记为C.
  2. 如果C中有f, 则直接得出x.f()翻译结果为C_f; 否则继续向上（在基类中）寻找。
  3. 假设C的基类为B, 在B中查找f, 如找到则得出x.f()翻译结果为B_f; 否则继续向上（在基类中）寻找。
  4. ……
  5. 直到在某个祖先中找到为止（或是一路找到Object还没有则报错），调用它。
- 对于 dynamic method 的处理略复杂:
  - 每个类维护一个 dispatch vector (例如 C++ 中的虚表 vtable = virtual table = VMT = virtual methods table) 储存每个 method 的地址。
    - 建立方式类似 prefixing: 派生类中新声明的方法跟在基类 dispatch vector 的后面；不过如果有基类的 method 被重写了，也要替换成自己重写后 method 的地址。
      这样，每个方法的偏移量是确定的。
  - 每个对象都关联某个 vtable: 对象的开头储存一个指针指向对应 class descriptor , 里面就有 vtable。
  - 需要动态查找(lookup), 有额外的开销。~~（虽然你可以说像 Rust 那样直接 monomorphization 就不需要动态开销了，但是 Rust 甚至都不是 OO 的啊！）~~
- 对于 dynamic method 的调用x.f(), 编译器将会：
  1. 在x的0偏移处（开头）找到 class descriptor d.
  2. 由于方法f的偏移量是确定的（记为F），从d中F偏移处获取f的函数地址。
  3. 调用f.

多继承Multiple-Inheritance

每个类可以继承多个基类。
~~笔者认为多继承是纯纯的方向错误，C++为了多继承打了一堆补丁最后还是破破烂烂。~~

引入了经典的菱形继承/钻石继承问题：
diamond

歧义：如果B1和B2中都有 method m, 那么C的实例c上调用c.m()时应该调用哪个m? 无法确定。
field replication: 对于A中的一个 field x, 由于B1和B2中都继承了A.x, 最终C中会有重复的两个x都来自A.
Field layout: 通过图染色获取。
- 目标：静态分析所有类，为每个 field 的找到一个固定偏移量。如果不同 field 在同一个类中出现，则不能共享同一个偏移量。
- - 节点：不同的 field 名
  - 边：同时在某个类中出现的 field 则连边
  - 颜色：最终偏移量(0, 1, 2, …)
  例如从上图我们将得到：
- 优化：可以看出存在许多空的 slot 被浪费了。我们可以把 fields 在内存上合并，转而在每个类的 class descriptors 中记录各个 field 的真实偏移量。
  
  由于类的数量远少于对象（类的实例）数量，所以这样能节省空间。
  不过这种优化导致每个 field 的具体偏移不固定了，因此需要在运行时在 class descriptor 中动态查找(lookup) field 的真实偏移量.
Method dispatch: 仍然使用图染色。我们可以直接把 method 名混合进上述的图中，一起染色；也就是求解如下两个映射关系：field 索引 -> field 实际偏移量；method 索引-> method 实际地址。
- 也有动态查找的开销。

不过，并非所有时候都可以静态知晓所有类的存在并统筹规划。例如我们知道在 Java 里类可以被动态加载。

解决方案：Hashing
其实就是又包了一层新表，允许通过 field/method 的名字本身索引到 field offset 或 method address.
更简单地说，原先是OffsetOrAddr[]，现在是hashmap<Name, OffsetOrAddr>.
- Ftab(field table): field offset 或 method address （之前就有的）
- Ktab(key-table): 记录注册过的名字（因为有哈希冲突的问题，需要确认名字是否真的匹配）

基于类的类型系统

每个类都是一种类型。派生类可以看作一种 sub-type. 在进行类型转换时：
- upcast: 派生类转为基类。永远是安全的。例如Cat实例一定也是Animal实例, 所以随时都可以将Cat*转为Animal*.
  - 有时被叫做“裁剪” “narrow”之类的：因为在这种转换中相当于“丢失”了一些信息，upcast 后能调用/访问的 method/field 变少了。
- downcast: 反之，基类转为派生类不一定安全。例如Animal很可能不是Cat, 所以冒然转换就可能通过错误的 offset 访问到错误的、越界的内存，很危险。
Membership test: 为了安全的类型转换，需要测试某个对象是否是某个类的实例。参见：
- Java: instanceof 操作符
- C++: dynamic_cast vs static_cast
- …
如何判断x是不是类C的实例？
- 朴素（慢）的做法：
  - 递归地检查x 的 class descriptor (记作x.0) 开始的继承链 x.0, x.0.super, x.0.super.super, x.0.super.super.super, …
  - 如果发现某个是C的 class descriptor 则x是C的实例；否则如果到最上层（...super==NIL）仍未发现，则说明不是C的实例。
- 更快的做法：display.
  - 每个 class descriptor 储存一个 display, 也就是一个足够长（比最长继承链长）的定长列表，记录对象的整条继承链。就像：
    - 0: Object
    - 1: GrandparentClass
    - 2: ParentClass
    - 3: MeClass
    - 4: (nil)
    - 5: (nil)
    - …
  - 我们可以给每个类一个专属的数字 ID (例如对于 SI, 可以按照继承关系树的 BFS 序为每个类编号), 然后 display 中储存这些 ID 代表类。
  - 由于对每个类，其继承关系的嵌套深度在编译期已知，因此可以立刻找到需要比较 display 中的哪一项。
    - 例如，假设MeClass的继承深度是第 3 层，要检查x是否为MeClass的实例，只需检查x的继承深度是否大于等于 3, 且x.0.display[3]是否指向MeClass的 class descriptor 即可。

私有 field/method

private field/method: 私有的 field/method 只能被类的其他 method 访问/调用，而不能被外部调用。
- 这是封装思想的体现：调用者不该知道内部实现细节。
- 通过类型检查确保私密性(privacy)：每个访问/调用处检查是否 private.
其他语言中 private field/method 的实现：
- 和 Tiger 一样，只允许声明它的类访问。
- C++ 的protected: 只允许类或派生类访问，介于public和private中间。
- 通过package namespace等划分不同包、命名空间。
- 外部可见，但是是只读的；修改必须通过public的公共方法、接口进行。
- ……

Part 20: 循环优化

循环结构在程序中随处可见；程序执行时间有很大一部分都是在循环中度过的。我们需要对循环做出一些优化：

Low level: 针对单个循环
- loop invariant code motion: 把循环中不变化的代码移动到循环外
- strength reduction: 强度折减，用代价低的运算取代代价高的运算
- loop unrolling: 循环展开，增加每次循环迭代的元素个数，减少小循环的循环开销
High level: 重构、修改多个循环
- loop fusion: 融合多个循环，减少循环开销
- loop interchange: 调换内外循环顺序，提高内存局部性等
- loop tiling: 循环遍历数组时，通过适当的重新分块，提高内存局部性等

CFG 图中的循环结构

循环在控制流图(CFG)体现为 一个节点集合 S, 包含 header node h, 并且对于S中的任何节点x:

都有一条从x到h的路径
都有一条从h到x的路径
除了h, 没有任何其他S以外的节点能到达x

重要概念：

Loop entry: h是唯一一个能从外部到达的节点，是循环的唯一入口
Loop exit: 可以有多个节点能跳出循环（i.e. 后继节点不都属于S）
Predecessor: pred, 前驱节点
Successor: succ, 后继节点
Dominator: 如果 CFG 的入口节点s0到节点n的所有路径都经过节点d, 我们就称d是n的支配节点(dominator)
- 记作d dom n
- 可以理解为简单版的图论中的“割点”
- 每个节点都支配(dominate)自己
- 节点可以有多个 dominators
- 求解每个节点的 dominators D[n]:
  - 入口节点的唯一 dominator 就是自己：D[s0]={s0}.
  - 对于其它节点：$ D[n] = {n} \cup \left( \underset{p\in pred[n]}{\cap} D[p] \right) \text{for }n\neq s_0 $
  - 求解过程：一开始时令D[s0]={s0}, 其余节点D[x]=所有节点；然后使用上面的式子不断迭代更新直到不动点。
Immediate dominator: 直接支配节点，支配n的节点中距离n最近（但不是自己）的节点。
- 也就是从入口结点到达n的任何路径(不含n) 中，路径中最后一个支配n的结点。
- n的直接支配节点记作idom(n).
- 除了初始节点s0以外，每个节点有且仅有一个直接支配节点。
  - 可以证明，如果d和e都支配n, 那么要么d支配e, 要么e支配d.
  - 因此对于某个节点n的支配节点集合D[n], D[n]中的 dominators 上有全序关系。
  - 而idom(n)就是“最小”的那个 dominator: 不支配D[n]中任何其他的 dominator.
Dominator tree: 支配节点树
- 对于每个节点n, 连接边：idom(n)->n.
- 每个节点支配以自己为根的子树中的所有节点。
Natural loop: 自然循环
- 我们并不关心循环具体代码形式（for, while, goto, …），而是关心能否提取出易于优化的循环结构。
- Back edge: 如果边 n->h 满足 h dom n, 则这是一个 back edge
- Back edge 指向的节点 h 称为 loop header.
- 我们可以基于 back edge 严谨地定义 CFG 图中的一个自然循环：
  每个 back edge n->h 对应一个 natural loop (但可以有多个 back edge 对应一个 natural loop: 例如 for 语句中的每个 continue 都给这个 natural loop 新增了一个 back edge).
  这个 natural loop 中的节点集合包含一些节点x满足：
  - h dom x
  - 存在一条从x到n的路径不经过h
  说人话就是 back edge 是回到循环头(loop header)的边。 至少有一条路径能返回首节点h: 循环尾部回到循环头部的那条边；循环体就是中间那些被 loop header 支配的节点。
- 循环可以嵌套：
  
  图中外层循环”5-8-9-10”嵌套了内层循环”8-9”.
- 循环可以共享首节点：见上图”2-3” “2-4”
- 除了共享首节点的情况外，两个循环要么完全不相交，要么一个完全嵌入另一个（或者说后者包含前者）。
- 最内循环(innermost loop): 最“里”的循环，不包含其他循环（不被其他循环嵌入）。例如图中的 7-8-10:
Loop-nest tree: 表达循环的嵌套关系
- 树中每个节点对应一个 loop header 及其对应的 natural loops 节点集合。
- 如果这个 loop heder 对应多个 natural loops (共享首节点)，也合并到同一个节点。
- 节点的上半部分表示该节点对应的 loop header.
- 可以把整个 procedure 视为在一个假想的大循环中，作为树的根节点。
- 叶节点即对应最内循环。
Loop preheader: 前置首节点
- 许多优化操作会在进入循环前进行一些准备工作，也就是在紧挨着循环头之前插入一些语句。
- 因此我们可以在 loop header 之前插入一个 loop preheader 用来安置这些语句。
  - loop preheader 的唯一后继就是 loop header
  - 循环L里到达首节点的边x->h改为进入前置首节点：x->p
  - 循环L外到达首节点的边不变

循环不变代码外提Loop Invariant Hoisting

Loop-invariant: 如果某个表达式的值在循环中不会改变，对循环来讲是固定值，则称表达式 loop-invariant.
- 显然，所有常数都 loop-invariant.
- 赋值语句 x := v1 OP v2 是 invariant 的当且仅当其操作数v1和v2都满足：
  - 操作数是常数，或是
  - 对于操作数中使用到的变量，其 def 都在循环外，或是
  - 对于操作数中使用到的变量，在执行赋值语句时其 def 唯一，且 loop-invariant.
  ……说人话就是操作数及其使用的变量也得 loop-invariant, 而且不能在循环中因为控制流跳转等原因导致变量 def 不唯一（反例：for...{a=1; if (random()>0.5) continue; a=2;}）。
- 我们可以归纳地检查赋值语句 x := v1 OP v2 的操作数是否 invariant:
  - Base cases:
    - 常数：一定是 invariant 的。
    - 变量的 use: 该变量所有 defs 都在循环外则 invariant.
  - Inductive cases:
    - 表达式：多个 invariant 表达式进行运算仍然 invariant.
    - 变量的 use: 要求在执行该语句时只可能有唯一的 def 有效，且这个 def 的右侧(RHS) 是 loop-invariant 的。
- 优化：这样的表达式在循环外就可以求值，而非每轮循环都计算一次。这就是 loop-invariant code motion.
  - Code hoisting: 如果这样的表达式在循环中需要使用，则可以将求值提升到循环开始前。
  - Code sinking: 如果这样的表达式在循环结束后需要使用，则可以将求值下沉到循环结束后。

接下来我们重点关注 hoisting.

例如，对于如下代码：

//before

L0: t := 0

L1: i := i + 1
    t := a + b // hoist!!!
    *i := t // ...hoist?
    if i<N goto L1 else L2

L2: x := t

我们注意到t := a+b这个赋值语句是 loop-invariant 的（a和b的 defs 均在循环外）。因此我们对其进行提升：

//after

L0: t := 0
    t := a + b //!!!

L1: i := i + 1
    *i := t
    if i<N goto L1 else L2

L2: x := t

但并非所有的 hoisting 都是合法的。例如对于原先的程序，尽管t的 def 是 loop-invariant 的，但我们仍然不能提升*i := t.
这是因为在循环中t的值在之后会被改变，从而改变之后要写入内存的地址。
这说明，表达式的值是 loop-invariant 的不代表 hoisting 就是合法的：归根结底，这相当于我们只关心了 表达式 的值，但忽视了其副作用；盲目上提会破坏代码的语义(semantics)信息。

（划重点！）hoisting 的判据：当且仅当满足如下所有条件时可以提升形如t := a OP b的赋值语句（赋值语句就是 def）d:
- d 必须支配所有t在其上 live-out 的循环出口(loop exits).
  - 人话：如果可能在不执行这条赋值语句的情况下提前跳出循环，显然不能上提（上提后相当于变成一定会执行的）。
- 在循环中t只能有唯一的 def.
  - 人话：不能在循环中先后给t赋不同的值并使用这些不同的值。如果t的值在每轮循环中都要不断改变，这就不是 hoisting 能优化掉的需求。
- t不属于 loop preheader 的 live-out 集合；换句话说，t在进入循环前不是活跃的。
  - 人话：如果在循环体中，要提升的这个赋值语句前还有别的语句o用到了t, 那么错误的 hoisting 就会导致在循环的一开始o就得到了错误的t值。我们要避免这种情况就要保证t只能通过当前赋值语句“激活”，在那之前不能被使用。
我们可以验证一下这些判据：

杂项：

如果这个赋值语句有一定的副作用，那么上述规则就不足够，需要添加更多判断、约束。例如：
- 可能抛出算术异常：例如除法可能触发Div-by-zero
- 可能有副作用：例如 Python 的海象运算符:=会在表达式中引入副作用（变得不“纯”）
将 while 转写为 for 有助于优化：拷贝一份条件判断块到循环体末尾即可。
- 这是由于 while 特殊的控制流结构可能会导致判据中最后一条要求无人能达到，要把 while 转化为我们刚刚研究的 repeat-until 这种模式的 natural loops.

*其他循环优化

本部分内容不属于考试范围。

Stength reduction: 强度折减，用开销低的操作代替开销高的操作。
- 2.0 * x -> x + x
- x / 2 -> x * 0.5
- …
Induction variable: 循环中一种常见的模式是在每次循环执行i := i+c; 我们可以在不依赖每轮循环中i的情况下，推导部分这样的变量的值。
- Linear induction variable: 每轮循环中以固定量改变的变量。
- 上图展示了这种优化：basci induction variable i直接被省去了，而使用 derived induction variable k 代替。
- 结合 strength reduction: 例如j := a + i * b 可以被优化成 j' := a, 而后每轮循环中 j' := j' + b.
Elimination: 消除无用代码，例如删除没有被其他变量使用的变量。
Rewriting comparisons: 改写部分比较表达式，识别出更多的无用变量进而删除。
- 如果某个变量只和 loop-invariant variable 比较，则称它 “almost useless”. 经过改写即可彻底变得 “useless” 而删除。
Loop unrolling: 循环展开，把多次循环做的工作合并到一个循环中完成。
- 需要有某个 induction variable 在每次循环中都 i := i + delta (这个语句要 dominate 这个循环的每一个 back edge, 也就是每次循环都不能跳过这条语句)
- 例如，假设每次循环处理一个数组的某一行；合并后则可以在每次循环中批量处理8行。如此一来总循环次数减少了，循环带来的开销也就降低了。对于小循环优化效果好。
- 需要特殊处理边界情况：在刚刚的例子中，循环展开后的版本只能处理行数为 8 的倍数的情况。
  因此我们应当只对剩余行数足够的部分进行循环展开优化（批量处理），而剩余行数不足时在”epilogue”部分进行收尾工作：按照原先做法一次一行地处理。
如果编译器可以证明部分数组边界检查是不需要的，则可以省去。

编译原理Speed-run any%