Use-Def Analysis and SSA (Static Single Assignment)

Use-Def Analysis and SSA (Static Single Assignment)

Use-Definition chains (ud chains)

Each use of a variable is linked to all assginments that reach it

Definition-Use chains (du chains)

Each assignment to a variable is linked to all uses of it

SSA (Static Single Assignment Form)

UD를 좀더 축약한 것이다.

Definition: each assignment to a variable is given a unique name

All of the uses reached by that assignment are renamed

Easy for straight-line code

What about control flow? ==> X nodes

Dominator

만약 어떤 노드 x가 Entry에서 y까지 가는 모든 path에 의해서 반드시 호출 되어지는 것이라면

그것을 우리는 y의 dominator x라고 부른다.

" x dominates y " means  

x is always executed before y is executed 

▶ 특성

- 모든 노들은 그것 스스로 dominate 하다.

- 만약, x가 y를  dominate하고, y가 z를 dominate 한다면, x는 z를 dominate 한다.

(transitivity 성질을 만족함)

- x y 둘다 z를 dominate 한다면, 

Strictly dominating

x가 y의 strictly dominator 라고 한다면, x는 y를 domiante 한다 하지만 x는 y가 아니라는 것이다.

Dominance Frontiers

X 는 Y의 predecessor들중 한개를 dominate한다. 하지만, x는 y를 strictly dominate 하지 않아야 한다.]

그냥 dominate라고 보면, 자기 자신도 포함대므로, x=y를 허용하게 된다. 그러면 정의가 꼬인다.

DF(2) = {6} 이다.

풀어서 써보면,

2에 대한 Dominance Frontier를 구하는 것이다.

2는 2,3,4,5들을 dominate 한다.