Partial Evaluation, Constant Propagation, AI的關係是什麼？

01-16

AI -&> Abstract Interpretation

樓上對於 AI 「找出某些屬性」的思想總結的很好。總感覺 AI 偏向於理論指導——先找出某些屬性，然後依據這些屬性來進行優化或者干別的什麼就隨意了。從優化的角度來看，我們可以說 AI 「激活」了一些優化。

從具體的例子上來講，Click 的 SCCP [1] 是一種基於 SSA 的 Constant Propagation 演算法，核心的思想就是在 SSA edge 上做 optimistic 的 AI：它會從 graph entry 開始，把 reachable 的 SSA edge 的 value 給 map 成 lattice，在 phi 上做 meet（通常是簡單的 Constant1 ∨ Constant2 = ⊥），直到 fixed point，最後把 ? 的 edge 刪掉。

PE 感覺也是激活更多優化的一種思想 [2]：將已知的 argument value / type 塞進一個 function 里，然後我們就能做更多的 Inlining, Constant Propagation, Loop Unrolling, Strength Reduction, Code Motion 等等。

PyPy 和 Graal/Truffle 應該是近年來比較知名的應用了 PE 的項目。前者有個 (meta-)tracing interpreter [3]，interpret 的時候收集精確的 profiling data，去掉其中過於 specific 的部分 [4]（不然總是需要 deoptimize），將餘下的部分作為 PE 的 input，然後優化；後者基於 self-modifying AST interpreter [5]，(一個不錯的範例在 [6])，interpret 的時候 AST 就把自己給 specialize 了，然後在 specialized AST 上做 PE（看起來就是猛 inline [7]，直到 method body 太大 [8]），接著各種優化。

JIT PE 很有趣的一點是，由於是 self-modifying code，所以可以做一些特別 speculative 的事情，比如*假設*一個 value 是 constant（或者 dynamically type language 里某個 variable 的 type 是 constant，某個 Java interface 只有一個 class implement，某個 heap-allocated struct 不會 escape 等等），然後針對基於這個假設所獲得的新的信息，來做非常 aggressive 的優化，完全不考慮另一個 branch（甚至根本不生成 native code）。萬一真的出現了意料之外的情況，則會直接 deoptimize 回到 interpreter 裡面，重新收集 profiling data。像 Graal 裡面有專門的 AST node 來記錄 branch 的 probability [9]，然後根據不同的情況生成不同的 native code [10]。

沒啥理論基礎，拋磚引玉，胡寫一通..

——————————————————————————

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.8510rep=rep1type=pdf

[2] Comp.compilers: Re: Partial evaluation vs flow-graph analysis，接近 20 年前了，正是 PE 火的時候...

[3] http://stups.hhu.de/mediawiki/images/1/18/Pub-BoCuFiRi09_246.pdf，cfbolz 的 Tracing the Meta-Level: PyPy"s Tracing JIT Compiler

[4] https://hal.inria.fr/hal-01205345/file/Marr15b-Oopsla15-TracingVSPartial.pdf，這人在 RPython 和 Graal/Truffle 上用三種方式實現了同一種 Smalltalk 的實現，真能寫

[5] http://lafo.ssw.uni-linz.ac.at/papers/2013_Onward_OneVMToRuleThemAll.pdf

[6] https://github.com/graalvm/simplelanguage

[7] graal-core/PartialEvaluator.java at 5eca9540a6be27a45b7a131b1a108db9b916964f · graalvm/graal-core · GitHub

[8] graal-core/InliningData.java at f28cb4f0e84524dc84205fb023944b9ccccaf055 · graalvm/graal-core · GitHub

[9] graal-core/BranchProbabilityNode.java at 32a4eeeaa9301ef05f72b0fcb538b864a9a564af · graalvm/graal-core · GitHub

[10] graal-core/MonitorSnippets.java at 92ab54c0f5ae640b2f7850cd43ef9b9a9b7b4718 · graalvm/graal-core · GitHub

CP $in$ AI(狹義地)

PE $in$ AI(廣義地, [1])

[1] Systematic design of program transformation frameworks by abstract interpretation, POPL 02