【輸入】
程序控制流圖CFG
【輸出】
帶區(qū)域結(jié)點(diǎn)的控制依賴圖CDG
【流程】
1. 為CFG添加一個虛構(gòu)謂詞結(jié)點(diǎn)start，它的Y邊指向入口結(jié)點(diǎn)entry，出邊指向出口結(jié)點(diǎn)exit，得到CFG+。添加start是因為entry到第1個基本塊沒有條件判斷
2. 為CFG+構(gòu)建后必經(jīng)結(jié)點(diǎn)樹PDOMTree，將CFG+中所有n不是m的后必經(jīng)結(jié)點(diǎn)的邊m->n加入集合S，邊的標(biāo)號來自CFG為Y或N
3. 遍歷S，對每條邊m->n，先在PDOMTree中找到最低公共祖先p（如果m為根結(jié)點(diǎn)則為m，否則為m的父結(jié)點(diǎn)），再將PDOMTree中p到n路徑上每個結(jié)點(diǎn)（p和entry除外）x加入CDG，并添加邊m->x，其邊標(biāo)號同m->n
4. 對CDG的每個內(nèi)部結(jié)點(diǎn)，若存在Y邊，則新建一個區(qū)域結(jié)點(diǎn)，連接所有Y邊對應(yīng)的子結(jié)點(diǎn)；若存在N結(jié)點(diǎn)，則新建一個區(qū)域結(jié)點(diǎn)，連接所有N邊對應(yīng)的子結(jié)點(diǎn)
【應(yīng)用】
對于控制依賴于同一結(jié)點(diǎn)的所有結(jié)點(diǎn)，只要它們之間沒有數(shù)據(jù)依賴關(guān)系，就可以并行執(zhí)行
posted on 2023-09-06 23:07
春秋十二月 閱讀(135)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler