第9章机器无关优化

本章考虑的是全局代码优化问题，即考虑多个基本块。
大部分全局优化方法是基于数据流分析技术实现的：对于程序中的每个指令，描述该指令每次执行时必然成立的一些性质。

优化的主要来源

编译优化必须保持源程序的语义。所以，通常编译器只能应用一些相对低层的语义转换。
冗余：通常是高级程序设计语言的副产物（比如高层数据结构的访问，高维数组）。

下面是一个例子：

快速排序算法：

对应的直接生成的三地址运算序列及其流图

全局公共子表达式优化后（比如 B5 中的 t6, t7, t8, t10 和 B6 中的 t11, t12, t13, t15）：

公共子表达式消除的同时，可能会引入额外的赋值语句，如下图：

而赋值语句允许我们使用复制传播进一步优化。
这里提到了一个观点，当出现赋值语句 u=v 后，尽可能用 v 来替代 u，这样能为后面的消除提供机会。
下面是使用复制传播后，进一步优化的 B5。

死代码消除：复制传播后，B5 可以进一步使用死代码消除来优化：

代码移动：主要针对循环，关注循环不变计算，将对它们的求值移动到循环之外，这样就以增加循环外代码的代价，减少了循环内的指令个数。

归纳变量和强度消减：归纳变量即循环中那个每次有规律地递增或递减的值。由于归纳变量是有规律地递增或递减的，所以循环内有关该变量的高代价运算（比如乘法）就可以替换为一个较低代价的运算（比如加法）。另外，如果有一组归纳变量的变化步调一致，我们可以进一步将其规约删减为一个。
循环的优化处理通常是从里到外的。

下面是一个归纳变量的例子，关注到 B3 中的归纳变量 j 和与其相关的 t4。可以优化如下，注意到在循环入口增加了 t4 的初始赋值：

进一步的优化可以将 B2, B3, 中的 i,j 全部替换如下

数据流分析简介

数据流抽象：将程序的执行看作是对程序状态的一系列转换。考虑经过一个语句的所有可能路径。一般来说，可能的执行路径也许有无穷多条，跟踪所有的程序状态也是不可能的。所以一般不区分路径之间的差异，也不跟踪整个状态，仅保留进行分析需要的数据。
在数据流分析模式中，通常将每个程序点和一个数据流值关联起来。该值即为在该点可能观察到的所有状态的抽象表示。

数据流问题：定义语句 s 之前和之后的数据流值为 $I N [s]$ 和 $O U T [s]$ ，数据流问题即是对一组约束求解，该约束限定了语句 s 的 $I N [s]$ 和 $O U T [s]$ 之前的关系。
约束可以分为两类：基于语句语义（传递函数）的约束和基于控制流的约束。

在基本块上，由于内部的处理通常比较简单，所以可以节约相关分析的空间和时间。类似的，记基本块 B 的数据流值为 IN[B] 和 OUT[B]。

数据流方程通常没有唯一解，故其分析的目标是寻找一个最精确的满足两组约束的解。它能够支持有效的代码改进，但又不会导致不安全的转换。

下面给出几个例子。

到达定值

一种常见的数据流模式，当到达程序中的每个点时，每个变量 x 可能在程序中的哪些地方被定值。
过程参数、数组访问和间接引用都可以有别名，故分析时需要保守。如果我们不知道一个语句是否给 x 赋了一个值，那么必须假定它可能对 x 赋值。本节中我们不考虑别名这样的情况。

传递方程：对于定值 $d : u = v + w$ ，该语句生成了一个变量 u 的定值 d，其传递函数可以表示为 $f_{d} (x) = g e n_{d} \cup (x - ki l l_{d})$ ，其中 $g e n_{d} = {d}$ ， $ki l l_{d}$ 是程序中所有其他对 u 的定值。对于基本块的传递方程也是同理。
控制流方程：对于基本块 B，有 $I N [B] = ⋃_{P 是 B 的一个前驱基本块} O U T [P]$ 。
我们采用迭代的方式来求解，记 $O U T [ENTR Y] = \emptyset$ ，迭代地求解该方程组地最小不动点（即方程其他解所给出地值地子集）。算法流程是不断地向前传播各个定值，直到该定值被杀死。不断重复该过程，直到所有的值收敛。

活跃变量分析

对于变量 x 和程序点 p ，x 在点 p 上的值是否会在流图中某条从 p 出发的路径中使用。该信息依赖程序控制流的相反方向进行计算。
该分析可以用于寄存器分配。

定义 IN[B] 和 OUT[B] 分别为活跃变量集合。 $d e f_{B}$ 为一个包含变量的集合，这些变量在 B 中的定值（赋值）先于任何使用； $u s e_{B}$ 则相反，是可能的使用先于定值。
方程定义为 $I N [EX I T] = \emptyset$ ， $I N [B] = u s e_{B} \cup (O U T [B] - d e f_{B}), O U T [B] = ⋃_{S 是 B 的后继} I N [S]$ 。
使用上一节中迭代算法的类似版本，逆向传播即可求解最小不动点。

可用表达式

定义：从流图入口节点到程序点 p 的每条路径都对 x+y 表达式求值，且最后一个求值后没有对 x 或 y 重新赋值，则称 x+y 在 p 可用。
如果一个基本块对 x 或 y 赋值且之后没有再重新求 x+y，则称其杀死了表达式 x+y。
如果一个基本块求 x+y 且之后未修改 x 或 y，则称其生成表达式 x+y。
该信息主要用于寻找公共子表达式。
方程为 $O U T [ENTR Y] = \emptyset$ , $O U T [B] = e_g e n_{B} \cup (I N [B] - e_ki l l_{B}), I N [B] = ⋂_{P 是 B 的前缀} O U T [P]$ 。
与求解定值中相反的是，这里我们想要得到的是最大可用表达式集合的解，所以是先给出较大的近似值，然后逐步消减。

总结

下表展示了三个例子之间的区别

数据流分析基础

基本问题：迭代算法的正确性，解的精确程度，迭代算法是否收敛，解的含义。

定义数据流分析框架 $(D, V, \land, F)$ 如下：

D 为数据流方向，取值包括 FORWARD 前向和 BACKWARD 逆向两种。
一个半格 semilattice，包含值集 V 和二元交汇运算 $\land$ 。
一个 V 到 V 的传递函数 F，其中必须包含可用于刻画边界条件的函数（即 ENTRY 和 EXIT 的常值函数）。

半格

半格 semilattice 定义为：满足下列条件的集合 V 和一个二元交汇运算 $\land$ ，对于 V 中的所有 x,y 和 z：

等幂： $x \land x = x$
可交换： $x \land y = y \land x$
结合律： $x \land (y \land z) = (x \land y) \land z$

半格包含一个顶元素 $⊤$ 满足对于 V 中所有的 x 有 $T \land x = x$ ；可能有一个底元素 $⊥$ 满足对于 V 中所有的 x $⊥ \land x = ⊥$ 。

偏序：设 $\leq$ 为 V 上的一个关系，如果对于 V 上所有的 x,y 和 z 都有：

自反 $x \leq x$
反对称：如果 $x \leq y$ 且 $y \leq x$ ，则有 $x = y$
传递：如果 $x \leq y$ 且 $y \leq z$ ，则有 $x \leq z$

二元组 $(V, \leq)$ 就被称为偏序集，定义 $x < y$ 当且仅当 $x \leq y$ 且 $x \neq = y$ 。

一个半格的交汇运算定义了值域上的一个偏序。对于 V 中所有的 x 和 y ，定义 $x \leq y$ 当且仅当 $x \land y = x$ .

最大下界。定义域元素 $x, y$ 的最大下届是满足下列条件的元素 $g$ ： $g \leq x$ 且 $g \leq y$ 且如果 $z$ 满足 $z \leq x, z \leq y$ 那么 $z \leq g$ 。
注意到 x 和 y 的交汇运算值就是它们的唯一最大下界。

并函数、最小上界和格
类似最大下界，也可以定义最小上界 $b$ ： $x \leq b, y \leq b$ 且如果 $z$ 满足 $x \leq z, y \leq z$ 都有 $b \leq z$ 。可以证明，若最小上界 b 存在，则唯一。
在一个真的格中有两个域上的运算，与我们讨论的 $\land$ 交汇运算对应，有并函数 $\lor$ 。并函数给出了两个元素的最小上界。
我们讨论的半格其实是交半格，另外也可以使用并半格。

格图：下图是一个例子。我们可以很方便地从该图上读出交汇值，此时 $x \land y$ 为最大下界。这个值总是最高的。

乘积格：假设 ${A, \land_{A}}$ 和 ${B, \land_{B}}$ 是两个半格，其乘积格定义如下：

乘积格的域为 $A \times B$
乘积格的交汇运算定义为，如果 $(a, b)$ 和 $(a^{'}, b^{'})$ 是乘积格域中的元素，那么 $(a, b) \land (a^{'}, b^{'}) = (a \land_{A} a^{'}, b \land_{B} b^{'})$
乘积格的偏序定义为 $(a, b) \leq (a^{'}, b^{'})$ 当且仅当 $a \leq_{a} a^{'}$ 且 $b \leq_{b} b^{'}$

上述定义的格的乘积，是一个满足结合律的运算，故上述定义可以扩展到多个格。

半格的高度：研究半格的高度，可以知道数据流分析算法收敛的信息。定义偏序集 $(V, \leq)$ 中的一个上升链是一个满足 $x_{1} < x_{2} < \dots < x_{n}$ 的序列，半格的高度即为所有上升链中 $<$ 关系个数的最大值。如果一个半格具有有穷的高度，就可以比较容易地证明其迭代数据流算法的收敛性。一些具有无穷多个值的格也可能具有有穷的高度。

传递函数

数据流框架中的传递函数族 $F : V \to V$ 具有下列性质：

存在单元函数 I，使得对于 V 中所有 x 都有 $I (x) = x$
对函数组合运算封闭。即对于 F 中的任意函数 f 和 g， $h (x) = g (f (x))$ 也在 F 中。

单调框架：一个数据流框架是单调的，当且仅当对于所有 V 中的 x 和 y 以及 F 中的 f， $x \leq y$ 蕴含 $f (x) \leq f (y)$ ，也可以等价定义为 $f (x \land y) \leq f (x) \land f (y)$
可分配的框架：在单调上遵循一个更强的条件（可分配条件），对于 V 中所有的 x 和 y 和 F 中的 f，有 $f (x \land y) = f (x) \land f (y)$

通用框架的迭代算法

类似前文中给出的三个例子，我们可以将该算法推广，使之处理各种数据流问题

常量传播

常量传播：把每次运行时总是得到相同常量值的表达式替换为该常量值。
不同之处：可能的数据流值集合是无界的；不是可分配的。

数据流值

其数据流值是一个乘积格，每个份量对应程序中的一个变量。
一个变量的格的元素包括：所有符合该变量类型的常量值，NAC(not-a-constant)，UNDEF（未定义）。
一个典型的半格如下所示

因此有 $U N D EF \land v = v, N A C \land v = N A C, c \land c = c$ ，对于两个不同的常量 $c_{1}, c_{2}$ 有 $c_{1} \land c_{2} = N A C$

传递函数

下面假设一个基本块只包含一个语句（包含多个的可以将对应的传递函数组合起来构造得到）。
函数集合 F 由一组传递函数组成，他们接收的输入是一个从程序变量到常量格中元素的映射，返回值也是这样一个映射。
记变量 v 在映射 m 中的值为 $m (v)$ 。

F 包含单元函数，返回与输入相同的映射。
F 包含对应于 ENTRY 节点的常值传递函数，对于任意输入的映射都返回 $m_{0}$ 。 $m_{0}$ 定义为，对任意 v 都有 $m_{0} (v) = U N D EF$ 。

对于一般的情况， $f_{s}$ 为语句 s 的传递函数，令 $m, m^{'}$ 表示满足 $m^{'} = f_{s} (m)$ 的两个数据流值，用 $m, m^{'}$ 的关系来描述 $f_{s}$ ：

如果 s 不是一个赋值语句，那么 $f_{s}$ 为单元函数。
如果 s 是一个对变量 $x$ 的赋值，那么对于所有的变量 $v \neq = x$ ， $m^{'} (v) = m (v)$ ，而对于 $m^{'} (x)$ 的定义为：a) 如果语句 s 的右部是一个常量 c ，那么 $m^{'} (x) = c$ ；b) 否则，如果右部形如 $y + z$ 那么：i) m(y)+m(z)，若两者都是常量值；ii) NAC，m(y) 或 m(z) 为 NAC ；iii) UNDEF，其他情况；c) s 的右部是其他表达式（如函数调用，指针赋值），那么 $m^{'} (x) = N A C$

常量传播框架是单调的，但不是可分配的。

部分冗余消除

目标：减少表达式求值的次数。
考虑流图中可能的执行顺序，移动对 x+y 求值的位置，并在必要时将求值结果保存在临时变量中。

冗余的来源：公共子表达式，循环不变表达式和部分冗余表达式。下图展示了三种冗余，以及其优化后的代码。

除非创建新的基本块来改变流图，否则我们不能消除各条路径上的所有冗余计算。下图是一个例子，其中我们可以选择在 B3-B4 这条路径上插入 B6 块，在其中添加 t=b+c 来消除 B4 中的冗余。像这种，从一个具有多个后继的节点，移动到另一个具有多个前驱的节点的边，定义为流图的关键边。

但这一复制也可能引入额外的开销。下图是一个例子，为了消除 B1-B2-B4-B6 中 B6 的冗余计算，需要额外复制一条路径出来。考虑到程序中路径数目与条件分支的指数关系，消除所有的冗余表达式可能会大大增加优化后代码的大小。

懒惰代码移动问题

期望优化后的程序具有以下性质

所有不复制代码就可以消除的表达式冗余计算均被消除。
优化后的程序不会执行原来程序中不执行的任何计算。
表达式的计算时刻应该尽量靠后。

完全冗余：在到达基本块 B 的所有了路径中，表达式 e 已被求值且运算分量在之后不变，那么 B 中的 e 就是冗余的。令 S 是那些令 B 中 e 冗余且包含 e 的基本块的集合，所有从 S 出发的边必然形成一个割集，即把这些边删除会使基本块 B 与入口点分离。
部分冗余：如果 e 仅是部分冗余，算法将在流图中放置 e 使其变成完全冗余。

表达式的预期执行

约束：保证优化后的程序不会执行额外的运算。
一个表达式的各个拷贝，其防止的程序点必须预期执行该表达式。即，若原本存在路径经过该程序点，但它原本不执行该表达式，那么这里就不应该放置该表达式。
预期执行限制了一个表达式最早可以被插入到何处。

考虑一个无环路径 $B_{1} \to B_{2} \to \dots \to B_{n}$ ，假设表达式 e 仅在 $B_{1}$ 和 $B_{n}$ 求值，且其运算分量在中间不变。那么 e 在基本块 $B_{i}$ 肉蔻没有被预期执行，当且仅当存在 $i \leq j < n$ 满足 $B_{j}$ 通向一条不适用 e 的值的执行路径。
基于此，我们可以创建一个关于 $B_{i - 1} \to B_{i}$ 的割集。如果 e 在 $B_{i}$ 入口可用或被预期执行，这个割集就使 e 在 $B_{n}$ 中冗余；如果 e 在 $B_{i}$ 入口处被预期执行却不可用，那么就需要在这条进入 $B_{i}$ 的边上放置一个拷贝。
流图中通常有多个割集满足该条件，而这里给出的则是一个在不引入冗余计算的条件下，尽可能使表达式的计算靠近对表达式使用的方案。

懒惰代码移动算法

该算法包含四个步骤。

这是四个数据流分析问题。

最终总的算法如下

流图中的循环

识别与针对性的处理循环很重要：程序花费大部分时间来执行循环。

支配节点

如果每一条从入口到节点 n 的路径都经过节点 d，则称 d 支配 dominate n，记为 d dom n。每个节点支配其自己。
根据支配的定义，可以构造一棵支配节点树，每个节点 d 支配且仅支配它在树上的后代节点，下面是一个例子，包含一个流图以及其支配节点树。

形成树的原因：每一个节点具有唯一的直接支配节点。

可以使用数据流算法来计算支配节点。

如果沿着入口节点，遵循一条无环路径到达点 n ，那么 n 的所有支配节点都会出现在路径中，且无论这条路径怎么走，这些支配节点的出现顺序不会变化。
dom 关系是传递且反对称的。

深度优先排序

使用深度优先搜索得到一颗深度优先生成树 DFST。
在这颗深度优先生成树上得到的后序遍历，其反过来就是深度优先排序。下面给出了深度优先排序的构造算法。

在构造 DFST 时，流图中的边可以被分为三大类：前进边（从节点 m 到 m 在树上中一个真后代节点的边，DIST 中的所有边均为前进边），后退边（从节点 m 到 m 在树中的某个祖先），交叉边（ m 和 n 在树中都不是对方的祖先）。
边 $m \to n$ 是一个后退边当且仅当 $df n [m] \geq df n [n]$ 。

回边和可归约性

回边：一条边 $a \to b$ ，它的头 b 支配了它的尾 a。对于任何流图，每条回边都是后退边，但不是每条后退边都是回边。
如果一个流图的任何深度优先搜索树中，所有后退边都是回边，则称该流图为可归约的。
如果我们删除流图中所有的回边后，得到的流图中带有环，则该图是不可归约的，反过来也成立。下面给出了一个不可归约的流图。

实践中出现的流图几乎都是可以规约的（使用 if-then-else, while-do, continue 和 break 语句）。即使使用了 goto，大部分情况下也是可归约的。

流图的深度

深度：给定深度优先生成树，则深度是各条无环路径上的，后退边数量的最大值。
直观上，深度小于等于流图中循环嵌套的深度。深度的定义独立于实际的 DFST。

自然循环

性质：

具有唯一的入口节点循环头。入口节点支配了循环中的所有节点。
必然存在一条进入循环头的回边。

给定回边 $n \to d$ ，定义该边的自然循环是 d 加上那些不经过 d 就能到达 n 的节点集合。 d 是这个循环的循环头。
如果只把自然循环当作循环，那么除非两个循环具有相同的循环头，否则他们要么是分裂的要么是嵌套的。
最内层循环：不包含其他循环的循环。

迭代数据流算法的收敛速度

该算法的最大迭代次数，可能是格的高度和流图节点数的乘积。但调整访问节点的顺序，可以减小迭代的次数，使结果快速收敛。
关注的性质：影响一个节点的重要事件，是否均可以通过一个无环的路径到达该点。到达定值、可用表达式和活跃变量这几个问题具有该性质，但常量传递则不具备。
对于无环路径，如果在迭代数据流算法中按照深度优先顺序遍历，那么迭代的轮次不会大于路径中从高编号基本快到低编号基本块的边的个数加一，而这些边恰好就是后退边。故，所需的轮次就是流图的深度加一。

基于区域的分析

建立在数据流分析上。一个基于区域的框架包含一个数据流值的半格和一个传递函数的半格。后一个半格必须包含一个交汇运算、一个组合运算符和一个闭包运算符。
关注那些包含环的路径可能改变数据流值的数据流问题。
该闭包运算符允许我们概括描述一个循环的运行效果。

区域

区域：流图中只具有单个入口节点的部分。类似代码中的块结构。

流图的一个区域使满足如下条件的一个节点集 N 和边集 E：

在 N 中存在一个节点 h 支配 N 中所有节点，称为头节点。
如果某个节点 m 能够不经过 h 到达 N 中的 n，那么 m 也在 N 中。
E 是所有位于 N 中的任意两节点之间控制流边的集合。

一个自然循环就是一个区域，但一个区域不一定包含一条回边，也不需要包含环。

可归约流图中的区域层次结构

先找出自然循环。把每个基本块本身看作一个区域（称为叶子节点），然后将自然循环从内到外排序。
归约方式为，将循环体替换为单一节点，对应原本与外界相连的边替换为与该单一节点相连的边，然后将自循环回边删掉。重复该过程。
各个自然循环最终都会归约为单一的节点，此时流图要么被归约为单一节点，要么还有多个节点但不包含循环。在后一种情况下，需要再为整个流图构造一个区域。
下图是一个例子

基于区域的分析技术

对于区域 R 以及每个在 R 中的子区域 R’，计算传递函数 $f_{R, I N [R^{'}]}$ 来概括在 R 内部从 R 的入口到 R’ 的入口的全部可能执行路径的执行效果。
对于 R 中的基本块 B，如果存在一条边从 B 到达 R 之外的基本块，则称 B 是 R 的一个出口基本块。
为 R 的每个出口基本块计算一个传递函数 $f_{R, O U T [B]}$ ，概括在 R 中从 R 的入口基本快到达 B 的出口处的所有可能路径的执行效果。
从单个基本块组成的区域开始，向上计算。对于单个基本块区域 B， $f_{B, I N [B]}$ 就是单元函数，而 $f_{B, O U T [B]}$ 则是基本块 B 本身的传递函数。
对于更大的区域 R 则有：
如果 R 是一个体区域，那么属于 R 的边构成了 R 子区域的一个无环图，按照拓扑顺序计算传递函数。
如果 R 是一个循环区域，那么我们只需要考虑到达 R 头节点回边的效果。

对于数据流值，则是从层次结构的顶部 $R_{n}$ 开始。对于其内的区域，计算其入口处的数据流值， $f_{R_{n}, I N [R]} (I N [ENTR Y])$ 。重复该过程，直到层次结构中的叶子基本块也被计算为止。

必要假设

组合： $f_{2} \circ f_{1}$ 封闭。

交汇运算：传递函数本身就是具有交汇运算 $\land_{f}$ 的半格的值域。定义 $f_{1} \land f_{2}$ 为 $(f_{1} \land_{f} f_{2}) (x) = f_{1} (x) \land f_{2} (x)$ ，其中 $\land$ 是数据流的交汇运算。

闭包运算：如果 f 表示一个环的传递函数，那么 $f^{n}$ 表示沿着这个环执行 n 次的效果。定义 $f^{*}$ 为这样的闭包 $f^{*} = \land_{n \geq 0} f^{n}$ ，即假设这个环被执行 0 到多次。注意到 $f^{0}$ 必须是单元传递函数。

处理不可归约流图

节点分割技术：首先尽可能按照自然循环来构造区域。如果流图是不可归约的，那么必然会发现，得到的流图包含环但没有回边。
选取一个具有多个前驱，且不是整个流图头节点的区域 R。如果 R 有 k 个前驱，那么建立 k 个对应于 R 的整个流图的拷贝，并将 R 的头节点的 k 个前驱分别连到对应的拷贝上。
这样节点分割后，在寻找新的回边并构造出这些回边的区域后，区域的个数至少减少了一。
新的流图可能仍然是不可归约的，但可以不断交替进行分割和寻找新自然循环并归约坍缩两个步骤。在最坏的情况下，最后得到的基本快个数和原本的基本块个数成指数关系。
下面给出了一个例子

符号分析

用符号表示来跟踪程序中变量的值。将变量的值表示为关于输入变量及其它变量的表达式。这些值称为参考变量。
下图给出了一个例子，这里我们使用 x 作为唯一的参考变量，此时 y 和 z 的值都与 x 相关。我们据此能确定第 4 和第 5 行的两个数组位置赋值互不干扰，可以并行。

仿射表达式

仿射表达式：一个关于 $v_{1}, v_{2}, \dots, v_{n}$ 的表达式可以表示为 $c_{0} + c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} v_{n}$ ，其中 $c_{i}$ 均为常量。
归纳变量：如果一个变量在某个程序点的上的值表示为 $c_{1} i + c_{0}$ ，其中 i 为包含该程序点的最内层循环的迭代次数，此时程该变量为归纳变量。
其他参考变量：比如在 $a = f (); b = a + 10; c = a + 11;$ 中 a 可以作为后续语句的参考变量。

下面展示了一个例子，在该例子中，令 $f = i + 99, g = j + 9$ 从而用 i 和 j 代替 f 和 g，得到 i 和 j 两个循环变量。可以发现 a,b,c,d 都是归纳变量，可以找到用参考变量 i 和 j 表示这些变量的仿射表达式。

数据流问题的公式化

寻找关于某些参考变量的仿射表达式。参考变量包括：1) 循环迭代计数的变量；2) 在必要时存放区域入口处的值的参考变量。

数据流值：符号化映射。
将程序中的变量映射到一个仿射函数，或者表示非仿射表达式的特殊符号 NAA 。
使用 $m_{N AA}$ 表示该半格的底元素，它将所有变量都映射为 NAA 。
下表展示了上述程序的符号化映射：

单个语句的传递函数：
一个语句 s 的传递函数 $f_{s}$ ，定义为：
如果 s 不是一个赋值语句，则 $f_{s}$ 是单元函数。
如果 s 是一个对 x 赋值的语句，那么 $f_{s} (m) (x) =$

$m (v)$ ，若对于所有的变量 $v \neq = x$
$c_{0} + c_{1} m (y) + c_{2} m (z)$ ，若 x 被赋值为 $c_{0} + c_{1} y + c_{2} z$ ，当 ( $c_{1} = 0$ 或 $m (y) \neq = N AA$ ) 且 ( $c_{2} = 0$ 或 $m (z) \neq = N AA$ )，即 y 和 z 均必须满足，要么其系数为 0 ，要么它本身不是一个 NAA。
NAA，对于其他所有情况。

值得指出的是， $c_{0} + c_{1} m (y) + c_{2} m (z)$ 是表示所有可能出现在对 x 赋值的语句的右部，关于 y 和 z 的各种表达式。
m(x) 实际上表示的是变量 x 在入口处可能具有的任何值。

传递函数的组合：
令 $f_{1}, f_{2}$ 是两个传递函数，有：

如果 $f_{2} (m) (v) = N AA$ ，那么 $(f_{2} \circ f_{1}) (m) (v) = N AA$
如果 $f_{2} (m) (v) = c_{0} + \sum_{i} c_{i} m (v_{i})$ ，那么 $f_{2} \circ f_{1} (m) (v) =$
i) NAA，如果对于某个 $i \neq = 0, c_{i} \neq = 0, f_{1} (m) (v_{i}) = N AA$
ii) $c_{0} + \sum_{i} c_{i} f_{1} (m) (v_{i})$ ，其他情况。

下表给出了上述程序例子的传递函数

数据流问题的解决办法：
定义 $I N_{i, j} [B_{3}], O U T_{i, j} [B_{3}]$ 表示内层循环的第 j 次迭代和外层循环第 i 次迭代时，基本块 $B_{3}$ 的输入和输出流值。
其他的块则直接定义 $I N_{i} [B_{k}], O U T_{i} [B_{k}]$ 为外层循环在第 i 次迭代时的数据流值。下图现实了符号化映射满足传递函数给出的约束

基于区域的符号化分析

包含自底向上和自顶向下的两个部分。

交汇运算，除非两个函数把一个变量映射为同一个不是 NAA 的值，否则这个变量的值就是 NAA。有 $(f_{1} \land f_{2}) (m) (v) =$

$f_{1} (m) (v)$ 若 $f_{1} (m) (v) = f_{2} (m) (v)$
NAA，其他情况

函数组合：关注变量表示为关于循环下标的放射函数。记迭代一次用传递函数 f 概括，则执行 i 次的效果为 $f^{i}$ 。根据程序中变量的类型分别处理（ $f^{0} = I$ 固定为单元函数）：

如果 $f (m) (x) = m (x) + c$ ，其中 c 为常数，那么 $f^{i} (m) (x) = m (x) + c i$ 。此时称 x 为循环的一个基本归纳变量。
如果 $f (m) (x) = m (x)$ ，那么 $f^{i} (m) (x) = m (x)$ 。此时称 x 微循环的符号化常量。
如果 $f (m) (x) = c_{0} + c_{1} m (x_{1}) + \dots + c_{n} m (x_{n})$ ，其中每个 $x_{k}$ 要么是基本归纳变量要么是符号化常量，那么 $f^{i} (m) (x) = c_{0} + c_{1} f^{i} (m) (x_{1}) + \dots + c_{n} f^{i} (m) (x_{n})$ 。此时 x 不是基本归纳变量，但依然是归纳变量。
其他情况下 $f^{i} (m) (x) = N AA$ 。

当迭代次数未知时，只有循环不变量的值可以用仿射函数表示，即 $f^{*} (m) (v) =$

$m (v)$ ，若 $f (m) (v) = m (v)$
NAA，其他情况

数学分析

探索

第9章机器无关优化

优化的主要来源

数据流分析简介