静态程序分析chapter5 - 常量传播分析(Costant Propagation Analysis)

四、

数据流分析之常量传播(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 不是一个常量值。这需要分情况来讨论。

      学习了格理论之后,数据流分析框架常被描述为下面这样:
静态程序分析chapter5 - 常量传播分析(Costant Propagation Analysis)
      上图和之前讲的数据流分析步骤都能对应上,只不过是更加专业点而已。

用途

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

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。

静态程序分析chapter5 - 常量传播分析(Costant Propagation Analysis)

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 的精度要更高一些。
静态程序分析chapter5 - 常量传播分析(Costant Propagation Analysis)

示例和算法实现

      暂无

Java代码测试

      暂无

总结

      未完待续~

上一篇:[论文理解] An Analysis of Scale Invariance in Object Detection – SNIP


下一篇:You should consider upgrading via the 'pip install --upgrade pip' command