目标代码生成

基本块

只有一个入口语句和一个出口语句
除入口语句外其他语句均不可以带标号
除出口语句外其他语句均不可能是转移或停语句

入口语句

程序的第一个语句
条件转移语句或无条件转移语句的转移目标语句
紧跟在条件转移语句后面的语句

划分基本快

求出 TAC 中各个基本快的入口语句
对每一入口语句，构造其所属的基本块。它是由该语句到
- 下一入口语句（不包括下一入口语句）
- 或到一转移语句（包括该转移语句）
- 或到一停语句（包括该停语句）之间的语句序列组成的
凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除

流图

为构成程序的基本块增加控制流信息，方法是构造一个有向图，称之为流图或控制流图。

流图以基本块集为结点集；第一个结点为含有程序第一条语句的基本块；从基本块 i 到基本块 j 之间存在有向边，当且仅当

基本块 j 在程序的位置紧跟在 i 后,且 i 的出口语句不是转移 (可为条件转移)语句、停语句或者返回语句
或者 i 的出口是 goto(S) 或 if goto(S), 而 (S) 是 j 的入口语句

循环

如果从流图首节点出发，到达 n 的任意通路都要经过 m，则称 m 支配 n，或 m 是 n 的支配节点，记为 m DOM n。节点 n 的所有支配节点的集合称为它的支配节点集，记为 $D (n)$

自然循环

假设 $n \to d$ 是一条流图中的有向边，如果 d DOM n，则称它是一条回边。

有向边 $n \to d$ 是回边，它对应的自然循环是由结点 d ，结点 n 以及有通路到达 n 而该通路不经过 d 的所有结点组成

d 是该循环的唯一入口结点，且必可达该循环中任意结点

数据流分析

数据流方程：

o u t [S] = g e n [S] \cup (in [S] - ki ll [S])

含义为：

基本块 S 出口处的数据流信息 $o u t [S]$
内部产生的信息 $g e n [S]$
从 S 开始处进入但在穿过 S 的控制流时未被杀死的信息 $in [S] - ki ll [S]$

到达-定值

变量 A 的定值是一个 TAC 语句，它赋值或可能赋值给 A
最普通的定值是对 A 的赋值或读值到 A 的语句，该语句的位置称作 A 的定值点
变量 A 的定值点 d 到达某点 p，是指如果有路径从紧跟 d 的点到达 p，并且在这条路径上 d 未被“杀死”（指该变量重新被定值）

数据流方程求解算法：

活跃变量

对程序中的某变量 A 和某点 p 而言，如果存在一条从 p 开始的通路，其中引用了 A 在点 p 的值，则称 A 在点 p 是活跃的
直观地说，对于全局范围的分析来说，一个变量是活跃的，如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用

L i v e I n (B) = L i v e U se (B) \cup (L i v e O u t (b) - De f (B))

$L i v e U se (B)$ 为 B 中被定值之前要引用变量的集合
$De f (B)$ 为在 B 中定值的且定值之前未曾在 B 中引用过的变量集合
$L i v e I n (B)$ 为 B 入口处为活跃的变量集合
$L i v e O u t (B)$ 为 B 的出口处的活跃变量集合

数据流方程求解算法：

UD 链

UD 链：假设在程序中某点 u 引用了变量 A 的值，则把能到达 u 的 A 的所有定值点的全体，称为 A 在引用点 u 的引用-定值链，简称 UD 链

如果在基本块 B 中，变量A的引用点 u 之前有 A 的定值点 d，并且 A 在点 d 的定值到达 u，那么 A 在点 u 的 UD 链就是 ${d}$
如果在基本块中，变量 A 的引用点 u 之前没有 A 的定值点，那么， $I N [B]$ 中 A 的所有定值点均到达 u，它们就是 A 在点 u 的 UD 链

DU 链

假设在程序中某点 u 定义了变量 A 的值，从 u 存在一条到达 A 的某个引用点 s 的路径，且该路径上不存在 A 的其他定值点，则把所有此类引用点 s 的全体称为 A 在定值点 u 的定值－引用链，简称 DU 链

方法类似 UD 链

待用信息 & 活跃信息

待用信息：基本块中某变量定值点的待用信息链即为该点在基本块范围内的 DU 链中最近的引用点
活跃信息：基本块中的活跃信息链体现了以语句为单位的活跃变量信息
计算
- 初始时，把每个变量“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或 “非活跃”
- 从基本块出口到入口对每个TAC 语句 i: A := B op C 依次执行下述步骤
  - 把变量A的待用信息和活跃信息附加到 TAC 语句 i 上
  - 把变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”
  - 把变量 B 和 C 的待用信息和活跃信息附加到 TAC 语句 i 上
  - 把变量 B 和 C 的待用信息栏置为“i” ，活跃信息栏置为 “活跃”

基本块的 DAG 表示

基本块的 DAG 是在结点上带有标记的 DAG

叶结点：代表名字的初值，以唯一的标识符（变量名字或常数）标记
内部结点：用运算符号标记所有结点都可有一个附加的变量名字表

构造

对基本块的每一 TAC 语句，依次进行下列步骤

若 node(y) 无定义，则创建一个标记为 y 的叶结点，并令node(y) 为这个结点
- 对于 x := y op z, 若 node(z) 无定义，再创建标记为 z 的叶节点，令 node(z) 为这个节点
对 x := y op z,
- 若 node(y) 和 node(z) 都是标记为常数的叶节点，执行 y op z，令得到的新常数为 p，若 node(p) 无定义，则构造一个用 p 做标记的叶结点 n。若 node(y)或 node(z)是处理当前语句时新构造出来的结点，则删除它。置 node(p)=n
- 若 node(y) 或 node(z)不是标记为常数的叶结点，则检查是否存在某个标记为 op 的结点，其左孩子是 node(y) ，而右孩子是node(z) ？若无，则创建这样的结点。无论有无，都令该结点为 n
对 x := op y
- 若 node(y) 是标记为常数的叶结点，执行 op y，令得到的新常数为p。若 node(p)无定义，则构造一个用 p 做标记的叶结点 n。若 node(y) 是处理当前语句时新构造出来的结点，则删除它。置 node(p)=n。
- 若 node(y) 不是标记为常数的叶结点，则检查是否存在某个标记为 op 的结点，其唯一的孩子是 node(y)？若无，则创建这样的结点. 无论有无，都令该结点为 n.
对 x := y，令 node(y) 为 n
最后，从 node(x) 的附加标识符表中将 x 删除，将其添加到结点 n 的附加变量名字表中，并置 node(x) 为 n。