流敏感的结果同之前不同,是为了捕获更加精确的结果。那么相比较于之前的set作为结果集合,此时要流敏感,也就是要引入先后关系,也就是时序关系,那么有向图是一个很好地扩展。

    即使没有记录,我们也可以通过TIP的编写程序生成有趣的堆结构。一个非平凡的堆结构的例子如下:

Untitled

其中xyz是三个程序变量。我们将试图回答有关程序变量中包含的结构是否不相交的问题。在上面的例子中,x 和 y 相交,而 y 和 z 是不相交的。这样的信息可能是有用的,例如,在优化编译器中自动并行化执行。对于这样的分析,无流敏感的推理有时过于不精确。然而,我们可以创建Andersen分析的流敏感变体。

    我们使用一个指向图(points-to graphs)的格,这是一个有向图,其中节点是给定程序的抽象单元,边对应可能的指针。指向图通过包含它们的边集进行排序。因此,bottom是没有边的图,而 top是完全连接的图。形式化的来说,我们抽象状态的格定义如下:

Untitled

偏序关机就是子集的包含关系。对于程序中的每一个CFG节点v,我们引入一个约束变量[[v]],表示当前节点v处的指向图,存储的是所有当前的指向关系。对于与指针操作相关的各种指针操作,我们的约束规则如下:

  1. 申请内存:合并v之前的结果,移除X,增加一个指向关系(X,alloc -i),表示X指向alloc-i
  2. 取地址:合并v之前的结果,移除X1,增加一个指向关系(X1, X2),表示X1指向X2
  3. 赋值操作:合并v之前的结果,移除X1,得到R;同时对于所有R里面,X2指向的结果t,都增加一个(X1,t),表示此时X1也指向t
  4. 取值并赋值-load:合并v之前的结果,移除X1,得到R;对于X2所有指向的s,如果s还指向t,那么增加一个(X1,t)。因为是指向图,所以*X2与X等价,所以就是s与X等价,那么相当于X1=s
  5. 赋值写入-store:合并v之前的结果,得到R(注意这里面不用移除之前的X1,因为是weak update);对于X1所有指向的s,X2指向的t,增加一个(s,t)。这里相当于*X1 与s等价,s=X2
  6. 赋值为null,那么就是移除

Untitled

对于其他的节点,我们就是朴素的做[[v]] = JOIN(v),特别的这些规则里面的辅助函数定义如下:

Untitled

Untitled

注意,对于store操作,我们采取weak update的策略,也就是做合并操作。

例子: