데이터 흐름 분석

**데이터 흐름 분석**(Data-flow analysis)은 컴퓨터 프로그램에서 다양한 지점에서 계산된 가능한 값들의 집합에 대한 정보를 모으는 기법이다. 프로그램의 제어 흐름 그래프(CFG)는 프로그램의 이러한 값들에서 변수에 저장되기 위해서는 어떤 값이 전파돼야 하는지를 결정하는데 사용된다. 모은 정보는 종종 컴파일러가 프로그램을 최적화할 때 사용된다. 데이터 흐름 분석의 고전적인 예로 도달 정의(reaching definition)가 있다.

프로그램의 데이터 흐름 분석을 수행하는 간단한 방법은 제어 흐름 그래프의 각 정점에 대해 데이터 흐름 방정식을 세우고, 전체 연립 방정식이 수렴할 때까지, 즉 고정점에 도달할 때까지 각 정점에서 입력에 대한 출력을 반복적으로 계산하여 푸는 것이다. 이 일반적인 접근법은 개리 킬달에 의해 개발되었다.

## 기본 원리
데이터 흐름 분석은 프로그램에 정의된 변수들이 어떻게 사용되는지에 관한 정보를 모으는 과정이다. 분석은 대상 함수 안의 각각의 지점에서 특정한 정보를 모으려고 시도한다. 보통, 기본 블록의 주변에서 이 정보를 얻는 것으로 충분한데, 왜냐하면 기본 블록에서 각 지점의 정보를 계산하는 것이 쉽기 때문이다. 정방향 흐름 분석 시에, 한 블록에 대한 종료 상태는 블록의 진입 상태에 대한 함수로 나타낸다. 이 함수는 블록 안에 있는 각 구문들의 영향을 조합한 것이다. 블록의 진입 상태는 그 블록의 (그래프 상의) 선행 노드들의 종료 상태에 대한 함수로 나타낸다. 이를 통해 데이터 흐름 방정식의 집합을 얻을 수 있다.

각 블록 b에서:

:  out_b = trans_b (in_b) 
:  in_b = join_{p \in pred_b}(out_p) 

여기서,  trans_b  은 블록 b의 **전이 함수**이다. 이것은 진입 상태 in_b에 적용되어 종료 상태 out_b을 만들어낸다. 상한 연산 join은 b의 선행 노드 p \in pred_b 의 종료 상태들을 조합하여 b의 진입 상태를 만들어 낸다.

이 방정식의 집합을 풀고 나면, 블록의 진입과 종료 상태는 블록 주변의 프로그램의 성질을 추론하는데 사용할 수 있다. 각 구문의 전이 함수는 기본 블록 안의 각 지점에 대한 정보를 얻기 위해 따로 적용될 수 있다.

각각의 데이터 흐름 분석은 특정한 전이 함수와 상한 연산을 갖는다. 어떤 경우 역방향 흐름 분석이 필요할 수도 있다. 이 경우 전이 함수는 종료 상태에 적용되어 진입 상태를 만들어내고, 상한 연산은 후행 노드의 진입 상태들을 조합하여 종료 상태를 만들어내는 것 외에는 같은 방법으로 수행된다.

엔트리 포인트는 (정방향 흐름에서) 중요한 역할을 수행한다. 이는 선행 노드를 갖지 않기 때문에, 이것의 진입 상태는 분석 시작 시에 잘 정의되어 있어야 한다. 예를 들면, 일반적인 값을 갖는 지역 변수의 집합은 빈 집합이다.

만약 제어 흐름 그래프가 싸이클을 갖지 않으면 (즉, 함수 안에 명시적 또는 묵시적인 반복문이 없으면), 방정식은 자명하게 풀린다. 그러면 제어 흐름 그래프에 위상 정렬을 적용할 수 있다. 이 정렬 순서로 진행하면, 진입 상태는 각 블록의 시작에서 계산될 수 있는데, 왜냐하면 블록의 모든 선행 노드들이 이미 처리되어서 그들의 종료 상태를 구할 수 있기 때문이다. 만약 제어 흐름 그래프가 사이클을 가지면, 더 발전된 알고리즘이 필요하다.

## 반복 알고리즘
데이터 흐름 방정식을 푸는 가장 흔한 방법은 반복 알고리즘을 사용하는 것이다. 이것은 각 블록에 들어오는 상태의 근사치로 시작한다. 나가는 상태는 들어오는 상태에 전이 함수를 적용함으로써 계산된다. 이를 통해 들어오는 상태들은 상한 연산을 적용하여 갱신된다. 이 두 단계들은 **고정점(fixpoint)**에 도달할 때까지 반복된다. 들어오는 상태(그리고 이로부터 나가는 상태)에서 상황은 바뀌지 않는다.

데이터 흐름 방정식을 푸는 기본 알고리즘은 **라운드-로빈 반복 알고리즘**이다.

: for *i* ← 1 to *N*
:: *initialize node i*
: while (*sets are still changing*)
:: for *i* ← 1 to *N*
::: *recompute sets at node i*

### 수렴
사용되기 위해서는, 반복적인 접근은 실제로 고정점에 도달해야 한다. 이는 상태의 값 도메인과 전이 함수, 그리고 상한 연산의 조합에 제약을 도입하여 보장할 수 있다.

값 도메인은 유한한 높이를 가진 (**finite height**) 부분 순서여야 한다. (즉, 무한한 증가하는 체인 x_1 x_2 0*를 포함할 때, 완료되지 않는다면 분석은 *x0*를 갖고 있다고 가정할 것이다.
* *'문맥에 민감한 (context-sensitive)*' 분석은 절차 사이의 분석으로서 함수 호출의 대상을 분석할 때 호출 문맥을 고려한다. 특히, 문맥 정보를 사용하는 것은 원본 호출 지점으로 *jump back* 한다. 반면 정보 없이는 분석 정보는 가능한 호출 위치로 전파되어야 하며, 정확성을 잃는다.

== 데이터 흐름 분석 목록 ==
* [[도달 정의]]
* [[전파 상수]]

== 같이 보기 ==
* [[XLT86]]
* [[제어 흐름 분석]]

== 각주 ==


== 더 읽어보기 ==
* Cooper, Keith D. and Torczon, Linda. *Engineering a Compiler*. Morgan Kaufmann. 2005.
* Muchnick, Steven S. *Advanced Compiler Design and Implementation*. Morgan Kaufmann. 1997.
* Hecht, Matthew S. *Flow Analysis of Computer Programs*. Elsevier North-Holland Inc. 1977.
* [https://web.archive.org/web/20150625233755/http://www.cse.iitb.ac.in/~uday/dfaBook-web/ Khedker, Uday P. Sanyal, Amitabha Karkare, Bageshri. *Data Flow Analysis: Theory and Practice*][https://web.archive.org/web/20150625233755/http://www.cse.iitb.ac.in/~uday/dfaBook-web/], CRC Press (Taylor and Francis Group). 2009.
* Flemming Nielson, Hanne Riis Nielson, Chris Hankin. *Principles of Program Analysis''. Springer. 2005.


분류:프로그램 분석
분류:컴파일러 최적화