考虑我们的小型语言TIP,其中允许函数作为值。对于计算得到的函数调用 E(E1,...,En),从语法中我们无法直接看出可能会被调用的函数。一个粗糙但正确的控制流图可以通过假设任何具有正确数量参数的函数都可以被调用来获得。然而,通过执行控制流分析,我们可以做得更好。

    对于所有程序中的函数名X的集合,我们的格是这个集合的幂集合;偏序关系是子集合包含。对于语法树节点v,我们引入一个约束变量[[v]] 表示v节点处,可能指向的函数的集合。那么约束规则如下:
  1. 对于一个名字为f的函数:

    $f \in [[f]]$

  2. 对于赋值运算X=E:

    $[[E]] \subseteq [[X]]$

  3. 对于函数调用 E(E1,E2,…En),对于每一个函数f的定义,a表示函数的形参、E‘表示返回表达式:(也就是说,如果想E的调用是函数f,那么实参E1必须是形参a1的子集合。设想如果不是,那么这个程序就有问题!同理,对于返回值,则反过来即可,形式返回值只要是实际的一种即可。)

Untitled

    如果我们限制分析范围在可类型化的程序上,并且仅为那些函数 f 生成约束,以使函数调用在类型上是正确的,那么我们可以得到更精确的分析结果。我们还可以选择为直接以名称给出要调用的函数(就像在我们将头等函数添加到TIP之前的简单函数调用中一样)引入一个更简单的规则。对于直接函数调用 f (E1,...,En),其中 f 是一个带有参数 a1, ..., an  和返回表达式 E‘ 的函数,我们可以有以下(无条件的)约束:

Untitled

    通过控制流分析的结果,我们可以构建一个类似第8.1章中的控制流图(CFG),但是在调用点和根据控制流分析确定的所有可能目标函数之间有边。考虑以下示例程序:
inc(i) {return i+1;}
dec(j) {return j-1;}
ide(k) {return k;}
foo(n,f) { // f是一个函数调用
	var r;
	if (n==0) { f = ide; }
	r = f(n);
	return r;
}
main() {
	var x,y;
	x = input;
	if (x>0) { y = foo(x,inc); } else { y = foo(x,dec); }
	return y;
}

可以生成如下约束:

Untitled

计算之后,非空的结果:

Untitled

我们可以得到如下控制流图:

Untitled