개요
지금까지 살펴본 최적화 기법들은 대부분 하나의 함수(프로시저) 내에서 수행되는 **프로시저 내 분석**(intraprocedural analysis)이었습니다. 그러나 실제 프로그램은 많은 함수 호출로 이루어져 있으므로, 함수 경계를 넘어선 **프로시저 간 분석**(interprocedural analysis)이 필요합니다.
이번 글에서는 프로시저 간 분석의 핵심 개념과 가장 중요한 응용인 포인터 분석을 다룹니다.
1. 프로시저 간 분석의 필요성
1.1 함수 호출이 최적화를 방해하는 예
void init(int* arr, int n) {
for (int i = 0; i < n; i++)
arr[i] = 0;
}
void process() {
int a[100];
init(a, 100);
int x = a[0]; // x = 0인가?
}
`init` 함수의 내부를 분석하지 않으면 `a[0]`의 값을 알 수 없습니다. 보수적으로 `a[0]`이 어떤 값이든 될 수 있다고 가정해야 하므로 상수 전파가 불가능합니다.
1.2 프로시저 간 분석이 필요한 정보
| 정보 | 필요한 이유 |
| ------------------------------ | -------------------------------------- |
| 함수의 부수 효과(side effects) | 어떤 전역 변수를 수정하는지 |
| 매개변수 별칭(aliasing) | 두 매개변수가 같은 메모리를 가리키는지 |
| 반환값 범위 | 함수의 반환값이 상수인지 |
| 호출 대상 | 함수 포인터를 통한 간접 호출의 대상 |
1.3 보수적 가정 vs 프로시저 간 분석
// 보수적 가정 (프로시저 간 분석 없이):
// - 함수 호출이 모든 전역 변수를 수정할 수 있음
// - 포인터 매개변수를 통해 접근 가능한 모든 메모리를 수정할 수 있음
// - 반환값에 대해 아무것도 알 수 없음
// 프로시저 간 분석 후:
// - init()은 arr이 가리키는 배열만 수정함
// - init()은 전역 변수를 수정하지 않음
// - init() 후 arr[0..n-1]은 모두 0임
2. 호출 그래프 (Call Graph)
2.1 정의
**호출 그래프**는 프로그램의 함수들을 노드로, 호출 관계를 간선으로 표현한 그래프입니다.
// 프로그램:
// main() -> foo() -> bar()
// -> baz() -> bar()
// -> qux()
// 호출 그래프:
// main -> foo -> bar
// -> baz -> bar
// -> qux
2.2 간접 호출의 문제
함수 포인터를 통한 간접 호출은 호출 대상을 정적으로 알기 어렵습니다.
typedef int (*FuncPtr)(int);
int add1(int x) { return x + 1; }
int mul2(int x) { return x * 2; }
void apply(FuncPtr f, int x) {
int result = f(x); // f가 add1인지 mul2인지 알 수 없음
}
이 경우 포인터 분석을 통해 `f`가 가리킬 수 있는 함수의 집합을 추정합니다.
2.3 호출 그래프 구성 방법
**Class Hierarchy Analysis (CHA)**: 객체 지향 언어에서 클래스 계층을 기반으로 가능한 호출 대상을 결정
// Java 예시:
// Animal.speak()가 호출되면
// Dog.speak(), Cat.speak() 등 모든 하위 클래스의 메서드가 가능한 대상
// CHA: Animal의 모든 하위 클래스의 speak()를 후보에 포함
// RTA(Rapid Type Analysis): 실제 생성된 타입만 고려
// VTA(Variable Type Analysis): 변수의 실제 타입을 추적
3. 문맥 민감성 (Context Sensitivity)
3.1 문맥 비민감 분석
함수가 호출되는 문맥을 구분하지 않고, 모든 호출 지점의 정보를 합쳐서 분석합니다.
// 함수 identity:
int identity(int x) { return x; }
// 호출 지점:
a = identity(1); // 호출 1
b = identity(2); // 호출 2
// 문맥 비민감 분석:
// identity의 x = {1, 2} (모든 호출의 인수 합침)
// identity의 반환값 = {1, 2}
// -> a = {1, 2}, b = {1, 2} (부정확!)
3.2 문맥 민감 분석
각 호출 지점을 별도로 분석합니다.
// 문맥 민감 분석:
// 호출 1 문맥: identity(1) -> 반환값 = 1 -> a = 1
// 호출 2 문맥: identity(2) -> 반환값 = 2 -> b = 2
// 정확한 결과!
3.3 문맥 표현 방법
**호출 문자열(Call String)**: 호출 스택을 문맥으로 사용
// main -> foo -> identity (문맥: [main, foo])
// main -> bar -> identity (문맥: [main, bar])
// k-제한 호출 문자열: 최근 k개의 호출만 고려
// k=1: [foo], [bar]
// k=2: [main,foo], [main,bar]
**함수 요약(Summary)**: 함수의 입출력 관계를 요약
// identity 함수의 요약:
// 입력 x -> 출력 x (항등 함수)
// 각 호출 지점에서 요약을 적용:
// identity(1) -> 1
// identity(2) -> 2
4. 포인터 분석 (Pointer Analysis)
4.1 포인터 분석이란
프로그램의 각 지점에서 포인터가 가리킬 수 있는 메모리 위치의 집합을 결정하는 분석입니다.
// 포인터 분석의 질문:
// 포인터 p가 가리킬 수 있는 대상은?
int a, b;
int *p;
if (cond)
p = &a;
else
p = &b;
// 이 지점에서 p의 포인트-투 집합: pts(p) = {a, b}
4.2 포인트-투 관계의 종류
// 주소 취득: p = &x -> p가 x를 가리킴
// 복사: p = q -> p가 q가 가리키는 것을 가리킴
// 로드: p = *q -> p가 q가 가리키는 것이 가리키는 것을 가리킴
// 저장: *p = q -> p가 가리키는 것이 q가 가리키는 것을 가리킴
4.3 Andersen의 분석
**포함 기반(inclusion-based)** 분석이라고도 합니다. 각 포인터 변수에 대해 별도의 포인트-투 집합을 유지합니다.
알고리즘: Andersen 분석
입력: 포인터 대입문들의 집합
출력: 각 변수의 포인트-투 집합
규칙:
p = &x -> {x}를 pts(p)에 추가
p = q -> pts(q)를 pts(p)에 추가
p = *q -> pts(q)의 각 원소 r에 대해, pts(r)를 pts(p)에 추가
*p = q -> pts(p)의 각 원소 r에 대해, pts(q)를 pts(r)에 추가
반복: 변화가 없을 때까지
예시:
// 프로그램:
p = &a; // pts(p) = {a}
q = &b; // pts(q) = {b}
p = q; // pts(p) = {a, b} (pts(q)를 pts(p)에 추가)
r = &p; // pts(r) = {p}
s = *r; // r이 p를 가리키므로, pts(p) = {a, b}를 pts(s)에 추가
// pts(s) = {a, b}
복잡도: O(n^3) - n은 포인터 변수의 수
4.4 Steensgaard의 분석
**통합 기반(unification-based)** 분석입니다. 같은 대상을 가리킬 수 있는 포인터들을 하나의 등가 클래스로 합칩니다.
알고리즘: Steensgaard 분석
규칙:
p = &x -> p의 타입이 x를 가리키도록 설정
p = q -> p와 q의 포인트-투 집합을 통합(union)
p = *q -> 적절한 통합 수행
*p = q -> 적절한 통합 수행
Union-Find 자료구조 사용
예시:
// 프로그램:
p = &a; // pts(p) = {a}
q = &b; // pts(q) = {b}
p = q; // p와 q 통합 -> pts(p) = pts(q) = {a, b}
// Andersen과 동일한 결과
// 하지만:
r = &c; // pts(r) = {c}
p = r; // Andersen: pts(p) = {a, b, c}, pts(r) = {c}
// Steensgaard: p,q,r 모두 통합 -> pts = {a, b, c}
// Steensgaard가 덜 정밀 (r은 a,b를 실제로 가리키지 않음)
복잡도: O(n \* alpha(n)) - 거의 선형, alpha는 역 아커만 함수
4.5 비교
| 특성 | Andersen | Steensgaard |
| ----------- | ------------- | --------------------------- |
| 정밀도 | 높음 | 낮음 |
| 복잡도 | O(n^3) | 거의 O(n) |
| 방식 | 포함 기반 | 통합 기반 |
| 적합한 용도 | 정밀한 최적화 | 대규모 프로그램의 빠른 분석 |
5. 별칭 분석 (Alias Analysis)
5.1 정의
두 표현식이 같은 메모리 위치를 참조하는지 판별하는 분석입니다.
// 별칭 관계:
// *p와 a가 별칭인가? -> p가 a를 가리키면 별칭
// 별칭의 세 가지 답:
// Must-alias: 항상 같은 위치를 가리킴
// May-alias: 같은 위치를 가리킬 수 있음
// No-alias: 절대 같은 위치를 가리키지 않음
5.2 별칭 분석과 최적화
void foo(int *p, int *q) {
*p = 10;
*q = 20;
int x = *p; // x = 10? 아니면 20?
}
별칭 분석 결과에 따라:
- p와 q가 **no-alias**이면: x = 10 (상수 전파 가능)
- p와 q가 **may-alias**이면: x의 값을 알 수 없음 (보수적)
- p와 q가 **must-alias**이면: x = 20
5.3 타입 기반 별칭 분석 (TBAA)
C/C++의 엄격한 별칭 규칙(strict aliasing rule)을 이용합니다.
// C에서 서로 다른 타입의 포인터는 별칭이 아니라고 가정 가능
int *pi;
float *pf;
// pi와 pf는 no-alias (타입이 다름)
// 예외: char* 는 모든 타입과 별칭 가능
// 예외: union의 멤버들
5.4 restrict 키워드
C99의 `restrict` 키워드는 포인터가 가리키는 메모리에 대한 유일한 접근 수단임을 프로그래머가 보장합니다.
// restrict가 없으면 a, b, c가 별칭일 수 있음
void add(int *a, int *b, int *c, int n) {
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i];
}
// restrict 사용: 별칭 없음을 보장
void add(int * restrict a, int * restrict b, int * restrict c, int n) {
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i]; // 벡터화 가능!
}
6. 흐름 민감 vs 흐름 비민감 분석
6.1 흐름 비민감 (Flow-Insensitive)
프로그램의 실행 순서를 무시하고, 모든 문장을 동시에 고려합니다.
// 흐름 비민감 분석:
p = &a; // 문장 1
p = &b; // 문장 2
x = *p; // 문장 3
// 결과: pts(p) = {a, b} (모든 지점에서 동일)
// 문장 1 이후에도 pts(p) = {a, b}
장점: 빠르고 간단
단점: 부정확 (문장 1 직후에는 p가 a만 가리킴)
6.2 흐름 민감 (Flow-Sensitive)
프로그램의 실행 순서를 고려하여, 각 프로그램 지점에서 별도의 정보를 유지합니다.
// 흐름 민감 분석:
p = &a; // 이 지점 이후: pts(p) = {a}
p = &b; // 이 지점 이후: pts(p) = {b} (이전 값 덮어씀)
x = *p; // 이 지점에서: pts(p) = {b}
// -> x는 b만 가리킬 수 있음 (더 정확!)
장점: 정확함
단점: 느리고 메모리 소비가 큼
6.3 실용적 선택
// 일반적인 컴파일러의 선택:
// - 프로시저 내 분석: 흐름 민감 (정확도 중요, 규모가 작음)
// - 프로시저 간 분석: 흐름 비민감 (확장성 중요, 규모가 큼)
// - 포인터 분석: 대부분 흐름 비민감 (규모 문제)
7. 프로시저 간 데이터 흐름 분석
7.1 MOD/REF 분석
각 함수가 어떤 변수를 수정(MOD)하고 참조(REF)하는지 분석합니다.
// MOD(f): 함수 f가 수정할 수 있는 변수 집합
// REF(f): 함수 f가 참조할 수 있는 변수 집합
void foo() {
x = 1; // MOD(foo) = {x, ...}
y = x + z; // REF(foo) = {x, z, ...}
bar(); // bar의 MOD/REF도 전파
}
// MOD(foo) = {x} U MOD(bar) (bar가 수정하는 것도 포함)
// REF(foo) = {x, z} U REF(bar)
7.2 함수 인라이닝 (Function Inlining)
프로시저 간 분석의 가장 간단한 대안은 함수를 호출 지점에 인라이닝하는 것입니다.
// 원본:
int square(int x) { return x * x; }
int result = square(5);
// 인라이닝 후:
int result = 5 * 5; // -> 상수 폴딩 가능 -> result = 25
인라이닝의 장점:
- 함수 호출 오버헤드 제거
- 프로시저 내 최적화가 더 많은 코드를 볼 수 있음
인라이닝의 단점:
- 코드 크기 증가 (명령어 캐시에 악영향)
- 재귀 함수는 인라이닝 불가
- 과도한 인라이닝은 오히려 성능 저하
7.3 부분 인라이닝과 클로닝
// 부분 인라이닝: 핫 경로만 인라이닝
void foo(int x) {
if (x > 0) { // 90% 확률
// 간단한 코드 -> 인라이닝
} else {
// 복잡한 코드 -> 함수 호출 유지
}
}
// 함수 클로닝: 호출 문맥에 따라 특화된 버전 생성
void foo_const5() { // x=5일 때 특화
// x=5로 상수 전파된 코드
}
정리
| 개념 | 설명 |
| ---------------- | ----------------------------------------- |
| 프로시저 간 분석 | 함수 경계를 넘어선 프로그램 분석 |
| 호출 그래프 | 함수 간 호출 관계를 나타내는 그래프 |
| 문맥 민감성 | 호출 문맥에 따라 분석 결과를 구분 |
| Andersen 분석 | 포함 기반 포인터 분석, O(n^3) |
| Steensgaard 분석 | 통합 기반 포인터 분석, 거의 O(n) |
| 별칭 분석 | 두 표현식이 같은 메모리를 참조하는지 판별 |
| 흐름 민감 분석 | 프로그램 실행 순서를 고려한 분석 |
| 흐름 비민감 분석 | 실행 순서를 무시한 분석 (빠르지만 부정확) |
| MOD/REF 분석 | 함수가 수정/참조하는 변수 집합 분석 |
프로시저 간 분석과 포인터 분석은 전체 프로그램 최적화의 기반입니다. 특히 포인터가 빈번하게 사용되는 C/C++ 프로그램에서는 정확한 포인터 분석 없이는 효과적인 최적화가 어렵습니다. Andersen과 Steensgaard의 분석은 정밀도와 효율의 트레이드오프를 대표하는 두 가지 접근법입니다. 다음 글에서는 현대 컴파일러의 핵심 중간 표현인 SSA 형식을 다루겠습니다.
현재 단락 (1/238)
지금까지 살펴본 최적화 기법들은 대부분 하나의 함수(프로시저) 내에서 수행되는 **프로시저 내 분석**(intraprocedural analysis)이었습니다. 그러나 실제 프로그...