四、

数据流分析之常量传播（Constant Propagation）

概述

      Constant Propagation：Given a variable x at program point p, determine whether x is guaranteed to hold a constant value at p. 比如在 p 处之前的一条语句是 x = 2，那就认为在 p 处 x 是一个常量值。反过来若在 p 处之前的一条语句为 x = y，那在 p 处 x 是否为一个常量值不能确定。

      要判断在每一个程序点处变量是否为一个常量值，按照之前的分析框架能够一步步得到：首先，应该采用位向量对所有变量是否为常量值进行抽象，应该采用前向分析，应该采用 must analysis（从 guaranteed 能够看出，这是一个 1 op 0 = 0 的故事），并且迭代算法在边界处的初始值应该为 ⊥。其次，除边界处外别的语句的初始值应为 T ，控制流处理应该采用 与操作。最后，转换函数的分析也可以采用前面的 Gen/Kill 框架，至此分析结束。
      上述分析流程具体可见博客：https://blog.csdn.net/Little_ant_/article/details/118732952

      但是这个问题又有点不太一样，它会稍微复杂一点。比如在两条路径汇聚的情况下，一条路径上 x = 1，另一条路径上 x = 2，因为1和2不相等，所以在汇聚点处 x 不是一个常量值。这需要分情况来讨论。

      学习了格理论之后，数据流分析框架常被描述为下面这样：

      上图和之前讲的数据流分析步骤都能对应上，只不过是更加专业点而已。

用途

      为了用常量值替换掉变量来优化程序。对于简单的程序如下：

int a = 2 ;
int b;
b = a + 4;
printf("%d\n",b);

      在编译时采用常量传播优化之后：

printf("%d\n",6);

D

      从 CPA 的语义上可以得出应该采用前向分析。

L

抽象

      在这里不采用位向量对变量是否为常量值进行抽象，因为当变量为一个常量值的话，为了用常量值替换掉变量来优化程序，需要存储每一个变量的常量值。因此令 CFG 中每一个节点的 OUT 中包含一系列的元素对（x ，v），其中 x 为变量，v 为 x 的值。这里和之前抽象不一样的地方在于从位向量变为元素对向量。

      而每一个变量的值现在有三种情况：未初始化（UNDEF）、常量（c）和非常量（NAC）。其中 NAC 作为 ⊥，UNDEF 作为 T。对于 must analysis 而言，初始化每一个 OUT 为 T，即将每一个元素对中变量的值都置为 UNDEF，此时是不安全的或者说是不正确的。而当每一个元素对中变量的值都为 NAC时，对于 CPA 来说就不会做优化了，因此也不会出错了，这是一个正确但是无用的结果。这对应于数据流分析的特点 unsafe → safe。

控制流处理

      之前抽象的结果只有两种情况 0 和 1，所以在控制流处理时 meet 采用 与 操作。现在抽象的结果有三种情况，所以控制流处理时 meet 操作需要分类讨论：

      NAC ⊓ v = NAC；非常量和其他任意值 meet 的结果为非常量。
      UNDEF ⊓ v = v；从逻辑上来看，一条路径为 UNDEF，另一条路径为 v，在汇聚点处取二者之间的哪一个都不太好，但是因为 UNDEF 不在常量传播的分析范围之内，所以 meet 之后的结果为 v 。从操作符本身来看，⊓ 表示取最大下界，而 UNDEF 和 v 的最大下界为 v。
       c ⊓ v 的结果需要讨论变量 v 的值，若 v 的值和 c 相等，则 c ⊓ v = c。若 v 的值和 c 不相等，则 c ⊓ v = NAC。

F

       转换函数仍然通过对于一个语句的分析，得到一般性的结论。比如对于一个语句 s：x = … ，它的转换函数需要 kill 掉原来的元素对中 x 对应的值，然后根据具体的语句来执行 gen 给 x 生成一个新的值，这样就得到了 OUT[s]。

      转换函数 F 表示为：OUT[s] = gen ∪ (IN[s] – {(x, _)})

       令元素对中 x 对应的值用 val(x) 来表示，对语句 s 分类讨论：

      1，s: x = c; //c为常量      那么生成新的元素对 gen = { (x,c) }

      2，s: x = y;       那么生成新的元素对 gen = { (x, val(y)) }

      3，s: x = y op z;       那么生成新的元素对 gen = { (x, f(y,z)) }
      其中 f(y,z) 的结果：在当 val(y) 和 val(z) 都是常量时，f(y,z) = val(y) op val(z)。
                                    在当 val(y) 或 val(z) 是非常量 (NAC) 时，f(y,z) = NAC。
                                    在当 val(y) 和 val(z) 一个为常量，另一个为 UNDEF 时，或者两个都是 UNDEF时，f(y,z) = UNDEF。这里指的是常量和一个未定义的变量执行某种操作，其结果自然是未定义。据说：如果令一个常量和 UNDEF 操作的结果为常量，那么转换函数 F 就不再是单调的啦。

      如果语句 s 不是一个赋值语句，那么 OUT[s] = IN[s] 。

常量传播不是可分配的

      不是可分配的意味着迭代算法的精度没有 MOP 高。在下图中，迭代算法得到的结果为 NAC ，MOP 得到的结果为常量 10，参照 must analysis 的那张图片，可得，MOP 的精度要更高一些。

示例和算法实现

      暂无

Java代码测试

      暂无

总结

      未完待续~