---
# System prepended metadata

title: Dominator

---

[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不是**    
![image](https://hackmd.io/_uploads/Sku0Ec34A.png)        

定義:    
若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    
![image](https://hackmd.io/_uploads/HJsfPq240.png)        

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

原flow-control graph:    
![image](https://hackmd.io/_uploads/r1HUwqnNR.png)    

畫成dominate tree:    
![image](https://hackmd.io/_uploads/Skztv92ER.png)    


### 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**    




