2006 Frances Allen —— 編譯器的隱形女主人#

「IBM 內部教學課程找不到教材，她開始自己寫——結果寫出了 最佳化編譯器的理論基礎。四十五年前，程式設計師還不知道 『自動並行』這個詞。」

案件檔案#

前因#

1957 年，數學教師 Allen 因欠學費加入 IBM 教學 Fortran （Backus 1977 案的產品）。當時謎題：編譯器產出的碼 為何總比手工組語慢？慢在哪裡？能否有系統地縮小差距？

線索與推理#

線索一：資料流分析的形式化（1970，與 Cocke 1987 案）#

把程式視為控制流圖，在各節點解方程組：

OUT[n] = IN[n] ∪ GEN[n]     （可用表示式）
IN[n]  = OUT[p1] ∩ OUT[p2] ∩ ...  （交會運算隨分析而定）
迭代到不動點 → Cocke–Allen 證明格上單調函數收斂

最佳化從技巧清單變成數學：不變式外提、公共子表示式、 死碼刪除，皆有統一的理論框架（1987 案的深化）。

線索二：強化樹與區間分析（1970）#

Allen 的 interval analysis：把循環巢識別為「強化樹」 （reducibility），首次讓編譯器自己理解迴圈結構—— 這是迴圈最佳化（展開、交換、融合）的入口。

線索三：自動並行化（1980s，PTRAN 專案）#

挑戰：把 Fortran 的迴圈自動拆到多處理器。核心障礙：

資料相依性分析：兩次存取同一陣列，何時可能衝突？
  A[i], A[i+1] → 依賴距離 1 → 不能並行
  A[2i], A[2j+1] → 不相交 → 可並行
需要整數線性不等式組的可解性判定（陣列區間分析）

PTRAN 的成果成為日後所有並行編譯器（含 GPU 編譯器） 的理論母體。

線索四：超長指令與 IBM 的戰場#

Allen 參與 IBM 801（Cocke 的 RISC）、Advanced Computing System、並行編譯器 XL 系列——編譯器部門是 IBM 的 秘密武器。

理論評析#

Allen 的偵探學貢獻：把「慢」分解為可命名、可消除的 冗餘。她的隱喻至今有效：編譯器最佳化 = 尋找「程式的 語義等價變換」，而正確性由資料流方程的數學性質保證—— 自動並行化則是其中最難的子案（ NP 難的相依性判定 + 收益模型），至今仍是活躍研究（自動調優、ML for compilers）。

後果#

• LLVM/GCC 的最佳化管線直接沿用其框架。
• 她是圖靈獎史上第一位女性得主（1966–2005 空白四十年）， 自身的導師生涯（含指導多位女性研究者）改變了領域 性別結構。

關聯案件#

→ 1987-John-Cocke與編譯器最佳化及RISC、1977-John-Backus與FORTRAN高階程式語言、2020-Aho-Ullman與編譯器理論