基本块
基本块是满足下列条件的最大的连续三地址指令序列。
- 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
- 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机
一个基本块的指令要么都执行，要么都不执行。
基本块划分算法
首先，确定指令序列中哪些指令是首指令，即某个基本块的第一个指令：
- 指令序列的第一个三地址指令是一个首指令
- 任意一个条件或无条件转移指令的目标指令是一个首指令
- 紧跟在一个条件或无条件转移指令之后的指令是一个首指令
然后，每个首指令对应的基本块包括从它自己开始，直到下一个首指令 (不含) 或者指令序列结尾之间的所有指令
流图
就是不同根据上面的基本块，然后判断其跳转关系可以作得流图。
优化方法
分类
- 机器无关优化：针对中间代码
- 机器相关优化：针对目标代码
- 局部代码优化：单个基本块范国内的优化
- 全局代码优化：面向多个基本块的优化
常用的优化方法
删除公共子表达式
如果表达式先前已被计算过，并且从先前的计算到现在，表达式中变量的值没有改变，这次出现就称为公共子表达式。
碰到这种情况，我们把后面的那一个删除即可。
删除无用代码
复制传播：常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句 (形如x = y的赋值语句)，在复制语句 x = y之后尽可能地用 y 代替 x ：
优点是可以方便的删除无用（没有用的赋值语句就删掉了），关于上面的基本块，经过优化后有：
常量合并
如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为常量合并。
代码移动
这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式，即循环不变计算。（即进入循环之前就进行运算）
强度削弱
用较快的操作代替较慢的操作，如用加代替乘
归纳变量：对于一个变量 x ，如果存在一个正的或负的常数 c 使得每次 x 被赋值时它的值总增加 c ，那么 x 就称为归纳变量。
如下图，对于 t2 就是一个归纳变量（每次增加4），所以我们可以把乘法换成加法。
删除归纳变量
在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个。
下面这个，因为 i 和 j 的作用只用来控制 t2，t4 所以删除也没什么影响。
基本块的优化
很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图。
基本块的无环有向图表示
构建算法如下，从第一条语句开始：
- 把语句左边的作为根节点，运算符作为标号，然后两个操作数作为叶子。
- 如果语句的左边在之前已经有了，那么我们就把它之前的那个结点删除。
根据算法，可以得到无环有向图如下：
注意一下，对于数组复制指令 a[j] = y ， 创建一个运算符为“[]=” 的结点，这个结点有3个子结点， 分别表示a、j 和 y
基于基本块的 DAG 删除无用代码
从一个DAG上删除所有没有附加活跃变量（指其值可能会在以后被使用的变量，是人为设计的）的根结点。重复这样的处理，就可以从DAG中消除所有对应于无用代码的结点。
对于这个问题，一开始根节点是 a 和 e，而 a 是活跃变量，不能删除，所以删除 e。删除 e 后，a，c 和 b 是根节点，然后删除非活跃变量 c。
从 DAG 到基本块的重组
因为 G 不是活跃变量，然后和活跃变量没什么关系，所以可以删除。然后 J，I，H 重复然后删除。所以可以得到优化过的代码块：
数据流分析
一组用来获取程序执行路径上的数据流信息的技术
模式
IN[s]: 语句s之前的数据流值OUT[s]: 语句s之后的数据流值fs：语句 s 的传递函数，描述的是一个赋值语句 s 之前和之后的数据流值的关系。对于相邻两个语句有
$$
I N\left[s_{i+1}\right]=O U T\left[s_{i}\right] \quad i=1,2, \dots, n-1
$$
到达定值分析
- 定值：变量 x 的定值是(可能)将一个值赋给 x 的语句
- 到达定值：如果某个变量 x 的一个定值 d 到达点 p，在点 p 处使用的 x 的值可能就是由 d 最后赋予的（中途不能有其它赋值）
例：可以到达各基本块的入口处的定值
对 B2 分析：因为 d1,d2,d3 中间没有改变，所以三个均可到达 B2 入口处。对于 d4，在 B2->B4->B2 的过程中，在 B4 中 i 改变了，所以说 d4 是不可到达的。 同理，d5,d6,d7 可到达 B2 入口处。对于 B3，B4 同理。
到达定值分析的主要用途
- 循环不变计算的检测：如果循环中含有赋值 x=y+z ，而 y 和 z 所有可能的定值都在循环外面 (包括 y 或 z 是常数的特殊情况) ，那么 y+z 就是循环不变计算。直观上来说，就是 y 和 z 是由循环外的值决定的。
- 常量合并：如果对变量 x 的某次使用只有一个定值可以到达，并且该定值把一个常量赋给 x ，那么可以简单地把 x 替换为该常量。意思就是说，这个变量只由一个常量决定的，所以可以替换为常量。
- 判定变量 x 在 p 点上是否未经定值就被引用：没有任何定值可到达。
“生成”与“杀死”定值
假如我们有定值 d: u=v+w
该语句“生成”了一个对变量 u 的定值 d，并“杀死” 了程序中其它对 u 的定值
对于 b1，他生成了 d1，d2，d3，然后因为 d4 , d5 , d6 , d7 都有 i, j, a，所以d4 , d5 , d6 , d7 被杀死了。
到达定值的数据流方程
对于某个语句 x，有传递函数：
$$
f_{B}(x)=g e n_{B} \cup\left(x-k i l l_{B}\right)
$$
意思是在执行 x 后，传递函数传递的定值等于生成的加上 x 中为未被杀死的。
活跃变量分析
对于变量 x 和程序点 p，如果在流图中沿着从 p 开始的某条路径会引用变量 x 在 p 点的值，则称变量 x 在点 p 是活跃的。
对于上面这个例子，我们只需要分析他的引用路径即可即可。比如在 B2 中我们使用了 B1 中 i 的值，所以 i 对于 B1 来说是活跃的。而在 B4->B2 这条路径中， B2 引用了B4 的值，所以 B4 也是活跃的。以此类推（很多时候，只要看后续路径是否有式子右边出现了变量）
活跃变量信息的主要用途
- 删除无用赋值：如果 x 在点 p 的定值在基本块内所有后继点都不被引用，且 x 在基本块出口之后又是不活跃的，那么 x 在点 p 的定值就是无用的
- 为基本块分配寄存器：如果所有寄存器都被占用，并且还需要申请一个寄存器，则应该考虑使用已经存放了死亡值的寄存器，因为这个值不需要保存到内存。如果一个值在基本块结尾处是死的就不必在结尾处保存这个值。
传递函数如下：
$$
f_{B}(x)=u s e_{B} \cup\left(x-d e f_{B}\right)
$$
- defB：在基本块B中首次为定值的元素
- useB：在基本块B中首次为引用元素
注意：i=i+j 中，先计算 i+j，然后再把值赋给 i。所以 i 和 j 都在 useB
可用表达式分析
在点 p 上，x op y 已经在之前被计算过，而且没有重新定值，所以不需要重新计算。
消除全局公共子表达式
复制传播：
在 x 的引用点 u 可以用 y 代替 x 的条件：从流图的首节点到达 u 的每条路径都存在复制语句 x = y，并且从最后一条复制语句 x = y 到点 u 之间没有再次对 x 或 y 定值。
循环及其识别
支配结点和回边
如果从流图的入口结点到结点n的每条路径都经过结点 d，则称结点d支配结点n，记为d dom n ，每个结点都支配它自己。从入口结点到达n的所有路径上，结点n的最后一个支配结点称为直接支配结点
回边：假定流图中存在两个结点d和n满足d dom n。如果存在从结点n到d的有向边n→d，那么这条边称为回边。
自然循环
自然循环是满足以下性质的循环：
- 有唯一的入口结点，称为首结点(header)。首结点支配循环中的所有结点，否则，它就不会成为循环的唯一入口
- 循环中至少有一条返回首结点的路径，否则，控制就不可能从 “循环” 中直接回到循环头，也就无法构成循环。
下面这个循环入口不唯一，所以不是自然循环：
给定一个回边 n → d，该回边的自然循环为：首结点 d，以及所有可以不经过 d 而到达 n 的结点。d 为该循环的首结点。
自然循环的一个重要性质：除非两个自然循环的首结点相同，否则，它们或者互不相交， 或者一个完全包含(嵌入)在另外一个里面。
最内循环: 不包含其它循环的循环
如果两个循环具有相同的首结点，那么很难说哪个是最内循环。此时把两个循环合并，删除全局公共子表达式和复制语句
