结果相同、代价更低的程序 — CFG 与 SSA

한국어 원문으로 표시합니다.

한 줄 요약

최적화는 프로그램을 같은 결과를 내는 더 싼 프로그램으로 바꾸는 일입니다. 트리에서는 상수를 미리 계산하고 정해진 가지를 걷어 내고, 명령 목록에서는 기본 블록과 제어 흐름 그래프(CFG) 를 세워 들어갈 길이 없는 코드를 지웁니다. 그 그래프 위에서 지배자를 구하면, 실무 컴파일러의 중간 표현인 SSA 가 φ 를 어디에 두는지까지 계산할 수 있습니다.

왜 이게 필요했나

사람은 읽기 좋게 씁니다. 60 * 60 * 24 라고 쓰지 86400 이라고 쓰지 않고, 디버그용 if (false) { … } 를 남겨 두며, return 뒤에 줄을 남기기도 합니다. 6모듈의 컴파일러는 이것을 적힌 그대로 옮기므로, 반복문 안의 60 * 60 * 24 는 돌 때마다 곱셈 두 번이 됩니다. 컴파일러가 대신 미리 계산할 수 있다면 사람은 읽기 좋은 코드를 쓰고도 빠른 프로그램을 얻습니다.

단, 최적화에는 넘으면 안 되는 선이 하나 있습니다. 결과가 달라지면 안 됩니다. 7 / (3 - 3) 을 "상수니까 미리 계산" 하려다 컴파일러가 죽거나, 오류를 없애 버리면 안 됩니다 — 그 줄은 실행될 때 그 자리에서 0 나누기 오류를 내야 합니다. 최적화기는 할 수 있는 것보다 하면 안 되는 것을 먼저 아는 쪽이 좋은 최적화기입니다.

어떻게 동작하나

상수 접기. 트리를 아래에서 위로 걸으며 양쪽이 리터럴인 연산을 계산해 리터럴 하나로 바꿉니다. 64비트 감기와 0 쪽 나눗셈은 인터프리터와 똑같이 지키고, 실행하면 오류가 날 식(0 나누기, 음수 지수, 타입이 맞지 않는 연산)은 접지 않고 남깁니다. 접은 리터럴은 원래 연산자의 위치를 물려받습니다. false && f() 는 오른쪽이 실행되지 않으므로 통째로 false 이고, true && e 는 e 가 됩니다. if (true) 는 그 가지(블록 그대로 — 스코프가 남도록)로, while (false) 는 통째로 사라집니다.

기본 블록과 CFG. 명령 목록에서 첫 명령, 점프가 가는 곳, 점프·RETURN 바로 다음을 '리더' 로 표시하면, 리더에서 다음 리더 앞까지가 기본 블록입니다. 블록 안으로는 첫 명령으로만 들어오고 마지막 명령으로만 나갑니다. 블록마다 다음 블록(흘러내리는 쪽, 점프하는 쪽)을 적은 것이 CFG 입니다. 입구에서 CFG 를 따라 닿지 않는 블록은 지워도 됩니다 — 이 코스의 컴파일러는 모든 함수 끝에 CONST 0 · RETURN 을 붙이므로, return 으로 끝나는 함수마다 그 두 명령이 닿지 않는 코드로 남아 있습니다. 지우고 나면 남은 점프의 오프셋을 새 자리로 다시 재야 합니다.

fn pos(v) { if (v < 0) { return 0; } return v; }

 B0  0 GET_LOCAL 0         B0 → B1(흘러내림), B2(점프)
     1 CONST 0   ; 0
     2 LT
     3 JUMP_IF_FALSE 2 ; → 6
 B1  4 CONST 0   ; 0       B1 → 없음(RETURN)
     5 RETURN
 B2  6 GET_LOCAL 0         B2 → 없음
     7 RETURN
 B3  8 CONST 0   ; 0       ← 입구에서 닿지 않는다(컴파일러가 붙인 꼬리): 지운다
     9 RETURN

지배자와 SSA. 블록 d 가 블록 b 를 지배한다는 것은 입구에서 b 로 가는 모든 길이 d 를 지난다는 뜻입니다. 모든 블록의 지배자 집합은 "b 의 지배자 = {b} ∪ (앞 블록들의 지배자의 교집합)" 을 더는 바뀌지 않을 때까지 되풀이해 구합니다. 이것이 왜 필요한가 — 실무 컴파일러(LLVM·GCC)의 중간 표현은 SSA, 모든 변수가 딱 한 번만 대입되는 형태입니다. x = 1; if (c) x = 2; print x; 를 SSA 로 바꾸면 x1 = 1, x2 = 2, 그리고 두 길이 합쳐지는 곳에 x3 = φ(x1, x2) 가 생깁니다. φ 는 "어느 길로 왔느냐에 따라 고른다" 는 뜻입니다.

      B0: x1 = 1; if c
       /          \
  B1: x2 = 2       |
       \          /
      B2: x3 = φ(x1, x2); print x3        ← B2 는 B1 의 지배 경계

φ 를 어디에 둘지는 지배 경계(dominance frontier)가 알려 줍니다. 블록 b 의 지배 경계는 b 가 지배하는 곳에서 한 걸음 나가 처음으로 지배가 끊기는 블록들 — 곧 b 에서 온 값과 다른 길에서 온 값이 처음 만나는 곳입니다. 변수가 대입되는 블록들의 지배 경계에 φ 를 두고, 새로 둔 φ 도 대입으로 쳐서 더는 늘지 않을 때까지 넓힙니다(반복 지배 경계).

현장에서 만나는 모습

-O2 의 거의 전부가 이 그래프 위에서 돈다. 상수 전파, 죽은 코드 제거, 공통식 제거, 반복문 밖으로 끌어내기가 모두 SSA 와 CFG 위의 계산입니다. SSA 에서는 변수마다 정의가 하나라 "이 값은 어디서 왔나" 가 한 번에 보이기 때문입니다. 10모듈에서 clang 의 LLVM IR 을 열면 phi 명령을 직접 보게 됩니다.
최적화가 버그를 드러낼 때. "-O0 에서는 되는데 -O2 에서 결과가 다르다" 는 대부분 최적화기의 버그가 아니라 프로그램의 정의되지 않은 동작(부호 있는 정수 넘침 같은)을 최적화기가 '일어나지 않는 일' 로 믿고 지운 결과입니다. 결과를 바꾸지 않는다는 약속은 정의된 동작에 대해서만 지켜집니다.
디버깅이 어려워지는 이유. 최적화된 코드에서 변수가 "optimized out" 으로 보이는 것은 그 변수가 SSA 의 여러 값으로 쪼개지고 일부가 사라졌기 때문입니다.

다음 실습에서 할 것

opt.py 에 식 접기, 프로그램 접기(정해진 가지 걷기), 기본 블록, CFG, 닿지 않는 블록 지우기(점프 다시 재기), 지배자와 직속 지배자, 지배 경계와 φ 자리, 그리고 접기 → 컴파일 → 지우기 파이프라인을 만듭니다. 채점기는 트리·청크·그래프를 기준과 대조하고, 최적화한 프로그램이 같은 결과를 내면서 명령을 덜 실행하는지 VM 으로 확인합니다.