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