Dataflow Analysis

Live Variable Analysis

=> X가 이전에 defined 되었을때 X가 나중에 사용되는지 확인

 

 

OUT은 successor들의 IN의 합집합

IN은 USE와 (OUT - DEF)의 합집합

 

- register allocation의 live range를 알아보는 것

- scheduling

- dead code 삭제

- Def-Use Chains, Use-Def Chains

- out edges: successor nodes의 leading edge

- in edges: predecessor nodes의 coming edge

 

Reaching Definitions

=> node가 x를 쓸때 누가 x를 define했는지 찾음

 

unambigous - explicitly define

ambigous - may or may not define

 

IN은 predecessor들의 OUT의 합집합

OUT은 GEN과 (IN-KILL)의 합집합

 

- Constant Propagation

d: a=c

u: t=a op b

u에 reach 할수 있는 다른 definition이 없다면

t = c op b

 

- Constant Folding

d: t = a op b

a, b가 상수라면 t도 상수로 replace 가능

 

- Copy Propagation

d: a = z where a and z are registers

u: t = a op b

t = z op b

d와 u사이에 path가 없어야 됨

 

 

Available Expression

=> 이미 계산된 expression 재사용

IN은 Predecessor들의 OUT의 교집합

OUT은 GEN과 (IN-KILL)의 합집합

 

- CSE(Common Sub-expression Elimination)

동일한 operation이 반복될 경우 몇몇 중복된 연산을 제거함