(基于字符串的方式,会重复的分析某个函数;这会带来极大的性能问题)考虑如下程序:

f(z) {return z*42;}
main() {
  var x,y;
  x = f(42); // call 1
  y = f(87); // call 2
  return x + y;
}

使用k ≥ 1的调用字符串方法会对函数f进行两次分析,这是不必要的;因为在两次调用中,参数的抽象值都是+。函数式上下文敏感性方法不是基于来自调用堆栈的控制流信息,而是基于调用时的抽象状态数据来区分调用的上下文。在最一般的形式中,函数式上下文敏感性方法使用:

$$ Contexts = States $$

尽管通常只需要States的一个子集。使用这组调用上下文,分析格变为:

$$ (States \rightarrow lift(States))^n $$

这显然导致了理论最坏情况复杂度的显著增加,与上下文不敏感分析相比。

    这个想法是,对于控制流图(CFG)节点v,格元素是一个映射$m_v:States \\rightarrow lift(States)$,其中$m_v(s)$ 近似表示在当前包含v的函数以匹配s的状态进入时,在v处可能的状态。当$m_v(s) = unreachable$ 时,意味着在程序的执行中,没有函数以匹配s的状态进入,并且v被执行到。如果v是函数f的出口节点,那么映射$m_v$是f的一个摘要,将抽象的入口状态映射到抽象的出口状态,类似于传递函数(参见第5.10节)对单个指令的执行效果进行建模,但现在是针对整个函数的。

    我们来看例子,我们现在希望定义一组约束来实现特别的需求,我们希望在分析之后在函数f退出的时候得到如下约束:

Untitled

这段信息表明,除非函数的入口处z为0或+,否则函数f的出口是不可达的,并且在出口处的结果的符号与输入处z的符号相同。特别地,当z为-时的上下文映射为不可达,因为在程序中从未使用负数作为f的输入调用。

    对于函数$f(b_1,\\dots,b_n)$的入口节点v的约束规则,在调用 $w\\in~pred(v)$处时的定义与调用字符串方式一致,只需要将上下文c的条件置换一下:

Untitled

Untitled

这个规则的含义是,在所有上下文c’的调用w处,抽象状态$s_w^{c'}$ 只会传递到入口节点的上下文同当前抽象状态一样的地方。这样做是有道理的,因为现在的上下文是基于函数式的抽象状态。

    假设v时函数调用之后存储返回值到变量X的节点,v’是调用点,w是被调用的函数的返回点之一。那么,在v处的约束规则需要合并v’和w处,同时需要考虑调用的上下文和可达性:

Untitled

为了找到函数出口节点的相关上下文,这个规则构建的抽象状态与调用节点处构建的抽象状态相同。

    在这里所介绍的函数式方法中,使用上下文敏感性可以提供最优的精度,即它的精度与将所有函数调用(包括递归调用)内联展开一样精确。这意味着它完全避免了在跨过程无效路径上的数据流问题。

    由于最坏情况下的复杂性较高,实际上在实践中,函数式方法通常会有选择地应用,要么只应用于某些函数,要么使用只考虑部分程序变量的调用上下文。其中一种选择是参数敏感性,其中调用上下文由函数参数的抽象值定义,而不考虑程序状态的其他部分。在本章中使用的TIP版本中,没有指针或全局变量,因此函数入口处的整个程序状态由参数的值定义,这意味着本节中介绍的分析与参数敏感性相一致。在分析面向对象的程序时,一种常见的选择是对象敏感性,它本质上是函数式方法的一种变体,它不是根据函数入口处的整个抽象状态来区分调用,而是仅根据接收对象的抽象值来区分调用。