【輸入】
ssa控制流圖。結(jié)點為一個phi函數(shù)或一條運算指令，邊包含控制流邊和ssa邊
【輸出】
所有ssa變量的最終LatCell（常量半格值）
【流程】
1. 算法維護兩個工作表，一是流圖邊FlowWL，用于跟蹤控制流的執(zhí)行，二是ssa邊SSAWL，用于單賦值變量的傳播。還有一個ExecFlag映射，用于確保僅有控制流邊導(dǎo)向的運算結(jié)點最多執(zhí)行一次，多次執(zhí)行是沒必要的，因為運算涉及的分量不會變（沒有ssa前驅(qū)邊），ExecFlag(a,b)為true表示邊a->b導(dǎo)向的結(jié)點b已執(zhí)行，否則未執(zhí)行
2. 兩種結(jié)點的分析：
a) 對于phi結(jié)點，不管被哪種邊導(dǎo)向，都先計算其LatCell（phi結(jié)果與各個phi參數(shù)的交），若與舊值不同，則將它的ssa后繼邊加入SSAWL，若控制流后繼邊尚未執(zhí)行即對應(yīng)ExecFlag為false，則將它的控制流后繼邊加入FlowWL
b) 對于運算結(jié)點，若是控制流邊導(dǎo)向且未被執(zhí)行過（到結(jié)點的所有邊的ExecFlag為false）或ssa邊導(dǎo)向且以前執(zhí)行過（存在至少一條邊的ExecFlag為true），則執(zhí)行其運算，計算左值變量的LatCell（解釋執(zhí)行整數(shù)運算），若與舊值不同，則將ssa后繼邊加入SSAWL，若LatCell是常量且為條件運算，則將滿足條件的Y或N邊加入FlowWL，否則將所有控制流后繼邊加入FlowWL
3. 算法初始時，設(shè)置所有控制流邊的ExecFlag為false，設(shè)置所有ssa變量的LatCell為未知（半格頂元素），將流圖入口到第1個結(jié)點的邊加入FlowWL。然后進行主循環(huán)，先從FlowWL移出一條邊，若邊的ExecFlag為false則設(shè)為true，判斷尾結(jié)點類型，若為phi則轉(zhuǎn)到上述2-a處理，若為運算則轉(zhuǎn)到2-b處理；再從SSAWL移出一條邊，若邊尾結(jié)點為phi類型則轉(zhuǎn)到2-a處理，否則為運算類型轉(zhuǎn)到2-b處理，以上過程直至FlowWL和SSAWL皆為空
【分析】
該算法思想是符號執(zhí)行，對于運算x=y或x=y+z（這里+泛指對整型有意義的操作），在常量半格中，x、y、z初值為未知，y和z單調(diào)降低，導(dǎo)致x也單調(diào)降低，它們最多降低2次，故當(dāng)格值不變后，SSAWL終為空，另外由于ExecFlag的作用導(dǎo)致所有僅控制流邊導(dǎo)向的結(jié)點最多執(zhí)行一次，因此FlowWL終為空，算法是收斂的，復(fù)雜度取決于控制流邊和ssa邊的總數(shù)
posted on 2023-09-06 23:10
春秋十二月 閱讀(98)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler