한 문장이 다른 문장에 기대는 두 가지 방식 — 프로그램 의존 그래프(PDG)

들어가며 — 두 가지 "기댐"을 한 그림에

코드를 읽다 보면 한 줄이 다른 줄에 기대고 있다는 느낌을 자주 받는다. 그런데 가만히 보면 그 "기댐"은 한 종류가 아니다. 어떤 줄은 앞 줄이 만든 값을 가져다 쓰기 때문에 앞 줄에 기댄다. 또 어떤 줄은 위에 있는 조건문이 참이어야만 실행되기 때문에 그 조건에 기댄다. 나는 이 두 가지가 본질적으로 다른 기댐인데도, 정작 코드를 분석하는 도구들이 이걸 따로따로 본다는 게 늘 답답했다.

프로그램 의존 그래프(PDG, Program Dependence Graph)는 바로 이 두 가지 기댐을 한 장의 그림에 합쳐 놓은 표현이다. PDG는 정적 분석(static analysis, 프로그램을 실행하지 않고 소스 코드만 보고 성질을 알아내는 분석)에서 쓰는 그래프 표현 중 하나다. 이 글은 내가 "왜 합치지?"라는 의문에서 시작해 "아, 합쳐야만 풀리는 문제들이 있구나"로 도착한 학습 노트다.

PDG란 무엇인가

PDG의 정의는 의외로 간단하다.

구성요소	PDG에서의 의미
노드(node)	문장(statement) 하나, 또는 조건(predicate) 하나
엣지(edge) — 데이터 의존	"이 문장이 만든 값을 저 문장이 읽는다"
엣지(edge) — 제어 의존	"이 조건의 결과가 저 문장의 실행 여부를 결정한다"

여기서 predicate(조건)는 if (x > 0)처럼 참/거짓을 따져 흐름을 가르는 지점을 뜻한다. PDG의 핵심은 엣지가 두 종류라는 점이다. 데이터 의존(data dependence)과 제어 의존(control dependence)을 같은 그래프 위에 같이 그린다.

다이어그램 설명. 위 그림은 PDG가 무엇으로 이뤄지는지를 한눈에 보여준다. 문장과 조건이 점이 되고, 거기에 "값이 흐른다"는 선과 "실행 여부를 가른다"는 선 두 종류가 동시에 얹힌다. 핵심 함정은 이 두 선을 하나로 뭉뚱그리는 것 — 둘은 의미가 완전히 다르므로 같은 그래프에 있어도 색이 다른 선으로 구분해 두어야 한다.

일상 비유 — 요리 레시피

나는 PDG를 요리 레시피로 이해한다. "달걀을 푼다 → 푼 달걀을 팬에 붓는다"는 데이터 의존이다. 앞 단계가 만든 결과물(푼 달걀)을 뒷 단계가 쓰기 때문이다. 반면 "프라이팬이 충분히 달궈졌으면 기름을 두른다"는 제어 의존이다. '달궈졌는가'라는 조건이 참일 때만 '기름 두르기'가 일어난다. 레시피 한 장 안에 이 두 종류의 화살표가 섞여 있는 게 정확히 PDG다.

배경 — 어디서 왔나

PDG의 대표 문헌은 Ferrante, Ottenstein, Warren의 "The Program Dependence Graph and Its Use in Optimization"(ACM TOPLAS, 1987)이다. 이 그래프는 갑자기 등장한 게 아니라, 이미 컴파일러가 쓰고 있던 두 가지 토대 위에 세워졌다.

하나는 제어 흐름 그래프(CFG, Control Flow Graph)다. CFG는 "문장들이 어떤 순서로 실행될 수 있는가"를 그린다. 다른 하나는 데이터 흐름 분석(data-flow analysis)이다. 데이터 흐름 분석은 "어떤 변수의 값이 어디서 만들어져 어디서 쓰이는가"를 추적한다. PDG는 이 둘에서 뽑아낸 정보를 의존 관계라는 한 가지 시각으로 재배열한 결과다.

다이어그램 설명. 이 그림은 PDG가 무에서 나온 게 아니라 이미 있던 두 분석을 재료로 조립됐음을 보여준다. 실행 순서를 그린 그래프에서 "어떤 조건이 어떤 문장을 좌우하는가"라는 제어 의존을 뽑고, 값 추적에서 "누가 만들고 누가 읽는가"라는 데이터 의존을 뽑아, 둘을 한 그래프로 모은다. 함정은 CFG의 화살표(실행 순서)와 제어 의존 화살표를 같은 것으로 착각하는 것 — 실행 순서가 곧 의존은 아니다.

어떤 문제를 풀려 했나

그렇다면 왜 굳이 합쳐야 했을까. 내가 찾은 답은 이렇다. 컴파일러 최적화, 프로그램 슬라이싱, 자동 병렬화 같은 작업은 "어떤 값이 무엇에 의존하나"와 "무엇이 어떤 조건 아래 실행되나"를 동시에 봐야 한다. 그런데 CFG만 보면 값의 흐름이 안 보이고, 데이터 흐름 그래프만 보면 조건의 영향이 안 보인다. 두 그래프를 따로 펼쳐 놓고 사람 머릿속에서 합치는 건 비효율적이고 실수가 잦다.

다이어그램 설명. 위 그림은 분석 작업이 던지는 두 질문과, 단일 그래프만으로는 각각 반쪽만 답한다는 한계를 보여준다. 흐름은 "한 작업이 두 질문을 동시에 던지는데, 따로 보는 그래프는 한 질문씩만 답한다"는 것이다. 함정은 "둘 중 더 중요한 하나만 보면 되지 않나"라고 타협하는 것 — 실제 작업은 두 답을 교차해야 정확해진다.

왜 따로 보면 부족한가 — 짧은 코드 예

아래 코드를 보자. 마지막 줄 print(total)이 어디에 기대고 있는지 따져보면 두 종류의 의존이 함께 등장한다.

줄	코드	의존
1	total = 0	—
2	if items > 0:	—
3	total = total + price	2번 조건에 제어 의존, 1번 값에 데이터 의존
4	print(total)	1번·3번 값에 데이터 의존

합계를 더하는 줄은 조건이 참일 때만 실행되므로 조건에 제어 의존하고, 동시에 이전 합계 값을 읽으므로 그 값에 데이터 의존한다. 한 줄이 두 종류로 동시에 기댄다. 이게 바로 두 그래프를 합쳐야 하는 이유다.

어떻게 해결했나 — 두 의존을 한 그래프에

해결책은 단순하면서도 강력하다. 데이터 의존과 제어 의존을 같은 그래프에 함께 그려 넣는다. 그러면 한 문장을 골랐을 때, 그것이 기대고 있는 것(들어오는 엣지)과 그것에 기대는 것(나가는 엣지)을 그래프 탐색만으로 한 번에 따라갈 수 있다. 위의 짧은 코드를 PDG로 그리면 이렇게 된다.

다이어그램 설명. 이 그림은 앞의 4줄 코드를 PDG로 옮긴 것이다. 점선은 제어 의존(조건이 합산 문장의 실행 여부를 가른다)이고 실선은 데이터 의존(값이 흘러간다)이다. 흐름을 보면 출력 문장은 초기화와 합산 양쪽에서 값을 받는다. 함정은 실선과 점선을 같은 의미로 읽는 것 — 점선이 끊긴다고 값이 안 흐르는 게 아니고, 실선이 있다고 항상 실행되는 것도 아니다.

효과 — 프로그램 슬라이싱이 도달성 문제가 된다

PDG의 진가는 프로그램 슬라이싱(program slicing)에서 드러난다. 슬라이싱이란 "프로그램의 특정 지점에 영향을 주는 문장들만, 또는 그 지점이 영향을 미치는 문장들만 골라내는" 기법이다. 슬라이싱 개념 자체는 Mark Weiser가 1981년에 제시했고, Ottenstein & Ottenstein이 1984년에 이를 PDG 위에서 계산하는 방법을 보였다.

핵심은 이거다. 일단 PDG가 있으면, "이 변수가 여기서 가진 값에 영향을 준 모든 문장"을 구하는 일은 그래프 위의 도달성(reachability) 문제로 환원된다. 도달성이란 "어떤 점에서 출발해 화살표를 거꾸로(또는 앞으로) 따라가 닿을 수 있는 모든 점을 모으는" 단순 탐색이다. 복잡한 의미 분석이 평범한 그래프 순회로 바뀌는 것이다.

다이어그램 설명. 이 그림은 백워드 슬라이스(특정 지점에 영향을 준 문장 모으기)를 계산하는 절차다. 흐름은 관심 지점을 고른 뒤 그곳으로 들어오는 의존 엣지를 거꾸로 따라가, 닿는 모든 문장을 슬라이스로 모으는 것이다. 왜 강력하냐면 "영향 추적"이라는 어려워 보이는 질문이 그래프 역방향 탐색이라는 익숙한 알고리즘으로 떨어지기 때문이다. 함정은 데이터 의존만 따라가는 것 — 제어 의존 엣지도 같이 따라가야 "어떤 조건 때문에 실행됐는가"까지 슬라이스에 포함된다.

슬라이싱 외의 쓰임

같은 구조가 여러 작업에 재활용된다. 자동 병렬화에서는 서로 의존하지 않는(엣지로 연결되지 않은) 문장들을 찾아 동시에 실행할 후보로 삼는다. 리팩토링에서는 한 함수에서 떼어낼 코드 덩어리가 바깥과 어떤 의존으로 묶여 있는지 본다. 변경 영향 분석(change impact analysis)에서는 한 줄을 고쳤을 때 그 영향이 어디까지 번지는지를 포워드 슬라이스(나가는 엣지를 따라가기)로 가늠한다.

작업	PDG에서 무엇을 보나
최적화	의존이 없는 부분 = 자유롭게 재배치 가능
프로그램 슬라이싱	도달성 = 영향 주고받는 문장 집합
자동 병렬화	엣지로 안 묶인 문장 = 동시 실행 후보
변경 영향 분석	포워드 슬라이스 = 변경이 번지는 범위

관계 정리 — CFG, 데이터흐름, 그리고 코드 속성 그래프

마지막으로 여러 그래프 표현들이 어떻게 층층이 쌓이는지를 정리하면 머릿속이 깔끔해진다. 실행 순서를 보는 층(CFG), 값의 흐름을 보는 층(데이터흐름), 조건의 영향을 보는 층(제어 의존)을 통합한 게 PDG다. 그리고 여기에 코드의 문법 구조인 구문 트리(AST, Abstract Syntax Tree — 코드를 괄호·연산자·블록 같은 문법 단위로 나눈 트리)까지 합치면 코드 속성 그래프(CPG, Code Property Graph)가 된다.

다이어그램 설명. 이 그림은 표현들이 쌓이는 층위를 보여준다. 흐름은 아래쪽 기본 분석들이 모여 데이터·제어 의존을 합친 그래프가 되고, 거기에 문법 구조 트리까지 더해 가장 풍부한 통합 그래프로 올라가는 것이다. 왜 중요하냐면 이 사다리에서 어느 층까지 올라가느냐가 곧 분석의 표현력을 결정하기 때문이다. 함정은 맨 위 통합 그래프가 아래 층들을 대체한다고 보는 것 — 사실은 아래 층 정보를 품고 올라가는 것이다.

코드 위키 자동 생성에 왜 핵심인가

내가 이 주제에 끌린 진짜 이유는 따로 있다. 나는 코드를 읽고 코드 위키(문서)를 자동 생성하는 일에 관심이 있는데, 그 일의 본질이 결국 "이 함수가 무엇에 기대고, 무엇이 이 함수에 기대는가"를 정확히 말하는 것이기 때문이다. 위키 한 줄이 "이 함수는 설정 값이 로드된 뒤에만 의미가 있다"고 주장하려면, 그 주장을 코드에서 검증 가능한 의존 관계로 뒷받침할 수 있어야 한다.

PDG는 바로 그 "기댐"을 기계가 따라갈 수 있는 형태로 만들어 준다. 문서가 "이 줄을 바꾸면 저쪽 출력이 달라진다"고 적으려면 포워드 슬라이스가 그 범위를 알려주고, "이 결과는 이 조건과 이 입력에서 비롯된다"고 적으려면 백워드 슬라이스가 근거 문장들을 모아준다. 즉 자연어 서술의 모든 의존 주장이 PDG 위의 도달성으로 grounding(근거 연결)될 수 있다.

다이어그램 설명. 이 그림은 코드에서 시작해 의존 그래프를 거쳐 검증 가능한 위키 서술에 도달하는 흐름이다. 흐름은 코드가 진실의 원천이고, 의존 그래프가 거기서 "기댐"을 뽑아내며, 그 위에서 위키의 주장이 슬라이스로 뒷받침되는 것이다. 왜 핵심이냐면 "근거 없는 문서"를 "코드로 검증 가능한 문서"로 바꾸는 다리가 바로 이 의존 구조이기 때문이다. 함정은 의존 그래프 없이 LLM의 인상만으로 서술하는 것 — 그러면 그럴듯하지만 검증할 수 없는 문장이 남는다.

정리

한 줄로 요약하면 PDG는 "값의 흐름"과 "조건의 영향"이라는 두 가지 기댐을 한 그래프에 합친 표현이다. 합쳤기 때문에 최적화·슬라이싱·병렬화처럼 두 가지를 동시에 봐야 하는 작업이 그래프 도달성이라는 단순한 문제로 환원된다. 나에게 가장 값진 깨달음은 "두 개를 따로 보는 것"과 "두 개를 합쳐 보는 것" 사이에 표현력의 질적 도약이 있다는 점이었다. 그리고 이 도약이 코드에서 근거 있는 문서를 길어 올리는 일의 토대가 된다는 것까지가 이번 학습의 결론이다.

---

이 글은 생성형 AI의 도움을 받아 작성되었습니다. 원본 자료를 기반으로 AI가 초안을 생성하고, 작성자가 검토·편집하였습니다.