[컴파일러] 13. 머신 독립 코드 최적화 기초

// 최적화 전
a = b + c
d = a - e
f = b + c    // b + c는 이미 계산됨
g = f - e

// 최적화 후
a = b + c
d = a - e
f = a        // b + c 대신 a 재사용
g = f - e    // 또는 g = d (a-e도 공통 부분식)

// 블록 B1:
//   t1 = a + b
//   ...
// 블록 B2: (B1에서 도달 가능, a와 b가 변경되지 않음)
//   t2 = a + b    // B1의 t1과 같은 값

// 최적화 후
// 블록 B2:
//   t2 = t1       // 재사용

// C 코드
x = a[i][j] + a[i][j+1];

// 컴파일 시 생성되는 중간 코드
t1 = i * n       // 행 오프셋
t2 = t1 + j      // a[i][j]의 인덱스
t3 = a[t2]
t4 = i * n       // 공통 부분식! (t1과 동일)
t5 = t4 + j + 1  // a[i][j+1]의 인덱스
t6 = a[t5]
x = t3 + t6

// 최적화 후
t1 = i * n
t2 = t1 + j
t3 = a[t2]
t5 = t1 + j + 1  // t4 대신 t1 재사용
t6 = a[t5]
x = t3 + t6

// 최적화 전
a = b + c       // a가 이후에 사용되지 않으면 죽은 코드
d = e * f
return d

// 최적화 후
d = e * f
return d

// C 코드 예시
int debug = 0;    // 디버그 모드 끔

void process() {
    // ... 처리 로직 ...

    if (debug) {    // 조건이 항상 false
        printf("Debug info");  // 죽은 코드
    }
}

// 최적화 전
x = 3 + 5
y = x * 2

// 상수 폴딩 후
x = 8
y = x * 2

// 상수 전파 + 상수 폴딩 후
x = 8
y = 16

// 최적화 전
n = 10
i = 0
limit = n - 1

// 상수 전파 후
n = 10
i = 0
limit = 10 - 1  // n을 10으로 대체

// 상수 폴딩 후
n = 10
i = 0
limit = 9

// 최적화 전
x = 1
if x > 0 goto L1
goto L2

// 상수 전파 + 상수 폴딩 후
x = 1
if 1 > 0 goto L1  // 항상 true
goto L2            // 도달 불가능

// 분기 간소화 후
x = 1
goto L1

// 최적화 전
while (i < limit) {
    // t = n * 4 는 루프 불변
    t = n * 4
    a[i] = t + i
    i = i + 1
}

// 최적화 후
t = n * 4          // 루프 밖으로 이동
while (i < limit) {
    a[i] = t + i
    i = i + 1
}

명령어 s: x = y op z를 루프 밖으로 이동할 수 있는 조건:

1. s가 포함된 블록이 루프의 모든 출구를 지배(dominate)
2. x가 루프 내에서 다른 곳에서 정의되지 않음
3. 루프 내에서 x를 사용하는 모든 곳이 s의 정의에만 도달

// i는 기본 유도 변수 (매 반복 +1)
// j는 파생 유도 변수 (j = 4*i이므로 매 반복 +4)
for (i = 0; i < n; i++) {
    j = 4 * i
    a[j] = 0
}

// 최적화 전
i = 0
L1: if i >= n goto L2
    j = 4 * i        // 곱셈 (비쌈)
    a[j] = 0
    i = i + 1
    goto L1
L2:

// 강도 감소 후
i = 0
j = 0              // j의 초기값
L1: if i >= n goto L2
    a[j] = 0
    i = i + 1
    j = j + 4       // 곱셈을 덧셈으로 대체
    goto L1
L2:

// 강도 감소 후
i = 0
j = 0
L1: if i >= n goto L2
    a[j] = 0
    i = i + 1
    j = j + 4
    goto L1
L2:

// 유도 변수 제거 후 (i를 j로 대체)
j = 0
limit = 4 * n      // 종료 조건 변환
L1: if j >= limit goto L2
    a[j] = 0
    j = j + 4
    goto L1
L2:

// 최적화 전
x = y
z = x + 1     // x 대신 y 사용 가능

// 복사 전파 후
x = y          // 이 줄은 죽은 코드가 될 수 있음
z = y + 1

// 공통 부분식 제거 후
a = b + c
...
f = a          // b + c 대신 복사

// 복사 전파 후 (f 사용처에 a를 대입)
// f가 불필요해지면 죽은 코드로 제거

// 블록 B:
//   d1: x = a + b    // gen: d1, kill: x의 다른 모든 정의
//   d2: y = c - d    // gen: d2, kill: y의 다른 모든 정의

// 도달 정의 분석의 전달 함수
OUT[B] = gen(B) U (IN[B] - kill(B))

// IN[B]는 모든 선행 블록의 OUT 합집합
IN[B] = U OUT[P]  (P는 B의 모든 선행 블록)

1. 상수 폴딩 / 상수 전파
   -> 상수를 먼저 확정하여 다른 최적화에 기여

2. 공통 부분식 제거
   -> 중복 계산 제거

3. 복사 전파
   -> 불필요한 복사 제거 준비

4. 죽은 코드 제거
   -> 위 최적화로 인해 발생한 죽은 코드 정리

5. 루프 불변 코드 이동
   -> 루프 밖으로 코드 이동

6. 유도 변수 / 강도 감소
   -> 루프 내 비용 절감

7. 반복 (수렴할 때까지)