過程內(nèi)分析，顧名思義， 不考慮任何的過程/函數(shù)間調(diào)用的分析算法。 總的來說，這是最基礎(chǔ)也是最簡單的一類程序分析算法， 但是其實(shí)還是比較有用， 特別是在二進(jìn)制分析的實(shí)際應(yīng)用中這還算是比較常用的。 因?yàn)楹芏鄷r(shí)候recover procedure 和indirect jump的存在， 其實(shí)過程間分析的精度可能會(huì)非常的糟糕。而且過程內(nèi)其實(shí)往往已經(jīng)能夠幫我們解決非常多的問題了。 一般常見的有Available Expression, Reaching Definition, Live Variable , Very Busy Expression。這幾個(gè)算法的實(shí)現(xiàn)其實(shí)非常的類似我以Available Expression為例子，上面的算法我都實(shí)現(xiàn)了一下。
Available Expressions Analysis
這個(gè)分析算法主要是為了找出在每一個(gè)程序位置， 什么表達(dá)式已經(jīng)被計(jì)算過了并且不會(huì)被改變。 在編譯優(yōu)化過程中我們就不必重新計(jì)算某一個(gè)表達(dá)式了。
在PPA 的example language中這里的表達(dá)式指的其實(shí)就應(yīng)該是非平凡的算術(shù)表達(dá)式了。 所以我們的算法最終需要給出一個(gè)從每一個(gè)程序label(也就是程序位置)到某些算術(shù)表達(dá)式的完全映射
根據(jù)每一個(gè)程序的輸入和輸出狀態(tài)我們可以列出方程組(當(dāng)然我們討論的域是Available Expression)。然后求解最大解(largest solution)就可以得到結(jié)果。
我們可以定義如下的偏序關(guān)系
請腦補(bǔ)把里面的RD 換成AE
這樣就可以比較解的大小了，并且能使解P(AExpr*)構(gòu)成一個(gè)完全格。然后我們可以發(fā)現(xiàn)求最大解其實(shí)就是求解他的不動(dòng)點(diǎn)。
什么是最大解呢， 首先我們不難發(fā)現(xiàn)如果令 那肯定是可以去解l'， 但是我們希望能得到信息量更多的結(jié)果，空沒有意義。
但是其實(shí)這里在真正實(shí)現(xiàn)的時(shí)候是有一些問題的。Kill Gen 其實(shí)并沒有什么問題，這兩個(gè)函數(shù)也比較簡單。問題在 的求解上。這是一個(gè)方程組。這種描述方式在邏輯式編程當(dāng)中會(huì)非常好解，基本上算是直接照著寫了。如果我們使用racket之類的函數(shù)式語言，顯然就不能直接寫一個(gè)遞歸的函數(shù)，肯定是直接死循環(huán)的，因?yàn)橛衎ack edge。
PPA 在第一章給出了一種算法來求解這個(gè)方程組，叫 混沌迭代(Chaotic Iteration)。 首先這個(gè)方程組一定能解，這一點(diǎn)會(huì)在后面的章節(jié)中給出證明。 其次， 最大意味著如果我們的迭代是單調(diào)增的那么，我們總能找到一個(gè)不動(dòng)點(diǎn)，而這個(gè)不動(dòng)點(diǎn)就是最大解(Top)。(其實(shí)這個(gè)證明不是很難)。所以在我們的代碼中我們可以先無限迭代，如果我們發(fā)現(xiàn)我們的最終輸出結(jié)果(AvailiableExpr的 return)不再變大了，我們就可以退出迭代了。
還有需要注意的是這個(gè)算法是個(gè)前向分析(Forward Analysis)要用正向的dataflow。
其他的幾個(gè)算法關(guān)鍵區(qū)別在于是要求最大還是最小解是前向還是反向。
代碼
https://github.com/StarGazerM/ppa-in-code/blob/master/dataflow/avaliable-expression.rkt
