基本块和流图

基本块

对每个过程内的指令进行划分，必然连续执行的指令划入一组，称为基本块。控制流只能从基本块的第一条指令进入，除基本块的最后一条指令外，控制流不会跳转/停机。

每个基本块内只有一条执行路径，易于分析。

划分基本块的方法

输入：三地址指令序列

输出：基本块的列表

制定首指令leader（基本块的第一个指令）：

• 第一个三地址指令

• 任意一个（条件或无条件）转移指令的目标指令

• 紧跟在一个（条件或无条件）转移指令之后的指令

确定基本块：每个首指令对应于一个基本块，从首指令开始到下一个首指令。

确定基本块中的活跃性、后续使用

基本块B，开始时B中的非临时变量都是活跃的。从B的最后一个语句开始反向扫描，对于每个语句i：x=y+z，令语句i和x、y、z的当前活跃信息/使用信息关联，设置x为不活跃（代表结果），设置y和z为活跃，并指明它们的下一次使用设置为语句i。

寄存器分配和指派

简单方法：把特定类型的值分配给特定的寄存器。数组基地址指派给一组寄存器，算术计算分配给一组寄存器，栈顶指针分配一个 寄存器，循环，……。缺点：寄存器的使用效率较低

全局寄存器分配：在循环中频繁使用的值存放在固定寄存器。分配固定多个寄存器来存放内部循环中最活跃的值。

可以通过使用计数的方法来估算把一个变量放到寄存器中会带来多大好处，然后根据这个估算来分配寄存器。