【輸入輸出】
一個過程的所有基本塊，除entry和exit外的每個基本塊包含指令序列
【流程】
由前向數據流分析、局部復寫傳播和遍歷基本塊構成
1. 前向數據流分析：目標是計算出每個基本塊入口處有效的復寫賦值集合，這里定義為CPin(i)，i為基本塊，其元素為表示復寫賦值的四元組<u,v,blk,pos>，u為左變量，v為右變量，blk為基本塊，pos為在blk中的位置。另外定義COPY(i)為基本塊i中出現且到達了出口的那些復寫賦值集合，即u和v在i中pos后沒被賦值；KILL(i)為被基本塊i殺死的那些賦值集合，即i中存在對其它基本塊復寫賦值右變量的賦值；CPout(i)為基本塊i出口處有效的復寫賦值集合。以上四種集合的數據流方程為：CPin(i)等于i的每個前驅p的CPout的交集，CPout(i)等于COPY(i)與CPin(i)減去KILL(i)之差的并集。CPout(entry)初值為空集，其它基本塊的CPout初值為全集U，U為過程所有復寫賦值的集合即所有基本塊的COPY之并集，根據迭代求不動點法可算出每個基本塊最終的CPin值
2. 局部復寫傳播：作為被全局復寫傳播調用的例程，有兩個參數，一個為輸入輸出參數單個基本塊，另一個為輸入參數CPin，即前向數據流分析求得的結果。該例程內部維護一個有效復寫賦值的表，稱作ACP，其元素為二元組<u,v>，u是復寫賦值的左變量，v是右變量。首先初始化ACP即將CPin中的復寫賦值加入到ACP，再遍歷基本塊的每條指令，針對指令類別做對應的處理，有以下幾種情況
a）對于一元/二元表達式及過程調用，將表達式的操作數或調用參數替換為ACP中對應元組的第二分量，若不存在這樣的元組則不用替換
b）對于賦值語句（包括復寫賦值），從ACP中刪除第一或第二分量為賦值語句左變量的元組，這是為了刪除被殺死的復寫賦值
c）對于復寫賦值且左變量u不等于右變量v，將元組<u,v>加入到ACP
當遍歷結束后，局部復寫傳播就完成了
3. 遍歷基本塊：對每個基本塊調用局部復寫傳播，當遍歷結束后，全局復寫傳播就完成了
【分析】
數據流分析的復雜度取決于基本塊總數及指令總數，局部復寫傳播的復雜度取決于基本塊的指令總數，遍歷基本塊復雜度取決于基本塊數量。全局復寫傳播會造成無用的賦值指令，但是這正給死代碼刪除和強度削減（比如兩個相同的整型變量加法用移位代替）提供了機會
posted on 2023-09-06 23:13
春秋十二月 閱讀(126)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler