데이터 흐름 분석

데이터 흐름 분석(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}$ < ...이 없다.) 전이 함수와 상한 연산의 조합은 이 부분 순서에 대하여 단조함수여야 한다. 단조성은 각 반복 시에 값이 같은 상태로 유지되거나 더 커질 것이라는 것을 보장하고, 이때 값 도메인의 유한한 높이는 이것이 무한하게 증가하지 못하게 한다. 그래서 우리는 궁극적으로 모든 x에 대해서 고정점인 T(x) = x라는 상황에 도달하게 된다.

작업 목록 접근

블록의 선행 노드들의 나가는 상태가 변하지 않는다면 그 블록의 들어오는 상태가 변하지 않는다는 사실을 알면 알고리즘을 개선할 수 있다. 그러므로 우리는 작업 목록을 소개한다: 이것은 아직 처리해야 하는 블록들의 목록이다. 블록의 나가는 상태가 바뀔 때마다, 그 블록의 후행 노드들을 작업 목록에 추가한다. 각 반복에서 처리하는 블록은 작업 목록에서 제거한다. 그리고 그 블록의 나가는 상태를 계산한다. 만약 나가는 상태가 변한다면, 그 블록의 후행 노드들을 작업 목록에 추가한다. 효율을 위해, 한 블록은 작업 목록에 딱 한번만 존재한다.

알고리즘은 작업 목록에서 블록을 생성하는 정보를 넣음으로써 시작된다. 이것은 작업 목록이 비면 종료된다.

순서 문제

데이터 흐름 방정식을 반복적으로 푸는 것의 효율성은 지역 노드가 방문되는 순서에 영향을 받는다. 게다가, 이것은 데이터 흐름 방정식이 정방향 데이터 흐름 분석에 사용되는지 역방향 데이터 흐름 분석에 사용되는지에 의존한다. 직관적으로, 정방향 흐름 문제에서, 이것은 블록의 선행 노드들들이 블록 이전에 진행되었다면 더 빠르며, 이후 반복은 최신 정보를 사용한다. 루프가 없는 경우, 각 블록을 단 한번만 진행하면서 정확한 나가는 상태들이 계산되는 방식으로 블록을 정렬하는 것은 가능하다.

아래는, 데이터 흐름 방정식을 푸는 몇 가지 반복 순서이다. (CFG의 반복 순서에 관련된 것은 트리의 트리 순회이다.).

• 랜덤 순서 (Random order) - 이 반복 순서는 데이터 흐름 방정식이 정방향 데이터 흐름 문제를 푸는지, 역방향 데이터 흐름 문제를 푸는지에 대해서 알지 못한다. 그러므로 성능은 특화된 반복 순서와 비교해서 상대적으로 덜어진다.

• 후위 순서 - 이것은 역방향 데이터 흐름 문제를 위한 일반적인 반복 순서이다. 후위 반복에서 노드는 모든 계승자 노드가 방문된 후에 방문된다. 일반적으로, 후위 반복은 깊이 우선 전략에서 구현된다.

• 역 후위 순서 - 이것은 정방향 데이터 흐름 문제를 위한 일반적인 반복 순서이다. 역 후위 순서 반복에서 노드는 계승자가 백 엣지에 의해 도달하는 경우를 제외하고는 모든 계승자 노드들이 방문되기 전에 방문된다.

초기화

들어오는 상태들의 초기 값은 정확한 결과를 얻기 위해 중요하다. 만약 결과들이 컴파일러 최적화에 사용된다면, 이것들은 보수적인 정보를 제공해야 한다. 즉, 정보를 적용할 때 프로그램은 의미를 바꿔서는 안된다. 고정점 알고리즘의 반복은 최대값 요소의 방향에서 값을 갖는다.

예시

아래는 데이터 흐름 분석으로 계산되는 컴퓨터 프로그램들의 속성들의 예시들이다. 데이터 흐름 분석으로 계산되는 속성들은 일반적으로 실제 속성들의 근사치라는 것을 기억하자. 이것은 데이터 흐름 분석이 프로그램의 정확한 제어 흐름 시뮬레이션 없이 CFG의 구문론적 구조에서 동작하기 때문이다. 그러나 실생활에 유용하기 위해서, 데이터 흐름 분석 알고리즘은 일반적으로 실제 프로그램 속성들의 근사치를 계산하도록 설계되었다.

정방향 분석

도달 정의 분석은 각 프로그램 포인트에서 잠재적으로 이 프로그램의 포인트에 닿을 수 있는 정의들의 집합을 계산한다.

역방향 분석

라이브 변수 분석은 각 프로그램 지점에서 다음 쓰기 갱신 전에, 잠재적으로 추후에 읽어지는 변수를 계산한다. 결과는 일반적으로 불필요한 코드 제거에서 값이 나중에 사용되지 않는 변수로 정해진 구문을 제거하기 위해 사용된다.

블록의 나가는 상태는 블록의 끝에 살아 있는 변수들의 집합이다. 이것의 들어오는 상태는 시작 시에 살아 있는 변수들의 집합이다. 나가는 상태는 블록 계승자의 들어오는 상태의 연합이다. 구문의 전이 함수는 dead 변수들을 만들면서 적용된다. 그리고 살아있는 것을 읽는 변수들을 만든다.

초기 코드:

역방향 코드:

c가 써졌기 때문에, b3의 들어오는 상태는 단지 b와 d를 포함한다. b1의 나가는 상태는 b2와 b3의 들어오는 상태들의 연합이다. c가 구문 직후에 살아있지 않기 때문에 b2에서 c의 정의는 제거될 수 있다.

데이터 흐름 방정식을 푸는 것은 모든 들어오는 상태와 나가는 상태를 빈 집합으로 초기화하면서 시작된다. 작업 목록은 작업 목록에서 종료 지점(b3)을 삽입함으로써 초기화된다. 이것의 계산된 들어오는 상태는 이전의 것과 다르며, 선행 노드들 b1과 b2는 삽입되고, 진행은 계속된다. 과정은 아래의 테이블로 요약된다.

과정	나가는 상태	이전의 들어오는 상태	새로운 들어오는 상태	작업 목록
b3	{}	{}	{b,d}	(b1,b2)
b1	{b,d}	{}	{}	(b2)
b2	{b,d}	{}	{a,b}	(b1)
b1	{a,b,d}	{}	{}	()

b1이 b1을 두 번 진행하게 강요된 b2 이전에 리스트에 들어간다는 것을 기억하자. (b1은 b2의 선행 노드들로써 다시 들어간다.) b1 이전에 b2를 삽입하는 것은 이전 완료에서 허락된다.

빈 집합으로 초기화하는 것은 낙관적인 초기화이다. 모든 값들은 죽은 상태로 시작된다. 나가는 상태들은 비록 들어오는 상태들보다 적다 하더라도 다음으로의 반복을 꺼린다는 것을 기억하자. 들어오는 상태가 빈 집합으로 시작되기 때문에, 추후의 반복에서만 커질 수 있다.

민감도

데이터 흐름 분석은 본질적으로 흐름에 민감하다. 그리고 비록 경로에 민감한 분석을 산출하는 데이터 흐름 방정식을 정의할 수도 있지만 일반적으로 경로에 민감하지 않다.

• 흐름에 민감한 (flow-sensitive) 분석은 프로그램에서 구문들의 순서를 고려한다. 예를 들면 흐름에 민감하지 않은 분석은 포인터로 "같은 위치를 가리키는 변수 x와 y"를 결정할 수 있다. 흐름에 민감한 분석은 "구문 20 이후로 변수 x와 y를 같은 위치를 참조"하게 결정할 수 있다.
• 경로에 민감한 (path-sensitive) 분석은 조건 분기 명령의 예상에 따라 다른 분석 정보를 계산한다. 예를 들면, 분기가 조건 x>0를 포함할 때, 완료되지 않는다면 분석은 x<=0라고 가정할 것이고, 대상의 분기는 x>0를 갖고 있다고 가정할 것이다.
• 문맥에 민감한 (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.
• Khedker, Uday P. Sanyal, Amitabha Karkare, Bageshri. Data Flow Analysis: Theory and Practice[1], CRC Press (Taylor and Francis Group). 2009.
• Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Principles of Program Analysis. Springer. 2005.