過程間和過程內的數據流分析演算法在類似LLVM的IR或HotSpot C1的HIR中，是如何實現的？
我自己為了學習的目的，實現了一個類C語言的編譯器，想把數據流分析演算法應用進去，迄今未知，一直非常的困惑是經典的數據流分析演算法如何在類似LLVM的IR和HotSpot的HIR中實現（因為我自己實現的編譯器參考了它們兩者的特點）。
--------------------------------------------------------------------------------------------------------------
我看LLVM的源代碼沒找到對應實現，如果能說出哪個文件就非常好了，謝謝！
HotSpot的C1編譯器中為了編譯效率，沒有實現，Joeq中是實現的IR是基於顯示寄存器IR的，把每個變數（也就是寄存器）使用一個整數代替，但是HotSpot C1中的HIR無法這麼處理，soot中的Jimple也類似於這種方式。
咦題主把之前的問題刪掉了么…我還打算回答之前那個呢。
呃原來之前那個不是題主問的。我把這篇答案聯動到之前的問題了：新版的龍書和鯨書上講了很多數據流分析的理論，LLVM中有對應的實現嗎？ - RednaxelaFX 的回答
Z大 @zephyr z 的回答對LLVM的講解到位。正是因為SSA形式貫穿於LLVM IR，所以針對SSA value的數據流分析，在LLVM里都是用sparse的方式做的，而不像傳統的IR那樣要用bit vector / int vector / set迭代遍歷每條指令去傳播信息直到到達fixpoint。
- dense分析：要用個容器攜帶所有變數的信息去遍歷所有指令，即便某條指令不關心的變數信息也要攜帶過去。
- sparse分析：變數的信息直接在def與use之間傳播，中間不需要遍歷其它不相關的指令。
不過Z大的答案略微不準確的是，即便是sparse分析，放在一個dataflow framework里還是可以使用lattice的，而且分析過程可能還是迭代的（只是不需要每次都迭代所有指令而已）。
過程內分析（intraprocedural analysis）
LLVM
LLVM IR雖然被許多人叫做「low-level IR」，但由於它還持有GEP之類的頗為高級的之類，我覺得把它看作「middle-level IR」比較好。
LLVM的大部分優化都在LLVM IR上做，包括所有平台無關優化以及少量平台相關優化（主要是平台相關性影響一些本來通用的優化的策略）。
LLVM IR是SSA形式的，並且維護雙向的def-use信息：use-def信息是很自然的通過指針實現，而def-use則是通過一種比較節省內存的跳錶/鏈表來實現的。維持雙向def-use信息便於在IR上做各種操作，例如前向數據流分析（forward dataflow analysis）、後向數據流分析（backward dataflow analysis），以及方便的變換IR（例如RAUW——replaceAllUsesWith）。
作為LLVM IR上的數據流分析例子，可以看看這個超簡單的optimistic (aggressive) dead code elimination：
llvm/ADCE.cpp at master · llvm-mirror/llvm · GitHub
這個pass自身已經被更強的別的版本的DCE替代了。但是這個用來作為例子講解還是很不錯的。
這個ADCE的本質就是，這是liveness analysis的應用，是一個backward dataflow problem（所以信息順著use-def方向傳播）：
- 使用一個只有2個元素的lattice，top是unreachable（U），bottom是reachable（R）
- 樂觀（optimistic）的分析策略，也就是最初假定所有指令都是U，除非能證明是R
- 演算法的起點是所有terminating指令（例如return）、potentially side effecting指令（例如store、call），這些認為肯定是R
- 然後，利用SSA形式的use-def信息，從上述root出發迭代出去，把所有能通過use-def鏈到達的指令都標記為R（注意這個標記過程，從lattice的角度看是單調（monotonic）的——只能從U變成R）
- 最後，沒有被標記為R的指令就是U，遍歷一次所有指令，把沒有被標記為R的指令刪除，DCE就完成了。
這裡最最重要的地方就是上面的(3)和(4)，不是以函數的入口為起點，也不需要線性迭代所有指令（dense）；而是以別的特殊指令為起點，並且通過use-def鏈直接把信息傳播到相關的指令上（而不需要攜帶這些信息逐條指令去看誰需要這些信息，所以叫做sparse）。
上面的描述其實挖了個坑，那就是「針對SSA value的數據流分析」。LLVM IR里，「memory」不是一個SSA value（直到LLVM的memory SSA項目完成為止），所以如果要對memory分析的話，就無法sparse了。留意上面的(3)中的「起點」有potentially side effecting指令，這就是對內存的保守分析。
HotSpot Client Compiler （C1）
HotSpot C1的話，嗯它真的是個超級簡單的編譯器，沒做那麼多正式的重量級的分析和優化。
先舉個C1 LIR的例子。C1有兩層IR，SSA形式的平台無關HIR，和傳統形式（非SSA形式）的平台相關LIR。大部分優化都是在HIR上做的，LIR基本上只用來做寄存器分配和最終的代碼生成。
在這傳統形式的LIR層面上，有個頗為傳統liveness analysis：LinearScan::compute_local_live_sets() 與 LinearScan::compute_global_live_sets()
jdk8u/jdk8u/hotspot: ddce0b7cee93 src/share/vm/c1/c1_LinearScan.cpp
先在每個基本塊內遍歷所有LIR指令算出基本塊的live_in和live_out，然後在CFG上從後向前遍歷基本塊來傳播liveness信息。這是典型的dense analysis的思路。
HotSpot C1 HIR的SSA形式…（待續）
LLVM是完全基於SSA的 傳統的基於lattice的那種迭代式數據流分析就沒有了
優化的話 大部分在lib/Transform/scalar目錄下, 比如說
EarlyCSE.cpp 就是做common subexpression elimination
DCE.cpp 就是做Dead code elimination
推薦閱讀：