부록 B. 자료 구조

집합 표현, IR 자료구조, 해시 테이블, 심볼 테이블 설계 — 컴파일러 작가의 도구상자.

B.1 들어가며 — 효율은 인프라에서 결정된다

본문 13개 장에서 우리는 알고리즘과 변환을 이야기했다. 그러나 컴파일러가 실제로 빠르게 돌아가느냐, 큰 입력에서도 멀쩡히 살아남느냐를 결정짓는 것은 의외로 그 아래 깔린 자료구조다. 컴파일러는 매일, 어쩌면 매분 실행된다. 그래서 한 번 한 번의 패스(pass)가 1% 빨라지면 그것이 누적되어 엄청난 시간이 절약된다. 점근 복잡도(asymptotic complexity)와 기대 복잡도(expected complexity)가 모두 중요하다는 뜻이다.

부록의 핵심 메시지는 이렇다 — 컴파일러가 푸는 문제는 대부분 오프라인(offline) 문제다. 운영체제가 페이지를 교체할 때는 미래에 어떤 페이지가 필요할지 알 수 없지만, 컴파일러는 입력 프로그램 전체를 미리 읽을 수 있다. 그래서 OS에서는 학술적 호기심에 그치는 알고리즘(예: 벨라디(Belady)의 MIN)이 컴파일러에서는 실용 알고리즘이 된다. 같은 이유로, 우주(universe) U의 크기가 미리 알려진 자료구조를 자유롭게 쓸 수 있다.

그러나 무료 점심은 없다. 첫 패스는 입력을 다 읽기 전까지 IR이 얼마나 커질지 모른다. 따라서 프론트엔드(front end)는 자료구조가 우아하게 자라도록 설계해야 한다. 반대로 그 다음 패스부터는 IR 크기를 어림짐작할 수 있으므로, 1만 개 이름이 등록된 IR을 받아놓고 1024개 슬롯짜리 심볼 테이블로 시작하는 멍청한 일은 하지 말아야 한다. IR 파일 자체에 주요 자료구조의 대략적 크기를 적어두는 것은 좋은 관행이다.

B.2 집합(Set)을 표현하는 세 가지 방법

컴파일에는 집합이 끊임없이 등장한다. 부분집합 구성(subset construction, 2장), LR(1) 항목들의 정준 모음(canonical collection, 3장), 데이터 흐름 분석(8·9장), 명령어 스케줄링의 ready queue(12장)…. 집합 연산의 비용은 표현 방식에 따라 천차만별이다. 자주 쓰는 연산 — member, insert, delete, clear, union, intersect, complement — 중에 어느 것이 자주 호출되느냐에 따라, 그리고 |S|가 |U|에 비해 얼마나 희소(sparse)하냐에 따라 최적의 자료구조가 달라진다.

여기서는 컴파일러가 즐겨 쓰는 세 가지 표현을 살펴본다. 정렬 연결 리스트(ordered linked list), 비트 벡터(bit vector), 그리고 다소 영리한 희소 집합(sparse set)이다.

B.2.1 정렬 연결 리스트

가장 단순한 방법이다. 노드 하나가 원소 하나를 담고, 다음 노드를 가리킨다. 원소를 오름차순으로 배열해둔다. 공간은 |S|에 비례하고, |U|의 크기를 미리 몰라도 된다 — 그래서 그래프 컬러링 레지스터 할당기에서 라이브 레인지(live range)를 발견하는 단계처럼 우주의 크기를 동적으로 발견하는 상황에 잘 어울린다.

대부분의 연산은 O(|S|)이다. 리스트를 끝까지 걷어야 하기 때문이다. clear만은 예외인데, 아레나(arena) 기반 할당이나 가비지 컬렉션 환경이라면 노드를 일일이 풀어줄 필요가 없어 상수 시간이 된다.

한 가지 영리한 변형 — 한 노드에 여러 원소를 묶어 담기다. k개씩 묶으면 할당 횟수가 ⌈n/k⌉로 줄어든다. 점근 복잡도는 그대로지만 상수 인자가 좋아진다. 9장의 빠른 지배자(dominator) 계산에 쓰이는 IDoms 배열은 이 아이디어의 정수다 — 정렬 집합에서 "e ∈ S₁이고 e ∈ S₂이면 e 이후의 모든 원소가 S₁에서도 S₂에 있다"는 특이한 성질을 이용해, n개 원소짜리 배열 하나로 n개의 정렬 집합을 동시에 표현하고 빠른 교집합 연산까지 얻어낸다.

B.2.2 비트 벡터

우주 U의 크기를 미리 알 수 있다면, 길이 |U|의 비트열을 통째로 깔아버리는 것이 압도적으로 빠르다. i번째 비트가 1이면 i ∈ S다. 이를 특성 벡터(characteristic vector)라 부른다.

  0       i-1  i  i+1     j-1  j  j+1     k-1  k  k+1     |U|-1
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 |...| 0 | 1 | 0 |...| 0 | 1 | 0 |...| 0 | 1 | 0 |...|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                S = { i, j, k },  i < j < k

겉보기에 많은 연산이 O(|U|)지만, 한 워드(word)가 32비트나 64비트씩 한꺼번에 처리되므로 상수 인자가 워드 크기만큼 작다. 32개 이하 원소짜리 우주라면 단일 워드로 표현되어, union은 OR 한 번, intersect는 AND 한 번이다. 이 압축성과 단순성 때문에 데이터 흐름 분석에서 비트 벡터가 표준이 되었다.

B.2.3 희소 집합 — 두 개의 배열로 만든 마법

|S|가 |U|보다 워드 크기 이상의 비율로 작다면, 비트 벡터조차 낭비다. 희소 집합(sparse set)은 이 영역의 챔피언이다. 길이 |U|짜리 두 배열 sparse와 dense, 그리고 스칼라 next(=원소 개수)로 이루어진다.

                0         i              j           k                |U|-1
        sparse [...] [   1   ] [...] [   0   ] [...] [   2   ] [...]
                                                       ^

                0    1    2    3                                    |U|-1
        dense  [ j ][ i ][ k ][   ] [   ] ........................
                              ^
                              |
                            next = 3

핵심은 두 배열이 서로를 가리키도록 유지하는 것이다. 원소 i가 집합에 있다는 것은 다음 두 조건이 동시에 성립한다는 뜻이다:

0 ≤ sparse[i] < next   AND   dense[sparse[i]] = i

이 발상의 묘미는 — 두 배열을 초기화할 필요가 없다는 것이다. 멤버십 검사 자체가 진위(validity) 검사 역할을 하기 때문에, 쓰레기 값이 sparse에 들어 있어도 위 조건을 통과할 수 없다. 그래서 clear는 next ← 0 한 줄, 즉 O(1)이다. add·member·delete도 모두 O(1). dense는 빽빽하게 채워지니, 집합을 순회할 때는 dense[0..next−1]만 훑어 O(|S|)에 끝낸다. 비트 벡터의 약점인 "초기화 비용"과 "희소할 때의 낭비"를 정확히 노린 자료구조다.

세 표현의 점근 비용 한눈에 보기

점근만 보면 희소 집합이 비트 벡터를 압도하지만, 비트 벡터의 워드 단위 병렬성은 무시 못 할 무기다. 집합이 정말 희소할 때만 희소 집합이 이긴다. 둘 중 무엇을 고를지는 |S|/|U| 비율과 연산 빈도를 함께 봐야 한다.

B.3 중간 표현(IR) 구현하기

IR 스타일을 골랐다고 끝이 아니다 — 어떻게 메모리에 깔 것인지가 또 한 차원의 결정이다. DAG는 포인터로 노드를 잇는 게 자연스럽고, quadruple은 n×4 배열이 어울린다. 그러나 늘 그렇듯, 가장 좋은 구현은 컴파일러가 그 IR을 어떻게 쓰느냐에 달렸다.

B.3.1 그래프형 IR

트리 표현 — 포인터 vs. 배열

AST 같은 트리는 두 가지 정통 구현이 있다.

• 포인터 방식: 노드를 힙(heap)에 동적으로 할당하고 자식 포인터로 연결. 임의 크기로 자라며, 노드 종류마다 다른 크기를 쓸 수 있다.
• 배열 방식: 구조체 배열에 노드를 차례로 쌓고, 포인터 대신 정수 인덱스(integer index)를 쓴다. 하나의 통일된 노드 크기를 강요하지만 다른 면에서 보상이 크다.

임의 트리를 이진 트리로 매핑하기

for i = 1 to n by 2 같은 구문은 자식이 5개나 되는 노드를 만든다. 자식 수가 가변인 노드를 처리하려면 횡단(traversal) 코드가 매번 자식 개수를 읽어 분기해야 하니 번거롭다. 영리한 트릭 — 모든 트리를 이진 트리로 변환하는 것. 왼쪽 자식 포인터는 "맏이 자식"을, 오른쪽 자식 포인터는 "오른쪽 형제"를 가리키게 한다. 그러면 모든 노드가 자식 두 개짜리로 통일되고, 아레나 할당과 같은 일률적인 메모리 관리가 가능해진다.

    원래 트리:                이진 트리(맏이-형제 변환):

         for                      for ──→ next-stmt
       / | | | \                   |
      i  1 n 2 body                i ──→ 1 ──→ n ──→ 2 ──→ body

임의 그래프 — CFG, 의존 그래프

제어 흐름 그래프(control-flow graph, CFG)나 데이터 우선순위 그래프는 트리가 아니다. 노드마다 들어오는/나가는 간선 수가 다르다. 가장 단순한 구현은 노드별로 후속 간선 리스트를 들고 다니는 것인데, 이러면 데이터 흐름 분석에서 자주 쓰는 역방향 횡단(predecessor를 찾는 일)이 어려워진다.

그래서 책이 추천하는 방식은 두 개의 테이블 — 노드 테이블과 간선 테이블 — 을 쓰는 것이다.

각 노드는 첫 후속 간선과 첫 선행 간선만 들고 있다. 간선은 다음 후속·다음 선행을 체이닝한다. 후속도 선행도 O(1)에 시작점을 잡을 수 있다.

한편 간섭 그래프(interference graph)처럼 크고 희소한 그래프는 두 가지 표현을 동시에 둔다 — 비트 행렬(간선 존재 검사용; 무방향이라 하부 삼각으로 절반 절약)과 인접 벡터(adjacency vector)(이웃 순회용). 13장의 그래프 컬러링이 이 패턴을 쓴다.

B.3.2 선형(linear) IR

ILOC 같은 선형 IR은 n×4 정수 배열로 즉시 매핑된다 — 가장 단순하고, 가장 빠르고, 캐시에 가장 친화적이다. 하지만 단점도 분명하다.

• 연산 삽입·삭제 시 배열을 밀거나 당겨야 한다.
• 코드 모션(code motion)은 이 문제의 약한 버전이다. 분기 직후처럼 죽은 슬롯을 미리 비워두면 셔플 양이 줄어든다.
• detour 연산자 트릭: 삽입할 자리에 detour를 박고, 원래 명령은 배열 끝에 붙여 두고, 다시 detour로 돌아온다. 패스 끝에서 한꺼번에 평탄화하면 된다.
• 가변 길이 연산 — φ-함수(phi function)는 피연산자가 가변이고, 프로시저 호출은 형식 매개변수, 반환 값, 수정·사용되는 변수 리스트까지 한 연산에 다 담는다. 이런 변종은 4-tuple 틀에 들어가지 않아 별도 처리가 필요하다.

대안은 구조체 리스트다. 각 연산이 독립 구조체이고 다음 연산 포인터를 갖는다. 삽입·삭제는 포인터 한두 개만 바꾸면 끝. 가변 길이 연산은 변종(variant) 구조체로 자연스럽게 표현된다. 다만 포인터 체이싱 때문에 캐시 지역성이 나쁘고, 외부 I/O도 한 노드씩 직렬화해야 한다.

중간 절충점 — 리스트를 아레나나 배열 안에 구현하는 것. 아레나는 할당 비용을 거의 0으로 줄이고 배열에 가까운 지역성을 준다. 배열에 리스트를 깔면 모든 포인터가 정수 인덱스가 되어 디버깅이 편해지고, 블록 I/O로 한 번에 입출력이 가능해진다.

B.4 해시 테이블 구현하기

해시 테이블의 두 골칫거리는 (1) 사용하는 모든 테이블 크기에서 인덱스를 고르게 분포시키는 좋은 해시 함수와 (2) 충돌(collision)을 효율적으로 처리하는 전략이다. 다행히 해싱은 오래된 분야라 검증된 함수와 기법이 즐비하다.

B.4.1 해시 함수 고르기

곱셈 해시 함수(Multiplicative)

Knuth가 추천하는 단순한 형태:

h(key) = ⌊TableSize · ((C · key) mod 1)⌋

상수 C로는 황금비의 분수부 0.6180339887 ≈ (√5 − 1)/2를 권한다. C · key의 소수부에 테이블 크기를 곱해 인덱스를 얻는다.

유니버설 해시 함수(Universal)

해시 함수를 한 가족(family) 안에서 매개변수화하고, 실행마다 무작위로 한 멤버를 고른다. 한 컴파일에서 병적인 입력을 만났더라도 다음 컴파일에서는 같은 패턴이 재현되지 않는다. 곱셈 해시의 유니버설 버전은 시작할 때 C를 무작위로 골라 쓰면 된다.

B.4.2 Open Hashing — 체이닝(chaining)

Open hashing(또는 bucket hashing)은 테이블 크기 S의 슬롯 각각이 연결 리스트(체인) 헤드다. h(name)이 같은 모든 이름이 같은 버킷의 체인에 매달린다. 충돌이 일어나면 체인의 앞에 새 노드를 끼운다.

      Index  Bucket
        0    --+
        1    --+--> [b]
        2    --+
   h(d) 3    --+--> [d] -> [a]
        4    --+
        5    --+
        6    --+
        7    --+
        8    --+
        9    --+--> [c]

장점은 분명하다 — 이름이 무한정 들어와도 공간 부족 없이 처리된다. 한 버킷이 길어져도 다른 버킷의 비용에는 영향이 없다. 단점도 둘.

1. 할당 집약적: 매 삽입마다 새 노드 할당. 무거운 메모리 할당기에서는 부담이 된다 — 아레나 기반 할당으로 완화 가능.
2. 체인이 길어지면 선형 검색: N이 S보다 훨씬 커질 때. 구현이 이를 감지해 버킷 배열을 확장하고 재해시(rehash)해야 한다.

B.4.3 Open Addressing — 재해시(rehashing)

Open addressing(또는 rehashing)은 충돌이 나면 테이블 안에서 다른 빈 슬롯을 찾는다. 보조 해시 함수 g(n)으로 증분(increment)을 만들어 (h(n) + g(n)) mod S, (h(n) + 2g(n)) mod S, … 식으로 탐사한다. n을 찾거나, 빈 슬롯을 만나거나, h(n)으로 한 바퀴 돌아오면 종료한다.

       Index  Slot
         0
         1    [b]
         2
    h(d) 3    [a]
         4         <-- rehash
         5    [d]
         6
         7
         8
         9    [c]

두 충돌 해결 방식 비교

Open addressing의 묘미는 — 보조 해시 g를 매번 다시 계산하면 충분하므로 포인터를 저장하지 않아도 된다. 그렇게 절약된 공간으로 S를 더 키우면 충돌 자체가 줄어든다. 다만 S는 소수(prime)여야 한다 — 그래야 0 < g(n) < S인 어떤 g를 써도 모든 슬롯을 한 번씩 방문한 뒤에야 h(n)으로 돌아온다.

B.4.4 심볼 레코드(record)는 어디에 둘까

해시 테이블 자체와 별개로, "각 항목의 정보를 어디에 저장할 것인가"라는 별도 문제가 있다. 직관적 후보는 두 가지 — 체인 노드 안에 직접 박거나(open hashing), 인덱스 테이블 슬롯에 직접 두거나(open addressing). 그러나 둘 다 단점이 있다. 별도의 스택(stack)에 레코드를 모아 쌓고, 인덱스 테이블은 그 스택의 인덱스만 가리키게 하는 방식이 훨씬 낫다.

     Index Set         Stack
        0  -+
        1  -+
        2  -+         +-----+
        3  -+         | a   |  <- 0
        4  -+         | b   |  <- 1
   h(c) 5  -+-------> | c   |  <- 2  (Next Slot)
        6  -+
        7  -+
        8  -+
        9  -+

장점이 줄줄이다.

• 밀집 테이블(dense table)로 외부 I/O가 효율적.
• 심볼들을 순회하기 쉽다 — 저장 위치 할당 같은 작업에 유용.
• 가비지 컬렉터에서 마크할 객체 수가 줄어든다.
• 인덱스 셋 확장이 쉽다 — 레코드를 그대로 두고 인덱스 테이블만 새로 할당해 스택을 다시 해시해 채운다. 두 테이블을 동시에 메모리에 들고 있을 필요가 없다.
• 스택을 k개 레코드씩 담는 노드 체인으로 구현하면 할당 비용과 낭비 공간 사이를 자유롭게 조절할 수 있다.

B.4.5 중첩 스코프(nested lexical scope) 다루기

5장의 스코프는 sheaf-of-tables(테이블의 묶음)로 단순하게 구현하면 깔끔하다 — 그러나 LookUp 비용이 늘어난다. LookUp은 다른 어떤 루틴보다 자주 호출되므로, 이 비용을 InitializeScope·FinalizeScope·Insert 쪽으로 미는 게 낫다.

예시 코드의 동작 시퀀스(↑는 InitializeScope, ↓는 FinalizeScope):

↑ ⟨w,0⟩ ⟨x,0⟩ ⟨example,0⟩ ↑ ⟨a,1⟩ ⟨b,1⟩ ⟨c,1⟩
↑ ⟨b,2⟩ ⟨z,2⟩ ↓ ↑ ⟨a,2⟩ ⟨x,2⟩ ↑ ⟨c,3⟩ ⟨x,3⟩ ↓ ↓ ↓ ↓

Open Hashing에 스코프 얹기

각 레코드에 lexical level 필드를 더하고, 새 이름은 체인의 앞쪽에 끼운다. LookUp은 처음 만나는 매치를 반환하므로 — 자동으로 가장 안쪽 스코프의 정의를 얻는다. InitializeScope는 레벨 카운터만 ++. FinalizeScope는 그 레벨에 속한 모든 레코드를 체인에서 떼어내야 한다.

레코드를 스택에 따로 쌓는 방식이라면 FinalizeScope가 훨씬 우아해진다 — 스택을 위에서부터 훑어 내려가다 폐기 대상 레벨보다 낮은 레코드를 만나면 멈추면 끝. 각 폐기 레코드의 다음 노드 포인터를 인덱스 테이블에 다시 꽂아주면 체인이 자동으로 복구된다.

  스택 (위에서 아래로):              인덱스 셋 (Next Slot↑)
     +-----------+
     | x, 3      |  <- 가장 안쪽 스코프
     | c, 3      |
     | x, 2      |
     | a, 2      |
     | c, 1      |
     | b, 1      |
     | a, 1      |
     | example,0 |
     | x, 0      |
     | w, 0      |  <- 가장 바깥 스코프
     +-----------+

  Push: InitializeScope → 레벨 ++
  Pop : FinalizeScope    → 해당 레벨 모든 레코드 제거

Open Addressing에 스코프 얹기

open addressing은 한층 까다롭다 — 슬롯 하나를 비워버리면 그 자리를 지나가던 다른 이름의 rehash 체인이 끊긴다. 그래서 이름 하나당 인덱스 테이블에 한 슬롯만 두는 전략을 쓴다. 같은 이름의 옛 선언들은 스택 안에서 별도 체인으로 엮어 둔다.

Insert는 인덱스 테이블에서 같은 이름의 옛 레코드를 찾으면, 그 인덱스를 새 레코드 쪽으로 갱신하고 옛 레코드는 새 레코드의 "이전 선언" 링크로 연결한다. 마지막 선언까지 사라지면 삭제 표시(deleted reference) 슬롯을 넣어둔다 — LookUp은 이를 지나치고, Insert는 이 자리를 재사용할 수 있다.

결과적으로 — 충돌 체인은 인덱스 셋을 통해 흐르고, 재선언 체인은 스택을 통해 흐른다. 두 체인이 분리되니, x가 한 버킷에 7번 등장해도 LookUp이 한 번만 보면 끝이다.

B.5 유연한 심볼 테이블 설계

실제 컴파일러를 만들다 보면 심볼 테이블 필드가 단조 증가한다. 새 패스가 추가될 때마다 새 필드, 패스 간 정보 전달용 필드가 추가된다. 더 이상 필요 없어진 필드도 잘 안 지워진다. 필드 하나 늘 때마다 모든 심볼 레코드가 부풀고, 심볼 테이블에 직접 손대는 코드는 모조리 다시 컴파일해야 한다.

저자들이 Rⁿ과 ParaScope 환경을 만들 때 이 문제를 정면으로 맞았다. 해법은 2차원 해시 테이블이었다.

                         h(name)  h(type) h(offset) h(length)
                          ┌─────┬─────┬─────┬─────┬─────┬─────┐
                          │     │     │     │     │     │     │  field hash
                          └──┬──┴──┬──┴──┬──┴──┬──┴─────┴─────┘
                             ▼     ▼     ▼     ▼
       symbol hash       ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
   h(foe)    -+   ──┐    │     │ │     │ │     │ │     │
              │     │    │     │ │     │ │     │ │     │
   h(fee)    -+     │    │ fum │ │ char│ │  16 │ │  12 │
              │     ├──> │ foe │ │ real│ │  8  │ │  4  │
   h(fum)    -+     │    │ fie │ │ real│ │  4  │ │  4  │
              │     │    │ fee │ │ int │ │  0  │ │  4  │
   h(fie)    -+   ──┘    └─────┘ └─────┘ └─────┘ └─────┘

왼쪽은 심볼 이름의 인덱스 테이블. 위쪽은 필드 이름의 해시 테이블. 프로그래머는 get(symbol="foe", field="type")처럼 두 이름을 키로 준다. 구현은 두 번 해시해 — 심볼 인덱스 한 번, 필드 인덱스 한 번 — 데이터 벡터의 한 칸을 짚는다.

비용은? 테이블 접근당 해시 계산이 두 번이다. 그러나 — 각 필드는 실제로 값이 들어갈 때까지 저장 공간을 잡지 않으므로, 안 쓰는 필드의 공간 낭비가 없다. 더 결정적인 장점은 개별 개발자가 다른 사람의 코드를 건드리지 않고 필드를 만들고 지울 수 있다는 것이다. 통계 보고용 진입점까지 넣어두면, 어떤 필드가 실제로 쓰이는지도 측정할 수 있다.

마지막 디자인 원칙 — 심볼 테이블 구현은 항상 특정 테이블 인스턴스를 매개변수로 받는 추상이어야 한다. 그래야 8장의 superlocal·dominator 기반 value numbering 알고리즘에서처럼 같은 구현을 여러 곳에 재활용할 수 있다.

핵심 요약

• 오프라인 컴파일은 우주 크기를 미리 알 수 있게 해주어, OS에서는 못 쓰는 자료구조를 자유롭게 쓸 수 있게 한다.
• 집합 표현 3종 — 정렬 리스트(우주 미상, 작을 때), 비트 벡터(우주 알려져 있고 밀집), 희소 집합(우주 알려져 있고 희소). 각각의 트레이드오프를 |S|/|U| 비율과 연산 빈도로 결정한다.
• 희소 집합은 두 배열의 상호 참조로 초기화 비용 없이 O(1) add/test/clear를 달성한다.
• 그래프 IR은 노드+간선 두 테이블로, 선형 IR은 배열 또는 (아레나 안의) 리스트로 — 패스가 IR을 어떻게 쓰느냐에 따라 결정된다.
• 해시 충돌은 체이닝(open hashing)과 탐사(open addressing) 두 갈래로 갈리며, 레코드는 별도 스택에 두는 것이 외부 I/O·확장·GC 모두에 유리하다.
• 중첩 스코프는 LookUp 비용을 늘리지 말고 Insert/InitializeScope/FinalizeScope 쪽에 비용을 미는 것이 정답이다.
• 2차원 해시 테이블로 심볼 테이블의 필드 변경을 다른 코드와 격리하면, 컴파일러 진화가 훨씬 부드러워진다.