什么是基本块？
什么是流图
优化的分类
- 机器无关优化
- 针对中间代码
- 局部代码优化
- 单个基本块范围内的优化
- 全局代码优化
数据流分析
s是一个语句，所以说数据流值在经过s之后会变化发，所谓传递函数。
到达定值分析
注意KILL这个概念，是变量x被重新赋值，则原来的定值（语句）被杀死。
到达定值分析的用途
杀死与生成
到达定值分析的算法
kill置为0，gen置为1
活跃变量分析
活跃变量就是定义了以后会被用到嘛2333
因为这是一个逆向数据流问题，所以用x表示在基本块出口处的活跃变量的集合，f(x)表示基本块入口处活跃变量的集合。
use表示在基本块中首次出现，以引用形式出现的变量的集合，所以这些变量在基本块入口处肯定是活跃的。
def表示在基本块中首次出现，以定值形式出现的变量的集合，所以这些变量在基本块入口处肯定是不活跃的。
所以说def杀死了某些变量在基本块入口处成为活跃变量的可能性。
解释一下B2，i和j在基本块B2中都是以引用形式首次出现，所以在use里，而def为∅
得到活跃变量表
可用表达式分析
z=x op y生成了表达式x op y，加入gen
同时这条语句对z定值，于是删除与z相关的表达式。
z = x op y，于是从kill中删除表达式x op y，代表它复活了。
同时这条语句对z定值，于是把和z相关的表达式加入kill中
注意是IN的交集
对循环的优化
要想对循环进行优化，首先要识别出流图中的循环。
支配节点（Dominators)和回边
- 支配节点
在支配节点树中，每个节点只支配它和它的后代节点。
可以看出一个节点可能会有若干个支配节点，于是给出直接支配节点的定义
寻找支配节点是一个数据流问题
注意交运算，所以初始化时初始为全集
- 回边
自然循环及其识别
如图2和3不存在彼此支配的关系，2和3构成了一个循环，控制既可以从2，也可以从3号节点进入，这样循环的入口节点就不唯一了。
删除全局子表达式
删除复制语句
注意到达定义分析是并 IN[P]，可用表达式分析是交 IN[P]
代码移动
注意不一定所有的循环不变量都能外提
如图，B2并不一定被执行，那么其中的代码外提就是错误的。
如果还有其他语句对x赋值，那么就有可能让原来的定值语句被杀死。
