[컴파일러] 19. SSA 형식과 현대 컴파일러 최적화

// 일반적인 세 주소 코드
x = 1
x = 2       // x가 두 번 정의됨!
y = x + 1   // 어떤 x를 사용하는가? -> 두 번째 정의

// SSA 형식
x1 = 1
x2 = 2      // 다른 버전!
y1 = x2 + 1 // 명확하게 x2를 사용

// 원본                    // SSA
a = x + y                 a1 = x1 + y1
b = a - 1                 b1 = a1 - 1
a = y + b                 a2 = y1 + b1
b = 4 * a                 b2 = 4 * a2

// 원본 코드:
if (cond)
    x = 1;     // 경로 A
else
    x = 2;     // 경로 B
y = x + 1;     // x는 1인가 2인가?

// SSA 형식:
if (cond)
    x1 = 1;          // 경로 A
else
    x2 = 2;          // 경로 B
x3 = phi(x1, x2);   // 합류 지점: 경로에 따라 x1 또는 x2 선택
y1 = x3 + 1;

// phi 함수는 합류 블록의 맨 앞에 위치
// 여러 phi 함수가 있으면 모두 "동시에" 실행된다고 간주

B3:
  x3 = phi(x1, x2)   // B1에서 오면 x1, B2에서 오면 x2
  y3 = phi(y1, y2)
  z1 = x3 + y3

// 원본:
i = 0
loop:
  if (i >= n) goto exit
  i = i + 1
  goto loop
exit:

// SSA:
i1 = 0
loop:
  i2 = phi(i1, i3)    // 루프 진입 시 i1, 루프 반복 시 i3
  if (i2 >= n1) goto exit
  i3 = i2 + 1
  goto loop
exit:

// 이유:
// B가 지배하는 영역 안에서는 x의 정의가 유일
// 지배 경계에서 다른 경로의 정의와 합류할 수 있음
// -> phi 함수가 필요한 곳 = 지배 경계

알고리즘: SSA 구성 (2단계)

1단계: Phi 함수 삽입
  for (각 변수 v):
    W = v를 정의하는 블록들의 집합
    while W가 비어있지 않음:
      B = W에서 블록 하나를 꺼냄
      for (DF(B)의 각 블록 D):
        if D에 v에 대한 phi 함수가 없으면:
          D의 시작에 phi 함수 삽입: v = phi(v, v, ...)
          if D가 W에 없으면 W에 D 추가
          // (phi 함수도 v의 새로운 정의이므로)

2단계: 변수 이름 변경 (Renaming)
  지배자 트리를 깊이 우선으로 순회하면서:
    각 정의에 새 버전 번호 부여
    각 사용을 현재 유효한 버전으로 대체
    phi 함수의 인수를 적절한 선행 블록의 버전으로 설정

// CFG:
//   B1: x = 5
//        |
//   B2: if cond
//      /     \
//   B3: x=10  B4: x=20
//      \     /
//   B5: y = x

// 지배 경계:
// DF(B3) = {B5}
// DF(B4) = {B5}

// 1단계: B5에 phi 함수 삽입
//   B5: x = phi(x, x)

// 2단계: 이름 변경
//   B1: x1 = 5
//   B2: if cond
//   B3: x2 = 10
//   B4: x3 = 20
//   B5: x4 = phi(x2, x3)  // B3에서 오면 x2, B4에서 오면 x3
//       y1 = x4

// SSA 코드:
x1 = 3
y1 = 5
z1 = x1 + y1    // 상수 폴딩: z1 = 8
w1 = z1 * 2     // 상수 폴딩: w1 = 16
if (w1 > 10) goto L1  // 항상 true -> goto L1

// 각 변수가 한 번만 정의되므로:
// x1의 값 = 3 (확정)
// y1의 값 = 5 (확정)
// z1의 값 = 8 (확정)
// 도달 정의 분석 없이 바로 전파 가능!

알고리즘: SCCP

격자: Top(미확인) > 상수값 > Bottom(비상수)

1. 모든 SSA 값을 Top으로 초기화
2. 진입 블록을 실행 가능으로 표시
3. 워크리스트에서 SSA 간선과 CFG 간선을 꺼내면서:
   - SSA 간선: 정의의 값이 변경되면 사용처 갱신
   - CFG 간선: 실행 가능한 간선만 고려
4. 수렴할 때까지 반복

핵심: 실행 불가능한 경로의 값은 고려하지 않음
-> phi(3, Top) = 3 (Top은 아직 도달하지 않은 경로)

// SSA 코드:
x1 = a1 + b1    // x1을 사용하는 곳이 없음 -> 죽은 코드
y1 = c1 * d1    // y1이 아래에서 사용됨
z1 = y1 + 1
return z1

// x1 제거 후:
y1 = c1 * d1
z1 = y1 + 1
return z1

알고리즘: 공격적 DCE

1. 부수 효과가 있는 명령어를 "유용"으로 표시
   (return, store, 입출력, 함수 호출 등)
2. 유용한 명령어가 사용하는 SSA 값의 정의를 "유용"으로 표시
3. 반복: 새로 유용해진 명령어의 피연산자 정의를 추가 표시
4. 유용하지 않은 모든 명령어 제거

// 기존 DCE보다 강력: 불필요한 제어 흐름까지 제거 가능

// SSA 코드:
a1 = x1 + y1
b1 = x1 + y1    // a1과 같은 값!

// 전역 값 번호화:
// x1 + y1에 값 번호 #1 부여
// a1의 값 번호 = #1
// b1의 값 번호 = #1 (같은 연산, 같은 피연산자)
// -> b1 = a1으로 대체

알고리즘: SSA 기반 GVN

해시 테이블 유지: (연산자, 피연산자의 값 번호) -> 값 번호

for (지배자 트리의 깊이 우선 순서로 각 명령어):
    피연산자의 값 번호를 조회
    (연산자, 피연산자 값 번호)로 해시 테이블 검색
    if 발견:
        기존 값 번호를 이 명령어에 배정 (중복!)
    else:
        새 값 번호 부여하고 해시 테이블에 추가

// SSA:
//   B1: a1 = x1 + y1          // 값 번호: v1
//       |
//   B2: b1 = x1 + y1          // 해시 조회: (+ v(x1) v(y1)) -> v1 발견!
//       c1 = b1 * 2            // b1을 a1으로 대체 가능
//
// 최적화 후:
//   B1: a1 = x1 + y1
//   B2: c1 = a1 * 2            // b1 제거

// SSA가 도움이 되는 최적화들:
// 1. 상수 전파    -> def-use 체인으로 효율적 전파
// 2. 죽은 코드 제거 -> 사용처 없는 def를 즉시 식별
// 3. 값 번호화    -> 해시 기반으로 중복 계산 식별
// 4. 복사 전파    -> phi 함수를 통해 복사 관계 추적
// 5. 부분 중복 제거 -> SSA 간선을 통한 효율적 분석
// 6. 레지스터 할당 -> SSA의 활성 범위가 더 짧음

// SSA:
//   B1: x1 = 5
//        |
//   B2: x2 = 10
//        |
//   B3: x3 = phi(x1, x2)

// phi 제거 후:
//   B1: x1 = 5
//       x3 = x1      // B3에서 B1 끝으로 이동
//        |
//   B2: x2 = 10
//       x3 = x2      // B3에서 B2 끝으로 이동
//        |
//   B3: (phi 제거됨, x3 사용)

// SSA:
//   B3: a2 = phi(a1, b1)
//       b2 = phi(b1, a1)
//   (swap 의미: B2에서 오면 a와 b를 교환)

// 잘못된 변환:
//   B2 끝: a2 = b1    // a2에 b1의 값
//          b2 = a1    // 올바름

// 올바른 변환 (임시 변수 사용):
//   B2 끝: temp = a1
//          a2 = b1
//          b2 = temp

// phi 제거 후:
//   B1: x1 = 5
//       x3 = x1     // 불필요한 복사

// 복사 병합 후:
//   B1: x3 = 5      // x1과 x3을 같은 변수로 합침

// 최소 SSA:
x2 = phi(x1, x1)   // 두 인수가 같음 -> 불필요
y2 = phi(y1, ...)   // y2가 이후에 사용되지 않음 -> 불필요

// Pruned SSA: 위 phi 함수들을 삽입하지 않음

// 일반 SSA:
x3 = phi(x1, x2)

// Gated SSA:
x3 = gamma(cond, x1, x2)  // cond가 true이면 x1, false이면 x2
// 최적화에 더 유용한 정보 제공