Question

3.1 相关概念

• 近似方案 1：忽略掉程序的条件判断，认为所有的分析都有可能到达
  • 程序可以看成是**状态（数据） 和 状态之间的转移（控制）**两部分，因为状态转移的条件都被忽略了，核心分析的部分是状态数据在转移过程中的变化，所以叫做数据流分析。
• 近似方案 2：不在路径末尾做合并，在控制流汇合的所有位置提前做合并

数据流分析要保证 Safe-approximation，即：

• may analysis: over-approximation
• must analysis: under-approximation

总之，不同的数据流分析有不同的数据抽象方法（应用不同），有不同的 Safe-approximation 策略，有不同的转移函数与控制流汇聚方式。

3.1.1 输入输出状态

• 每一条 IR 的执行，都会使状态从 输入状态 变成新的 输出状态
• 输入/输出状态与语句前/后的 program point 相关联。

在数据流分析中，我们会把每一个 program point 关联一个数据流值，代表在该点中可观察到的抽象的程序状态。数据流分析的目的是为所有语句的输入输出找到一组，基于控制流和转换函数的，安全的近似约束的解决方案。

3.1.2 转移函数

分析数据流有前向和后向两种：

3.1.2 控制流约束

每条语句 s 都会使程序状态发生改变。B 的输出自然是其输入在经过多次转换后得到的状态。而 B 的输入要根据数据流分析的需求，对其前驱应用合适的 meet operator 进行处理。后向分析时亦然。

3.2 应用

3.2.1 到达定值分析：Reaching Definitions Analysis

基本概念

假定 x 有定值 d ( definition )，如果存在一个路径，从紧随 d 的点到达某点 p，并且此路径上面没有 x 的其他定值点，则称 x 的定值 d 到达 ( reaching ) p。

如果在这条路径上有对 x 的其它定值，我们说变量 x 的这个定值 d 被杀死 ( killed ) 了

到达定值可以用来分析未定义的变量。例如，我们在程序入口为各变量引入一个 dummy 定值。当程序出口的某变量定值依然为 dummy，则我们可以认为该变量未被定义。

对于一条赋值语句 D: v = x op y ，该语句生成了 v 的一个定值 D，并杀死程序中其它对变量 v 定义的定值。

理解到达定值分析

数据流值：

• 程序中所有变量的定值。
• 可以用一个 bit vector 来定义，有多少个赋值语句，就有多少个位。

D 即 Definition，可以表示为： D：v = x op y

一个 D 可以视为一行三地址码，做了两件事：

• 生成了一个定义 D
• 在保持其他传入程序不受影响的同时，kill 了程序中其它对变量 v 的定义

转移方程与控制流：

其中 U 表示 union，结合前文使用 bit 字节表示的 D，可以知道，IN[B] 的输入等于 OUT[P1] 并 OUT[P2]，意味着只要存在一条路径可以 reach，那么就算作可以 reach。

达定值分析的算法表示

这是一个经典的迭代算法：

• 首先让所有 BB 和入口的 OUT 为空。因为你不知道 BB 中有哪些定值被生成。
• 当任意 OUT 发生变化，则分析出的定值可能需要继续往下流动，所需要修改各 BB 的 IN 和 OUT。
• 先处理 IN，然后再根据转移完成更新 OUT。
• 在 gen U (IN - kill) 中，kill 与 gen 相关的 bit 不会因为 IN 的改变而发生改变，而其它 bit 又是通过对前驱 OUT 取并得到的，因此其它 bit 不会发生 0 -> 1 的情况。所以，OUT 是不断增长的，而且有上界，因此算法最后必然会停止。
• 因为 OUT 没有变化，不会导致任何的 IN 发生变化，因此 OUT 不变可以作为终止条件。我们称之为程序到达了不动点（Fixed Point）

该算法为什么会终止？OUT[S] never shrinks 且状态是有限的（到达不动点）

3.2.2 活跃变量分析：Live Variables Analysis

基本概念

给定程序中的某条语句 s 和变量 v，如果在 s 执行前保存在 v 中的值在后续执行中还会被读取，就称之为活跃变量。

• 变量 x 在程序点 p 上的值是否会在某条从 p 出发的路径中使用
• 变量 x 在 p 上活跃，当且仅存在一条从 p 开始的路径，该路径的末端使用了 x，且路径上没有对 x 进行覆盖。
• 隐藏了这样一个含义：在被使用前，v 没有被重新定义过，即没有被 kill 过。

这个算法可以用于寄存器分配，当一个变量不会再被使用，那么此变量就可以从寄存器中腾空，用于新值的存储。

活跃变量中分析

数据流值

• 程序中的所有变量
• 依然可以用 bit vector 来表示，每个 bit 代表一个变量

转移方程和控制流处理

不同于 Reaching Definitions 的前向传播分析，Live Variables Analysis 使用反向传播进行分析效果更好。如果从后往前搜索，只要在某程序点处找到一个变量 v 的使用，就证明在此之前任意可达此点的、定义了 v 的程序点处，v 都是 live 的；而如果使用前向传播的算法，每到一个程序点都要正向搜索一遍后方的路径才能确认变量在此处是否 live，虽然也能进行分析，但是效率较低。

• 一个基本块内，若 v = exp, 则 def v。若 exp = exp op v，那么 use v。一个变量要么是 use，要么是 def，根据 def 和 use 的先后顺序来决定。
• 考虑基本块 B 及其后继 S。若 S 中，变量 v 被使用，那么我们就把 v 放到 S 的 IN 中，交给 B 来分析。
• 因此对于活跃变量分析，其控制流处理是 OUT[B] = IN[S]。
• 在一个块中，若变量 v 被使用，那么我们需要添加到我们的 IN 里。而如果 v 被定义，那么在其之上的语句中，v 都是一个非活跃变量，因为没有语句再需要使用它。
• 因此对于转移方程，IN 是从 OUT 中删去重新定值的变量，然后并上使用过的变量。需要注意，如果同一个块中，变量 v 的 def 先于 use ，那么实际上效果和没有 use 是一样的。

算法表示

3.2.3 可用表达式分析：Available Expression Analysis

基本概念

x + y 在 p 点可用的条件：从流图入口结点到达 p 的每条路径都对 x + y 求了值，且在最后一次求值之后再没有对 x 或 y 赋值。

可用表达式可以用于全局公共子表达式的计算。也就是说，如果一个表达式上次计算的值到这次仍然可用，我们就能直接利用其中值，而不用进行再次的计算。

可用表达式分析分析

数据流值

• 程序中的所有表达式
• bit vector 中，一个 bit 就是一个表达式

转换函数与控制流处理

• B，表达式都应该已经计算，才能将其视为可用表达式，因此这是一个 must analysis 。
• 注意到图中，两条不同的路径可能会导致表达式的结果最终不一致。但是我们只关心它的值能不能够再被重复利用，因此可以认为表达式可用。
• v = x op y ，则 gen x op y 。当 x = a op b ，则任何包含 x 的表达式都被 kill 掉。若 gen 和 kill 同时存在，那么以最后一个操作为准。
• 转移方程很好理解，和到达定值差不多。但是，由于我们是 must analysis，因此控制流处理是取交集，而非到达定值那样取并集。

算法表示

• 注意此时的初始化：一开始确实无任何表达式可用，因此 OUT[entry] 被初始化为空集是自然的。但是，其它基本块的 OUT 被初始化为全集，这是因为当 CFG 存在环时，一个空的初始化值，会让取交集阶段直接把第一次迭代的 IN 设置成 0，无法进行正确的判定了。
• 如果一个表达式从来都不可用，那么 OUT[entry] 的全 0 值会通过交操作将其置为 0，因此不用担心初始化为全 1 会否导致算法不正确。

3.2.4 常量传播：Constant Propagation

基本概念

在 程序点 p 处给定一个 变量 x ，判断 x 在程序点 p 处是否 一定 指向一个常量。

这是一个类似 must 分析，因为必须所有到点 p 的 path 都是这个常量才行；但有和传统的不大一样。在 CFG 中每个节点的输出包括一个对 (x, v)，其中 x 是变量而 v 是在该节点后 x 指向的具体值。

常量传播分析

转换函数：

OUT[s] = gen U (IN[s] - {(x, _)})

3.4 Work list 算法

最后再提一下 Worklist 算法，这是对之前数据流分析迭代算法一种完全的改进，不影响精度的情况下，有更高的效率。

不同于普通迭代算法，一个 OUT 变了所有的都要跑一遍，worklist 的效率高很多，因为 gen 和 kill 是不会变的，OUT 变化只取决于 IN 的变化，因此先把所有节点放进去，然后每个变化的 OUT 都把后继放进去，来回的跑直到结束。

3.5 总结