[toc]

# Dominator
https://en.wikipedia.org/wiki/Dominator_(graph_theory)

## 定義
Dominator是control-flow graph上node之間的描述關係
control flow graph有entry node(資料流最初的node).

### d dominates n (符號:d>>n)
代表的意思是所有從entry node開始到n的path都必定經過d

### strictly dominate
根據定義可知所有v都dominate自己
**而a strictly dominates b代表的情況是a!=b且a>>b的情況**

### immediate domindate
immediate dominate:
這個用圖好解釋:
這個圖中1跟2都dominiats 3，**但是2是immediate dominate 3但1不是**

定義:
若a immedidate dominates b則滿足兩個條件
1. a strictly dominiates b
2. a doesn't dominiate other d which d strictly >> b

### dominance frontier of a node d
白話來說就是d dominate的邊界(不屬於被d dominiate的範圍)

定義是set of nodes {ni},
d dominiate每個ni的父節點(immdiate predecessor)
但是d本身不dominiate ni

像這張圖， dominiace frontier (d) = node 3

### dominator tree
tree中的每個節點的child都是被node immediate dominate

原flow-control graph:

畫成dominate tree:

### post dominance
跟dominance很像，只是entry node變成exit node

z post-dominate n:
所有由n開始到exit node的path都通過z
z稱為n的post dominator

immediate post dominace:
n的post-dominator但沒有strictly postdominate 其他n的post-dominator

## applications
A number of compiler optimizations can also benefit from dominators

postdominace frontiers:
an efficient method of **computing control dependence**