7장. 코드 모양 만들기

표현식, 배열, 문자열, 제어 흐름, 호출까지 — 소스 구조를 IR로 옮기는 디테일.

7.1 들어가며 — "모양"이라는 단어의 무게

같은 일을 하는 코드도 어떻게 짜느냐에 따라 빠르거나 느리고, 메모리를 많이 먹거나 적게 먹는다. 컴파일러도 마찬가지다. 같은 소스 한 줄을 IR로 옮기는 길이 여러 갈래라면, 그중 어떤 길을 고르느냐가 최종 코드의 품질을 좌우한다. 저자들은 이 선택의 총체를 코드 모양(code shape)이라고 부른다 — 큰 결정이든 작은 결정이든, IR과 어셈블리에서 계산을 어떤 형태로 표현할지에 관한 모든 결정.

코드 모양이 왜 중요한지 한눈에 보이는 예가 C의 switch문이다. 1바이트짜리 문자값을 분기하는 switch를 구현하는 길은 적어도 셋이다. (1) if-then-else를 줄줄이 이어 붙여 선형 검색을 시키거나, (2) 정렬된 키 위에서 이진 검색을 돌리거나, (3) 256개 라벨 점프 테이블을 만들어 한 번에 점프시키거나. 균등 분포 입력이라면 선형 검색은 평균 128회 비교, 이진 검색은 8회 비교, 점프 테이블은 그냥 상수 시간이다. 같은 의미인데 성능은 두 자릿수씩 차이가 난다.

표현식도 마찬가지다. x + y + z는 정수의 덧셈이 결합·교환 법칙을 만족하므로 어느 순서로 더해도 된다. 그러나 어떤 순서로 묶느냐에 따라 (1) 사용하는 레지스터 수가 달라지고, (2) 상수 폴딩 같은 최적화 기회가 드러나거나 가려지고, (3) 이미 계산해둔 부분식을 재사용할지 말지가 갈린다. 좋은 컴파일러 작가는 이런 차이가 IR 단계에서 나중 패스(레지스터 할당, 명령어 스케줄링, 최적화)에 어떤 정보로 전달될지를 의식하면서 모양을 빚는다.

7.2 저장 위치 배정 — 값 하나에 자리 하나

코드를 만들기 전에 컴파일러는 프로그램이 만들어내는 모든 값에 살 곳을 정해줘야 한다. 변수의 타입·크기·가시성·수명을 따져 데이터 영역(data area)을 그룹별로 묶고, 정렬 규칙을 지키면서 각자에게 오프셋을 부여하고, 레지스터에 둘지 메모리에 둘지를 결정한다.

이름이 있는 값과 없는 값

변수처럼 소스에 이름이 박혀 있는 값은 수명이 명확하다. 정적 변수는 프로시저가 다시 호출돼도 살아남고, 지역 변수는 한 호출 안에서 마지막 사용까지만 살면 된다. 반면 A[i-3, j+2] 안의 i-3 같은 임시 값은 이름이 없다 — 컴파일러가 이런 값은 어디에 두고 얼마나 오래 살릴지 자유롭게 결정해도 된다.

메모리 모델: 두 갈래 길

컴파일러는 IR을 짤 때 큰 가정 하나를 깔고 간다. 바로 메모리 모델이다.

이 책 전체가 채택하는 쪽은 후자, 즉 레지스터-투-레지스터 모델이다. 분석과 최적화가 풀어야 할 이름 공간이 깔끔하게 드러나기 때문이다.

주소 공간 레이아웃

운영체제와 협력해 컴파일러는 단일 프로그램의 가상 주소 공간을 다음과 같이 나눈다.

  Low                                                 2ⁿ
  ┌──────┬────────┬──────────────  ──────────────┬──────┐
  │ Code │ Static │ Heap → ····      ···· ← Stack│      │
  └──────┴────────┴──────────────  ──────────────┴──────┘
                          (자유 메모리)

이 가상 주소를 OS가 페이지(page) 단위로 물리 주소에 매핑한다. 컴파일러 입장에선 물리 주소 자체는 신경 쓰지 않는다 — 다만 페이지 크기 안에서 두 변수가 같은 캐시 라인에 들어갈지 여부만 신경 쓸 뿐.

오프셋과 정렬

각 데이터 영역 안에서 컴파일러는 변수마다 오프셋을 부여해야 한다. 32비트 정수는 4바이트 경계에, 64비트 더블은 8바이트 경계에 시작하라는 식의 정렬 규칙(alignment rule)을 ISA가 강제한다. 변수를 나열할 때 가장 빡빡한 정렬부터 가장 느슨한 정렬까지 순서대로 배치하면 패딩 낭비가 최소화된다. 정렬 단위가 거의 항상 2의 거듭제곱이라 한 카테고리의 끝은 다음 카테고리의 시작에 자동으로 맞아떨어지기 때문이다.

모호한 값과 모호하지 않은 값

경험적 규칙은 단순하다 — 모호한 값은 정의 직후 store, 사용 직전 load. 그리고 다른 모호한 값에 대한 정의·사용을 사이에 끼고는 절대 모호한 값을 레지스터에 보존하지 않는다. ANSI C의 restrict 키워드는 "이 포인터는 모호하지 않다"고 알려주는 약속이고, volatile은 그 반대 — "예고 없이 값이 바뀔 수 있으니 캐싱하지 말라"는 신호다. 저장 배정 단계에서 모호성 정보를 IR에 새겨두면 이후 분석이 한결 단순해진다.

7.3 산술 연산자 — 트리워크의 미학

현대 RISC 명령어 집합은 산술·시프트·불 연산을 모두 3-주소 형식으로 제공한다. 즉 add ra, rb ⇒ rt 같은 모양이다. 결과에 새 이름이 붙으니 나중에 재사용할 수도 있고, 2-주소 형식의 골치(피연산자가 파괴됨)도 없다.

트리워크 코드 생성기

가장 우아한 표현식 코드 생성기는 AST(추상 구문 트리)에 대한 후위 순회(post-order tree walk)이다. 각 노드를 만났을 때:

expr(node) {
  int result, t1, t2;
  switch (type(node)) {
    case ×, ÷, +, -:                    // 이항 연산자
      t1 ← expr(LeftChild(node));
      t2 ← expr(RightChild(node));
      result ← NextRegister();
      emit(op(node), t1, t2, result);
      break;
    case IDENT:                          // 변수 식별자
      t1 ← base(node);                   // 베이스 주소가 들어 있는 레지스터
      t2 ← offset(node);                 // 오프셋이 들어 있는 레지스터
      result ← NextRegister();
      emit(loadAO, t1, t2, result);
      break;
    case NUM:                            // 정수 리터럴
      result ← NextRegister();
      emit(loadI, val(node), none, result);
      break;
  }
  return result;
}

예컨대 a - b × c를 이 생성기에 던지면, a·b·c 모두 현재 AR 안에 있다고 가정할 때 다음과 같은 7개 명령어가 나온다.

loadI   @a       ⇒ r1     // a의 오프셋
loadAO  rarp,r1  ⇒ r2     // a의 값
loadI   @b       ⇒ r3     // b의 오프셋
loadAO  rarp,r3  ⇒ r4     // b의 값
loadI   @c       ⇒ r5     // c의 오프셋
loadAO  rarp,r5  ⇒ r6     // c의 값
mult    r4,r6    ⇒ r7     // b × c
sub     r2,r7    ⇒ r8     // a - (b×c)

레지스터 수요 줄이기 — 평가 순서의 마법

같은 식을 어떤 순서로 평가하느냐에 따라 동시에 살아 있어야 하는 값의 개수가 달라진다. 일반 규칙: 각 노드에서 더 많은 레지스터를 필요로 하는 자식부터 먼저 평가하라. 그러면 두 번째 자식을 평가하는 동안 살려둬야 하는 값은 첫 번째 결과 하나뿐이다.

a + b × c를 왼쪽에서 오른쪽으로 평가하면 8개 레지스터가 동시에 살아 있어야 하지만, b × c를 먼저 평가하는 오른쪽 우선 방식으로 가면 한 개를 절약한다. a × b + c × d 같은 표현식에서는 왼쪽 우선이 더 적게 쓰고, a + (b + c) × d 같은 식은 또 다른 순서가 최적이다. 평소엔 컴파일러가 두 패스 — 먼저 자식별 레지스터 수요 분석, 다음에 그 정보로 코드 emit — 로 처리한다.

매개변수와 함수 호출이 끼어들면

매개변수가 값으로 전달(call-by-value)된 경우는 그냥 지역 변수와 같다. 그러나 참조 전달(call-by-reference)이라면 한 단계 추가된다 — 매개변수 슬롯에 들어 있는 게 값이 아니라 주소이므로, 그 주소를 먼저 로드한 뒤 다시 거기서 값을 로드해야 한다.

표현식 안에 함수 호출이 등장하면 평가 순서를 자유롭게 바꿀 수 없다. 부작용(side effect)이 호출 전후의 변수 값을 바꿀 수 있기 때문이다. 컴파일러 입장에선 호출이 어떤 부작용을 일으키는지 알 수 없으면 "최악의 경우"를 가정 — 즉, 호출 가능한 모든 변수를 호출 시점에 메모리로 내리고, 호출 후 다시 읽어야 한다. 인터프로시저 분석(9.4절)이 바로 이 보수적 가정을 깎아내려는 시도다.

혼합 타입과 대입

피연산자 타입이 다르면 컴파일러가 변환 코드를 자동으로 끼워 넣는다. 보통 둘 중 더 일반적인 타입으로 끌어올리고, 결과를 다시 좌변 타입으로 변환한다. 한편 대입(a ← b)은 다음 세 단계로 정리된다.

1. 우변(b)을 값(rvalue)으로 평가한다.
2. 좌변(a)을 위치(lvalue)로 평가한다 — 메모리 주소이거나 레지스터 이름.
3. 값을 위치에 store.

7.4 불(Boolean)과 관계 연산자 — 진리값을 어떻게 표현할까

불 값을 어떻게 표현할지를 두고 두 진영이 있다.

수치 인코딩 vs 위치 인코딩

a < b ∨ c < d ∧ e < f를 비교·분기 방식으로 곧이곧대로 짜면, 11개 연산에 분기 3번, 점프 3번이 들어간다. 그러나 단락 평가(short-circuit evaluation)를 적용해 위치 인코딩으로 다시 짜면, 결과 값을 만들지 않고도 진리값을 결정할 수 있는 시점에 곧장 분기 — 훨씬 짧아진다.

관계 연산을 지원하는 네 가지 하드웨어 모델

타깃 ISA에 따라 컴파일러의 선택지가 갈린다.

요지: 비교 결과를 변수에 담아야 한다면 수치 인코딩이 필요하지만, 결과가 단지 제어 흐름을 결정할 뿐이라면 위치 인코딩(또는 술어 실행)이 거의 항상 더 효율적이다.

7.5 배열 — 인덱스에서 주소까지

스칼라까지는 모두 메모리의 한 칸을 차지한다고 가정해왔지만, 실제 프로그램은 배열을 쓴다. 그리고 배열 원소 하나의 주소를 계산하는 일은 — 의외로 — 산수가 많이 들어간다.

벡터: 가장 단순한 배열

1차원 배열 V[low...high]의 V[i] 주소는 다음과 같다.

address(V[i]) = @V + (i - low) × w

여기서 w는 원소 하나의 바이트 길이. 단순한데도 여기서 곱셈 1개, 뺄셈 1개, 덧셈 1개가 등장한다. w가 2의 거듭제곱이라면 곱셈을 시프트로 바꿀 수 있고, 베이스+오프셋 주소 모드(loadAO)가 덧셈을 명령어 안으로 흡수해준다.

가짜 0 (false zero)

매번 (i - low)를 빼는 게 거슬린다. 그래서 컴파일러는 가짜 0 주소를 도입한다.

가짜 0을 한 번 계산해두면, 이후로는 address(V[i]) = @V₀ + i × w로 끝난다. 뺄셈이 사라진다. C가 모든 배열의 하한을 0으로 강제하는 이유 중 하나도 이것 — 자동으로 @V₀ = @V가 된다.

다차원 배열의 저장 방식

2차원 이상 배열은 1차원 메모리에 어떻게 펼치느냐에 따라 세 갈래다.

1. 행 우선(row-major) 순서 — C, Java가 사용. 같은 행의 원소들이 연속 메모리에 배치. A[1,1], A[1,2], A[1,3], A[1,4], A[2,1], ...
2. 열 우선(column-major) 순서 — FORTRAN. 같은 열이 연속. A[1,1], A[2,1], A[1,2], A[2,2], ...
3. 간접 벡터(indirection vectors) — BCPL, Java의 다차원 배열. 각 행마다 별도 저장 공간 + 그 행들을 가리키는 포인터 벡터. 톱니 배열(ragged array)을 자연스럽게 만들 수 있다.

저장 방식은 지역성과 직결된다. 다음 이중 루프를 보자.

for i ← 1 to 2
   for j ← 1 to 4
      A[i,j] ← A[i,j] + 1

행 우선이라면 가장 안쪽 첨자 j가 가장 빨리 변하므로 메모리를 순차 접근 — 캐시 친화적이다. 만약 루프 순서가 뒤집혀 j가 바깥, i가 안쪽이면, 같은 코드가 행 사이를 건너뛰며 접근해 캐시 미스가 폭발한다.

행 우선의 주소 다항식

A[1...2, 1...4]처럼 선언된 2차원 배열의 A[i,j] 주소는 다음과 같이 펼쳐진다.

address(A[i,j]) = @A + (i - low₁) × len₂ × w + (j - low₂) × w

여기서 len₂ = high₂ - low₂ + 1은 두 번째 차원의 길이. 가짜 0을 적용하면 다음처럼 깔끔해진다.

@A₀ = @A − (low₁ × len₂ × w + low₂ × w)
address(A[i,j]) = @A₀ + (i × len₂ + j) × w

곱셈 두 번, 덧셈 두 번, 그게 끝이다. i가 r_i, j가 r_j에 있고 len₂가 컴파일 타임 상수라면 ILOC 코드는 다음과 같다.

loadI   @A₀          ⇒ r@A₀     // 가짜 0 베이스
multI   r_i, len₂    ⇒ r1       // i × len₂
add     r1, r_j      ⇒ r2       // + j
multI   r2, 4        ⇒ r3       // × 원소 길이 (4바이트)
loadAO  r@A₀, r3     ⇒ r_a      // A[i,j] 값 로드

도프 벡터(dope vector)와 매개변수 배열

배열을 매개변수로 넘길 땐 보통 참조 전달이다. 그런데 callee가 주소 다항식을 만들려면 — 차원 정보가 필요하다. FORTRAN처럼 차원을 매개변수로 따로 받게 하든, 아니면 컴파일러가 도프 벡터(dope vector)라는 디스크립터를 만들어 함께 넘긴다.

도프 벡터를 통한 접근은 비용이 더 든다. 차원 정보를 메모리에서 한 번 더 읽어야 하고, 컴파일러가 배열 모양을 완전히 알지 못해 최적화 기회가 줄어든다.

범위 검사(range checking)

Java나 Ada는 배열 범위를 벗어난 접근을 런타임에 잡아 보고하라고 요구한다. 가장 단순한 구현은 매 참조마다 인덱스가 유효 범위에 있는지 검사를 끼워 넣는 것 — 배열을 많이 쓰는 프로그램에선 부담이 크다. 최적화 컴파일러는 (1) 검사가 절대 실패하지 않음을 증명해 제거하거나, (2) 루프 밖으로 검사를 빼내거나, (3) 여러 검사를 합쳐 하나로 만든다.

7.6 문자열 — 작은 데이터, 큰 디테일

문자열을 다루는 방식은 언어마다 천차만별이다. C는 라이브러리 호출(strcpy, strlen, …)에 의존하고, PL/I는 대입·부분 문자열·연결을 일급 연산으로 제공한다.

두 가지 표현

널 종료(null termination)는 C 스타일이다. 문자열 끝에 '\0'이라는 보초 문자를 둔다. 길이를 알려면 처음부터 끝까지 훑어야 한다 — O(n).

명시적 길이 필드는 PL/I 스타일이다. 문자열 앞에 길이를 정수로 박아둔다. 길이 계산이 상수 시간(loadAI 한 번)으로 끝난다.

   ┌─────────────────────────┐    ┌──────┬───────────────────┐
   │ a │ │ s │ t │ r │ i │ n │    │  8   │ a │ │ s │ t │ r │ │
   │ g │\0│   │   │   │   │   │    │      │ i │ n │ g │   │   │
   └─────────────────────────┘    └──────┴───────────────────┘
        널 종료 (C)                      명시적 길이 (PL/I)

문자 단위 vs 워드 단위 대입

하드웨어가 바이트 단위 load/store를 지원한다면 a[1] ← b[2] 같은 단일 문자 대입은 깔끔하다. 그렇지 않으면 — 워드를 통째 읽고, 마스크와 시프트로 해당 바이트만 추출하고, 다른 워드를 읽어 마스크로 비우고, OR로 끼워 넣고, 다시 store한다. 명령어 9개짜리 시퀀스가 된다.

긴 문자열 대입(a ← b)은 길이를 비교해 오버플로 라벨로 분기한 뒤, 카운터를 올리며 한 글자씩 옮기는 루프가 된다. 워드 단위 load/store로 한 번에 4바이트씩 옮기고 말미의 자투리 글자만 바이트 단위로 처리하면 더 빠르다.

현실 컴파일러는 단순 케이스만 인라인으로 짜고, 겹치는 부분 문자열이나 정렬이 다른 경우엔 OS의 잘 튜닝된 라이브러리(memcpy, memmove)를 호출한다.

연결과 길이

문자열 연결은 결국 대입의 연속이다 — a 뒤에 b를 붙이려면 (1) a의 길이를 구하고, (2) 그 뒤의 빈 공간이 충분한지 확인하고, (3) b의 글자들을 차례로 옮긴다. 길이가 명시적 필드라면 (1)이 상수 시간이고 (2)의 검사도 컴파일 타임에 끝낼 수 있다.

고전적인 최적화 예시: length(a + b)는 굳이 합쳐서 길이를 잴 필요가 없다 — 그냥 strlen(a) + strlen(b)로 푸는 게 낫다. 명시적 길이라면 두 번의 loadAI와 한 번의 add로 끝난다.

7.7 구조체 참조 — 오프셋 테이블의 세계

구조체(struct, record)는 서로 다른 타입의 값을 묶는 도구다. C의 연결 리스트 노드를 보자.

struct node {
   int value;
   struct node *next;
};

컴파일러는 구조체별로 레이아웃 테이블과 요소 테이블을 유지한다. 레이아웃 테이블은 구조체의 전체 크기와 첫 요소를 가리키고, 요소 테이블은 각 필드의 이름·길이·오프셋·타입을 적어둔다. 위 예시에서 node의 길이는 8, node.value의 오프셋은 0, node.next의 오프셋은 4이다.

그러므로 p1->next는 다음처럼 번역된다.

loadI   4         ⇒ r1   // next의 오프셋
loadAO  r_p1, r1  ⇒ r2   // p1->next 값

레이아웃과 정렬 패딩

다음 구조체를 보자.

struct example {
   int    fee;     // 4바이트, 4정렬
   double fie;     // 8바이트, 8정렬
   int    foe;     // 4바이트, 4정렬
   double fum;     // 8바이트, 8정렬
};

선언 순서대로 배치하면 fee(0–3) 뒤에 4바이트 패딩, fie(8–15), foe(16–19) 뒤에 4바이트 패딩, fum(24–31) — 총 32바이트. 그러나 컴파일러가 자유롭게 재배치할 수 있다면 8정렬 필드를 먼저 두고(fie, fum), 4정렬 필드(fee, foe)를 뒤에 모아 — 24바이트로 줄어든다, 패딩 0. 언어 정의가 사용자에게 레이아웃을 노출하느냐 마느냐가 컴파일러의 자유도를 결정한다.

구조체 배열과 유니온

구조체 배열은 두 가지 레이아웃이 가능하다 — 구조체 인스턴스를 통째로 반복(array of structs)하거나, 같은 필드끼리 모아 별도 배열로 분리(struct of arrays)하거나. 캐시 동작이 사뭇 달라진다.

유니온(union, variant record)은 하나의 메모리 영역을 여러 해석으로 공유한다. 같은 필드 이름이 여러 변형에 나타날 수 있어, C는 완전 한정 이름(fully qualified name)(u1.inode.value)으로 모호성을 해결한다. 일부 시스템은 런타임 태그(tag) 필드로 어느 변형인지 식별하는 동적 디스패치를 한다.

포인터와 익명 값

fee = (struct node *) malloc(sizeof(node))로 만든 노드는 — 이름이 없다. 오직 포인터 fee를 통해서만 접근된다. 컴파일러 입장에선 익명 값(anonymous value)이고, 두 포인터가 같은 메모리를 가리키는지 일반적으로 결정 불가능하다(undecidable). 그래서 포인터 기반 접근은 보수적으로 처리 — 매번 메모리에서 새로 읽는다. 이게 포인터-집약적 코드가 스칼라 코드보다 느린 본질적 이유다.

7.8 제어 흐름 구문 — 흐름의 꽃

컴파일러는 연속된 비분기 명령들을 모아 기본 블록(basic block)을 만들고, 블록 사이의 분기·점프 관계를 제어 흐름 그래프(CFG)로 표현한다. 그 위에 소스 언어의 제어 구조가 어떻게 얹히는지가 이번 절의 주제다.

7.8.1 조건 실행 — if-then-else

같은 if (x < y) then a ← c+d else a ← e+f도 하드웨어 모델에 따라 모양이 갈린다.

// 조건 코드 + 분기
comp    rx, ry     ⇒ cc1
cbr_LT  cc1        → L1, L2
L1: add rc, rd     ⇒ ra
    jumpI          → Lout
L2: add re, rf     ⇒ ra
    jumpI          → Lout
Lout: nop

// 술어 실행 — 분기 없음
cmp_LT  rx, ry     ⇒ r1
not     r1         ⇒ r2
(r1)? add rc, rd   ⇒ ra
(r2)? add re, rf   ⇒ ra

술어 실행은 분기를 완전히 없애 짧고 깔끔하지만, 모든 술어 명령어가 발급(issue) 슬롯을 잡아먹는다 — 술어가 false인 명령어도 자리를 차지한다. then·else가 작을 때는 분기 비용보다 술어 절약이 크지만, 둘 다 명령어 10개씩이고 머신이 사이클당 2개를 발급한다면 분기 버전이 분기 1번 + 5사이클 + 점프 1번 ≈ 7사이클로 끝나는 반면, 술어 버전은 양쪽 모두 발급하느라 10사이클을 쓴다. 어느 길에 코드가 얼마나 들어 있느냐, 한쪽이 훨씬 자주 실행되느냐, 내부에 또 다른 제어 흐름이 있느냐 — 이 셋이 결정 변수다.

7.8.2 루프와 반복

C의 for (e₁; e₂; e₃) { body }를 다음 5단계 스키마로 옮긴다.

1. e₁ 평가 (초기화)
2. e₂가 거짓이면 5번으로 점프 (진입 조건)
3. 본문 실행
4. e₃ 평가 후 e₂ 재평가, 참이면 3번으로 (재반복)
5. 루프 다음 코드

for (i=1; i<=100; i++) { body }를 ILOC로 옮기면 다음과 같다.

     loadI    1          ⇒ r_i      // Step 1
     loadI    100         ⇒ r1       // Step 2
     cmp_GT   r_i, r1     ⇒ r2
     cbr      r2          → L2, L1
L1:  loop body                       // Step 3
     addI     r_i, 1      ⇒ r_i      // Step 4
     cmp_LE   r_i, r1     ⇒ r3
     cbr      r3          → L1, L2
L2:  next statement                  // Step 5

두 군데에 비교가 있는 형태(스텝 2 + 스텝 4)는 살짝 길지만, 본문 외 비교가 한 번뿐인 컴팩트 형태로 줄일 수도 있다. 본문이 한 블록인지 두 블록인지에 따라 스케줄러가 분기 지연 슬롯을 채울 여지가 달라진다.

FORTRAN의 do 루프 — 그림자 인덱스 변수

FORTRAN의 do 루프는 시작 시점에 반복 횟수가 고정된다. 본문이 인덱스 변수를 바꿔도 횟수에 영향을 주지 않는다. 그래서 컴파일러는 본문이 못 건드리는 숨은 인덱스(그림자 인덱스 변수, shadow index variable)를 만들어 진짜 반복 카운터로 사용한다.

while, until, break, continue

while은 초기화가 없을 뿐 같은 스키마를 따른다. until은 반대로 — 조건이 거짓인 동안 반복하고, 본문 평가 뒤에 검사한다(따라서 최소 1회는 실행). break와 continue는 그냥 라벨로의 즉시 점프로 구현된다.

꼬리 재귀를 반복으로

Lisp 계열에선 반복을 표현하는 자연스러운 수단이 꼬리 재귀다. 호출 자체가 함수 본문의 마지막 명령이라면 호출 후 할 일이 없으므로, 새 활성 레코드를 쌓을 필요 없이 — 호출자의 AR을 그대로 재사용하고 점프로 끝낼 수 있다.

7.8.3 case 문 — 점프 테이블의 부활

본 장 도입부에서 미리 짚었던 switch가 다시 등장한다. 컴파일러는 케이스 라벨의 분포를 보고 세 전략 중 하나를 고른다.

1. 선형 검색 — 케이스가 서너 개 정도일 때. if-then-else 사슬로 변환. 빈도가 높은 케이스를 위에 배치해 평균 비용을 줄인다.
2. 이진 검색 — 케이스가 많고 라벨이 띄엄띄엄할 때. 정렬된 (값, 라벨) 테이블 위에서 로그 시간 검색.
3. 점프 테이블 (직접 주소 계산) — 라벨이 {0, 1, 2, …, 9}처럼 빽빽한 정수일 때. @Table + index × 4를 계산해 단번에 점프. 빈 슬롯은 default 라벨로 채운다.

t1 ← e1
if (0 > t1 or t1 > 9)
   then jump to LB_d
   else
      t2 ← @Table + t1 × 4
      t3 ← memory(t2)
      jump to t3

좋은 IR은 점프의 가능한 목적지 집합을 명시적으로 노출한다(예: ILOC의 tbl 의사 연산). 그래야 이후 분석이 더 정확한 결과를 만든다.

7.9 프로시저 호출 — 네 조각의 협주

프로시저 호출은 호출자(caller)와 피호출자(callee)에 분산된 네 조각의 코드 시퀀스로 구현된다.

Procedure p                            Procedure q
┌────────────┐                         ┌─────────────┐
│  Prologue  │                         │  Prologue   │
├────────────┤                         ├─────────────┤
│  Precall   │ ──── Call ────────────► │             │
├────────────┤                         │  ...callee  │
│ Postreturn │ ◄──── Return ────────── │             │
├────────────┤                         ├─────────────┤
│  Epilogue  │                         │  Epilogue   │
└────────────┘                         └─────────────┘

일반 규칙: 가능한 한 precall과 postreturn에서 일을 빼서 prologue와 epilogue로 옮겨라. callee에 한 번 들어가는 prologue는 호출 사이트마다 중복으로 들어가는 precall보다 코드 크기를 줄인다.

실 매개변수 평가

precall 시퀀스가 매개변수를 평가한다. 값 전달이라면 식을 평가해 미리 약속된 자리(레지스터 또는 callee의 AR)에 저장. 참조 전달이라면 매개변수의 주소를 그 자리에 저장. 만약 참조 전달인데 매개변수에 메모리 주소가 없다면(예: 임시 표현식의 결과), 컴파일러가 임시 저장 공간을 만들어 주소를 잡아줘야 한다.

평가 순서가 부작용을 가진 호출을 포함하면 결과가 달라질 수 있으므로, 컴파일러는 일관된 순서(왼쪽→오른쪽 또는 그 반대)를 지켜야 한다. subtract(pop(), pop())는 명시적 예시 — 어느 방향으로 평가하느냐에 따라 결과가 뒤집힌다.

레지스터 저장과 복원

호출 규약(linkage convention)은 어떤 레지스터를 caller가 보존할지(caller-saves), 어떤 레지스터를 callee가 보존할지(callee-saves)를 정한다. 레지스터 수가 늘면서 일일이 store/load하는 비용도 늘어났다. 컴파일러 작가가 쓸 수 있는 카드 셋:

• 다중 레지스터 메모리 연산 — SPARC의 register window, Power의 멀티워드 load/store처럼 여러 인접 레지스터를 한 명령어로 살리는 기능.
• 라이브러리 루틴 — save/restore를 컴파일러가 만든 도우미 함수로 묶는다. 호출 사이트엔 점프 한 번만. callee는 어떤 레지스터를 살릴지 비트마스크로 도우미에 알린다.
• 책임 통합 — caller가 "이런 레지스터를 살려라"는 신호를 callee에 넘기면, callee가 자신의 callee-saves까지 합쳐 한 번에 처리. 호출 한 번 비용으로 양쪽 책임을 다 끝낸다.

왜 호출이 어려운가

호출은 분석·최적화 관점에서 까다로운 지점이다. 첫째, caller-callee 관계가 다대일 — 한 callee가 여러 사이트에서 호출된다. 둘째, 코드가 분산돼 있어 변환이 일관되게 적용되기 어렵다. 셋째, 표준 호출 규약을 조금만 어겨도 다른 컴파일러가 만든 코드와 호환이 깨진다. 그래서 컴파일러 작가들은 호출 시퀀스를 매우 보수적으로 다룬다 — 안전이 곧 호환성이다.

7.10 마무리

같은 소스 한 줄을 어떤 모양의 IR과 어셈블리로 옮길지 — 이 결정의 누적이 컴파일러의 품질을 만든다. 학습용·디버깅용 컴파일러라면 가장 단순하고 직관적인 변환으로 충분하지만, 최적화 컴파일러라면 그다음 패스(저수준 최적화, 명령어 스케줄링, 레지스터 할당)에 정보를 최대한 노출하는 모양을 골라야 한다.

case문이 그 차이를 드러내는 고전적 예시다. 디버깅 컴파일러에선 if-then-else 사슬로도 충분하지만, 최적화 컴파일러는 IR 단계에서 이미 이진 검색이나 점프 테이블 형태로 빚어두지 않으면 — 나중 최적화 패스 어느 것도 사슬을 점프 테이블로 바꿔주지 않는다. 모양은 처음부터 옳게 잡아야 한다는 게 이 장의 핵심 메시지다.