8장. 최적화 입문

왜 최적화를 하는가, 어디서 어떻게 — 지역/지역간/전역/프로시저간 스코프 정리.

원서 범위: pp. 405–474 키워드: local/regional/global/interprocedural optimization, value numbering, loop unrolling, inline substitution

8.1 들어가며: 최적화는 "더 잘 알기"의 다른 이름

프론트엔드는 소스를 중간 표현(IR)으로 옮기고, 백엔드는 그 IR을 타깃 머신 코드로 옮긴다. 그 사이에 끼어 앉아 있는 미들엔드, 즉 최적화기(optimizer)의 일은 "들어온 IR을 더 좋은 IR로 다시 써내는 것"이다.

여기서 "더 좋다"는 말은 사람마다 다르게 들린다. 보통은 더 빠르게 돈다는 뜻이지만, 임베디드 환경이라면 코드 크기가 작다는 뜻일 수 있고, 모바일이라면 전력을 덜 먹는다거나, 실시간 시스템이라면 응답이 빠르다는 뜻이기도 하다. 모두 최적화의 영역이다.

이 장의 목표는 두 가지다. 하나는 최적화라는 분야의 큰 지도를 그려 보는 것, 다른 하나는 스코프(scope)별 대표 기법을 하나씩 따라가 보는 것이다. 알고리즘 디테일은 9장과 10장에서 더 깊이 파고든다.

8.2 배경: 왜 최적화가 필요한가

1980년대 초반까지만 해도 많은 컴파일러 작성자들은 최적화를 "다 만든 뒤 붙이는 옵션" 정도로 봤다. 그래서 한동안 컴파일러는 두 부류로 나뉘어 있었다.

RISC가 등장하고 프로세서 아키텍처가 점점 컴파일러의 도움을 전제로 설계되면서 — 분기 뒤의 지연 슬롯, 비차단(non-blocking) 메모리 연산, 깊은 파이프라인, 다수의 기능 단위(functional unit) — 이 분리는 무너졌다. 요즘은 어떤 컴파일러든 어느 정도의 최적화를 한다고 가정한다.

8.2.1 예시 — 작은 예와 큰 예

배열 주소 계산 줄이기

FORTRAN에서 m(i,j) 같은 2차원 배열 참조를 떠올려 보자. 프론트엔드는 문맥(context)을 거의 모르는 채로 IR을 만든다. 그래서 일단 가장 일반적인 형태로 적어둔다. 컬럼 메이저(column-major) 저장 기준으로 보면 대충 이런 식이다.

@m + (j − low2(m)) × (high1(m) − low1(m) + 1) × w
   + (i − low1(m)) × w
아무것도 모르는 컴파일러가 적어두는 일반형 주소식.

그런데 m이 로컬 배열이고, 차원의 하한이 1이라고 알면 식은 단숨에 짧아진다.

@m + (j − 1) × hw + (i − 1) × w

여기서 hw = high1(m) × w다. 이 참조가 루프 안에 있다면 어떨까? 강도 감소(strength reduction)를 적용해서 매번 곱하지 않고 덧셈으로 바꿀 수 있다. 안쪽 루프의 (i − 1) × w를 i'1, i'2, …처럼 누적 덧셈으로 풀어쓰는 식이다. 결과적으로 안쪽 주소 계산은 @m + j' + i'까지 쪼그라든다. 곱셈이 사라지고 덧셈 두 번이 남는다.

같은 코드도 문맥을 더 알수록 더 잘 줄일 수 있다는 점에 주목하자. 만약 m이 프로시저의 인자라면, 컴파일러는 차원 정보를 모를 수 있다. 그러면 위와 같은 정리가 막힌다. 최적화는 결국 "분석으로 알아낸 사실"의 양에 비례해서 가능해진다.

LINPACK의 dmxpy 루프

책은 두 번째 예로 LINPACK의 dmxpy 안쪽 루프를 든다. 이 루프는 y ← y + x · m을 수치적으로 계산하는 루틴인데, 손으로 다음 두 단계를 거쳐 최적화되어 있다.

  1. 바깥 j 루프를 16번 언롤링(loop unrolling)했다. 즉, 본문을 16벌 복제하고 인덱스를 그에 맞춰 조정.
  2. 16번 분량의 대입을 한 줄짜리 큰 식으로 합쳤다. y(i) ← y(i) + … 형태가 한 번만 등장.

이렇게 하면 (a) 루프 제어 오버헤드가 1/16로 줄고, (b) y(i)를 16번 적재/저장하던 게 한 번으로 줄며, (c) x(j..j-15)를 안쪽 루프 동안 레지스터에 잡아둘 수 있고, (d) m을 향한 16개의 적재가 메모리 대역폭을 잘 활용한다. 안쪽 루프의 산술 연산 대 메모리 연산 비율이 확 좋아진다.

이상적으로는 컴파일러가 이 변환을 자동으로 해줘야 한다. 그러나 16배 언롤링과 융합을 동시에 하면서, 33개의 서로 다른 주소식을 정리하고, 강도 감소를 적용하고, 적절한 어드레싱 모드를 고르는 일을 한꺼번에 해내는 컴파일러는 흔치 않다. 그래서 LINPACK의 작성자는 직접 손으로 했다.

8.2.2 두 축: 안전성(Safety)과 수익성(Profit)

모든 최적화 변환은 두 질문을 통과해야 한다.

최적화의 두 축
  • 안전성(Safety) — 이 변환이 프로그램의 의미를 바꾸지 않는가? 결과가 같은가?
  • 수익성(Profitability) — 이 변환을 적용하면 정말로 코드가 좋아지는가?

안전한데 이득이 없다면 굳이 적용할 이유가 없고, 이득은 있어 보이는데 안전하지 않다면 절대 해서는 안 된다. 둘 다 만족할 때만 변환이 정당화된다.

안전성 (safety) — 변환이 프로그램의 실행 결과를 바꾸지 않을 때 그 변환은 안전하다.
수익성 (profitability) — 변환을 적용한 결과가 실제로 더 나은 코드일 때 그 변환은 수익성이 있다.

안전성의 형식적 정의는 Plotkin의 관찰적 동치(observational equivalence)다. 두 식 M, N이 어떤 닫힌 문맥 C 안에서 평가될 때 같은 결과를 내거나 둘 다 종료하지 않으면 동치다. 실용에서는 더 느슨하게, "실제 코드 문맥에서 같은 값을 내면 바꿔도 된다" 정도로 쓴다.

dmxpy의 언롤링이 왜 안전한가? 안쪽 루프의 한 반복이 y(i)에만 쓰고, 다음 반복은 다른 y 원소에 쓰기 때문이다. 즉 반복 사이에 의존 관계가 거의 없다. 분석의 상당 부분이 이런 안전성을 증명하는 데 쓰인다.

수익성은 더 미묘하다. dmxpy의 16배 언롤링이 왜 32배가 아닌 16배일까? 16배쯤 되면 x의 값들을 레지스터에 다 담을 수 있기 때문이다. 32배로 가면 레지스터가 부족해져서 적재/저장(load/store)이 다시 추가되고, 그게 언롤링의 이득을 거꾸로 갉아먹는다. 여기서 알 수 있듯, 수익성은 거의 항상 타깃 머신의 자원과 결합돼 있다.

8.2.3 최적화 기회는 어디서 오나

최적화의 재료는 보통 세 곳에서 온다.

  1. 추상화 비용 줄이기 — 소스 언어의 자료구조와 추상은 런타임 지원이 필요하다. 배열 주소 계산이 좋은 예. 일반화된 식을 컴파일 시점에 줄이면 그만큼 명령어가 빠진다.
  2. 특수 케이스 활용 — C++ 컴파일러가 어떤 가상 함수 호출이 항상 같은 구현을 부른다는 걸 알면 일반 디스패치 대신 직접 호출로 바꿀 수 있다.
  3. 자원에 코드 맞추기 — 코드가 요구하는 자원이 프로세서가 줄 수 있는 자원과 맞지 않으면 정렬해줘야 한다. dmxpy의 언롤링이 그렇다. 부동소수 연산당 메모리 접근 수를 줄이는 식의 작업이다.

8.3 최적화의 스코프 — 얼마나 넓게 볼 것인가

최적화는 어느 범위의 코드를 한꺼번에 보느냐에 따라 4단계로 나뉜다. 더 넓게 볼수록 더 강한 사실을 알 수 있지만, 분석 비용도 더 든다.

최적화의 스코프 (scope of optimization) — 한 최적화가 한꺼번에 들여다보는 코드의 범위.

지역(Local) — 단일 기본 블록

기본 블록(basic block)은 분기가 없는 직선 코드의 최대 길이 시퀀스다. 한 번 들어오면 끝까지 실행되고, 중간에 점프해 들어오거나 점프해 나갈 수 없다. 이 단순한 구조 덕분에 두 가지 사실이 깨끗하게 성립한다.

이 두 성질만으로도 강한 분석이 가능하다. 그래서 지역 최적화는 단순한데도 효과적이다. 단점은 분명하다 — 블록 경계 너머의 정보는 못 본다.

지역간(Regional) — 둘 이상의 블록, 한 프로시저 안

여러 블록을 묶어서 본다. 묶는 방법은 자유다. 루프 전체, 확장 기본 블록(extended basic block, EBB), 도미네이터(dominator) 영역, 강연결 컴포넌트(SCC) 등 다양한 단위가 가능하다.

확장 기본 블록 (extended basic block, EBB) — 시작 블록 β1은 CFG에서 여러 선행자(predecessor)를 가질 수 있지만, 나머지 βi는 모두 EBB 안의 다른 블록 단 하나만을 선행자로 갖는 블록 집합. 즉, 한 진입점에서 갈라져 내려가는 트리 모양.

지역간 최적화의 강점은 (1) 자주 실행되는 영역(루프 본문 등)에 집중할 수 있고, (2) 영역마다 다른 전략을 쓸 수 있고, (3) 좁은 범위 안에서는 더 정확한 분석이 가능하다는 점이다.

전역(Global) — 한 프로시저 전체

프로시저 내부 최적화(intraprocedural optimization)라고도 부른다. 프로시저는 자연스러운 분석 단위이고, 분리 컴파일의 단위이기도 하다. 루프 같은 순환 구조까지 포함하므로, 보통 분석을 먼저 한 뒤에 변환을 적용하는 두 단계 구조를 쓴다. 데이터 흐름 분석(data-flow analysis)이 여기서 본격적으로 등장한다.

프로시저간(Interprocedural) — 둘 이상의 프로시저, 또는 전체 프로그램

전체 프로그램 최적화(whole-program optimization)라고도 한다. 프로시저 호출 경계를 넘어가서 분석한다. 호출 그래프(call graph) 위에서 작업한다. 인라인 치환(inline substitution), 프로시저간 상수 전파(interprocedural constant propagation) 등이 대표적이다.

"global"은 "전체 프로그램"이 아니다
컴파일러 용어로 global은 한 프로시저 전체라는 뜻이다. 일상 영어의 "전 우주를 아우르는"이라는 의미와 헷갈리기 쉽다. 프로시저 경계를 넘는 건 interprocedural 또는 whole program이라고 부른다.

일반적으로 스코프가 넓을수록 더 많은 기회가 보이지만, 동시에 분석은 더 흐릿해진다. 더 넓게 본다고 항상 더 좋은 코드가 나오는 건 아니다. 이 미묘한 균형을 잡는 게 컴파일러 작성자의 일이다.

8.4 지역 최적화 — 단일 블록

두 가지 대표 기법을 본다. (1) 중복 계산을 잡아내는 지역 값 번호 매기기(local value numbering, LVN), (2) 식 트리를 다시 짜서 명령어 수준 병렬성을 노출하는 트리 높이 균형(tree-height balancing).

8.4.1 지역 값 번호 매기기 (LVN)

다음 4줄짜리 블록을 보자.

a ← b + c
b ← a − d
c ← b + c
d ← a − d
원본 블록.

여기서 어떤 식이 중복(redundant)인가? 3번째 줄 b + c는 1번째 줄과 글자만 같지, 그 사이에 b가 재정의됐기 때문에 같은 값이 아니다. 반면 4번째 줄 a − d는 2번째 줄의 a − d와 같은 값이다 — 두 사이에 a도 d도 안 바뀌었으니까. 그래서 4번째 줄을 d ← b로 바꿔도 결과는 같다.

중복 (redundant) — 식 e가 점 p에서 중복이라 함은, p에 도달하는 모든 경로 위에서 e가 이미 평가된 적이 있다는 뜻.

알고리즘의 핵심 아이디어

각각의 "값"에 고유한 번호를 매긴다. 두 식이 같은 값을 만든다는 게 증명되면, 같은 번호를 받는다. 같은 번호를 받은 두 식 중 나중 것은 첫 번째 결과를 재사용하면 된다.

구현은 해시 테이블이다. 키는 ⟨피연산자_번호1, 연산자, 피연산자_번호2⟩의 트리플, 값은 그 식의 번호. 블록을 위에서 아래로 한 번 훑으면서, 매 연산마다:

  1. 피연산자 Li, Ri의 값 번호를 얻는다(없으면 새 번호를 발급).
  2. 해시 키를 만든다.
  3. 키가 이미 테이블에 있으면 → 중복! 이 연산을 "이전 값의 복사"로 바꾸고 같은 번호를 부여.
  4. 없으면 새 번호를 만들어 테이블에 등록.

위 예에 적용해 보면 다음과 같은 번호 매김이 나온다.

a2 ← b0 + c1     (값 번호 2 신규)
b4 ← a2 − d3     (값 번호 4 신규)
c5 ← b4 + c1     (b가 재정의됐으니 5 신규)
d4 ← a2 − d3     (이미 번호 4 — 중복!)

4번째 식의 키 ⟨2, −, 3⟩이 테이블에 이미 있다. d는 번호 4를 받고, 코드는 d ← b로 다시 쓰인다.

알고리즘 확장

LVN은 다른 지역 최적화의 자연스러운 틀이 된다.

이름 짓기의 함정

한 가지 미묘한 문제 — 이름이 재정의되면 LVN이 일부 기회를 놓칠 수 있다. 다음을 보자.

a3 ← x1 + y2
b3 ← x1 + y2     ⇒ b ← a   (중복)
a4 ← 174            (a 재정의)
c3 ← x1 + y2     ⇒ ?? a는 더 이상 값 3이 아님

네 번째 줄에서 x + y의 값 번호 3이 어디 있는지 알지만, 이제 a에는 그 값이 없다. 해결책은 두 가지: (1) 값 번호와 이름의 양방향 맵을 유지, 또는 (2) 코드 자체에 첨자를 붙여 각 정의에 고유 이름을 주는 것 (a0, a1, …). 두 번째 방식은 SSA(static single-assignment) 형식의 정신과 같다 — 9장과 5.4.2절에서 자세히 다룬다.

간접 대입의 그늘

포인터를 통한 대입(*p ← 0)이나 배열 원소 대입(a(i,j) ← 0)은 어떤 변수를 바꾸는지 정확히 알기 어렵다. 안전한 쪽은 "이 대입이 건드릴 수 있는 모든 변수의 첨자를 증가"시키는 것이다. 그러면 그 변수들의 기존 값 번호 정보가 무효가 된다. 가혹해 보이지만, 사실 이것이 모호한 간접 참조의 진짜 비용이다.

8.4.2 트리 높이 균형 — 명령어 수준 병렬성 깨내기

a + b + c + d + e + f + g + h를 어떻게 평가할까? 좌결합으로 풀면 ((((((a+b)+c)+d)+e)+f)+g)+h 모양의 깊은 트리가 된다. 이 모양은 한 번에 한 덧셈만 할 수 있다. 7사이클이 든다.

덧셈기가 두 개 있는 프로세서에서는 어떨까? 균형 트리로 다시 짜면 ((a+b)+(c+d)) + ((e+f)+(g+h))가 되어, 1사이클에 4개 덧셈을 동시에 하고 → 다음 1사이클에 2개 → 마지막 1사이클에 1개. 총 4사이클이면 끝난다.

좌결합 트리:                  균형 트리:
       +                          +
      / \                        / \
     +   h                      +   +
    / \                        / \ / \
   +   g                      +  + +  +
  / \                        /\ /\ /\ /\
 ...                         a b c d e f g h
 a   b
사이클: 7                    사이클: 4
같은 식, 다른 평가 순서. 두 개의 단주기 덧셈기 가정.

핵심은 산술의 교환법칙·결합법칙을 이용해 식을 다시 짜서 명령어 수준 병렬성(instruction-level parallelism)을 노출하는 것이다.

알고리즘 — 두 단계로

  1. 1단계: 후보 트리 찾기. 블록을 훑으면서 "재배열 가능한 트리의 뿌리"를 식별한다. 한 트리 안의 연산자는 모두 같아야 하고, 교환·결합 가능해야 한다. 트리가 클수록 재배열 여지가 커지므로 가능한 한 큰 후보 트리를 만든다. 결과를 우선순위 큐에 담는데, 우선순위는 연산자의 우선순위 순서(곱셈이 덧셈보다 먼저 처리되도록).
  2. 2단계: 트리를 평탄화하고(flatten) 다시 짓기(rebuild). 큐에서 뿌리를 하나씩 꺼내, 그 잎을 모은 우선순위 큐를 만든 뒤, 가장 낮은 랭크 두 개를 결합해 새 노드를 만들고 다시 큐에 넣는 식으로 균형 트리를 재구성한다.

이때 중요한 제약 — (a) 변환된 코드는 블록 밖에서 관찰되는 값(observable value)을 모두 보존해야 한다. (b) 블록 시작 이전으로 트리를 확장할 수는 없다. 그래서 UEVar(b)(블록 b에서 정의 전에 사용된 이름들)에 속한 이름은 트리의 잎으로 처리된다.

관찰 가능한 값 (observable value) — 어떤 값이 코드 단편(블록, 루프 등) 밖에서 읽힌다면 그 단편에 대해 관찰 가능하다.

8.5 지역간 최적화 — 블록 너머로

지역 기법을 여러 블록으로 확장해 보자. 한 블록 안에서 못 보던 중복이 인접 블록까지 보면 보일 수 있다.

8.5.1 초지역 값 번호 매기기 (Superlocal Value Numbering, SVN)

아이디어는 단순하다. EBB의 각 경로를 마치 하나의 큰 블록인 양 처리하자. EBB가 (B0, B1, …)이라면, 각 경로 (B0, B1), (B0, B2, B3) 식으로 나눠서 각 경로마다 LVN을 적용한다.

구현의 핵심은 "블록을 처리한 효과를 깔끔하게 되돌릴 수 있어야 한다"는 점이다. 같은 선행자 B0을 여러 경로가 공유하므로, B0을 처리한 뒤 그 상태에서 가지를 쳐 내려갔다가 또 가지를 쳐 내려가야 한다.

가장 깔끔한 방식은 스코프 해시 테이블(scoped hash table)을 쓰는 것이다. 블록에 들어갈 때 새 스코프를 만들고, 빠져나올 때 그 스코프를 지우면 된다(렉시컬 스코프 처리에 쓰던 것과 같은 도구를 재활용).

주의할 점 — 다중 선행자(multiple predecessors)를 가진 블록은 어떤 단일 선행자의 컨텍스트도 신뢰할 수 없으므로, 그냥 LVN으로 처리한다. SVN은 항상 EBB의 트리 구조를 따라 흐른다.

SVN이 LVN보다 더 잡아내는 게 무엇인가? B0에서 정의된 식이 B2나 B3에서 또 등장하면 LVN은 못 보지만 SVN은 본다. 반대로 한계도 있다 — EBB의 트리 모양에서 벗어나 진입(merge)이 일어나는 블록은 못 본다. 그걸 잡으려면 다음 단계, 전역으로 가야 한다.

8.5.2 루프 언롤링 (Loop Unrolling)

가장 오래된, 가장 잘 알려진 루프 변환. 본문을 k번 복제하고 인덱스 계산을 거기에 맞춘다. 앞서 본 dmxpy의 16배 언롤링이 그 예.

두 가지 전략이 있다.

이득과 위험

직접적 이득:

간접적 이득(다른 최적화의 도우미 역할):

위험:

그래서 언롤링 인자(unroll factor)는 정답이 없다. 일부 시스템은 여러 인자를 시도해서 가장 빠른 걸 고르는 적응적(adaptive) 접근을 쓴다.

8.6 전역 최적화 — 프로시저 한 통째로

스코프를 프로시저 전체로 넓히면 루프 같은 순환 구조가 들어온다. 이때부터는 분석 단계를 먼저 돌려서 사실을 모은 뒤 변환을 적용한다.

8.6.1 라이브 정보로 초기화 안 된 변수 찾기

변수 v가 정의 전에 사용될 가능성이 있는지 알면, 그건 보통 버그 신호다. 컴파일러가 알려주면 좋다.

핵심 개념은 생존성(liveness)이다. 점 p에서 변수 v가 살아 있다(live)는 건, p에서 v를 사용하는 어느 점까지 v를 재정의 없이 도달하는 경로가 있다는 뜻이다. 각 블록 b의 출구에서 살아 있는 변수 집합을 LiveOut(b)로 인코딩한다. 만약 진입 노드 n0의 LiveOut(n0)에 v가 있다면, v는 초기화 전에 사용될 수 있다.

데이터 흐름 분석 (data-flow analysis) — 컴파일 시점에 런타임 값들의 흐름에 대해 추론하는 일련의 기법. 보통 그래프의 노드와 간선 위에 정의된 집합 방정식의 동시 해(simultaneous solution)로 푼다.

방정식 세우기

LiveOut은 다음 식으로 정의된다.

LiveOut(n) = ⋃m ∈ succ(n) ( UEVar(m) ∪ ( LiveOut(m) ∩ VarKill(m) ) )

여기서:

해석은 직관적이다. n의 출구에서 살아 있는 변수는, n의 어느 후속 블록 m에 들어가서 (a) m에서 정의 전에 쓰이거나(UEVar(m)), (b) m에서 안 죽고 살아남아 m의 출구에서도 살아 있는(LiveOut(m) ∩ VarKill(m)) 그런 변수다.

이 방정식은 그래프의 간선을 거꾸로 따라가는 역방향 데이터 흐름 문제(backward data-flow problem)다. 모든 LiveOut을 빈 집합으로 초기화한 뒤, 모든 노드를 한 번씩 다시 계산하는 패스를 더 이상 변화가 없을 때까지 반복하면(고정점 반복, fixed-point iteration) 해가 나온다.

한계와 false positive

이 분석은 보수적이다. 즉 실제로는 절대 발생하지 않는 경로도 가능한 것으로 친다. 그래서 가짜 경고(false positive)가 나올 수 있다. 예를 들어 i = 1; while (i <= n) { if (i == 1) s = 0; … } 같은 코드는 첫 반복에서 반드시 s를 초기화하지만, 데이터 흐름 분석은 "if를 안 들어갈 수도 있다"고 가정해서 s가 초기화 안 된 상태로 쓰일 수 있다고 본다. 더 정확히 알려면 상수 전파나 심볼릭 평가가 필요한데, 비용이 훨씬 비싸진다.

라이브 정보의 다른 쓸모

8.6.2 전역 코드 배치 (Global Code Placement)

많은 프로세서는 분기 비용이 비대칭이다. 폴스루(fall-through) 분기(다음 명령어로 그냥 떨어지는 경우)가 테이큰(taken) 분기보다 싸다. 그러면 자주 가는 쪽을 폴스루로, 거의 안 가는 쪽을 테이큰으로 배치하면 이득이 있다.

예를 들어 (B0, B2) 간선이 (B0, B1)보다 100배 자주 실행된다면, B0 다음에 B2를 두는 "빠른 배치(fast layout)"가 좋다. 두 배치의 차이가 100배 비율로 누적된다.

핫 패스(Hot Path) 만들기

실행 빈도 정보(프로파일 데이터, 실측 또는 추정)를 CFG의 간선 가중치로 쓴다. 간선을 빈도 높은 순으로 정렬해서, 그리디하게 체인을 잇는다. 간선 (x, y)를 처리할 때, x가 자기 체인의 마지막이고 y가 자기 체인의 처음이라면 두 체인을 연결한다. 그렇지 않으면 건너뛴다(다른 체인 안에 묶인 상태로 둔다).

최종 결과는 "핫 패스 묶음" — 자주 실행되는 경로일수록 폴스루로 연결된 긴 체인 안에 들어 있다.

프로파일 데이터를 어떻게 모으나
  • 계측된 실행 파일 — 진입/이탈/분기 카운터를 코드에 박아 실행하면서 기록.
  • 타이머 인터럽트 — 일정 간격으로 PC를 샘플링해 히스토그램을 만든다.
  • 하드웨어 성능 카운터 — 사이클 수, 캐시 미스, 분기 등 하드웨어 이벤트를 직접 센다.

8.7 프로시저간 최적화 — 호출 경계를 넘어

프로시저 호출은 분석의 벽이다. fee가 fie를 호출할 때, 호출 전후로 x의 값이 보존되는지 알려면 fie가(그리고 fie가 다시 호출하는 모든 함수가) x를 안 건드린다는 걸 증명해야 한다. 또한 모든 호출은 precall/postreturn(호출자 측) prolog/epilog(피호출자 측) 시퀀스를 끌고 다닌다 — 일반화된 추상의 비용이다.

8.7.1 인라인 치환 (Inline Substitution)

호출 지점을 피호출자(callee)의 본문 복사본으로 바꾼다. 매개변수 바인딩에 맞게 본문을 살짝 다시 쓴다. 호출 그래프를 바꾸므로 프로시저간 변환으로 분류된다.

인라인 치환 (inline substitution) — 호출 지점을 피호출자 본문의 복사본으로 대체하는 변환. 매개변수 바인딩을 반영해서 본문을 다시 쓴다.

이득은 두 가지 출처에서 나온다.

  1. 직접 — 링키지 시퀀스(레지스터 저장/복원, 활성 레코드 할당 등)가 거의 사라진다. 호출자의 컨텍스트로 본문이 들어오니 죽은 코드가 더 잘 보일 수 있다.
  2. 간접 — 인라인된 본문이 호출자의 문맥(상수 인자 등)과 결합돼 후속 최적화가 더 강하게 작동한다.

손해도 있다 — 코드가 커지고, 이름 공간이 비대해지고, 한 영역에 레지스터 압력이 몰릴 수 있다. 그래서 어떤 호출 지점을 인라인할지의 결정 절차가 핵심이다.

결정 절차에 들어가는 기준

실제 결정 휴리스틱은 보통 임계값 파라미터 t0, t1, …의 조합으로 표현되며, 프로그램마다 최적값이 다르다.

8.7.2 프로시저 배치 (Procedure Placement)

전역 코드 배치(8.6.2)는 한 프로시저 안의 블록을 재배열했다. 같은 아이디어를 한 단계 위에서 — 실행 가능 이미지 안에서 프로시저들을 재배열할 수 있다. 목표는 가상 메모리 작업 집합(working set)을 줄이고 명령어 캐시 충돌을 줄이는 것.

호출 그래프 위에서, 간선 (p, q)가 자주 실행될수록 p와 q를 메모리에서 가까이 배치하고 싶다. 그러나 p가 q, r, s 셋 다 호출한다면 셋 모두를 p 옆에 둘 수는 없다 — 그래서 그리디 근사 알고리즘을 쓴다.

알고리즘 골격:

  1. 호출 그래프를 만들고, 각 간선에 실행 빈도로 가중치를 매긴다.
  2. 가중치가 큰 순서로 우선순위 큐에 넣는다.
  3. 큐에서 간선 (x, y)를 꺼내 y의 배치 리스트를 x의 리스트에 이어 붙인다. 그래프에서 y를 제거하고, y로/에서 가던 간선을 x로 옮긴다(ReSource, ReTarget).
  4. 큐가 빌 때까지 반복.

코드 배치(8.6.2)와 다르게, 프로시저 배치는 폴스루 분기를 만들 필요가 없다 — 단지 가까이 두기만 하면 캐시 이득을 본다. 그래서 프로시저 배치 쪽이 운신의 폭이 조금 더 넓다.

8.7.3 컴파일러의 구조적 영향

프로시저간 최적화는 컴파일러 구조 자체를 바꾼다. 전통적인 컴파일 단위(compilation unit)는 한 프로시저, 한 클래스, 또는 한 파일이었다. 최적화기가 프로시저 A의 정보를 써서 프로시저 B를 정리하면, A를 수정한 순간 B의 컴파일 결과가 무효가 된다 — 소스에는 안 보이는 의존성이 생긴다.

해결책 후보들:

8.8 정리 — 스코프가 넓어질수록 사실은 강해지지만…

최적화는 결국 "일반적인 번역 스킴을 그 자리의 구체적 사정에 맞춰 깎아내는 일"이다. 추상의 비용을 줄이고, 특수 케이스를 활용하고, 코드의 자원 요구를 머신의 자원에 맞춘다.

그 과정에서 두 축을 매번 검사한다 — 안전성(의미 보존)과 수익성(실제 개선). 안전성은 분석으로 증명하고, 수익성은 휴리스틱과 모델로 추정한다. 어느 한쪽이라도 깨지면 변환은 적용되지 않는다.

스코프별로 잡히는 것이 다르다.

한 가지 직관적이지 않은 사실로 끝맺는다 — 스코프를 넓힌다고 결과 코드가 항상 더 좋아지진 않는다. 더 넓게 보면 더 많은 사실이 들어오지만, 동시에 분석은 더 흐릿해지고 더 보수적이 되기 쉽다. 어떤 스코프에서 어떤 기법을 쓸지 고르는 일 — 그게 최적화기 설계의 본업이다. 다음 두 장에서 데이터 흐름 분석(9장)과 스칼라 최적화(10장)를 통해 이 주제를 더 깊이 들어간다.

← 이전7장. 코드 모양 다음 →9장. 데이터 흐름 분석