« 上一篇下一篇 »

一个指针和引用的模型

因为我们进行的是上下文无关的分析,所以只需要断定一个给定的变量u能够指向一个给定的堆对象h,不需要指出在程序中的什么地方u可能指向h,或者在什么样的上下文中u可以指向h请注意,变量可以通过它的全名来命名。在Java中,这个全名包括了模块、类、方法和方法中的块以及变量名本身。因此,我们可以区分标识符相同的多个变量。
假设我们的语言可以用下列方式来表示和操作引用:

1)某些程序变量的类型为“指向T的指针”或“指向r的引用”,其中T是一个类型。这些变量可以是静态的,也可能位于运行时刻栈中。我们简单地称它们为变量。

2)有一个对象的堆。所有变量都指向堆中的对象,不指向其他变量。这些对象称为堆对象 (heap object)。

3)一个堆对象可以有多个字段(field), —个字段的值可以是指向一个堆对象的引用(但是不能指向一个变量)。

可以使用这个结构很好地对Java建模,我们将在例子中使用Java的语法。请注意,在对C语言建模时这个结构的效果就不太好,因为在C语言中指针变量可以指向其他指针变量。而且,从原则上讲,任何C语言的值都可以被强制转化成为一个指针。

因为我们进行的是上下文无关的分析,所以只需要断定一个给定的变量u能够指向一个给定的堆对象h,不需要指出在程序中的什么地方u可能指向h,或者在什么样的上下文中u可以指向h请注意,变量可以通过它的全名来命名。在Java中,这个全名包括了模块、类、方法和方法中的块以及变量名本身。因此,我们可以区分标识符相同的多个变量。

堆对象没有名字。因为可能动态创建出无限多个对象,所以人们经常使用近似方式给对象命名。一个惯例是使用创建对象的语句来指定对象。因为一个语句可以被执行多次,每次都可以创建一个新的对象,因此一个形如“u可以指向h”的断言实际上是说“u可以指向标号为h的语句创建的一个或者多个对象。”

分析的目标是确定各个变量以及每个堆对象的各字段可能指向哪些对象。我们把这个分析称为指针指向分析(points-to analysis)。如果两个指针的指向集合相交,那么它们互为别名。这里 我们描述的是一个基于包含(inclusion-based)的分析技术。也就是说,一个形如v=w的语句使得变量u指向w所指向的所有对象,但是反过来不成立。虽然这个方法看起来显而易见,但我们还 可以使用其他的方法来定义指向分析。比如,我们可以定义一个基于等价关系(equivalence-based) 的分析,使得形如v=w的语句把变量u和w;转变成一个等价类。等价类中的变量指向同样的对象。虽然这种表示法不能很好地估算别名问题,但它仍然为哪些变量指向同一类对象的问题提供了一个快速的求解方法,而且效果通常很好。

« 上一篇下一篇 »