編譯器中都有哪些演算法？

01-05

詞法/語法分析、程序分析與程序變換、代碼生成、內存管理、虛擬機、函數式語言的實現與優化。。。每個話題都能出不止一本書。

用到的演算法/數據結構多如牛毛：

各種樹、圖為主，其他如棧、隊列、散列表、並查集。。。
貪心、回溯、動態規劃、遺傳演算法、矩陣變換。。

在一個問題下很難回答好。。先簡單介紹一下和圖相關的。

1. 和什麼圖打交道

CFG(Control Flow Graph)

控制流圖是對程序中分支跳轉關係的抽象，描述程序所有可能執行路徑

節點是語句集合（basic block)；
每個basic block有唯一入口和出口；
如果A到B有邊，表示A執行完後可能執行B

PDG(Program Dependence Graph)

PDG在編譯器中用得不多，常見於軟體工程/安全相關的應用（程序切片、安全信息流等）

SSA(Single Static Assignment)

SSA簡化了很多數據流分析問題。

其他圖

DJ Graph, Loop Nesting Forest, Program Structure Tree等等。

可參考：IR for Program Analysis。下面主要介紹CFG

2. CFG初步處理

CFG構造

dominator樹生成

在CFG中，如果A是B的dominator，則從程序入口執行到B的任意路徑一定經過A

控制依賴分析

根據dominator和post-dominator分析依賴關係。數據依賴、控制依賴信息在自動並行化中尤其重要（如果循環的每次迭代都沒有依賴，那麼可以並行處理）

控制流圖化簡

在複雜度相同的情況下，CFG的規模影響演算法的效果。如果一個CFG僅通過如下變換能化簡為一個節點，則它是可化簡的：

如果節點n有唯一的前驅，那麼將其和其前驅合併為一個節點
如果節點存在到自身的邊，那麼將該邊刪除

構造SSA

SSA可以由CFG構造。

3. CFG與數據流分析

下面才進入主題。。

一般的文獻介紹DFA（Data flow analysis），都會用幾個基礎的分析為例：Constant Propagation，Range propagation，Avaliable expressions，Reaching Definition。而Reaching Definition的一個應用，就是大家喜聞樂見的「跳轉到定義處」（真要做到「智能」跳轉並不簡單）

這部分涉及東西較多，一些演算法也和」圖「並不直接相關，不再展開。

PS，很多DFA問題可以用graph reachability統一建模，強烈推薦此文：

Program analysis via graph reachability

一般是編譯器後端會用到很多演算法，主要是圖論。 @姚培森已經說的挺好了，我就補充一個圖論應用於優化時的演算法PDF吧，就幾十頁吧，http://www.cs.umb.edu/~offner/files/flow_graph.pdf

@姚培森牛

整個編譯器就是一個巨大巨大的演算法

記得上standford的compiler課上，講過寄存器優化，其中用了染色定理。當時是第一次覺得演算法無處不在～