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