版權(quán)聲明：本文為CSDN博主「ashimida@」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/lidan113lidan/article/details/119336214

更多內(nèi)容可關(guān)注微信公眾號??

一、需要了解的基本概念

在gcc優(yōu)化的過程中,不論是循環(huán)的優(yōu)化還是數(shù)據(jù)流分析,支配樹在其中都起到至關(guān)重要的作用:

? *?對于循環(huán)來說,支配樹對找出代碼中的循環(huán)非常有用

? *?對數(shù)據(jù)流分析來說,支配樹對計算SSA_NAME中的phi函數(shù)插入點十分重要

支配樹中的主要概念包括:

? 1)?必經(jīng)結(jié)點(Dominator,又稱支配結(jié)點):?如果從(如函數(shù)的)起始節(jié)點S0到結(jié)點n的所有有效路徑都經(jīng)過結(jié)點d,?那么結(jié)點d則成為結(jié)點n的必經(jīng)結(jié)點,同時每一個結(jié)點都是自己的必經(jīng)結(jié)點

??????簡單的說,必經(jīng)結(jié)點的意思就是,從S0開始,如果控制流走到了n,那么在此之前其一定走過了結(jié)點d,?此時記為dom(n) = d;

? 2)?嚴(yán)格必經(jīng)結(jié)點:?若d是n的必經(jīng)結(jié)點,且d!=n,則d是n的嚴(yán)格必經(jīng)結(jié)點;

? 3)?直接必經(jīng)結(jié)點(Immediate Dominator,又稱直接支配結(jié)點):

? ? ? 首先對于畢竟節(jié)點有定理如下:?如果d,e都是n的必經(jīng)結(jié)點,則d一定是e的必經(jīng)結(jié)點或e一定是d的必經(jīng)結(jié)點;

? ? ? 而直接必經(jīng)結(jié)點的定義為:?若i是n的嚴(yán)格必經(jīng)結(jié)點,且i不是n的其他必經(jīng)結(jié)點的必經(jīng)結(jié)點,則i是n的直接必經(jīng)結(jié)點;

? ? ? 簡單說就是 i是距離n最近的n的(非!=n的)必經(jīng)結(jié)點,?即為 idom(n) = i;

? 4)?必經(jīng)結(jié)點樹(Dominator Tree,又稱支配樹):

? ? ? 一棵樹中包含圖中的所有節(jié)點,?但只為每個做一條從其直接支配節(jié)點到自身的邊(也就是對于所有節(jié)點n,只有 idom(n) => n的邊),?這樣構(gòu)成的一顆樹即為此圖的必經(jīng)結(jié)點樹;

? ? ? 對于流圖來說,?由于其中的每一個結(jié)點都至少有一個必經(jīng)結(jié)點(即起始結(jié)點),?且每個結(jié)點都只能有一個直接必經(jīng)結(jié)點,故一個流圖一定能畫出其對應(yīng)的必經(jīng)結(jié)點樹.且若流圖中每個節(jié)點均可達(dá),則對應(yīng)的必經(jīng)結(jié)點樹中的每個結(jié)點也必可達(dá).?以[1] C18.1.2為例,其中流圖和其對應(yīng)的支配樹的關(guān)系如圖:

? ? ?5)?必經(jīng)結(jié)點邊界(Dominance Frontier,?又稱支配結(jié)點邊界):?結(jié)點x的必經(jīng)結(jié)點邊界是所有符合下面條件的結(jié)點w的集合: x是w前驅(qū)的必經(jīng)結(jié)點,但不是w的嚴(yán)格必經(jīng)結(jié)點;

? ? ? ? 簡單說就是:?首先支配結(jié)點邊界是針對某個結(jié)點來說,?其是多個節(jié)點的集合;?支配結(jié)點是當(dāng)前結(jié)點和當(dāng)前結(jié)點前驅(qū)的其他后繼結(jié)點可能的控制流匯集處(也是在轉(zhuǎn)SSA過程中需要插入phi函數(shù)的位置),?以[1] C19.1.2為例:

?? ?? ? 其中結(jié)點5的必經(jīng)結(jié)點為{4,5,12,13},?這四個結(jié)點都是結(jié)點5和其他結(jié)點控制流的匯集處;

---

二、gcc中支配樹相關(guān)結(jié)構(gòu)體

? ? 支配樹是針對流圖的,而在gcc中則是針對函數(shù)的控制流圖(CFG)的,?故一個函數(shù)的支配樹信息最終是保存在函數(shù)內(nèi)的(實際上是各個bb->dom中),?在gcc中和支配樹相關(guān)的結(jié)構(gòu)體有三個:

? ? 1) enum dom_state:?此枚舉型中記錄當(dāng)前函數(shù)中支配樹的狀態(tài)

enum dom_state {DOM_NONE,????????? ? ??/*?代表當(dāng)前函數(shù)的支配樹還沒有計算 *DOM_NO_FAST_QUERY,? ? ?/* 代表當(dāng)前函數(shù)的支配樹已經(jīng)計算好了(記錄在各個bb->dom中), 但尚未建立快速查詢 */DOM_OK? ? ? ??? ? ?? ? /*?代表當(dāng)前函數(shù)支配樹的快速查詢也建立好了(更新好了bb->dom.dfs_num_in/out字段), 只有支配樹和快速查詢均建立好了才會有DOM_OK狀態(tài) */ };

? ? 2) class dom_info:?此類可以保存一個支配樹的完整信息,但在gcc中通常都是臨時的保存支配樹算法的結(jié)果(最終結(jié)果保存在bb->dom中)

class dom_info {......TBB *m_dfs_parent; /* Lengauer-Tarjan 算法中需要借助DFS來實現(xiàn)高效的支配樹計算,而此結(jié)構(gòu)體實際上是一個數(shù)組,其下標(biāo)為函數(shù)CFG在DFS下每個結(jié)點的父節(jié)點編號 */TBB *m_key;TBB *m_path_min;TBB *m_bucket;TBB *m_next_bucket;TBB *m_dom; /* 這里同樣是一個數(shù)組, 其中m_dom[x] 記錄DFS中編號為x的結(jié)點的直接必經(jīng)結(jié)點編號 */TBB *m_set_chain;unsigned int *m_set_size;TBB *m_set_child;TBB *m_dfs_order; /* 記錄基本塊在DFS遍歷中的編號,在DFS中編號從1開始 */TBB *m_dfs_last; /* 指向 m_dfs_order中最后一個bb */basic_block *m_dfs_to_bb; /* 記錄DFS中每個節(jié)點對應(yīng)的bb的 basic_block 結(jié)構(gòu)體指針 */unsigned int m_nodes;bitmap m_fake_exit_edge;unsigned m_n_basic_blocks; /* 記錄當(dāng)前支配樹中的結(jié)點個數(shù),實際上來自函數(shù)中基本塊的個數(shù) */bool m_reverse; /* 代表當(dāng)前記錄的是否為后序支配信息, gcc中可以計算支配樹和后序支配樹兩種, 此值來自參數(shù) CDI_DOMINATORS/CDI_POST_DOMINATORS */basic_block m_start_block; /* 記錄當(dāng)前函數(shù)的入口bb */basic_block m_end_block; /* 記錄當(dāng)前函數(shù)的出口bb */ };

? ? 3) struct et_node:?此結(jié)構(gòu)體實際上是代表元素樹(Element Tree)中一個結(jié)點信息的,而在gcc中,每個bb均通過此元素來保存其支配樹結(jié)點

struct basic_block_def {......struct et_node * dom[2]; /* 在基本塊(bb)中, dom[0/1]分別記錄此bb在其支配樹和后序支配樹(若有)中的結(jié)點信息, 整個函數(shù)的支配樹信息實際上就是記錄在由入口bb開始的各個bb的dom中 */...... }struct et_node {void *data; /* 在支配樹中,data指向當(dāng)前支配結(jié)點對應(yīng)的基本塊bb的指針 */int dfs_num_in, dfs_num_out; /* 記錄此結(jié)點在其對應(yīng)的樹結(jié)點的DFS遍歷過程中,進(jìn)/出此結(jié)點時遍歷到的結(jié)點編號. 對于支配樹來說,這兩個字段負(fù)責(zé)支配樹的快速查詢 */struct et_node *father; /* 記錄當(dāng)前節(jié)點的父節(jié)點,在支配樹中當(dāng)前節(jié)點的父節(jié)點為其直接支配節(jié)點(idom)*/struct et_node *son; /* 當(dāng)前節(jié)點的第一個子節(jié)點指針,在支配樹中則是最后插入的子節(jié)點 */struct et_node *left; /* 當(dāng)前結(jié)點的左右兄弟結(jié)點 */struct et_node *right; /* The brothers of the node. */struct et_occ *rightmost_occ; /* The rightmost occurrence. */struct et_occ *parent_occ; /* The occurrence of the parent node. */ };

---

三、gcc中支配樹的計算

? ? 在gcc中是通過calculate_dominance_info來計算當(dāng)前函數(shù)的支配樹的,?在調(diào)用此函數(shù)之前要求當(dāng)前全局的cfun記錄當(dāng)前要計算的函數(shù),?計算結(jié)果會以一個個支配結(jié)點的形式記錄在當(dāng)前函數(shù)的各個基本塊的bb->dom中,?而并不是以一個支配樹結(jié)構(gòu)體(如dom_info)保存的,函數(shù)定義如下:

/*此函數(shù)為當(dāng)前函數(shù)cfun計算[后序]支配樹信息(dir決定是否為后序),計算結(jié)果以支配結(jié)點的方式保存到cfun的各個bb->dom中,并將當(dāng)前函數(shù)的支配樹計算狀態(tài)更新到 cfun->cfg->x_dom_computed (即dom_computed)中;若此函數(shù)已計算了支配樹,則此函數(shù)需重新計算并驗證之前計算的支配樹的正確性,如果二者不匹配直接報錯,匹配則返回不做任何修改. */ void calculate_dominance_info (cdi_direction dir) {unsigned int dir_index = dom_convert_dir_to_idx (dir); /* 先確定本次是要計算支配樹(dir=0)還是后序支配樹(dir=1),后序均以后序支配樹舉例 */if (dom_computed[dir_index] == DOM_OK) /* 若當(dāng)前函數(shù)已有支配樹,則對當(dāng)前函數(shù)重新計算支配樹信息,并和原有的比較看是否正確 */{checking_verify_dominators (dir); /* 重新計算的支配樹(dom_info)和函數(shù)中已有的支配樹(各bb->dom)信息匹配,則直接返回 */return;}if (!dom_info_available_p (dir)) /* 若當(dāng)前函數(shù)的支配樹是完全不可用的(DOM_NONE),則在此循環(huán)中重新計算支配樹 */{gcc_assert (!n_bbs_in_dom_tree[dir_index]); /* 支配樹未計算時,cfg中支配節(jié)點數(shù)量應(yīng)給為0 */basic_block b;FOR_ALL_BB_FN (b, cfun) /* 在開始計算前先為當(dāng)前函數(shù)cfun的每個bb都分配一個元素樹結(jié)點,以存儲其在支配樹中的支配結(jié)點的信息 */b->dom[dir_index] = et_new_tree (b);n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun); /* 在cfg中記錄當(dāng)前支配樹中結(jié)點的個數(shù),支配樹中結(jié)點個數(shù)正常和函數(shù)中的結(jié)點個數(shù)是相同的 */dom_info di (cfun, dir); /* 創(chuàng)建并初始化一個臨時的dom_info類,用來先保存整個支配樹的計算結(jié)果,參數(shù)是要計算的函數(shù)和方向(支配樹or后序支配樹) */di.calc_dfs_tree (); /* DFS遍歷當(dāng)前函數(shù)中所有的結(jié)點,結(jié)果都存在這個臨時的dom_info di中, 根據(jù)Lengauer-Tarjan 算法,快速計算必經(jīng)節(jié)點的方法中首先就是要構(gòu)建DFS */di.calc_idoms (); /* 按照LT算法, 計算出當(dāng)前函數(shù)所有bb的直接支配結(jié)點,并將其保存在di.m_dom數(shù)組中 */FOR_EACH_BB_FN (b, cfun) /* 遍歷當(dāng)前函數(shù)的所有bb, 將計算出的支配樹信息轉(zhuǎn)換為一個個支配結(jié)點的形式保存到當(dāng)前函數(shù)的各個bb->dom中 */{if (basic_block d = di.get_idom (b)) /* 從dom_info di中獲取基本塊b的直接支配節(jié)點 d */et_set_father (b->dom[dir_index], d->dom[dir_index]); /* 將idom(b) = d 這個信息記錄到b/d兩個基本塊的 ->dom中(分別更新了d->dom[0]->son/ b->dom[0]->father等信息) */}dom_computed[dir_index] = DOM_NO_FAST_QUERY; /* 標(biāo)記當(dāng)前函數(shù)的支配樹狀態(tài)為尚未開啟快速查詢 */}else /* 若當(dāng)前函數(shù)的支配樹已經(jīng)計算,只是尚未建立快速查詢,則這里也是要重算并驗證一遍支配樹是否正確 */checking_verify_dominators (dir); /* 重算并驗證的流程實際上和if中的流程十分類似,只是最后的填充bb->dom變?yōu)榱藢Ρ仁欠裾_ */compute_dom_fast_query (dir); /* 建立支配樹的快速查詢,實際上只是修改了各個bb->dom的 dfs_num_in/out字段, 以便于快速查找當(dāng)前bb在dfs中包含的子結(jié)點編號 */ }

---

4. gcc中支配結(jié)點邊界的計算

? ? 在gcc中支配結(jié)點邊界的信息是通過compute_dominance_frontiers函數(shù)計算的,其定義如下:

void compute_dominance_frontiers (bitmap_head *frontiers) {timevar_push (TV_DOM_FRONTIERS);compute_dominance_frontiers_1 (frontiers);timevar_pop (TV_DOM_FRONTIERS); }

? ? 其具體實現(xiàn)就不展開了,此函數(shù)最關(guān)鍵的就是需要知道其返回的是一個n*n的二維數(shù)組,記錄在frontiers指向的一個bitmap中, n為當(dāng)前函數(shù)中基本塊的個數(shù),?frontiers[x][y] = 1;?則代表對于基本塊 x,?基本塊y是其支配結(jié)點邊界中的一個結(jié)點;

---

參考資料:

[1] 《現(xiàn)代編譯原理—C語言描述》

總結(jié)

以上是生活随笔為你收集整理的静态单赋值(一)—gcc中的支配树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。