本次笔记内容：
8-10 支配结点和回边
8-11 自然循环及其识别
8-12 删除全局工工资表达式和赋值语句
8-13 代码移动
8-14 作用于归纳变量的强度削弱
8-15 归纳变量的删除

本节课幻灯片，见于我的 GitHub 仓库：第19讲 代码优化_4.pdf

支配结点和回边

支配结点(Dominators)

如果从流图的入口结点到结点 n 的每条路径都经过结点 d ，则称结点 d 支配(dominate)结点 n ，记为d dom n。

每个结点都支配它自己。

例

每个结点只支配它和它的后代结点。

直接支配结点(Immediate Dominator)：

• 从入口结点到达n的所有路径上，结点n的最后一个支配结点称为直接支配结点

寻找支配结点

支配结点的数据流方程：

计算支配结点的迭代算法

• 输入：流图G，G的结点集是N，边集是E，入口结点是ENTRY
• 输出：对于N中的各个结点n，给出D(n)，即支配n的所有结点的集合
  

例

回边(Back Edges)

假定流图中存在两个结点d和n满足d dom n。如果存在从结点n到d的有向边n→d，那么这条边称为回边。

自然循环及其识别

自然循环(Natural Loops)

自然循环是一种适合于优化的循环。

从程序分析的角度来看，循环在代码中以什么形式出现并不重要，重要的是它是否具有易于优化的性质。

自然循环是满足以下性质的循环：

• 有唯一的入口结点，称为首结点(header)。首结点支配循环中的所有结点，否则，它就不会成为循环的唯一入口；
• 循环中至少有一条返回首结点的路径，否则，控制就不可能从“循环”中直接回到循环头，也就无法构成循环。

之前说的“回边”，就是用于自然循环的识别。

自然循环的识别

给定一个回边n → d，该回边的自然循环为：d，以及所有可以不经过d而到达n的结点。d为该循环的首结点。

算法：构造一条回边的自然循环

• 输入：流图G和回边n → d
• 输出：由回边n → d的自然循环中的所有结点组成的集合

结点d在初始时刻已经在loop中，不会去考虑它的前驱。因此, 找出的都是不经过d而能到达n的结点。

自然循环的一个重要性质：

• 除非两个自然循环的首结点相同，否则，它们或者互不相交，或者一个完全包含(嵌入)在另外一个里面。
• 例。
  

如果两个循环具有相同的首结点，那么很难说哪个是最内循环。此时把两个循环合并。

删除全局公共子表达式和复制语句

删除全局公共子表达式

可用表达式的数据流问题可以帮助确定位于流图中p点的表达式是否为全局公共子表达式。

全局公共子表达式删除算法

输入：带有可用表达式信息的流图

输出：修正后的流图

方法：对于语句s：z = x op y，如果x op y在s之前可用，那么执行如下步骤：

• ① 从s开始逆向搜索，但不穿过任何计算了x op y的块，找到所有离s最近的计算了x op y的语句
• ② 建立新的临时变量u
• ③ 把步骤①中找到的语句w = x op y用下列语句代替：u = x op y，w = u
• ④ 用z = u替代s

删除复制语句

对于复制语句s: x=y，如果在x的所有引用点都可以用对y的引用代替对x的引用(复制传播)，那么可以删除复制语句x=y。

在x的引用点u用y代替x (复制传播)的条件：复制语句s: x=y在u点“可用”。

删除复制语句的算法

输入：流图G 、du链、各基本块B入口处的可用复制语句集合

输出：修改后的流图

方法：对于每个复制语句x=y，执行下列步骤：

• ① 根据du链找出该定值所能够到达的那些对x的引用
• ② 确定是否对于每个这样的引用，x=y都在IN[B]中(B是包含这个引用的基本块) ，并且B中该引用的前面没有x或者y的定值
• ③ 如果x=y满足第②步的条件，删除x=y ，且把步骤①中找到的对x的引用用y代替

代码移动

• 循环不变计算的检测
• 代码外提

循环不变计算检测算法

输入：循环L，每个三地址指令的ud链

输出： L的循环不变计算语句

方法：

1. 将下面这样的语句标记为“不变”：语句的运算分量或者是常数，或者其所有定值点都在循环L外部
2. 重复执行步骤(3)，直到某次没有新的语句可标记为“不变”为止
3. 将下面这样的语句标记为“不变”：先前没有被标记过，且所有运算分量或者是常数，或者其所有定值点都在循环L外部，或者只有一个到达定值，该定值是循环中已经被标记为“不变”的语句

代码外提

前置首结点(preheader)：循环不变计算将被移至首结点之前，为此创建一个称为前置首结点的新块。前置首结点的唯一后继是首结点，并且原来从循环L外到达L首结点的边都改成进入前置首结点。从循环L里面到达首结点的边不变。

循环不变计算语句s : x = y + z 移动的条件

（1）s所在的基本块是循环所有出口结点(有后继结点在循环外的结点)的支配结点

(2) 循环中没有其它语句对x赋值

(3) 循环中对x的引用仅由s到达

代码移动算法

输入：循环L、ud链、支配结点信息

输出：修改后的循环

方法：

1. 寻找循环不变计算
2. 对于步骤(1)中找到的每个循环不变计算，检查是否满足上面的三个条件
3. 按照循环不变计算找出的次序，把所找到的满足上述条件的循环不变计算外提到前置首结点中。如果循环不变计算有分量在循环中定值，只有将定值点外提后，该循环不变计算才可以外提

例

作用于归纳变量的强度削弱

对于一个变量x ，如果存在一个正的或负的常量c ，使得每次x被赋值时，它的值总是增加c ，则称x为归纳变量。

如果循环L中的变量i只有形如i =i+c的定值(c是常量)，则称i为循环L的基本归纳变量。

如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则j也是一个归纳变量，称j属于i族。

• 基本归纳变量i属于它自己的族。

每个归纳变量都关联一个三元组。如果j = c×i+d，其中i是基本归纳变量，c和d是常量，则与j相关联的三元组是( i, c, d )。

归纳变量检测算法

输入：带有循环不变计算信息和到达定值信息的循环L

输出：一组归纳变量

方法：

1. 扫描L的语句，找出所有基本归纳变量。在此要用到循环不变计算信息。与每个基本归纳变量i相关联的三元组是(i, 1, 0)
2. 寻找L中只有一次定值的变量k，它具有下面的形式。

k=c′×j+d′。其中c′和d′是常量，j是基本的或非基本的归纳变量：

• 如果j是基本归纳变量，那么k属于j族。k对应的三元组可以通过其定值语句确定
• 如果j不是基本归纳变量，假设其属于i族， k的三元组可以通过j的三元组和k的定值语句来计算，此时我们还要求：
  • 循环L中对j的唯一定值和对k的定值之间没有对i的定值
  • 循环L外没有j的定值可以到达k
  • (这两个条件是为了保证对k进行赋值的时候，j当时的值一定等于c*(i当时的值)+d)
    

作用于归纳变量的强度削弱算法

输入：带有到达定值信息和已计算出的归纳变量族的循环L

输出：修改后的循环

方法：对于每个基本归纳变量i，对其族中的每个归纳变量j：(i, c, d)：
执行下列步骤

1. 建立新的临时变量t。如果变量j1和j2具有相同的三元组，则只为它们建立一个新变量
2. 用j=t代替对j的赋值
3. 在L中紧跟定值i=i+n之后，添加t=t+c*n。将t放入i族，其三元组为(i, c, d)
4. 在前置节点的末尾，添加语句t=c*i和t=t+d ，使得在循环开始的时候t=c*i+d=j

如上，将乘法运算转换为加减法运算，从而实现了强度削弱。

归纳变量的删除

对于在强度削弱算法中引入的复制语句j=t，如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用，并且j在循环的出口处不活跃，则可以删除复制语句j=t。

归纳变量的删除

对于在强度削弱算法中引入的复制语句j=t，如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用，并且j在循环的出口处不活跃，则可以删除复制语句j=t。

强度削弱后，有些归纳变量的作用只是用于测试。如果可以用对其它归纳变量的测试代替对这种归纳变量的测试，那么可以删除这种归纳变量。

删除仅用于测试的归纳变量

对于仅用于测试的基本归纳变量i，取i族的某个归纳变量j(尽量使得c、d简单，即c=1或d=0的情况)。把每个对i的测试替换成为对j的测试。

• ( relop i x B )替换为( relop j c*x+d B )，其中x不是归纳变量，并假设c>0；
• ( relop i1 i2 B )，如果能够找到三元组j1 ( i1, c, d )和j2 ( i2, c, d )，那么可以将其替换为( relop j1 j2 B ) (假设c>0 )。否则，测试的替换可能是没有价值的。

如果归纳变量i不再被引用，那么可以删除和它相关的指令。