【輸入】
調用圖，其頂端是根過程
【輸出】
每個過程每個參數的icp值
【算法步驟】
1. 將根過程加入工作表，遍歷調用圖，構建每個過程的形參集合，初始化每個形參的icp值為未知（icp格的頂元素）
2. 從工作表移出一個過程p，若工作表為空則終止
3. 遍歷p的指令序列，對每個調用點遍歷被調過程q的形參，對每個形參x，若對應的傳入實參是p的一個形參，則計算x的icp值（等于x舊值和傳入實參的icp值之交）
4. 若x的icp值比舊值小，則將q加入工作表，轉到步驟2繼續
【算法分析】
數學基礎是icp半格，高度為3，所以必定收斂（因為半格是單調偏序的，icp最多變小2次：未知->常量，常量->非常量）。步驟1復雜度取決于過程數及其參數數量，步驟2～4之外循環次數取決于調用圖的深度，內循環取決于調用點數、被調過程的參數數量。該算法是位置無關的，不能處理特定調用點的特定過程之常量傳播，另外過程的形參集合不能有交集
【應用】
可以計算出每個過程入口形參對應的常量實參集合，進而可以運用全局常數傳播使結果更精確。如果確定了一個過程的哪些參數是常量，那么可以克隆出一個副本，對副本進行優化，比如裁剪調用和起始代碼序列，使之不傳遞常數參數，再運用過程內優化
posted on 2023-09-06 23:02
春秋十二月 閱讀(62)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler