Dataflow Analysis

DataFlow Analysis

대표적인 알고리즘 3개를 설명한다.

Live Variables Analysis 

---

정의: 현재 변수 값이 다른곳에서 사용될 것인지를 알아보는 것

아래와 같은 데이터를 모아야 함.

USE: 변수가 외부에서 사용되는 것을 말한다, 하나의 베이직 블럭에서

DEF: 하나의 베이직 블럭에서 정의되는것을 말함.

IN: 시작 포인트에서의 변수들이 살아 있는지를 말한다.

OUT: 변수들이 살아 있는지를 말한다.

Reaching Definition Analysis 

---

정의: 어떤 변수의 정의가 특정 위치까지 도달 하는지를 분석함. 

이것의 개념은 최적화 뿐만아니라, 각종 분석에 많이 사용되는 개념임.

요약: 

Forward 방식

Inner Analysis

GEN - 해당 BB에서 생성되는 정의들의 집합

KILL - 모든 BB에서 해당 GEN에 의해서 사라지는 정의들의 집합

Outer Analysis

IN - 모든 이전의 OUT들을 더함

OUT - GEN + ( IN - KILL )

Available Expressions 

---

정의: 이미 계산된 expression을 재사용 하자.

E_GEN의 생성은 G + (E_GEN(X) - K) 이다.