词法分析

词法单元 (Token)

  • <词法单元名（类型）、属性值（可选）>
  • 单元名是表示词法单位种类的抽象符号，语法分析器通过单元名即可确定词法单元序列的结构
  • 属性值通常用于语义分析之后的阶段

词素 (Lexeme)

  • 源程序中的字符序列
  • 它和某个词法单元的模式匹配，被词法分析器识别为该词法单元的实例

模式 (Pattern)

  • 描述了一类词法单元的词素可能具有的形式

字母表 (Alphabet)

  • 一个有穷的符号集合
  • 符号典型例子：字母、数字、标点符号
  • 例子：${0, 1}$, ASCII, Unicode
  • 在理论上，我们可以把任意的有限集合看作字母表

字母表上的串 (String)

  • 是该表中符号的有穷序列
  • 串s的长度，即$|s|$，是指$s$中符号出现的次数（即长度）
  • 空串：长度为$0$的串，$\epsilon$
  • 前缀：从串的尾部删除$0$个或多个符号后得到的串
  • 后缀：从串的开始处删除$0$个或多个符号后得到的串
  • 子串：删除串的某个前缀和某个后缀得到的串
  • 连接 (Concatenation)：$x$和$y$的连接是把$y$附加到$x$的后面而形成的串，记作$xy$
    • $x = \mathrm{dog}$，$y = \mathrm{house}$，$xy = \mathrm{doghouse}$
  • 指数运算 (幂运算)：$s^0 = \epsilon$，$s^1 = s$，$s^i = s^{i-1}s$
    • $x = \mathrm{dog}$，$x^0 = \epsilon$，$x^1 = \mathrm{dog}$，$x^3 = \mathrm{dogdogdog}$

语言 (Language)

  • 某个给定字母表上的串的可数集合
  • $L = {A, B , ……, Z, a, b, ……, z}$
  • $D = {0, 1, ……, 9}$
  • $L \cup D = {A, B, ……, Z, a, b, ……, z, 0, 1, ……, 9}$
  • $LD$：520个长度为2的串的集合 (字母 + 数字)
  • $L^4$：所有由四个字母构成的串的集合
  • $L*$：所有字母构成的集合，包括$\epsilon$
  • $L (L \cup D)^*$：不含下划线的变量名
  • $D^+$：所有非空数字串

正则表达式

  • $L(r)$表示正则表达式$r$所表达的语言
  • 选择：$(r) | (s)$，$L((r) | (s)) = L(r) \cup L(s)$
  • 连接：$(r)(s)$，$L((r)(s))=L(r)L(s)$
  • 闭包：$(r)^*$，$L((r)^*)=(L(r))^*$
  • 括号：$(r)$，$L((r))=L(r)$
  • 一个或多个实例：单目后缀+
    • $r^+$等价于$rr^*$
  • 零个或一个实例：?
    • $r?$等价于$\epsilon | r$
  • 字符类
    • $[a_1a_2 \dots a_n]$等价于$a_1 | a_2 | \dots | a_n$
    • $-$符号，如：$[a-e]$等价于$a | b | c | d | e$

状态转换图

  • 点[状态(State)]：表示在识别词素时可能出现的情况
    • 状态看作是已处理部分的总结
    • 某些状态为接受状态或最终状态，表明已找到词素
    • 开始状态 (初始状态)：用Start边表示
  • 边[转换(Transition)]：从一个状态指向另一个状态
    • 边的标号是一个或多个符号
    • 当前状态为$s$，下一个输入符号为$a$，就沿着从$s$离开，标号为$a$的边到达下一个状态

Lex

声明部分
%%
转换规则
%%
辅助函数
  • 冲突：多个输入前缀与某个模式相匹配，或者一个前缀与多个模式匹配
  • Lex解决冲突的方法：
    • 多个前缀可能匹配时，选择最长的前缀。如，词法分析器把<=当作一个词法单元识别
    • 某个前缀和多个模式匹配时，选择列在前面的模式。如果保留字的规则在标识符的规则之前，词法分析器将识别出保留字

有穷自动机

  • 不确定的有穷自动机 (Nondeterministic Finite Automata/NFA)：边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上， $\epsilon$可以做标号
  • 确定的有穷自动机 (Deterministic Finite Automata/DFA)：对于每个状态以及每个符号，有且只有一条边 (或最多只有一条边)

对于每个可以用正则表达式描述的语言，均可用某个NFA或DFA来识别；反之亦然

  • 识别：判定一个串是否属于对应正则语言(Yes/No)

正则表达式到NFA

  • 根据正则表达式的递归定义，按照正则表达式的结构递归地构造出相应的NFA
  • 算法分成两个部分
    • 基本规则处理ε和单符号的情况
    • 对于每个正则表达式的运算，建立组合相应NFA的方法

$a|b$

       . --a--> .
      />         \
     /eps      eps\>
-...-              -...
     \eps      eps/>
      \>         /
       . --b--> .

$s*$

              --eps---
            </        \
-...--eps-> . --N(s)-> . -eps->.->
    \                         />
     \                       /
      ----------eps----------

NFA到DFA

每个NFA都有一个等价的DFA

  • 构造得到的DFA的每个状态和NFA的状态子集对应
  • DFA读入a1, a2, …, an后到达的状态对应于从NFA开始状态出发沿着a1, a2, …, an可能到达的状态集合
  • 在算法中“并行地模拟”NFA在遇到一个给定输入串时可能执行的所有动作

语法分析

语法分析器的作用

  • 从词法分析器获得词法单元的序列，确认该序列是否 可以由语言的文法生成
  • 对于语法错误的程序，报告错误信息
  • 对于语法正确的程序，生成语法分析树 (简称语法树)

一个上下文无关文法 (CFG) 包含四个部分

  • 终结符号：组成串的基本符号 (词法单元名字)
  • 非终结符号：表示串的集合的语法变量
    • 在程序设计语言中通常对应于某个程序构造，比如stmt (语句)
  • 产生式：描述将终结符号和非终结符号组成串的方法
    • 形式：头 (左) 部 -> 体 (右) 部
    • 头部是一个非终结符号，右部是一个符号串
    • 例子：expression -> expression + term
  • 起始符号：某个被指定的非终结符号
    • 它对应的串的集合就是文法的语言

推导

  • 将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体（右部）
  • 从起始符号出发，不断进行上面的替换，就可以得到文法的不同句型
  • 符号是=>
  • 句型 (Sentential form)：如果S=*>α，那么α就是文法S的句型
    • 可能既包含非终结符号，又包含终结符号，也可以是空串
  • 句子 (Sentence)
    • 文法的句子就是只包含终结符号的/空串句型
  • 语言
    • 文法G的语言就是G的句子的集合，记为L(G)
    • w在L(G)中当且仅当w是G的句子，即S=*>w

语法分析树

  • 推导的图形表示形式
    • 根结点的标号是文法的起始符号
    • 每个叶子结点的标号是非终结符号、终结符号或ε
    • 每个内部结点的标号是非终结符号
    • 每个内部结点表示某个产生式的一次应用
      • 结点的标号为产生式头，其子结点从左到右是产生式的体
  • 树的叶子组成的序列是根的文法符号的一个句型
  • 一棵语法分析树可对应多个推导序列
    • 但只有唯一的最左推导及最右推导
  • 消除二义性
    • 二义性：文法可以为一个句子生成多颗不同的分析树
    • 惯用技术：分层
  • 消除左递归
    • 左递归：文法中一个非终结符号A使得对某个串α，存在一个推导 A=>Aα，则称这个文法是左递归的
    • 直接左递归（文法中存在A->Aα）的消除：$A \to A\alpha | \beta$改成$A \to \beta A’$与$A’->\alpha A’ | \epsilon$
  • 提取左公因子
    • $A \to \alpha\beta_1 | … | \alpha\beta_n | \gamma$改成$A \to \alpha A’ | \gamma$与$A’\to \beta_1 | … | \beta_n$

自顶向下的语法分析

为输入串构造语法分析树

  • 从分析树的根结点（即文法的起始符号）开始，自顶相下，按照先根次序，深度优先地创建各个结点
  • 对应于最左推导
  • 关键步骤：应用产生式创建新的子结点
    • $A \to X1 | X2 | X3$ … 如何知道应用哪个产生式？
    • 依次猜$X1, X2, X3$ …猜对结束，猜错回溯
  • 需要消除左递归

预测分析法LL(k)

  • L: left-to-right 从左到右扫描

  • L: left-most 最左推导

  • 关键步骤：应用产生式创建新的子结点
    • $A \to X1 | X2 | X3$ … 如何知道应用哪个产生式？
    • 向前看$k$个输入符号，预测要使用的产生式
  • $\mathrm{FIRST}(\alpha)$：可以从$\alpha$推导得到串的首符号的集合
  • $\mathrm{FOLLOW}(A)$：可能在某些句型中紧跟在A右边的终结符号的集合

LL(1)

对于LL(1)文法，可以在自顶向下分析过程中，根据当前输入符号来确定使用的产生式

  • 定义：对文法的任意两个产生式$A \to \alpha | \beta$
    • 不存在终结符号$a$使得$\alpha$和$\beta$都可推导出以a开头的串
    • $\alpha$和$\beta$最多只有一个可推导出空串
    • 如果$\beta$可推导出空串，那么$\alpha$不能推导出以$\mathrm{FOLLOW}(A)$中任何终结符号开头的串
  • 等价于
    • $\mathrm{FIRST}(\alpha)$与$\mathrm{FIRST}(\beta)$不相交(条件一、二)
    • 如果$\epsilon \in \mathrm{FIRST}(\beta)$，即β =*> ε ，那么$\mathrm{FOLLOW}(A)$与$\mathrm{FIRST}(\alpha)$与不相交；反之亦然 （条件三）

预测分析表构造算法

  • 输入：文法$G$
  • 输出：预测分析表$M$
    • 二维表，非终结符 (行) $\times$ 终结符 (列) $\to$ 产生式
    • 展开非终结符时，根据输入终结符选择相应产生式
  • 方法
    • 对于文法G的每个产生式$A \to \alpha$
      • 对于$\mathrm{FIRST}(\alpha)$中的每个终结符号$a$，将$A \to \alpha$加入到$M[A, a]$中
      • 如果$\epsilon$在$\mathrm{FIRST}(\alpha)$，那么对于FOLLOW(A)中的每个符号$b$，将$A \to \alpha$也加入到$M[A, b]$中
  • 最后在所有的空白条目中填入$\mathrm{error}$

自底向上的语法分析

  • 为一个输入串构造语法分析树的过程
  • 从叶子 (输入串中的终结符号，将位于分析树的底端) 开始，向上到达根结点
    • 在实际的语法分析过程中并不一定会构造出相应的分析树，但是用分析树的概念可以方便理解
  • 最右句型：最右推导过程中出现的句型
  • 句柄：对于最右句型$\alpha\beta w$，如果$S$=>$\alpha Aw$=>$\alpha \beta w$，则$\beta$是$A \to \beta$的一个句柄 (方便起见，通常直接称$\beta$为句柄)
    • 在一个最右句型中，句柄右边只有终结符号
    • 如果文法是无二义性的，那么每个句型有且只有一个句柄
  • 最右句型中和某个产生式体 (右部) 相匹配的子串，对它的归约对应了该最右句型的最右推导的最后一步
  • 自底向上分析的过程就是识别和归约句柄的过程

重要的自底向上语法分析的通用框架：移入-归约 (shift-reduce)

  • 移入：将下一个输入符号移入到栈顶
  • 归约：将句柄归约为相应的非终结符号
    • 句柄总是在栈顶
    • 具体操作时弹出句柄，压入被归约到的非终结符号
  • 接受：宣布分析过程成功完成
  • 报错：发现语法错误，调用错误恢复子程序

LR(k)语法分析技术

  • L表示最左扫描，R表示反向构造出最右推导
  • k表示最多向前看k个符号，只考虑k <= 1的情况
  • 能分析的文法比LL(k)文法更多
  • 多种LR技术
    • 简单LR技术 (Simple LR)
    • 向前看LR技术(Look-Ahead LR)
    • …

项：一个文法产生式加上在其中某处的一个点

  • $A \to \cdot XYZ$，$A \to X\cdot YZ$，$A \to XY\cdot Z$，$A \to XYZ\cdot$
  • $A \to \alpha \cdot \beta$表示已扫描/归约到了$\alpha$，并期望在接下来的输入中经过扫描/归约得到$\beta$，然后把$\alpha\beta$归约到$A$
  • $A \to \alpha\beta\cdot$表示已扫描/归约得到了$\alpha\beta$，可以把$\alpha\beta$归约为$A$
  • 注意：$A \to \epsilon$只对应一个项$A \to\cdot$

LR(0)项集规范族的构造

  • 增广文法
    • $G$的增广文法$G’$是在$G$中增加新开始符号$S’$，并加入产生式$S’ to S$而得到的
    • 显然$G’$和$G$接受相同的语言，且按照$S’ \to S$进行归约实际上就表示已经将输入符号串归约成为开始符号
    • 方便引入S的项，表示识别的起始$(S’ \to \cdot S)$/结束$(S’ \to S\cdot)$
  • 根据一个项（状态），扩充读取相同输入后可能同时处于的多个项（状态），称为项集闭包 (CLOSURE)：如果$I$是文法$G$的一个项集，$CLOSURE(I)$就是根据下列两条规则从$I$构造得到的项集
    • 将$I$中的各项加入$CLOSURE(I)$中
    • 如果$A \to \alpha\cdot B\beta$在$CLOSURE(I)$中，而$B \to \gamma$是一个产生式，且项$B \to \cdot \gamma$不在$CLOSURE(I)$中，就将该项加入其中，不断应用该规则直到没有新项可加入
  • GOTO函数（状态跳转表）
    • $I$是一个项集，$X$是一个文法符号，则$GOTO(I, X)$定义为$I$中所有形如$[A \to \alpha\cdot X \beta]$的项所对应的项$[A \to \alpha X\cdot\beta]$的集合的闭包

以LR(0)自动机为基础的SLR语法分析表构造算法

  • 构造增广文法$G’$的LR(0)项集规范族${ I_0, I_1, \dots, I_n }$
  • 状态$i$对应项集$I_i$，相关的ACTION/GOTO表条目如下
    • $[A \to α⋅aβ]$在$I_i$中，且$GOTO(I_i, a) = I_j$，则$ACTION[i, a]$ = “移入$j$”
    • $[A \to α⋅]$在$I_i$中，那么对$FOLLOW(A)$中所有$a$，$ACTION[i, a]$ = “按$A \to \alpha$归约”
    • 如果$[S’ \to S⋅]$在$I_i$中，那么将$ACTION[i, $]$设为”接受”
    • 如果$GOTO(I_i, A) = I_j$，那么在GOTO表中，$GOTO[i, A] = j$
    • 空白的条目设为”error”
  • 如果SLR分析表没有冲突，该文法就是SLR的

规范LR方法 (LR方法)

  • 添加项$[A \to \cdot \alpha]$时，把期望的向前看符号也加入项中(成为LR(1)项集)
  • 向前看符号(串)的长度即为LR(k)中的$k$
  • 充分利用向前看符号，但是状态很多
  • LR(1)项的形式$[A \to \alpha\cdot\beta, a]$
    • $a$称为向前看符号，可以是终结符号或者$$$
    • $a$表示如果将来要按照$A \to \alpha\beta$进行归约，归约时的下一个输入符号必须是$a\in FOLLOW(A)$
    • 当$β$非空时，移入动作不考虑$a$，$a$传递到下一状态

向前看LR (LALR方法)

  • 基于LR(0)项集族，但每个LR(0)项都带有向前看符号
  • 分析能力强于SLR方法，且分析表和SLR分析表一样大
  • LALR已经可以处理大部分的程序设计语言
  • 寻找具有相同核心的LR(1)项集，并把它们合并成为一个项集
  • 合并不会导致移入/归约冲突
  • 合并会引起归约/归约冲突

语义分析

  • 语法制导的定义Syntax-Directed Definition (SDD) 是上下文无关文法和属性/规则的结合
    • 属性和文法符号相关联，按照需要来确定各个文法符号需要哪些属性
    • 规则和产生式相关联
  • 综合属性 (Synthesized Attribute)
    • 结点$N$的属性值由$N$的产生式所关联的语义规则来定义
    • 通过$N$的子结点或N本身的属性值来定义
  • 继承属性 (Inherited Attribute)
    • 结点$N$的属性值由$N$的父结点所关联的语义规则来定义
    • 依赖于$N$的父结点、$N$本身和$N$的兄弟结点上的属性值
  • 几条约束
    • 不允许$N$的继承属性通过N的子结点上的属性来定义，但允许$N$的综合属性依赖于$N$本身的继承属性
    • 终结符号有综合属性 (来自词法分析)，但无继承属性
  • S属性的SDD
    • 每个属性都是综合属性
  • L属性的SDD
    • 综合属性
    • 或继承属性，且$A \to X_1X_2 \dots X_n$中计算$X_i.a$的规则只用
      • A的继承属性，或
      • $X_i$左边的文法符号$X_j$的继承属性或综合属性$(j < i)$

类型检查

  • 通过带副作用的SDD分析变量类型
  • 通过L属性的SDD分析数组类型

语法制导的翻译方案 (SDT)

  • 在产生式体中嵌入语义动作 (程序片断) 的上下文无关文法
  • SDT的基本实现方法
    • 建立语法分析树 (CST)
    • 将语义动作看作是虚拟结点 (绑定语义动作)
    • 深度优先、从左到右地遍历分析树，在访问虚拟结点时执行相应的语义动作
  • 用SDT实现两类重要的SDD
    • 基本文法是LR的，SDD是S属性的
    • 基本文法是LL的，SDD是L属性的

中间代码生成

运行时环境

运行时刻环境

  • 为数据分配安排存储位置
  • 确定访问变量时使用的机制
  • 过程之间的连接、参数传递
  • 和操作系统、输入输出设备相关的其它接口

主题

  • 存储管理：栈分配、堆管理、垃圾回收
  • 对变量、数据的访问

存储分配的典型方式

  • （低地址）
  • 代码区：只读，程序代码
  • 静态区：编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形
  • 堆区：数据对象可比创建它的过程调用更长寿
  • 空闲内存
  • 栈区：和过程的调用/返回同步进行分配和回收，值的生命期与过程生命期相同
  • （高地址）

栈区管理

访问链被用于访问非局部的数据

  • 如果过程$p$在声明时 (直接) 嵌套在过程$q$中，那么$p$活动记录中的访问链指向上层最近的$q$的活动记录
  • 从栈顶活动记录开始，访问链形成了一个链路，嵌套深度沿着链路逐一递减
  • 设深度为$n_p$的过程$p$访问变量$x$，而变量$x$在深度为$n_q$的过程$q$中声明
  • $n_p – n_q$在编译时刻已知；从当前活动记录出发，沿访问链前进$n_p – n_q$次找到活动记录
  • $x$相对于这个活动记录的偏移量在编译时刻已知

显示表

  • 用访问链访问数据，访问开销和嵌套深度差有关
    • 使用显示表可以提高效率，访问开销为常量
  • 显示表：数组d为每个嵌套深度保留一个指针
    • 指针d[i]指向栈中最近的、嵌套深度为i的活动记录
    • 如果过程p访问嵌套深度为i的过程q中声明的变量x，那么d[i]直接指向相应的活动记录 (i在编译时刻已知)
  • 显示表的维护
    • 调用过程p时，在p的活动记录中保存d[np]的值，并将d[np]设置为当前活动记录 (即p)
    • 从p返回时，恢复d[np]的值

堆区管理

堆空间分配方法

  • Best-fit
    • 总是将请求的内存分配在满足请求的最小的窗口中
    • 好处：可以将大的窗口保留下来，应对更大的请求
  • First-fit
    • 总是将对象放置在第一个能够容纳请求的窗口中
    • 放置对象时花费时间较少，但是总体性能较差
    • 通常具有较好的数据局部性：同一时间段内生成的对象经常被分配在连续的空间内

手动回收

手动存储管理的两大问题

  • 内存泄露 (Memory leak)：未能删除不可能再被引用的数据
  • 悬空指针引用 (Dangling pointer)：引用已被删除的数据

自动回收

可达性

  • 可达性就是指一个存储块可以被程序访问到
  • 根集：不需要指针解引用就可以直接访问的数据
    • Java：静态成员、栈中变量
  • 可达性
    • 根集的成员都是可达的
    • 对于任意一个对象，如果指向它的一个指针被保存在可达对象的某字段或数组元素中，那么这个对象也是可达的
  • 性质
    • 一旦一个对象变得不可达，它就不会再变成可达的

自动回收实现方法

  • 引用计数
    • 相互引用产生循环垃圾
  • 基于跟踪的垃圾回收
    • 标记-清扫式垃圾回收
    • 一种直接的、全面停顿的算法
      • 标记：从根集开始，跟踪并标记出所有的可达对象
      • 清扫：遍历整个堆区，释放不可达对象
      • 回收效率不高，易造成碎片
    • 标记-拷贝式垃圾回收
      • 应用程序在某个半区内分配存储，当充满这个半区时，开始垃圾回收
      • 回收时，复制可达对象到另一个半区 (需修改引用地址)
      • 回收完成后，两个半区角色对调
      • 管理区域内大部分对象为垃圾对象时效率高 (只需移动少量可达对象)，反之则效率低
    • 标记-整理式垃圾回收
      • 对可达对象进行重定位可以消除存储碎片
      • 与标记-复制法将对象移动到预留另一半区不同，标记-整理法把可达对象移动到堆区的一端，另一端则是空闲空间
      • 空闲空间合并成单一块，提高分配内存时的效率
      • 管理区域内大部分对象为可达对象时效率高 (经过之前的整理、大部分对象已经到位)，反之则效率低
    • 分代式垃圾回收
      • 大多数对象刚创建不久后就不再使用 (短命)
      • 存在时间越长的对象，通常被回收的几率越小 (命硬)
      • 根据生存周期，对对象分代管理
        • 新创建的对象均放入年轻代区域 (从幼年期开始)
        • 年轻代空间不足时，对该区域执行回收 (标记-复制)
        • 熬过回收的对象移入下一区域 (进化)
        • 老年代空间不足时，对该区域执行回收 (标记-整理)

代码生成

指令选择：选择适当的指令实现IR语句

寄存器分配和指派：把哪个值放在哪个寄存器中

数据结构 (编译期)

  • 寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值
  • 地址描述符：各个变量的当前值存放在哪些位置 (包括内存位置和寄存器) 上

重要子函数：getReg(I)

  • 根据寄存器描述符和地址描述符等数据流信息，为三地址指令I选择最佳的寄存器
  • 得到的机器指令的质量依赖于getReg函数选取寄存器的算法

代码生成同时更新寄存器和地址描述符

  1. 处理指令时生成的LD R, x
    • R的寄存器描述符：只包含x
    • x的地址描述符：R作为新位置加入到x的位置集合中
    • 从任何不同于x的变量的地址描述符中删除R
  2. 生成的ST x, R
    • x的地址描述符：包含自己的内存位置 (新增)
  3. ADD Rx, Ry, Rz
    • Rx的寄存器描述符：只包含x
    • x的地址描述符：只包含Rx(不包含x的内存位置)
    • 从任何不同于x的变量的地址描述符中删除Rx
  4. 处理x = y时
    • 如果生成LD Ry, y，按照规则1处理
    • 把x加入到Ry的寄存器描述符中 (即Ry同时存放了x和y的当前值)
    • x的地址描述符：只包含Ry(不包含x的内存位置)

指令排序：按照什么顺序安排指令执行

机器无关优化

数据流分析

传递函数

控制流约束函数

部分冗余消除

目标：尽量减少表达式求值的次数

  • 全局公共子表达式：如果对$x + y$求值前的程序点上$x + y$可用，那么不需要再对$x + y$求值
  • 循环不变表达式：循环中的表达式$x + y$的值不变，可以只计算一次
  • 部分冗余：在程序按照某些路径到达这个点的时候$x + y$已经被计算过，但沿着另外一些路径到达时，$x + y$尚未计算过

懒惰代码移动

  • 所有不复制代码就可消除的冗余计算都被消除
  • 优化后的代码不会执行原程序中不执行的任何计算
  • 表达式的计算应该尽量靠后，以利于寄存器的分配 冗余消除
  • 完全冗余
  • 部分冗余：在流图中放置表达式$x + y$的拷贝，使得某处的$x + y$成为完全冗余，从而删除
  1. 找出各程序点上预期执行的所有表达式
  2. 在表达式被预期执行但是不可用的程序点上，放置表达式的计算
  3. 把表达式尽量后延到某个程序点，在到达这个点的所有路径上，这个表达式在这个程序点之前被预期执行，但是还没有使用这个值
  4. 消除只使用一次的临时变量

循环的识别、分析和优化

支配 (Dominate)

  • 如果每条从入口结点到达$n$的路径都经过$d$，那么$d$支配$n$，记为$d \mathrm{dom} n$
  • 自己一定支配自己
  • 一个结点的支配结点集合是它的所有前驱的支配结点集合的交集 (加上它自己)

支配结点树可以表示支配关系

  • 根结点：入口结点
  • 每个结点$d$支配且只支配树中的后代结点

深度优先生成树

  • 一个深度优先过程中的搜索路线形成了一个深度优先生成树 (Depth-First Spanning Tree / DFST)
  • 为一个流图构造出DFST之后，流图中的边可以分为三类
    • 前进边：从结点m到达m在DFST树中的一个真后代结点的边 (DFST中的所有边都是前进边)
    • 后退边：从m到达m在DFST树中的某个祖先 (包括m)的边
    • 交叉边：边的src和dest都不是对方的祖先

回边

  • 边$a \to b$，头$b$支配了尾$a$
  • 每条回边都是后退边，但不是所有后退边都是回边 如果一个流图的任何深度优先生成树中的所有后退边都是回边，那么该流图就是可归约的
  • 可归约流图的DFST的后退边集合就是回边集合
  • 不可归约流图的DFST中可能有一些后退边不是回边

流图的深度

  • 流图相对于DFST的深度
    • 各条无环路径上后退边数中的最大值
    • 不会大于直观上所说的流图中的循环嵌套深度
  • 对可归约的流图，可使用回边来定义，且可说是流图的深度

自然循环

  • 自然循环的性质
    • 有一个唯一的入口结点 (循环头Header)，这个结点支配循环中的所有结点
    • 必然存在进入循环头的回边
  • 自然循环的定义
    • 给定回边$n \to d$的自然循环是d，加上不经过$d$就能够到达$n$的结点的集合
    • $d$是这个循环的头
  • 自然循环构造算法
    • 输入：流图$G$和回边$n \to d$
    • 输出：给定回边$n \to d$的自然循环中的所有结点的集合$\mathrm{loop}$
    • 方法：
      • $loop = { n, d }$，$d$标记为visited
      • 从n开始，逆向对流图进行深度优先搜索，把所有访问到的结点都加入loop，加入loop的结点都标记为visited
      • 搜索过程中，不越过标记为visited的结点
  • 循环头上头 (Preheader)
    • 每个自然循环都有一个循环头header
    • 一些循环相关的优化 (如循环不变量移动) 需要在循环头之前插入代码
    • 常见做法是在循环头之前插入一个基本块 (称为preheader)，用于存放相关的代码