IDE(Interprocedural Distributive Environment)框架 [SRH96] 也涵盖了与IFDS类似的具有分布律的转移函数的流敏感分析,但支持更广类别的抽象状态的格。
在IDE框架,抽象状态的格是D→L,其中D是一个有限集合,L是一个具有有限高度的完全格。如9.3节所述,这是IFDS中抽象状态的一种泛化形式。对于CFG中的一个节点v,转移方程的形式为t_v:(D→L)→(D→L)。exploded CFG图也类似,对于边集合里面的任意边,现在需要带有一个标记函数 m: L→L,这个边记为$<v_1,d_1> \\stackrel{\\text{m}}{\\rightarrow} <v_2,d_2>$。一个缺失的边的含义同标记m=Bottom一致(bottom就是L→L的元素)。直接上,标记m表达v1处d1的抽象状态如何影响v2处d2的抽象状态。(对比IFDS,边<v1,d1>→<v2,d2>表示v1的d1是否影响v2的d2)
Exploded图里面的边,可以通过9.3节的二分图来构建:如果二分图对于转移函数t_v:(D→L)→(D→L),有一条CFG上的边事从v1到v2(比如v2是v1的后续节点),那么就可以在exploded图构建一条边$<v_1,d_1> \\stackrel{\\text{m}}{\\rightarrow} <v_2,d_2>$。
在IDE框架里面,路径边(叫做跳转函数)类似的,也被形如L→L的函数标记。回忆9.4节,IFDS构建了路径边集合P,从空集合开始,每次在迭代的时候加入一条边。IDE则是从bottom开始,构建边的标记函数,每次迭代在L→L的格向前移动。因此我们引入一个不同的标记方式。对于每一对exploded CFG的节点<v1,d1>和<v2,d2>,$[[<v_1,d_1>\\leadsto<v_2,d_2>]]_{\\mathbf{P}}: L \\rightarrow L$ 表示对应边的标记的约束变量。类似的,我们对于E里面从<v1,d1>到<v2,d2>的边上的标记,记作为$[<v_1,d_1>\\rightarrow<v_2,d_2>]_{\\mathbf{E}}$ 。
第一阶段
IDE的第一阶段构建路径边,类似于IFDS中的第一阶段,但使用更一般的由L→L 的函数组成的格。以下每个约束规则直接对应于IFDS中的一个约束规则。
第一个规则是,主函数永远可达,拥有个体跳转函数,其中id: L→L是个体函数,对于所有L的元素e,$id=\lambda e.e$
第二个规则是,v0是函数入口,函数有一个调用v1,被调用函数的入口是v,那么v这个函数入口的可达性约束规则
第三个规则是,v’是调用点,v是之后的点,v0是这两个点所在函数的入口,w是v’的后续,w’是v的前序,那么从函数入口v0到v’然后经过被调用函数,到达v的约束如下。下图是一个示意图,表示抽象状态<v0,d1>如何影响<v,d5>。特别的,要注意m4m3m2m1的组合。
第四个规则是:对于v’是调用,v是之后的节点,vo是入口。同IFDS,这个约束规则同样适用于其他类型的cfg节点,其中v‘是v的前序。
第二阶段
IDE分析的第二阶段使用在第一阶段生成的路径边(表示跳转函数)来计算每个exploded CFG节点<v,d>的抽象值[[v; d]] ∈ lift(L)。在这里,我们使用了一个带有底部元素表示不可达的lift格,表示从程序入口不可达的节点。这个分析阶段与第9.2节中描述的分析的主要阶段非常相似。
函数入口:
对于任意cfg的节点v,d的抽象值可以从函数入口v0获得,并且路径边可达,那么就有(也就是说从入口到v的结果要进行更新)
对于每一个函数入口点v,v1是v所在函数的一个调用点,我们需要处理函数调用参数传递,也就是从v1到v的传递
最后,cfg节点v的抽象状态表示为$[[v]]_2 : D \rightarrow L$,定义为$[[v]]_2(d)=[[<v,d>]] \in L \text{ for } d \in D$。
对于给定程序的每个分析阶段,可以使用工作列表算法计算出所得约束的最小解,类似于IFDS,但第二阶段需要更多的努力(伪代码可以在[SRH96]中找到)。
IDE的效率取决于边缘标签函数的高效表示。这意味着出现在爆炸CFG的边缘E和路径边缘P上的函数可以在常数空间中表示(即与程序的大小无关),并且函数的组合、最小上界、相等性和函数应用可以在常数时间内计算。对于复制常量传播分析,我们只需要恒等函数和常数函数,它们显然具有这个属性(假设常数操作可以在常数时间内执行)。