2006 - Allen 編譯器最佳化（首位女性圖靈獎得主）#

案件摘要#

2006 年，Frances Allen（法蘭絲·艾倫，1932–2020） 成為圖靈獎史上第一位女性得主—— 表彰她在編譯器最佳化（compiler optimization）的開創性貢獻：

\[ \boxed{\text{讓機器自動「看懂」程式的結構，並自動把它變快}} \]

她的破案工具是三件套： - 控制流圖（CFG）：把程式畫成一張「犯罪地圖」； - 資料流分析（data flow analysis）：追蹤每一筆「資料的行蹤」； - 區間分析（interval analysis）：把無窮迴路收斂成「有限嫌疑區」。

\[ \text{程式} \xrightarrow{\text{CFG}} \text{圖} \xrightarrow{\text{不動點迭代}} \text{可證明的最佳化}. \]

1957 年 FORTRAN 團隊靠蠻力手寫最佳化；Allen 證明了這件事可以系統化、自動化—— 今日 LLVM、GCC、Java JIT 的每一行最佳化代碼，都是她偵探方法的後裔。

前因 -- 為什麼會有這個案子#

FORTRAN 的賭注（1957）： John Backus 的團隊在 IBM 打造 FORTRAN 編譯器（見 1957-巴克斯FORTRAN.md）：

\[ \boxed{\text{賭注：編譯出來的碼，必須快得讓人願意放棄手寫組合語言}} \]

他們用大量的手工技巧（暫存器分配、公共子運算式消除）勉強達標—— 但這些技巧是師傅的經驗，不是科學。 - IBM Stretch 專案（1956–1961）： IBM 的超級電腦 Stretch（7030）需要更激進的最佳化才能餵飽硬體—— 1957 年，年輕的數學教師 Allen 加入 IBM，本來要教新進員工 FORTRAN，卻被拉進 Stretch 的編譯器小組，從此走上偵探之路。

\[ \text{Stretch 失敗了（商業上）} \xrightarrow{\text{但留下}} \text{最佳化理論的火種}. \]

1960 年代的危機：

\[ \boxed{\text{「最佳化到底能不能自動化？還是永遠只能靠手工？」}} \]

懷疑論者說：程式千變萬化，最佳化是藝術不是科學；更尖銳的問題：任意分析程式行為會撞上停機問題的牆（1936 Turing）—— 完美分析不可能。Allen 的答案：不求完美，求可證明的保守近似。 - 同行的呼應： McCarthy 的 LISP（1958，見 1958-麥卡錫LISP.md）早已把「程式 = 資料」付諸實踐； Kildall（1973） 把資料流分析統一成單調框架（monotone framework）—— 理論的地基已備，只欠一位總工程師。

線索與推理 -- 數學式、程式、理論#

第一條線索：控制流圖（CFG）——犯罪地圖#

控制流圖：把程式切成基本區塊（basic block），用有向邊連接可能的跳轉：

\[ G = (V, E), \quad V = \text{基本區塊},\ E \subseteq V \times V = \text{可能的跳轉}. \]

結點 \(V\) ：一段順序執行的指令（一進一出）；
邊 \(E\) ：分支或跳轉的可能路徑。

\[ \boxed{\text{最佳化的第一步：把「程式碼」翻譯成「圖」}} \]

有了地圖，偵探才能問：哪些路永遠走不到？（不可能路徑消除） 哪些路口的資訊始終有效？（可用運算式分析）

第二條線索：資料流分析——格上的不動點#

活躍變數分析（live variable analysis）：在程式點 \(p\) ，變數 \(x\) 活躍，若**未來可能不經重新定義就讀取 \(x\) **——活躍變數死掉時，暫存器可以回收。

單調框架：資料流事實形成一個格（lattice） \((L, \sqsubseteq)\) ，轉移函數 \(F: L \to L\) 單調（monotone）：

\[ x \sqsubseteq y \implies F(x) \sqsubseteq F(y). \]

Knaster–Tarski 不動點定理：單調函數在完備格上必有最小不動點：

\[ \boxed{\mathrm{lfp}(F) = \bigsqcap \{x \in L \mid F(x) \sqsubseteq x\}} \]

Kleene 迭代：從底端 \(\bot\) 開始反覆套用 \(F\) ：

\[ \bot \sqsubseteq F(\bot) \sqsubseteq F^2(\bot) \sqsubseteq \cdots \sqcup_i F^i(\bot) = \mathrm{lfp}(F). \]

格有限 ⟹ 迭代必在有限步收斂——這就是「可證明且會停」的最佳化！

\[ \text{完美分析（停機問題阻絕）} \xrightarrow{\text{保守近似 + 有限格}} \text{可判定}. \]

第三條線索：區間分析與向量化——從迴路到超級電腦#

區間分析（interval analysis, Allen 1970）：迴圈形成的強連通分量（不可約圖）令迭代混亂—— Allen 用區間（intervals）把控制流圖化約成層次結構，讓迴圈內的分析有秩序地由內向外收斂。
不可能路徑消除：若分支條件在編譯期可證明恆假，整條路徑連同其中的計算整批刪除——

\[ \text{if false} \Rightarrow \text{整段死碼（dead code）}. \]

Allen–Cocke 的最佳化目錄（1971）：兩人合寫《A Catalogue of Optimizing Transformations》—— 把散落各處的最佳化技巧編目成冊：

\[ \boxed{\text{最佳化不再是師傅的秘訣，而是一張可查的清單}} \]

公共子運算式消除、迴圈不變碼外提（loop-invariant code motion）、強度削減（strength reduction）、死碼消除——每一條都附「何時合法」的證明條件。這是藝術變科學的判決書。 - 靜態分析的對偶性：資料流分析分前向（可用運算式、到達定義）與反向（活躍變數、非常忙運算式）兩族——

\[ \text{前向：} IN = \text{transfer}(OUT) \qquad \text{反向：} OUT = \text{transfer}(IN). \]

兩者共用同一套格與不動點機制——Kildall 的單調框架一次統一； 克努特在《演算法的藝術》（1968，見 1968-克努特演算法藝術.md）把資料流分析寫進最佳化的科學章節，教科書自此定型。 - 向量化（vectorization）：迴圈內各次迭代若互不依賴（無真依賴跨越迭代），就能平行成一批：

\[ \text{for } i=1..n:\ A[i] \mathrel{+}= B[i] \quad\Longrightarrow\quad \text{一條向量指令算 } n \text{ 個}. \]

這是判斷依賴的資料流分析——日後超級電腦的生命線。

\[ \boxed{\text{資料流分析} \xrightarrow{1980\text{ s}} \text{向量化編譯器} \xrightarrow{} \text{超級電腦的靈魂}} \]

Python：活躍變數分析的資料流分析器（Kleene 迭代求不動點）#

# 活躍變數分析：控制流圖 + 反向資料流 + Kleene 迭代至不動點
# 每個區塊: use = 區塊內先讀後寫的變數, def = 區塊內定義(寫入)的變數

blocks = {
    "B1": {"use": {"n"},     "def": {"i", "s"}, "succ": ["B2"]},      # i=1; s=0; 迴圈開始
    "B2": {"use": {"i", "n"}, "def": set(),     "succ": ["B3", "B4"]}, # if i <= n ?
    "B3": {"use": {"i", "s"}, "def": {"s", "i"}, "succ": ["B2"]},      # s+=A[i]; i+=1
    "B4": {"use": {"s"},     "def": set(),     "succ": []},           # 輸出 s（出口）
}

# 活躍變數是「反向」分析：out = ∪ in(後繼)，in = use ∪ (out - def)
def transfer(b, in_of):
    info = blocks[b]
    return info["use"] | (in_of[b] - info["def"])

def analyze():
    in_of  = {b: frozenset() for b in blocks}   # 格的底端 ⊥
    out_of = {b: frozenset() for b in blocks}
    it = 0
    while True:                                  # Kleene 迭代
        it += 1
        new_out = {b: frozenset().union(*(in_of[s] for s in blocks[b]["succ"]))
                   if blocks[b]["succ"] else frozenset() for b in blocks}
        new_in = {b: blocks[b]["use"] | (new_out[b] - blocks[b]["def"])
                  for b in blocks}
        if new_in == in_of and new_out == out_of:  # 不動點：收斂！
            return it, in_of, out_of
        in_of, out_of = new_in, new_out

iters, IN, OUT = analyze()
print("活躍變數分析（Kleene 迭代求不動點）")
print(f"  收斂於第 {iters} 次迭代（有限格 ⟹ 必停）\n")
for b in ["B1", "B2", "B3", "B4"]:
    print(f"  {b}:  in  = {sorted(IN[b]) or '{}'}")
    print(f"  {' ':3}out = {sorted(OUT[b]) or '{}'}")
dead = [b for b in blocks if blocks[b]["def"] and
        not (blocks[b]["def"] & (OUT[b] | blocks[b]["use"]))]
print(f"\n  死碼偵測（定義後從未使用）：{dead or '無'}")
print("  → 所有定義皆活躍 → 這正是暫存器分配與死碼消除的判準")

輸出：

活躍變數分析（Kleene 迭代求不動點）
  收斂於第 4 次迭代（有限格 ⟹ 必停）

  B1:  in  = ['n']
     out = ['i', 'n', 's']
  B2:  in  = ['i', 'n', 's']
     out = ['i', 'n', 's']
  B3:  in  = ['i', 'n', 's']
     out = ['i', 'n', 's']
  B4:  in  = ['s']
     out = {}

  死碼偵測（定義後從未使用）：無
  → 所有定義皆活躍 → 這正是暫存器分配與死碼消除的判準

結案 -- 後果與影響#

向量化編譯器的誕生（1980s）：

\[ \text{Allen 的資料流理論} \xrightarrow{} \text{IBM 的向量化編譯器（1980s）} \]

她領導 PTRAN 與 PARALLEL FORTRAN——把 FORTRAN 迴圈自動平行化，餵飽 IBM 3090 向量機與 Cray 超級電腦——

\[ \boxed{\text{一個程式設計師寫迴圈，編譯器自動變出超級電腦的效能}} \]

每位編譯器的血統：
GCC / LLVM 的每一輪最佳化 pass，都是資料流分析 + CFG 的框架；
Java / JavaScript JIT 即時編譯在毫秒內跑完活躍變數、死碼消除—— 慢的話使用者就跑了，Allen 的有限格收斂保證即時性可達；
靜態分析工具（找漏洞、找死碼）同根同源。
圖靈獎（2006）——歷史性的一刻：

\[ \boxed{\text{2006：Frances Allen —— 圖靈獎 40 年來首位女性得主}} \]

1966 年設獎以來，得主全數是男性；Allen 的得獎改寫了這條單調上升的歷史線。她在 IBM 從教 FORTRAN 的小老師做到院士（Fellow）， 2002 年成為 IBM 首位女性院士退休，仍持續倡議女性投入資訊科學。 - 大師的謝幕（2020）： 2020 年 8 月 4 日，Allen 辭世，享年 88 歲—— 她留下的不是一台機器，而是一套方法：

\[ \text{FORTRAN（1957）} \xrightarrow{\text{Allen}} \text{資料流分析} \xrightarrow{} \text{LLVM/GCC/JIT（今日）}. \]

歷史定位：Allen 是編譯器的福爾摩斯—— Backus 證明「程式可以被編譯」，Allen 證明「程式可以被看懂再編譯」；

\[ \text{蠻力（1957）} \xrightarrow{} \text{科學（1960s–70s）} \xrightarrow{} \text{一切現代編譯器的地基}. \]

每一次你的程式莫名其妙變快，都是她在暗中辦案。

關鍵人物與文獻#

F. E. Allen：Program Optimization（1969, AFIPS）；Control Flow Analysis（1970, SIGPLAN）；Optimization of Uniform Loops（與 Cocke, 1972）；A Catalogue of Optimizing Transformations（與 Cocke, 1971）；2006 圖靈獎演講 The Reverend Bayes Optimizes 風格的回顧 Innovation in Compilation（2006）。
J. Cocke：IBM 同事——共同發展區間分析與全局資料流（Cocke–Allen）。
J. Backus：FORTRAN（1957）——最佳化的原始戰場（見 1957-巴克斯FORTRAN.md）。
G. Kildall：A Unified Approach to Global Program Optimization（1973）——單調框架的理論定型。
G. A. Kildall / P. Cousot & R. Cousot：抽象解譯（1977）——不動點理論的推廣。
相關案件：1957-巴克斯FORTRAN.md、1958-麥卡錫LISP.md、1968-克努特演算法藝術.md、1936-圖靈機.md。