Dominator tree @ A simple and fast dominance algorithm

在 compiler 中,為了要分析出 data 彼此間的相依關係, 可以透過 dominator tree 的方式來解決. 假設 a(b) & b(a) = b dom in a & a dom in b; #a = b, a(b) & b(c) = b dom in a & c dom in b; # a(c) c dom in a a(b) & c(b) = b dom in a & b dom in a; # a != b ... 當然也可以解決 loop 的問題, 之後可建立起 block graph + SSA(static single assignment) graph, 來做些 merge 跟 code reduction 的動作.

Dominator tree

View more presentations from sean chen.

refs: ^ Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). "A Simple, Fast Dominance Algorithm". http://www.hipersoft.rice.edu/grads/publications/dom14.pdf. http://en.wikipedia.org/wiki/Dominator_%28graph_theory%29