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