코드 최적화

코드 최적화는 프로그램의 의미를 바꾸지 않으면서 계산 횟수를 줄이거나 실행시간을 짧게, 기억용량을 적게 만드는 변환이다.

코드 최적화를 하기 위해선 두 가지 조건이 요구된다.

• 중간 결과에 이름이 있어야 한다. T2 := C + D처럼 결과에 이름이 붙어 있어야 그 줄을 다른 곳으로 옮길 수 있다. 스택 위 익명의 자리에 있으면 옮길 수 없다. 3-주소 코드가 최적화용 중간언어인 이유다.

• 제어 흐름이 그래프여야 한다. 분기 없이 순차 실행되는 최대 구간을 기본 블록이라 하고, 블록을 노드로 흐름을 간선으로 만든 것이 흐름 그래프라 한다. 최적화를 하기 위해선 이 값이 여기까지 살아 있는가, 이 코드에 도달할 수 있는가? 같은 질문에 답할 수 있어야 하고, 그래프 구조에선 이것들이 쉽게 가능하다.

두 벡터의 내적을 구하는 코드를 3-주소 코드로 바꾸면 이렇다.

(1)  PROD := 0
(2)  i := 1
(3)  T1 := 4 * i
(4)  T2 := addr(A) - 4
(5)  T3 := T2[T1]          /* A[i] */
(6)  T4 := addr(B) - 4
(7)  T5 := T4[T1]          /* B[i] */
(8)  T6 := T3 * T5
(9)  PROD := PROD + T6
(10) i := i + 1
(11) if i ≤ 200 goto (3)

(3)~(11)이 하나의 기본 블록이자 루프 몸통이다. T2 := addr(A) - 4와 T4 := addr(B) - 4는 i와 무관하므로 루프를 200번 도는 동안 값이 변하지 않는다. 루프 밖으로 빼면 계산 횟수가 400번에서 2번으로 줄어든다. 이 판단을 하려면 “무엇이 루프 안에서 바뀌는가”를 알아야 하고, 그러려면 흐름 그래프가 필요하다.

변환의 갈래

개별 기법은 많지만 무엇을 근거로 삼느냐로 묶인다.

값이 이미 정해져 있다

X := 3.14;  Y := 2 * X      →   Y := 6.28        상수 접기·전파
A := B;     C := A + D      →   C := B + D       복사 전파
Y := X + 0                  →   Y := X           대수적 간소화

이미 계산했다

A := B+C+D;  E := B+C+F;  K := (B+C)*G
→  T1 := B+C;  A := T1+D;  E := T1+F;  K := T1*G     공통 부분식 제거

여러 갈래에 같은 식이 있으면 그보다 앞선 한 곳으로 끌어올린다(code hoisting).

결과를 쓰지 않는다

도달할 수 없는 코드와 결과가 사용되지 않는 코드를 지운다.

더 싼 연산이 있다

X ** 2   →   X * X
X * 2    →   X + X

루프를 돌 때마다 일정하게 변하는 변수를 귀납변수라 하고, 곱셈을 덧셈으로 바꿀 수 있다. 위 예제의 T1 := 4 * i가 그렇다. 매번 곱하는 대신 T1 := 0 후 T1 := T1 + 4로 바꾼다.

루프

• 루프 불변 코드 이동: 값이 변하지 않는 계산을 루프 앞으로 뺀다
• 루프 융합: 범위가 같은 루프 둘을 하나로 합쳐 루프 제어 명령을 줄인다
• 루프 전개: 몸통을 복제해 반복 횟수와 분기 횟수를 줄인다

호출 경계

인자 전달, 레지스터 저장·복원, 프레임 확보가 호출마다 든다. 본체를 호출 지점에 펼치면 이 비용이 사라진다.

procedure P(X): if X < 10 then A := X+2 else A := X*2

P(5)  →  X := 5; if X < 10 then A := X+2 else A := X*2
      →  if true then A := 7 else A := 10        (상수 전파)
      →  A := 7                                   (분기 제거)

인라인은 다른 최적화를 열어 준다. 펼치기 전에는 P 안을 최적화할 근거가 없었는데, 펼치고 나니 상수 전파가 되고 분기가 사라졌다.

제어 흐름

goto L1
L1: goto L2       →    goto L2 …

if A > B goto L2; goto L3; L2: 같은 형태는 조건을 뒤집어 if A ≤ B goto L3; L2:로 줄인다.

실제로 일어나는 것

clang으로 확인할 수 있다. 공통 부분식 제거를 보자.

int f(int B, int C, int D, int F, int G) {
    int A = B + C + D;
    int E = B + C + F;
    int K = (B + C) * G;
    return A + E + K;
}

%6  = add nsw i32 %1, %0      ; B + C — 한 번만
%7  = add i32 %4, 2           ; G + 2
%8  = mul i32 %7, %6          ; (B+C) * (G+2)
%9  = add i32 %3, %2          ; D + F
%10 = add i32 %9, %8

B + C가 한 번만 계산된다. 그런데 그 이상을 했다. A+E+K = 2(B+C) + D + F + (B+C)·G를 (B+C)(G+2) + (D+F)로 다시 묶었다. 공통 부분식 제거 위에 대수적 재결합이 얹힌 것이다. 이 재결합은 정수라서 가능하다. 부동소수점에서는 (a+b)+c ≠ a+(b+c)이므로 같은 변환이 기본적으로 꺼져 있다.

루프 불변 코드 이동도 그대로 보인다.

for (int i = 0; i < n; i++)
    A[i] = B + C;

6:                                    ; 루프 진입 전(preheader)
  %7 = add nsw i32 %2, %1             ; B + C — 루프 밖으로 나왔다
  br label %10

10:                                   ; 루프 몸통
  %11 = phi i64 [ 0, %6 ], [ %13, %10 ]
  %12 = getelementptr inbounds nuw i32, ptr %0, i64 %11
  store i32 %7, ptr %12               ; 저장만 한다
  %13 = add nuw nsw i64 %11, 1
  br i1 %14, label %9, label %10

B + C가 몸통(블록 10) 밖의 preheader(블록 6)로 나갔고, 몸통은 저장만 한다. 교재 예제 T := B+C; for i:=1 to 1000 do A := T와 같다. 옮길 코드를 둘 자리가 필요해서 블록을 하나 새로 만든 것이다.

연산 세기 경감도 확인된다.

int f(int x) { return x * 8; }   →   shl nsw i32 %0, 3      곱셈 → 시프트
int g(int x) { return x / 4; }   →   sdiv i32 %0, 4         그대로

x * 8은 시프트가 되는데 x / 4는 그대로다. 부호 있는 나눗셈은 0 방향으로 반올림해야 해서 산술 시프트와 결과가 다르기 때문이다. 의미가 보존될 때만 바꾼다.

동적 타입 언어에서는 왜 안 되는가

CPython도 최적화를 한다. 상수 접기가 되고,

x = 2 * 3.14
#   LOAD_CONST  6.28        컴파일 시점에 계산됨

도달 불가능한 코드가 지워지고,

def f(a):
    return a
    print("never")     # 바이트코드에 없다

중첩된 조건의 분기가 하나의 목적지로 합쳐지고, 인접한 명령이 슈퍼명령어로 묶인다.

LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)     ← LOAD 둘이 하나로

Python/flowgraph.c 4,261줄이 이 일을 하고, 패스 이름을 보면 성격이 드러난다.

optimize_cfg  ├ optimize_basic_block       기본 블록 안 정리
              ├ optimize_load_const        상수 관련
              ├ optimize_load_fast         지역변수 로드
              ├ optimize_lists_and_sets
              ├ remove_unreachable         도달 불가능 블록
              └ remove_redundant_jumps/nops 점프·NOP 정리
remove_unused_consts
insert_superinstructions
push_cold_blocks_to_end

전부 peephole과 제어 흐름 수준이다. 앞에서 본 루프 불변 코드 이동은 없다.

def f(A, B, C, n):
    for i in range(n):
        A[i] = B + C

L1:  FOR_ITER
     STORE_FAST  i
     LOAD_FAST_BORROW_LOAD_FAST_BORROW (B, C)
     BINARY_OP  0 (+)          ← 루프 안에 그대로 남아 있다
     ...
     JUMP_BACKWARD  L1

B + C가 매 반복마다 계산된다. clang이 빼냈던 바로 그 코드다.

못 하는 게 아니라 할 수 없다. B + C의 +가 무엇을 하는지 컴파일 시점에 알 수 없기 때문이다. B가 __add__에 부수 효과가 있는 객체라면 200번 부르는 것과 1번 부르는 것은 다른 프로그램이다. 공통 부분식 제거도 마찬가지다. B와 C가 그사이에 다른 것을 가리키게 될 수도 있다.

교재의 최적화 기법 대부분은 타입이 정적이고 연산에 부수 효과가 없다는 전제 위에 있다. 그 전제가 없으면 컴파일 시점의 정보만으로는 안전한 변환을 증명할 수 없다.

그래서 동적 언어는 다른 길로 간다. 컴파일 시점에 증명할 수 없다면 실행 시점에 관찰하고, 관찰한 사실을 가드로 지키면서 최적화하는 것이다. 인라인 캐싱과 특수화가 그 답이고, 그 위의 JIT가 결국 하는 일도 가드로 타입을 고정한 구간에서 고전적 최적화를 적용하는 것이다. 최적화 기법 자체는 같고 전제를 확보하는 방법이 다르다.

순서 문제

최적화를 어떤 순서로 적용하느냐에 따라 결과가 달라진다. 앞서 본 인라인이 대표적이다. 인라인 → 상수 전파 → 분기 제거로 이어지지만, 순서가 반대면 아무것도 얻지 못한다.

반대로 서로를 방해하기도 한다. 루프 전개는 몸통을 키워 명령 캐시 압박을 늘리고, 인라인은 코드 크기를 늘려 다른 함수의 인라인을 막는다. 최적 순서를 구하는 일반적인 방법은 알려져 있지 않고, 실용적으로는 잘 듣는 순서를 경험적으로 정하거나 같은 패스를 여러 번 돌린다. 전역 분석은 그 자체로 비싸기 때문에 -O0부터 -O3까지 단계를 두어 컴파일 시간과 절충한다.

레지스터 할당은 별개의 어려움이다. 자료가 레지스터에 있으면 로드·저장 명령이 없어지지만 레지스터 개수는 한정되어 있고, 최적 할당은 그래프 착색 문제로 NP-완전이다. 실제로는 휴리스틱을 쓴다.

---

참고

• 중간언어
• 인라인 캐싱과 특수화
• opcode
• 컴파일 과정
• https://llvm.org/docs/Passes.html
• https://llvm.org/docs/LangRef.html
• https://github.com/python/cpython/blob/main/InternalDocs/compiler.md
• https://github.com/python/cpython/blob/main/Python/flowgraph.c