데이터 흐름 분석

소프트웨어 수치해석 마지막 수정: 2026-09-01 04:38:06

1. 개요[편집]

데이터 흐름 분석 Dataflow Analysis
틀을 세운 사람	Gary Kildall (1973, POPL)
구성 요소	격자 $L$ · 단조 전달함수 $f_B$ · 합류 연산 $\sqcap$
답의 정체	연립방정식의 최대 고정점(MFP)
이상적 답	모든 경로 합류(MOP) — 일반적으로 계산 불가능
둘이 같아지는 조건	전달함수의 분배성
수렴 속도	비트벡터 + 환원가능 그래프면 $d+2$ 회 순회
현대적 형태	SSA 위의 희소 분석 · 추상해석의 특수 사례

“이 변수, 여기서 값이 뭐예요?”에 프로그램을 실행하지 않고 답하려는 시도. 정직한 답은 언제나 “경우에 따라 다릅니다”이고, 그걸 격자 위에 올려 계산 가능하게 만든 것이 이 분야다.

데이터 흐름 분석(dataflow analysis)은 제어 흐름 그래프의 각 지점에서 프로그램의 실행 상태에 대해 성립하는 성질을, 격자 위의 단조 함수들이 이루는 연립방정식의 고정점으로 계산하는 정적 분석 기법이다. 컴파일러 최적화의 뼈대이자, 현대 정적 분석 도구 전부가 딛고 선 바닥이다.

출발점은 라이스 정리의 그늘이다. “이 변수가 항상 5인가”처럼 프로그램의 의미에 관한 비자명한 질문은 전부 결정 불가능하다(튜링 기계 문서 참조). 그래서 정적 분석은 정확한 답을 포기하고 한쪽으로만 틀리는 답을 택한다 — 최적화용 분석이라면 “혹시 모르니 최적화하지 않는” 쪽으로, 버그 검출용이라면 “혹시 모르니 경고하는” 쪽으로. 이 “한쪽으로만”을 수학적으로 못 박는 장치가 격자의 순서다.

시뮬레이션 하는 사람이 왜 이걸 알아야 하냐면, 솔버 커널의 성능이 대부분 여기서 결판나기 때문이다. 루프 불변식 이동, 공통부분식 제거, 벡터화 가능 여부 판정, 레지스터 배정, GPU 컴퓨팅의 커널 융합, 자동 미분 도구의 활성 변수(activity) 판별까지 — 전부 데이터 흐름 분석의 인스턴스다. -O3 를 붙였는데 왜 이 루프만 벡터화가 안 되는지 리포트를 읽으려면 결국 이 어휘가 필요하다.

2. 격자와 전달함수 — 킬달의 틀[편집]

게리 킬달이 1973년에 세운 틀은 놀랄 만큼 간결하다.¹ 분석 하나는 다음 네 가지로 정의된다.

제어 흐름 그래프 $G = (N, E)$ — 노드는 기본 블록, 간선은 가능한 제어 흐름.
격자 $(L, \sqsubseteq)$ — 분석이 다루는 “사실”들의 집합에 부분순서를 준 것. 위로 갈수록 정보가 많고(정밀), 아래로 갈수록 적다(보수적). 유한 높이면 종료가 보장된다.
합류 연산 $\sqcap$ — 여러 경로가 만나는 지점에서 정보를 합치는 방법. 보통 최대하한(meet).
전달함수 $f_B : L \to L$ — 블록 $B$ 를 통과하면 사실이 어떻게 바뀌는가. 단조( $x \sqsubseteq y \Rightarrow f(x) \sqsubseteq f(y)$ )여야 한다.

이제 전방 분석의 방정식은 이렇게 쓰인다.

\mathrm{IN}[B] = \bigsqcap_{P \in \mathrm{pred}(B)} \mathrm{OUT}[P], \qquad \mathrm{OUT}[B] = f_B\bigl(\mathrm{IN}[B]\bigr)

후방 분석이면 pred가 succ로 바뀌고 IN/OUT이 뒤집힌다. 그게 전부다. 이 연립방정식의 해가 존재한다는 것은 크나스터-타르스키 고정점 정리가 보장한다 — 완비격자 위의 단조 함수는 항상 최대 고정점과 최소 고정점을 갖는다.² 유한 높이 격자에서는 초기값에서 시작해 방정식을 반복 적용하는 것만으로 유한 단계에 그 고정점에 도달한다. 바나흐 고정점 정리의 이산 사촌쯤 되는 구조이고, 수치해석 하는 사람에게는 그냥 반복법으로 고정점을 찾는 일로 보일 것이다. 실제로 그렇다.

가장 흔한 격자는 비트벡터다. 변수나 표현식의 유한 집합을 원소로 삼고, 합류가 합집합 또는 교집합이며, 전달함수가

f_B(x) = \mathrm{gen}_B \cup (x \setminus \mathrm{kill}_B)

형태인 경우. 이 꼴이면 한 격자 원소가 machine word 몇 개로 표현되고 연산이 AND/OR/ANDN 몇 개라, 100만 줄짜리 코드도 눈 깜짝할 사이에 처리된다.

3. MOP와 MFP — 왜 답이 두 개인가[편집]

“진짜 정답”이 뭔지 먼저 정하자. 시작점에서 블록 $B$ 까지 이르는 모든 경로 $\pi$ 마다 전달함수를 합성해 적용한 뒤 전부 합류하면, 그게 우리가 원하는 답이다.

\mathrm{MOP}[B] \;=\; \bigsqcap_{\pi \,\in\, \mathrm{paths}(\mathrm{start} \to B)} f_\pi(\iota)

이걸 MOP(Meet Over all Paths)라 한다. 문제는 루프가 있으면 경로가 무한히 많고, 실제로 캄과 울만(1977)이 일반 단조 프레임워크에서 MOP가 계산 불가능함을 보였다. 반면 위의 연립방정식을 반복해서 얻는 해, 즉 MFP(Maximal Fixed Point)는 언제나 유한 시간에 계산된다.

둘의 관계가 이 분야의 핵심 정리다.

항상 성립: $\mathrm{MFP} \sqsubseteq \mathrm{MOP}$ . 즉 MFP는 MOP보다 같거나 덜 정밀하지만 언제나 안전하다. 합류를 경로 끝이 아니라 중간중간에 미리 해 버리기 때문에 정보가 조금씩 뭉개진다.
전달함수가 분배적이면 — $f(x \sqcap y) = f(x) \sqcap f(y)$ — $\mathrm{MFP} = \mathrm{MOP}$ . 킬달이 증명한 부분이 이것이고, 비트벡터 문제(gen/kill 형태)는 전부 분배적이다. 그래서 도달 정의·활성 변수 같은 고전 분석은 손해가 정확히 0이다.

분배적이지 않은 대표 사례가 상수 전파다. 격자는 각 변수에 $\top$ (아직 모름) / 상수 / $\bot$ (상수 아님)를 배정한 것인데, 다음을 보자.

if (c) { x = 2; y = 3; }
else    { x = 3; y = 2; }
z = x + y;

두 경로 각각에서 $z = 5$ 이므로 MOP는 ” $z$ 는 상수 5”라고 답한다. 그런데 MFP는 합류 지점에서 $x$ 와 $y$ 를 먼저 만나게 하고, $x = 2 \sqcap 3 = \bot$ , $y = \bot$ 이 된 뒤에 덧셈을 적용하므로 $z = \bot$ 이 나온다. 정답을 놓쳤지만 틀린 말은 하지 않았다 — 이 방향의 부정확성이 바로 “안전한 근사”다. 상수 전파의 전달함수는 단조이지만 분배적이 아니고, 실제로 상수 전파의 MOP 해를 구하는 문제는 결정 불가능이다.

4. 고전 4대 분석[편집]

전방/후방 × may/must 의 2×2 표가 이 분야의 구구단이다.

분석	방향	합류	격자 원소	초기값	쓰임새
도달 정의	전방	합집합 (may)	정의문 집합	공집합	use-def 연쇄, 상수 전파
가용 표현식	전방	교집합 (must)	표현식 집합	전체집합	공통부분식 제거
활성 변수	후방	합집합 (may)	변수 집합	공집합	레지스터 배정, 죽은 코드 제거
매우 바쁜 표현식	후방	교집합 (must)	표현식 집합	전체집합	코드 호이스팅, 크기 축소

읽는 법이 있다.

방향은 질문이 과거를 보느냐 미래를 보느냐다. “여기 도달한 정의는?”은 과거(전방), “이 값이 앞으로 쓰이나?”는 미래(후방).
may/must는 “어떤 경로에서라도”냐 “모든 경로에서”냐다. may 문제는 합집합이고 초기값이 공집합, must 문제는 교집합이고 초기값이 전체집합이다. must 문제를 공집합에서 시작하면 답이 통째로 공집합으로 붕괴하니 주의 — 이게 초보자가 가장 흔히 밟는 지뢰다.
안전한 방향도 반대다. may 분석은 과대추정이 안전하고(놓치면 안 되는 것), must 분석은 과소추정이 안전하다.

활성 변수 분석의 전달함수를 예로 보면 후방이라 이렇게 생겼다.

\mathrm{OUT}[B] = \bigcup_{S \in \mathrm{succ}(B)} \mathrm{IN}[S], \qquad \mathrm{IN}[B] = \mathrm{use}_B \cup \bigl(\mathrm{OUT}[B] \setminus \mathrm{def}_B\bigr)

“블록 안에서 정의되기 전에 읽히면 살아 있고, 정의되면 그 이전의 값은 죽는다.” 이 한 줄이 레지스터 배정의 간섭 그래프를 만들고, 그 그래프를 그래프 색칠로 칠하는 것이 고전적인 레지스터 할당이다.

5. 워크리스트와 수렴 속도[편집]

방정식을 푸는 방법은 반복법과 똑같다.

순회(round-robin) 반복. 모든 블록을 고정된 순서로 훑으며 갱신하기를, 변화가 없을 때까지 반복한다. 순서가 성능을 좌우하는데, 전방 분석은 역후위 순서(reverse postorder), 후방 분석은 후위 순서가 정답이다. 역후위 순서는 깊이 우선 탐색으로 얻고, 후방 간선이 아닌 모든 간선에 대해 원인이 결과보다 먼저 오도록 정렬한다 — 사실상 위상 정렬의 사이클 허용판이다.

수렴 속도에 관한 고전 결과가 있다. 환원 가능(reducible) 흐름 그래프³ 위의 비트벡터 문제를 역후위 순서로 순회하면, $d+2$ 회 순회면 끝난다. 여기서 $d$ 는 루프 연결도(loop connectedness), 즉 사이클 없는 경로 하나에 놓일 수 있는 후방 간선의 최대 개수 — 직관적으로 루프 중첩 깊이다. 실측하면 실제 프로그램에서 $d$ 가 3을 넘는 일이 거의 없어서, 결국 다섯 번 정도 훑으면 끝난다는 뜻이 된다. 반복법이 이렇게 얌전한 분야가 또 없다.

워크리스트 알고리즘. 순회는 아무것도 안 바뀐 블록까지 매번 다시 계산하니 낭비다. 대신 “입력이 바뀐 블록”만 큐에 넣고 꺼내 처리하며, 출력이 바뀌면 그 후속 블록들을 큐에 다시 넣는다. 큐를 역후위 순서 우선순위로 유지하면(우선순위 큐) 재방문이 크게 줄어든다. 큰 함수에서는 이쪽이 표준이다.

6. SSA — 분석을 희소하게 만들기[편집]

고전 데이터 흐름 분석의 진짜 비용은 반복 횟수가 아니라 격자 원소의 크기다. 활성 변수 분석은 모든 지점마다 “변수 전체 집합의 부분집합”을 들고 다녀야 하므로 공간이 $O(\text{지점 수} \times \text{변수 수})$ 로 부푼다. 100만 줄 코드에 10만 개 변수면 곤란해진다.

정적 단일 배정(SSA) 형식이 이 문제를 구조적으로 해결한다. 규칙은 하나 — 모든 변수는 딱 한 번만 정의된다. 여러 정의가 합류하는 지점에는 가짜 연산 $\phi$ 를 넣어 “어느 전임 블록에서 왔느냐에 따라 값을 고른다”를 명시한다.

x1 = 2;            x2 = 3;
        \           /
     x3 = φ(x1, x2);

이렇게 하면 정의-사용 연쇄가 이름 자체에 박히므로, 도달 정의 분석을 따로 돌릴 필요가 없어진다. 분석은 제어 흐름 그래프의 모든 지점을 훑는 대신 SSA 간선을 따라 값만 전파하면 되고, 이것을 “희소(sparse) 분석”이라 부른다. 웨그먼·재덱의 희소 조건부 상수 전파(SCCP)가 대표작으로, 도달 불가능한 분기를 상수 전파와 동시에 판정해 각각 따로 돌릴 때보다 더 정밀한 답을 낸다.

$\phi$ 를 어디에 넣을지는 지배 경계(dominance frontier)가 답한다. 노드 $d$ 의 지배 경계는 ” $d$ 가 지배하는 노드에서 나가는 간선이 닿지만 $d$ 가 지배하지는 않는 노드”들이고, 변수의 정의 지점 집합의 반복 지배 경계가 정확히 $\phi$ 를 넣어야 할 위치다. 사이트론·페란테·로젠·웨그먼·재덱(1991)의 결과이며, 지배자 트리 자체는 렝가우어-타잔 알고리즘이 거의 선형 시간에 만든다 — 여기서도 밑바닥은 깊이 우선 탐색이다. LLVM·GCC·JVM JIT 등 현대 컴파일러의 중간표현이 예외 없이 SSA인 이유가 이것이다.

7. 무한 격자 — 위젠과 내로잉[편집]

지금까지는 격자 높이가 유한해서 반복이 저절로 멈췄다. 그런데 “이 정수 변수의 값 범위는?”을 묻는 구간 분석의 격자는 $[a,b]$ 꼴 구간 전체라 높이가 무한하다. 다음 루프를 보자.

i = 0;
while (i < n) { i = i + 1; }

반복하면 $i \in [0,0]$ , $[0,1]$ , $[0,2]$ , … 로 영원히 올라간다. 종료하지 않는다.

쿠소 부부(1977)의 처방이 위젠(widening) $\nabla$ 다.⁴ 값이 커지는 방향으로 움직이는 성분을 발견하면 한 번에 $+\infty$ 로 밀어 버린다.

[a_1,b_1] \,\nabla\, [a_2,b_2] \;=\; [\,c,\,d\,], \qquad c = \begin{cases} a_1 & (a_2 \ge a_1)\\ -\infty & (\text{그 외})\end{cases}, \qquad d = \begin{cases} b_1 & (b_2 \le b_1)\\ +\infty & (\text{그 외})\end{cases}

위 예에서는 두 번째 반복에 곧장 $[0,+\infty]$ 로 점프해 즉시 수렴한다. 답이 거칠어졌지만 안전하고, 무엇보다 끝난다. 그다음 잃은 정밀도를 조금 되찾는 것이 내로잉(narrowing) $\triangle$ 으로, 위젠 결과에서 출발해 방정식을 다시 적용하며 아래로 내려온다. 루프 조건 $i < n$ 을 다시 먹이면 $[0, n]$ 까지 회복되는 식이다. 위젠은 종료를, 내로잉은 정밀도를 담당하는 역할 분담이고, 어디에 위젠 지점을 둘지가 정적 분석기 튜닝의 8할이다.

이 지점에서 데이터 흐름 분석은 추상해석(abstract interpretation)의 특수 사례로 재해석된다. 구체 의미론의 상태 집합 $\mathcal{P}(\Sigma)$ 와 추상 도메인 $A$ 사이에 갈루아 연결 $(\alpha, \gamma)$ 를 놓고, 구체 전이의 최적 근사를 추상 도메인에서 계산하는 일반 이론이다. 격자가 유한하면 위젠 없이 끝나고 그게 고전 데이터 흐름 분석, 무한하면 위젠이 필요하고 그게 구간 해석·다면체 도메인 같은 무거운 분석이다. 자세한 것은 추상 해석 문서로 넘긴다.

8. 수치 코드에서 실제로 벌어지는 일[편집]

솔버 커널을 짜는 사람에게 이 이론이 왜 실전인지 구체적으로 보자.

루프 불변 코드 이동. 루프 안에서 값이 변하지 않는 식을 밖으로 빼는 최적화다. “변하지 않는다”의 판정이 곧 도달 정의 분석이고, 뺀 자리에서 부작용이 없다는 보장이 필요해 별칭 정보까지 동원된다. 격자 루프 안의 dx*dx 나 1.0/rho 같은 것이 매 반복마다 다시 계산되고 있다면 대개 컴파일러가 별칭 때문에 이동을 포기한 것이다.

의존성 분석과 벡터화. for (i...) a[i] = b[i] + c[i]; 를 SIMD로 묶으려면 a, b, c 가 겹치지 않아야 한다. C에서 포인터 인자 셋의 별칭 여부는 정적으로 알 수 없으므로, 컴파일러는 (1) 벡터화를 포기하거나 (2) 런타임에 주소 범위 겹침을 검사하는 분기를 삽입한다. 포트란이 언어 규칙으로 인자 별칭을 금지하고 C99가 restrict 를 도입한 것이 정확히 이 비용을 없애기 위해서다. “포트란이 C보다 수치 코드에서 빠르다”는 오래된 속설의 기술적 알맹이가 여기에 있다. 루프 안 배열 첨자의 의존 거리를 푸는 것은 별도로 정수계획 문제(밴너지 검정, 오메가 검정)가 되며, 이건 데이터 흐름 분석의 사촌인 의존성 분석 영역이다.

부동소수점의 특수 사정. $(a+b)+c$ 와 $a+(b+c)$ 는 부동소수점 연산에서 다른 값이므로, 컴파일러는 기본 설정에서 실수 연산의 재결합을 금지한다. 즉 정수 코드였다면 자유롭게 했을 변환들이 수치 코드에서는 막혀 있고, -ffast-math 는 이 금지를 푸는 스위치다. 성능을 얻는 대신 재현성과 오차 보장을 내주는 거래이며, 검증 및 확인 관점에서는 신중해야 할 옵션이다.

자동 미분의 활성 변수 분석. 자동 미분 도구는 “출력에 영향을 주는 입력에서 파생된 변수”만 미분값을 들고 다녀야 메모리를 아낀다. 이 판정이 전방(입력에서 퍼짐)·후방(출력에서 역추적) 두 방향 도달성의 교집합이고, 형태가 도달 정의·활성 변수 분석과 판박이다. 체크포인팅 전략을 짜는 것도 결국 흐름 그래프 위의 최적화 문제다.

GPU 커널 융합. 연속된 원소별 연산을 하나의 커널로 합치려면 중간 배열이 그 뒤로 다시 쓰이지 않음을 알아야 한다 — 활성 변수 분석 그대로다. 딥러닝 프레임워크와 GPU 컴퓨팅 컴파일러가 계산 그래프 위에서 돌리는 패스들이 이름만 다를 뿐 같은 물건이다.

9. 정밀도의 눈금[편집]

분석기를 비교할 때 쓰는 축이 몇 개 있고, 각 축마다 비용이 붙는다.

흐름 민감(flow-sensitive) — 프로그램 지점마다 다른 답을 준다. 지금까지 본 것이 전부 이쪽. 흐름 둔감 분석은 함수 전체에 하나의 답만 주는 대신 훨씬 싸다(스틴스가드식 포인터 해석이 그 예).
경로 민감(path-sensitive) — if (p != NULL) 안쪽에서는 p 가 널이 아님을 안다. 분기 조건을 격자에 반영하는 것이며, 정밀하지만 경로 수가 지수로 늘어 곧 SAT 풀이기나 SMT 풀이기를 불러와야 한다.
문맥 민감(context-sensitive) — 아래 절에서 다룬다.
필드·요소 민감 — 구조체 필드를 구분하는가, 배열 원소를 구분하는가. 배열 전체를 한 덩어리로 보는 것이 기본값이라, 수치 코드에서 정밀도가 크게 떨어지는 지점이다.

축을 하나 올릴 때마다 비용이 뛰므로, 실전 분석기는 처음에는 싸고 거친 분석을 돌리고, 경고가 뜬 곳만 비싼 분석으로 다시 본다는 계층 전략을 쓴다. 다중격자에서 거친 격자로 대충 풀고 세밀한 격자로 정련하는 것과 발상이 같다.

10. 어려운 것들[편집]

여기까지가 교과서고, 실무의 고통은 다음 두 곳에 몰려 있다.

별칭·포인터. *p = 0; 한 줄의 전달함수를 쓰려면 $p$ 가 무엇을 가리킬 수 있는지 알아야 한다. 모르면 “모든 메모리가 바뀌었다”고 가정할 수밖에 없고, 그 순간 모든 분석이 무의미해진다. 포인터 해석의 양대 계보는 앤더슨 방식(포함 제약, $O(n^3)$ , 정밀)과 스틴스가드 방식(단일화 제약, 거의 선형, 거칠다)이며, 앤더슨 방식은 제약을 풀다가 새 간선이 생기는 동적 이행 폐포 문제가 된다. C/C++ 의 restrict 키워드와 포트란이 배열 별칭을 언어 차원에서 금지한 것이 왜 성능 차이를 만드는지가 여기서 설명된다 — 수치 커널의 벡터화 가능 여부가 실제로 이 한 줄에 걸려 있다.

문맥 민감성. 함수 호출을 넘나드는 분석에서, 호출 지점 A에서 들어간 정보가 호출 지점 B로 나오는 비현실적 경로를 세면 정밀도가 무너진다. 처방은 호출 문자열(call string)로 문맥을 구분하는 $k$ -CFA, 함수를 요약 전달함수로 바꾸는 함수형 접근(샤리르·프누엘리 1981), 그리고 유한 도메인 분배 문제를 그래프 도달성으로 환원해 다항 시간에 정확한 문맥 민감 답을 얻는 IFDS(렙스·호르비츠·사기브 1995)다. 정밀도를 한 칸 올릴 때마다 비용이 지수로 뛰는 것이 이 바닥의 국룰이고, 상용 분석기의 실력은 결국 “어디서 포기할지”를 얼마나 잘 고르느냐다.

11. 관련 문서[편집]

Kildall, G. A. (1973). “A unified approach to global program optimization”. POPL. 그 게리 킬달 맞다 — CP/M을 만들고, IBM과의 협상이 틀어진 자리에 마이크로소프트가 들어가 MS-DOS가 태어났다는 그 전설의 인물. 컴파일러 이론 쪽 업적이 훨씬 오래 남았다는 게 아이러니. ↩
정확히는 완비격자 위의 단조 함수의 고정점 전체가 다시 완비격자를 이룬다는 정리다. 최대·최소 고정점이 항상 존재한다는 것은 그 따름정리. 분석 설계자가 “최소 고정점을 쓴다/최대 고정점을 쓴다”를 고르는 것은 취향이 아니라 안전 방향의 문제이며, 문헌마다 격자를 뒤집어 놓아서 MFP 의 M 이 maximal 인지 minimal 인지 헷갈리는 사고가 자주 난다. ↩
대략 “모든 루프가 진입점 하나만 갖는” 그래프. while·for·if 만으로 짠 코드는 항상 환원 가능하고, 루프 몸통 한가운데로 goto 를 던지면 깨진다. 그래서 다익스트라의 goto 비판은 미학적 취향이 아니라 컴파일러가 최적화할 수 있느냐의 문제이기도 했다. 환원 불가능한 그래프는 노드를 복제해(node splitting) 강제로 환원 가능하게 만들 수 있는데, 최악의 경우 코드 크기가 지수로 늘어난다. ↩
Cousot, P. & Cousot, R. (1977). “Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints”. POPL. 제목이 논문 초록보다 길다는 농담이 있는데, 실제로 저 제목 안에 이 분야의 모든 것이 들어 있다. 이 틀로 만든 Astrée 분석기가 에어버스 A340/A380 비행제어 소프트웨어에서 런타임 오류 없음을 증명해 낸 것이 정적 분석 역사상 가장 유명한 실전 성과다. ↩