6. Data Flow Model

Finite Model의 한계

변수의 값이 언제, 어디서 정의되고 변화되는지 알 수 없다 -> DFG 사용

DFG (Data Flow Graph)

1. Definition-Use pair (DU pair)
   Definition : 변수의 값이 정해지는 곳(선언, 초기화, 파라미터로부터 전달 등)
   Use : 변수의 값이 사용되는 곳 (분기문, 파라미터에 전달, 리턴 등)
   변수의 Definition과 Use의 위치를 파악해서 묶은 것을 DU pair라고 한다.
   definition-use path는 definition과 use 사이의 구간

2. Definition-clear
   definition이 중첩되는 경우, 이전 definition은 kill된다.
   definition-clear path는 definition과 clear 사이의 구간

3.Data Dependence Graph

• Node : basic block
• Edge : du pair, 변수 이름을 label로 명시
• Pre-dominator : 특정 노드에 진입하기 전에 꼭 지나쳐야 하는 노드를 뜻함
• Post-dominator : 특정 노드를 지나서 꼭 들러야 하는 노드를 뜻함
• Control-dependent on : 분기가 있는 pre-dominator를 뜻함

4. 장점

• iterative한 알고리즘에 적용할 수 있다.
• 적용 가능성이 높다

5. 단점

• 유효한 경로와 비유효한 경로를 구분할 수 없다.