關(guān)于“活躍性分析”的問題

landker

最近碰到一些關(guān)于“活躍性分析”的問題（在《虎書（C語言描述）》中文版的第156、157頁），具體如下：

1、對于“算法10-1”（157頁），該如何理解？具體為：

1）對于“算法10-1”，里面的 n，是指“結(jié)點” 還是 “迭代次數(shù)” ？

2）對于“算法10-1”，如何理解迭代的終結(jié)條件，即何為一個不動點？（書里的例子是 6th列 和 7th列 的所有內(nèi)容都相同則停止迭代）

3）如果將“算法10-1”轉(zhuǎn)換成 C語言，該是怎樣的？

2、對于“表10-1”（157頁），它的內(nèi)容是如何得出的？希望可以舉例說明，例如：1st列，2st列。

landker

回復(fù) 1# landker

ding
   

duanlin

live 這個詞翻譯成活躍的，我覺得有點歪曲意思。
大白話：“有用的”也許更貼切。意思就是“別刪，一會兒用”，反義詞就是“沒用了”。

1) 首先n 是節(jié)點，是一個編號。out[n] 代表這個編號的節(jié)點產(chǎn)生的out，如果這個節(jié)點產(chǎn)生a,b兩個out，則
out[n] == {a,b}
2）我想是翻譯問題，并沒有一個什么“不動點”，這里的意思我理解為“算法收斂為止”。收斂的時候即為所謂的“不動點”。

不用太糾結(jié)書上說的算法細(xì)節(jié)。本身算法基于的數(shù)據(jù)結(jié)構(gòu)和想要做的事情可能沒說清楚。
一個節(jié)點有幾個in和out還有def和use，
in,out是數(shù)據(jù)流在節(jié)點間的連接，比如：我這個節(jié)點計算出來的out 給我下面其他節(jié)點當(dāng)作in來使用。
舉個例子
(n=1)add r0, r1 -> r2
(n=2)sub r2, r3 -> r4
加法節(jié)點的in[1]={r0, r1} out[1]={r2} , 這時該節(jié)點使r2變得活躍
減法節(jié)點的in[2]={r2, r3} out[2]={r4} 這時該節(jié)點使r4變得活躍

def并不是該節(jié)點的out但它是由該節(jié)點計算出來的一個結(jié)果，同樣use也不是該節(jié)點的in但是這個節(jié)點要使用。
比如cmp r0,r1的輸入是 {r0,r1}，而隱含定義（def）了比較結(jié)果 EFLAGS，
而接下來的跳轉(zhuǎn)指令jne r2 隱含使用了（use）比較結(jié)果EFLAGS。

對于這個算法的意圖，是這樣的，
在上面舉例的減法節(jié)點，單靠減法節(jié)點自己并不知道r3狀態(tài)（之前是何情況），所以可以用書里的方程，靠上下節(jié)點推算出當(dāng)前的所有活躍總集，再參考這個總集做某些處理。上下層越多，收斂越慢。