7.3 迭代式資料流分析#

概念說明#

編譯器最佳化前必須先「知道事實」：哪些變數還活著？哪些表達式已算過可用？指標可能指向哪裡？這些事實沿著控制流圖（CFG）傳播，而求它們的標準方法正是迭代式資料流分析：為每個節點維護一組事實，反覆套用轉移函數直到所有節點的事實不再變化——到達不動點為止。

形式化框架：每個節點 \(n\) 有事實集合 \(\text{in}[n]\) 與 \(\text{out}[n]\) ，轉移函數 \(f_n\) （語句的效果），匯合函數 \(\wedge\) （多條入邊資訊如何合併）：

不同分析只是選擇不同的半格（lattice）與匯合：

• 到達定值：格為集合，匯合取聯集，方向前向。
• 活變數：變數在未來會被讀取，匯合取聯集，方向後向： \(\text{in}[n] = \text{use}[n] \cup (\text{out}[n] - \text{def}[n])\) 。
• 可用表達式：匯合取交集，前向。

為什麼一定會收斂？克萊尼/Tarski 不動點定理：在有限格上，單調函數的不動點存在，且從底（或頂）開始的反覆套用必在有限步到達最小（或最大）不動點。因為格有限、每次迭代事實集合單調增大（或減小）、嚴格變化的次數有限——所以「迭代直到不變」必然終止。這與第 2 章壓縮映像形成漂亮對照：連續世界靠壓縮性保收斂，離散世界靠單調性＋有限性保終止。

效率細節：節點處理順序影響輪數（逆後序通常最佳）；工作清單演算法（worklist）只重處理 out 有變化的節點的後繼，避免整圖掃描。位向量實作（每個事實一個 bit）使聯集/交集成為一條 CPU 指令，大型程式的分析因此可行。

生活類比#

辦公室傳聞的散播：每個人（節點）把聽到的訊息加工後告訴所有同事（轉移函數），多條來源合併取並集（匯合），直到某天沒有新訊息——系統到達不動點，傳聞穩定。安全公告的「必經」訊息（所有人都收到才算數）則是交集匯合。

演算法步驟#

以活變數分析（後向、並集）為例：

1. 初始化：所有 in[n] = out[n] = ∅。
2. 反覆掃描所有節點直到無變化：
3. out[n] = ∪ in[s]（所有後繼 s）
4. in[n] = use[n] ∪ (out[n] - def[n])
5. 任一集合變化則繼續；全部不變即不動點，分析完成。
6. （加速版）用工作清單：僅當某節點 in 變化時，把其前驅加入待處理清單。

Python 範例#

對一段玩具程式的 CFG 做活變數分析：

# 節點 -> (use, def, 後繼清單)   後向分析
cfg = {
    "B1": ({"a", "b"}, set(), {"B2"}),
    "B2": ({"a"}, {"c"}, {"B3", "B4"}),
    "B3": ({"b", "c"}, {"d"}, {"B5"}),
    "B4": ({"a"}, {"c"}, {"B5"}),
    "B5": ({"d"}, set(), set()),      # 出口
}

def liveness(cfg, max_rounds=20):
    live_in = {n: set() for n in cfg}
    for _ in range(max_rounds):
        changed = False
        for n in reversed(list(cfg)):          # 逆序：後向分析快
            use, defs, succs = cfg[n]
            new_out = set().union(*(live_in[s] for s in succs)) if succs else set()
            new_in = use | (new_out - defs)
            if new_in != live_in[n]:
                live_in[n] = new_in
                changed = True
        if not changed:
            return live_in
    raise RuntimeError("未收斂")

result = liveness(cfg)
for n in reversed(list(cfg)):
    print(f"{n}: 活變數 = {sorted(result[n]) or '{}'}")

輸出顯示 B5 之後無事實、B1 之前 a, b 皆活——與人工推演一致；迭代兩三輪即不動。

複雜度與收斂性分析#

樸素掃描：每輪 \(O(|E| \cdot \text{成本}(f, \wedge))\) ，輪數上限為格高（位向量分析即事實總數 \(|F|\) ），最壞 \(O(|E| \cdot |F|)\) 。工作清單＋逆後序在實際程式上通常 2～5 輪收斂。分類口訣：並集匯合（may 分析）從 ∅ 出發單調增大；交集匯合（must 分析）從全集出發單調減小——兩者都靠單調性保證到達最小/最大不動點。這套框架也是抽象解譯（abstract interpretation）與靜態分析工具的基礎。

練習#

1. 把上例改為「到達定值」分析（前向、並集，def 為產生的定值點），驗證收斂。
2. 實作可用表達式分析（前向、交集），初始 out[entry] = 全集，觀察「從頂往下」的收斂方向。
3. 構造一個循環內反覆賦值的 CFG，比較「正序掃描」與「逆後序＋工作清單」的迭代輪數。