第八章

基本块

基本块入口语句可能是：

• 程序的第一个语句
• 跳转的目标语句
• 条件跳转的下一条语句

基本块的结束语句可能是：

• 停机语句
• 跳转语句
• 跳转目标语句的前一个语句

后续使用信息

三地址语句i中将a的值赋值给x，若语句j用x作为运算对象，并且控制从i流向j，这条路径中没有x的其他赋值，则称j引用x在i定的值，x在语句i处活跃

每个基本块反向扫描，每个表达式左值设置为非活跃，无后续使用，右值中变量设置为活跃，有后续使用

DAG

• 每个变量有DAG节点表示初始值
• 每个语句s有一个相关节点N，其子节点为基本块中其他语句对应节点，它们为s之前最后对运算分量定值的语句，或初始值节点

节点标号为s中运算符

节点被指名为输出节点，其变量在基本块的出口处活跃

局部公共子表达式

当新节点M被加入到DAG中

• 检查是否存在节点N，与M运算符、子节点（与其顺序）相同，且N在出口处不活跃
• 若存在，NM同值，可用N替换M

消除死代码

DAG图上没有附加活跃变量的根节点（无父节点）为死代码节点，父子关系从上至下看

数组

节点=[], []=

去数组左值将杀死所有当前已建立，依赖于数组的节点

DAG到基本块重组

根据活跃变量决定是否需要计算

指令顺序

• 满足依赖关系，父在子后
• 数组赋值

控制流图

节点为基本块，增加ENTRY, EXIT节点

若从root到m的所有路径都经过n，则n为m的主导者

若不存在n’在中间被n控制且控制m，则n直接主导m

循环为控制流图中单入口的强连通分量，回边构成自然循环，终点dominate起点的边

调用图

节点为过程调用（函数），边为函数指向调用关系

数据流分析

到达定值问题

分析程序中到达某点的定值

• 定值：给某个变量赋值
• 定值注销：如果在这条路径上有对变量a的其他定值，前面的定值将被注销，只有控制节点无二义的定值才能注销其他定值

存在一条从定值到达程序点的路径，在这条路径上被定值的变量的值保持为该定值所赋的值

• gen[B]: 基本块B中到达B的结束点定值d
• kill[B]: 程序中不能到达B的结束点的定值d
• in[B]: 到达B的开始点的定值集合
• out[B]: 到达B的结束点的定值集合

流方程

• $in[B] = \bigcup\limits_{P\in B的前驱}out[P]$
• $out[B] = gen[B] \bigcup(in[B] - kill[B])$

可用表达式问题

程序初始点到该店每条路径都有对该表达式的计算，且在最后一个计算和该点之间没有对此表达式中所用到的变量赋值

基本块注销可用表达式：对右值变量赋值但未重新计算左值

基本块产生可用表达式：计算表达式并且为对右值赋新值

求解算法

对p及其下一点q之间的表达式x=y+z，则y+z为可用表达式，并且将含有x的可用表达式删除

数据流方程

• in[B]: 到达B开始点的可用表达式集合

• out[B]: 到达B结束点可用表达式集合

• e_gen[B]: 块B生成的可用表达式集合

• e_kill[B]: 块B注销的可用表达式集合

• $out[B] = (in[B] -e_kill[B]) \bigcup e_gen[B]$

• $in[B] = \bigcap\limits_{P是B的前驱}out[P]$

• $in[B_{start}] = \varnothing$

与到达定值数据流比较：

• 初始值有定义
• 到达定值的算符为并，求May，先从小集合开始，迭代得到最终解；可用表达式算符为交，求Must，由大集合削减

引用-定值链(ud链)：记录到达变量的某个引用所有可能的定值集合

活跃变量问题

分析程序在某点有哪些变量活跃：从此点开始路径上有引用该变量

数据流方程

• in[B]: 到达B开始点的活跃变量集合

• out[B]: 到达B结束点的活跃变量式集合

• use[B]: 块B可能引用且在该引用前没有定值的变量集

• def[B]: 块B中无二义定值且在该定值前没有引用的变量集

• $in[B] = use[B]\bigcup(out[B] - def[B])$

• $out[B] = \bigcup\limits_{S是B的后继}in[S]$

定值-引用链：du链，给出变量的某个定值可以到达的引用点的集合

数组：对数组的任何元素定值时，都看作是对整个数组的定值，如a[i]；

对常量索引单个元素的定值，特殊处理

分类

传播方向：

• 前向
• 后向

信息合流：

• Must: $\bigcap$
• May: $\bigcup$

跨基本块优化

公共子表达式

表达式E先前已计算，且从先前计算到现在E中变量没改变，则称为公共子表达式

删除算法

对每个形如x = y+z的语句s，若y+z在s所在块的起始点可用，且在块中s前没有y+z的定值，则：

1. 从该块反向搜索，在遇到的每个计算y+z的块中，取最后计算y+z：
2. 建立新变量u
3. 把1中找到的每个语句w = y+z用下面两个语句代替：

1
2

u = y + z
w = u

4. 用x = u代替语句s

复写传播

形如x = y的复写语句可删除

可以考虑在这个语句中 x定制的所有引用点用y代替，从而删除复写语句，但每个x的引用u需满足：

• 语句s为到达u的唯一的x定值
• 从s到u的每条路径，没有对y的赋值

数据流方程

• in[B]: 到达B开始点的复写语句s: x = y的集合，从初始节点到块B开始点的每条路径上都有语句s，且最后出现的s后面没有对x或y的赋值，在集合中只能含有一个x为左值的语句

• out[B]: 到达B结束点的上述复写语句集合

• c_gen[B]: 块B生成的复写语句集合，复写语句出现在块B中，且其后面没有对左右值赋值的语句

• c_kill[B]: 块B注销的可用表达式集合，若左右值在B中被赋值，且语句不在块中，则被注销

• $out[B] =c_gen[B]\bigcup(in[B] -c_kill[B])$

• $in[B] = \bigcup\limits_{P是B的前驱}out[P]$

• $in[B_{start}] = \varnothing$

算法

对每个复写s: x := y执行下面的步骤：

(1) 找出该x的定值能够到达的x的引用 (2) 对(1)中找到的每个x引用，确定s是否在in[B]中（块B是含这个x引用的基本块，且块B中该引用的前面没有x或y的定值），如果s在in[B]中，则x是到达块B的唯一的x定值 (3) 如果s满足(2)的条件，则删掉s，且把(1)中找出的所有x引用以y代替

循环不变计算

ud链寻找循环不变计算

循环特点：首节点为所有其他块的控制节点，循环中任何块至少有一条路径返回首节点

对循环中赋值x = y + z，后两者的所有可能定值都在循环外或者是常数，即ud链中所有def都不在循环体中

由x定值的循环内变量也会受到影响，若另一定值量循环不变则结果循环不变

寻找算法

(1) 对所有下列语句标记“不变”：它的运算对象是常数，和所有的到达—定值在循环L外 (2) 给下面的语句标记“不变”：它们先前没有标记，所有运算对象是常数，或到达—定值都在循环L外，或者只有一个到达—定值，这个定值是循环L中已标记为“不变”的语句 (3) 重复(2)，知道某次重复没有新的语句可标记为“不变”为止

代码外提

外提语句s: x = y + z条件（非必要）：

• 含语句的块是所有出口节点的必经节点（后提）
• 循环中没有其他语句对x定值
• 循环中x的引用仅由s到达

归纳变量

在循环中对某些变量的改变每次都以固定形式

• 强度削弱：对归纳变量i，有语句t = 4 * i，则设置另一归纳变量，在循环外有i赋初值，在循环内使用每次+4的方式代替乘法

强度削弱算法：依次考虑基本归纳变量i，对每个三元组为（i , c , d）的 i 族归纳变量j：

(1) 建立新变量s，但如果变量j1和j2有同样的三元组，则仅建一个新变量用于两者 (2) 用 j := s 代替 j 的赋值 (3) 在L中每个赋值 i := i + n后面（n是常数），紧接它加上: s := s + c * n 其中的表达式 c * n 计算为一个常数（c和n都是常数）, 把s加入i族，三元组为（ i , c , d ） (4) 还必须保证在循环的入口处s的初值为c * i + d，这个初始化可以放在前置块的末尾，它由： s := c * i /* 如果c为1，则s := i / s := s + d / 如果d为0，则省略 */ 组成。注意s是i族的归纳变量

归纳变量删除算法：

(1) 考虑每个仅用于计算同族中其它归纳变量和条件分支的基本归纳变量i。 (a) 取i族的某个j，优先于其三元组( i, c, d )中的c = 1或d = 0这种尽可能简单的j，把每个含i的测试改成用j代替i。假定c>0，则测试if i relop x goto B等价于(其中，x不是归纳变量)： r := c * x /* 如果c = 1，则r := x / r := r + d / 如果d = 0，则省略 */ if j relop r goto B (b) if x relop i goto B的处理类似 (c) 如果if i1 relop i2 goto B中i1和i2都是归纳变量，也可以考虑借鉴上述方法处理，特别是存在三元组( i1, c1, d1 )的j1和三元组( i2, c2, d2 )的j2，且c1 = c2, d1 = d2，则i1 relop i2等价于j1 relop j2 (d) 当被删掉的归纳变量不再引用时，从循环中删去所有对它的赋值 (2) 考虑前面算法引入的赋值语句j := s的每个归纳变量j (a)如果在引入的j := s和任何j的引用间没有对s的赋值（一般是没有这种赋值的），则用引用s代替所有j的引用，并删除语句j := s (b) 如果存在对s的赋值，则要考虑到达—定值信息等，进行检查，以决定是否可以进行删除

窥孔优化

目标代码优化

消除不可达代码

控制流图消除不可达节点

控制流优化

连续跳转指令

代数恒等式化简

强度削减

机器特有指令，SIMD

寄存器

• 寄存器分配：决定哪些变量该占用寄存器
• 寄存器指派：决定变量该使用哪个寄存器

图着色：将变量使用无穷多寄存器存储，构造变量使用的干涉图

一个变量的活跃区间：变量的定值与引用的子集，对应于流图上连接变量的定值点和引用点的连通区域

求解算法：从定值开始到引用之前结束的所有路径点的集合，左闭右开

干涉：若在其中某个变量的定值处，另一个变量是定值到达和活跃的

干涉图：每个节点代表一个变量的活跃区间，若两个变量干涉，则将节点相连

收益计算

• 若x在寄存器中，每次引用节省一个单位加载开销：只有x在基本块内被使用，且在同一基本块中未先行赋值，才节省一单位开销
• 若x在基本块中定值且在出口活跃，则x分配在寄存器中可节省2单位开销（保存与之后的加载）
• 循环入口/出口基本块：
  • 若x在入口活跃，循环前夹在寄存器，需要2单位开销
  • x在出口活跃，需要2单位开销保存

收益估算：

$$\sum\limits_{L中全部基本块}use(x, B) + 2\times live(x, B)$$

• $use(x, B)$：x在基本块中被定值之前使用的次数
• $live(x, B)$：若x在B的出口处活跃，且x在B中被赋值，则$live(x, B)$为1，否则为0