关于“活跃性分析”的问题

landker

最近碰到一些关于“活跃性分析”的问题（在《虎书（C语言描述）》中文版的第156、157页），具体如下：

1、对于“算法10-1”（157页），该如何理解？具体为：

1）对于“算法10-1”，里面的 n，是指“结点” 还是 “迭代次数” ？

2）对于“算法10-1”，如何理解迭代的终结条件，即何为一个不动点？（书里的例子是 6th列 和 7th列 的所有内容都相同则停止迭代）

3）如果将“算法10-1”转换成 C语言，该是怎样的？

2、对于“表10-1”（157页），它的内容是如何得出的？希望可以举例说明，例如：1st列，2st列。

landker

回复 1# landker

ding
   

duanlin

live 这个词翻译成活跃的，我觉得有点歪曲意思。
大白话：“有用的”也许更贴切。意思就是“别删，一会儿用”，反义词就是“没用了”。

1) 首先n 是节点，是一个编号。out[n] 代表这个编号的节点产生的out，如果这个节点产生a,b两个out，则
out[n] == {a,b}
2）我想是翻译问题，并没有一个什么“不动点”，这里的意思我理解为“算法收敛为止”。收敛的时候即为所谓的“不动点”。

不用太纠结书上说的算法细节。本身算法基于的数据结构和想要做的事情可能没说清楚。
一个节点有几个in和out还有def和use，
in,out是数据流在节点间的连接，比如：我这个节点计算出来的out 给我下面其他节点当作in来使用。
举个例子
(n=1)add r0, r1 -> r2
(n=2)sub r2, r3 -> r4
加法节点的in[1]={r0, r1} out[1]={r2} , 这时该节点使r2变得活跃
减法节点的in[2]={r2, r3} out[2]={r4} 这时该节点使r4变得活跃

def并不是该节点的out但它是由该节点计算出来的一个结果，同样use也不是该节点的in但是这个节点要使用。
比如cmp r0,r1的输入是 {r0,r1}，而隐含定义（def）了比较结果 EFLAGS，
而接下来的跳转指令jne r2 隐含使用了（use）比较结果EFLAGS。

对于这个算法的意图，是这样的，
在上面举例的减法节点，单靠减法节点自己并不知道r3状态（之前是何情况），所以可以用书里的方程，靠上下节点推算出当前的所有活跃总集，再参考这个总集做某些处理。上下层越多，收敛越慢。