[컴파일러] 18. 프로시저 간 분석과 포인터 분석

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()은 arr이 가리키는 배열만 수정함
// - init()은 전역 변수를 수정하지 않음
// - init() 후 arr[0..n-1]은 모두 0임

// 프로그램:
// main() -> foo() -> bar()
//        -> baz() -> bar()
//                 -> qux()

// 호출 그래프:
//   main -> foo -> bar
//        -> baz -> bar
//               -> qux

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인지 알 수 없음
}

// Java 예시:
// Animal.speak()가 호출되면
// Dog.speak(), Cat.speak() 등 모든 하위 클래스의 메서드가 가능한 대상

// CHA: Animal의 모든 하위 클래스의 speak()를 후보에 포함
// RTA(Rapid Type Analysis): 실제 생성된 타입만 고려
// VTA(Variable Type Analysis): 변수의 실제 타입을 추적

// 함수 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}  (부정확!)

// 문맥 민감 분석:
// 호출 1 문맥: identity(1) -> 반환값 = 1 -> a = 1
// 호출 2 문맥: identity(2) -> 반환값 = 2 -> b = 2
// 정확한 결과!

// main -> foo -> identity  (문맥: [main, foo])
// main -> bar -> identity  (문맥: [main, bar])

// k-제한 호출 문자열: 최근 k개의 호출만 고려
// k=1: [foo], [bar]
// k=2: [main,foo], [main,bar]

// identity 함수의 요약:
// 입력 x -> 출력 x (항등 함수)
// 각 호출 지점에서 요약을 적용:
// identity(1) -> 1
// identity(2) -> 2

// 포인터 분석의 질문:
// 포인터 p가 가리킬 수 있는 대상은?

int a, b;
int *p;
if (cond)
    p = &a;
else
    p = &b;

// 이 지점에서 p의 포인트-투 집합: pts(p) = {a, b}

// 주소 취득: p = &x  -> p가 x를 가리킴
// 복사:     p = q    -> p가 q가 가리키는 것을 가리킴
// 로드:     p = *q   -> p가 q가 가리키는 것이 가리키는 것을 가리킴
// 저장:     *p = q   -> p가 가리키는 것이 q가 가리키는 것을 가리킴

알고리즘: 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}

알고리즘: 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를 실제로 가리키지 않음)

// 별칭 관계:
// *p와 a가 별칭인가? -> p가 a를 가리키면 별칭

// 별칭의 세 가지 답:
// Must-alias: 항상 같은 위치를 가리킴
// May-alias:  같은 위치를 가리킬 수 있음
// No-alias:   절대 같은 위치를 가리키지 않음

void foo(int *p, int *q) {
    *p = 10;
    *q = 20;
    int x = *p;  // x = 10? 아니면 20?
}

// C에서 서로 다른 타입의 포인터는 별칭이 아니라고 가정 가능
int *pi;
float *pf;
// pi와 pf는 no-alias (타입이 다름)

// 예외: char* 는 모든 타입과 별칭 가능
// 예외: union의 멤버들

// 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];  // 벡터화 가능!
}

// 흐름 비민감 분석:
p = &a;     // 문장 1
p = &b;     // 문장 2
x = *p;     // 문장 3

// 결과: pts(p) = {a, b} (모든 지점에서 동일)
// 문장 1 이후에도 pts(p) = {a, b}

// 흐름 민감 분석:
p = &a;     // 이 지점 이후: pts(p) = {a}
p = &b;     // 이 지점 이후: pts(p) = {b}  (이전 값 덮어씀)
x = *p;     // 이 지점에서: pts(p) = {b}
            // -> x는 b만 가리킬 수 있음 (더 정확!)

// 일반적인 컴파일러의 선택:
// - 프로시저 내 분석: 흐름 민감 (정확도 중요, 규모가 작음)
// - 프로시저 간 분석: 흐름 비민감 (확장성 중요, 규모가 큼)
// - 포인터 분석: 대부분 흐름 비민감 (규모 문제)

// 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)

// 원본:
int square(int x) { return x * x; }
int result = square(5);

// 인라이닝 후:
int result = 5 * 5;  // -> 상수 폴딩 가능 -> result = 25

// 부분 인라이닝: 핫 경로만 인라이닝
void foo(int x) {
    if (x > 0) {     // 90% 확률
        // 간단한 코드  -> 인라이닝
    } else {
        // 복잡한 코드  -> 함수 호출 유지
    }
}

// 함수 클로닝: 호출 문맥에 따라 특화된 버전 생성
void foo_const5() {   // x=5일 때 특화
    // x=5로 상수 전파된 코드
}