Points-to analysis和BDD

前几天看了一篇文章《Points-to analysis using BDD》。
Points-to analysis：指向分析。这个分析的目的很简单，就是分析出程序中任何两个指针或引用变量是否可能指向同一个主存的位置。该分析在优化编译器中还是很有用的。在某两个变量可以确定无关的情况下，编译器常常可以进行更加激进的优化。同时，在自动向量化，自动并行化的方法中，也需要指向分析的信息。
传统上，指向分析有两种方法，一种是基于等价关系的（这个没有看它是怎么做的），而另一种是比较精确的基于子集合的方法。该方法是控制流和上下文不敏感的。
基于子集的执行分析的算法思想如下：
首先，根据程序本身，得到一个初始的指向集合，例如对于Java而言，如果有语句a=new A()；那么，变量a就指向这行所分配的内存。第二，根据语言的属性，给出一些规则，例如，如果有赋值语句a=b，那么所有b可能指向的对象，a也可能指向。第三，在整个程序的范围内不断地迭代应用规则，直到达到了不动点。
这个算法的平凡实现虽然简单，但效率很低，并且很难处理大一些的程序（指向信息的集合可能含有几百万个元素），常常会由于out of memory而失败。所以很多人提出了很多方法来压缩集合的表示，同时又不会造成过大的时间复杂度。
这篇文章实际上也是在想办法压缩集合的表示，作者使用了ROBDD（Reduced Ordered Binary Decision Diagram）来表示集合。这种集合的表示方法可以比较有效的处理较大的集合，同时高效的支持集合操作。BDD有专门的库来实现，如果使用一个Buddy的库，那么points-to算法的实现完全可以写在一张纸上。并且很清晰简明。大概来数，所有的迭代操作都是用集合上的操作来表示，每一步操作不是针对一个变量，而是针对整个集合。
在此基础之上，作者进一步提出了优化性能的方法：选择合适的变量顺序（非常重要，变量顺序不合适，得到的算法的复杂度非常）；增量式迭代。在这些处理之后，作者在一些Java程序上给出了实验结果。这篇文章中提出的算法在时间复杂度上和手工优化的代码很接近（这个代码基本上是没有使用BDD的最好的points-to代码之一），在较大的程序上甚至更好；而空间复杂度则远远优于手工优化的代码。
这篇文章，使得在大型的、实际中的程序上使用points-to分析成为可能。它提出的增量式迭代还可能用于其他数据流分析的算法中。