我们使用包含函数的TIP语言的子集,但仍然忽略指针和函数作为值的情况。正如我们将看到,获得整个程序的控制流图(CFG)变得非常简单。当添加函数值时,情况变得更加复杂,我们将在第10章中讨论这个问题。
首先,我们像往常一样构建所有单个函数主体的控制流图(CFG)。然后,我们需要将它们正确地连接在一起以反映函数调用。我们需要处理参数传递、返回值和跨函数调用的局部变量值。为了简单起见,我们假设所有函数调用都是与赋值操作相关联的:
$$ X = f(E_1,\dots,E\_n); $$
在控制流图(CFG)中,我们使用两个节点来表示每个函数调用语句:一个调用节点(call node)表示从调用者到函数f的入口的连接,以及一个调用后节点(after-call node),在从函数f的出口返回后继续执行的节点:
接着,我们处理return语句:“return E;”,将这个E 赋值给一个特殊的叫做“result”的变量
在2.5节中,我们已经明确说明一个CFG有一个唯一的入口节点和一个唯一的出节点,因此这样的结构一定能构建出。
那么我们接可以讲函数的调用者caller和被调用的函数callee连接到一起:
在调用节点和调用后节点之间的连接由一条特殊的边表示(不在succ和pred中),我们需要它来传播调用者的局部变量的抽象值。
有了这个函数间的控制流图(CFG),我们可以应用单调框架(monotone framework)。在接下来的章节中,将给出一些过程间分析的示例。
对于4.1节和5.1节我们描述的过程内符号分析,对于值的符号抽象描述是Sign格:
抽象状态则是一个映射格$States = Vars \rightarrow Sign$。对于任意的程序节点,抽象状态仅仅提供给了在当时范围的变量的情况;其他所有的变量则认为是bottom。
为了使符号分析成为过程间分析,我们需要定义约束对函数调用和返回时的信息流进行建模。首先,我们将调用节点视为仅收集来自它的前继的信息的朴素操作。因此,对于函数调用的节点v,我们定义$[[v]] = JOIN(v)$。对于一个函数$f(b_1,\\dots,b_n)$ 的入口节点$v$,我们需要考虑所有调用这个函数f的调用点集合$pred(v)$,并且对传递的参数建模如下:
$$ [[v]]=\bigsqcup_{w \in ~ pred(v)}~~s_w $$
其中:
这里面,$\bot$表示映射 $Vars\rightarrow~Sign$的bottom元素,也就是将所有变量映射到Sign格的bottom;$E_i^w$表示对于w这个调用点的第i个参数。如4.4节所有讨论,约束不仅仅可以用等式表示,也可以用不等式。如上约束可以从新定义如下,其中v是一个函数的入口点,w是一个调用点: