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