流敏感的结果同之前不同,是为了捕获更加精确的结果。那么相比较于之前的set作为结果集合,此时要流敏感,也就是要引入先后关系,也就是时序关系,那么有向图是一个很好地扩展。
即使没有记录,我们也可以通过TIP的编写程序生成有趣的堆结构。一个非平凡的堆结构的例子如下:
其中xyz是三个程序变量。我们将试图回答有关程序变量中包含的结构是否不相交的问题。在上面的例子中,x 和 y 相交,而 y 和 z 是不相交的。这样的信息可能是有用的,例如,在优化编译器中自动并行化执行。对于这样的分析,无流敏感的推理有时过于不精确。然而,我们可以创建Andersen分析的流敏感变体。
我们使用一个指向图(points-to graphs)的格,这是一个有向图,其中节点是给定程序的抽象单元,边对应可能的指针。指向图通过包含它们的边集进行排序。因此,bottom是没有边的图,而 top是完全连接的图。形式化的来说,我们抽象状态的格定义如下:
偏序关机就是子集的包含关系。对于程序中的每一个CFG节点v,我们引入一个约束变量[[v]],表示当前节点v处的指向图,存储的是所有当前的指向关系。对于与指针操作相关的各种指针操作,我们的约束规则如下:
对于其他的节点,我们就是朴素的做[[v]] = JOIN(v),特别的这些规则里面的辅助函数定义如下:
注意,对于store操作,我们采取weak update的策略,也就是做合并操作。
例子: