Stanford Compiler Week 8 Global Optimization

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这次回顾全局优化。

数据流分析

简介

回顾简单的基本块优化
- 常数传播
- 消除死亡代码
- $\begin{aligned} \begin{aligned} &\mathrm{X:=3} \\ &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=X +Y } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{X:=3} \\ &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=3 +Y } \end{aligned} \Rightarrow \begin{aligned} &\mathrm{Y:=Z\star W} \\ &\mathrm{Q:=X +Y } \end{aligned} \end{aligned}$
这些优化可以扩展到整个控制流图
我们如何知道可以全局传播常量？
要用常数$\mathrm k$代替$\mathrm x$的使用，我们必须知道：
- 在使用$\mathrm x$的每条路径上，对$\mathrm x$的最后一个赋值是$\mathrm {x:= k}$
正确性条件不容易检查
因为“所有路径”包括循环的路径以及通过条件分支的路径
检查条件需要全局数据流分析
- 以及整个控制流图的分析

全局优化

全局优化任务具有以下几个特征：
- 优化取决于在程序执行的特定点上知道属性$\mathrm X$
- 在任何时候证明$\mathrm X$都需要整个程序的知识
- 优化可以是保守的，我们需要知道如下三个事实之一
  - $\mathrm X$绝对正确
  - 不知道$\mathrm X$是否正确
  - 说“不知道”总是安全的
全局数据流分析是解决具有这些特征的问题的标准技术
全局常数传播是需要全局数据流分析的优化例子之一

常数传播

常数传播是指将变量用常数替换的方法，但是，要用常数$\mathrm k$代替$\mathrm x$的使用，我们必须知道：在使用$\mathrm x$的每条路径上，对$\mathrm x$的最后一个赋值是

$\mathrm{x:=k}\ \ \star\star$

可以在性质$\star\star$成立的任何位置执行全局常数传播。
考虑在所有程序点为单个变量$\mathrm X$计算$\star\star$的情况。

为了使问题更精确，我们在每个程序点将以下值之一与$\mathrm X$关联：

值	解释
$\perp$	该语句从未执行
$\mathrm c$	$\mathrm{X=c}$（$\mathrm c$为常数）
$\mathrm T$	$\mathrm X$不是常数

问题描述

给定全局常数信息，可以轻松执行优化
- 只需检查$\mathrm {x =?}$ ，使之与使用$\mathrm x$的语句相关联
- 如果$\mathrm x$在那个点是常数，则用常数代替对$\mathrm x$的使用

基本规则

但是我们如何计算属性$\mathrm {x =?}$
可以将复杂程序的分析表示为相邻语句之间信息更改的简单规则组合
想法是将信息从一个语句“推送”或“转移”到下一个语句
对于每个语句$\mathrm s$，我们计算紧跟在$\mathrm s$之前和之后的$\mathrm x$值的信息
$\begin{aligned} \mathrm{C(x, s, i n)}&=\text {value of x before s} \\ \mathrm{C(x, s, o u t)}&=\text {value of x after s} \end{aligned}$
定义将信息从一个语句传递到另一个语句的传递函数
在以下规则中，令语句$\mathrm s$的前驱语句为$\mathrm{p_1,\ldots,p_n}$

规则1

规则图示：

规则描述：

$\mathrm{if\ C\left(p_{i}, x, out \right)=T\ for\ any\ i,}\\ \mathrm{ then\ C}(\mathrm{s}, \mathrm{x}, \mathrm{in})=\mathrm{T}$

规则2

规则图示：

规则描述：

$\mathrm{if\ C(p_i, x, out) = c\ \&\ C(p_j, x, out) = d\ \&\ d <> c}\\ \mathrm{then\ C(s, x, in) = T}$

规则3

规则图示：

规则描述：

$\mathrm{if\ C(p_i, x, out) = c\ or \perp for\ all\ i,}\\ \text{then C(s, x, in) = c}$

规则4

规则图示：

规则描述：

$\mathrm{if\ C(p_i, x, out) = \perp for\ all\ i,}\\ \text{then C(s, x, in) = c}$

规则1-4指定语句结果和后续语句输入的关系
现在，我们需要将语句的输入与同一语句的输出相关的规则

规则5

规则图示：

规则描述：

$\mathrm{C(s, x, out) = \perp\ if\ C(s, x, in) = \perp}$

规则6

规则图示：

规则描述：

$\mathrm{C(x:=c,x,out) = c\ if\ c\ is\ a\ constant}$

规则7

规则图示：

规则描述：

$\mathrm{C(x := f(...), x, out) = S}$

规则8

规则图示：

规则描述：

$\mathrm{C(y := ..., x, out) = C(y := ..., x, in)\ if\ x <> y}$

应用

对于程序的每个入口$\mathrm s$，设置$\mathrm{C(s,x,in)=T}$
在其他所有地方设置$\mathrm{C(s,x,in)=C(s,x,out)=\perp}$
重复，直到所有点都满足1-8：
- 选择不满足1-8的$\mathrm s$并使用适当的规则进行更新

例子

习题

选择第三项。

循环分析

$\perp$的必要性

为了理解为什么需要$\perp$，考虑循环

考虑语句$\mathrm{Y:=0}$
要计算此时$\mathrm{X}$是否恒定，我们需要知道$\mathrm X$在两个前驱语句中是否恒定
- $\mathrm{X:= 3}$
- $\mathrm {A:= 2 \star X}$
但是$\mathrm {A:= 2 \star X}$的信息取决于其前驱语句，包括$\mathrm{Y:=0}$
由于循环的缘故，所有点必须始终具有值
直观上，分配一些初始值可以使分析中断循环
初始值$\perp$表示“到目前为止，控制流没有到达这一点”

例子

习题

选择第三项。

排序

引入排序

我们可以通过对值进行排序来简化分析的表示方式，这里假设
$\mathrm{\perp< c < T}$
画图得到

分析

$\mathrm T$最大值，$\perp$是最小值
所有常数都介于两者之间并且无法比较
令$\mathrm{lub}$是在此排序下的最小上界：
$\begin{aligned} \mathrm{lub(\perp,1)}&=1\\ \mathrm{lub(1,2)}&=\mathrm T\\ \mathrm{lub(T,\perp)}&=\mathrm T\\ \end{aligned}$
规则1-4可以使用$\text{lub}$简化：
$\text{C(s, x, in) = lub{C(p, x, out) | p is a predecessor of s} }$

说明

之前简单地说“重复直到没有改变”并不能保证循环会终止
使用$\mathrm{lub}$解释了为什么算法终止
- 值以$\perp$开始，并且只会增加
- $\perp$会变成为常数，而常数可以变成为$\mathrm T$
- 因此，$\mathrm{C(s,x,in),C(s,x,out)}$最多会改变两次
因此，常数传播算法的时间复杂度关于的程序大小是线性的
步骤数 = $\mathrm{C(….)}$计算数量$\times 2$ = 程序语句的数量$\times 4$