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