📚 지식 노트

컴파일러 파이프라인

컴파일러는 한 언어로 쓴 프로그램을 같은 뜻의 다른 언어로 옮기는 프로그램이다. 대개 사람이 읽는 언어에서 CPU가 실행하는 기계어로 옮긴다. 한 번에 하지 않고, 앞 단계의 출력을 다음 단계가 받는 여러 단계로 나눈다.

• 프런트엔드: 글자를 토큰으로 자르고(렉서), 문법에 맞춰 트리로 묶고(파서), 이름이 정의돼 있는지·타입이 맞는지 확인한다(의미 분석). 언어마다 따로 있다.
• 미들엔드: 트리를 기계에 가까운 중간 표현(IR)으로 바꾸고 최적화한다. 언어와 CPU 모두와 무관하다.
• 백엔드: IR을 특정 CPU의 명령으로 고르고, 변수를 레지스터에 배정하고, 명령 순서를 다듬는다. CPU마다 따로 있다.

이 구조를 가장 잘 보여 주는 것이 LLVM이다. Clang(C·C++), Rust, Swift, Zig 같은 언어가 저마다 프런트엔드만 만들어 LLVM IR을 내놓으면, 최적화와 x86·Arm·RISC-V·WebAssembly 백엔드는 LLVM이 함께 맡는다. GCC도 같은 구조다.

렉서와 파서

렉서(어휘 분석기)는 글자 열을 의미 있는 낱말인 토큰으로 자른다. 숫자 10, 이름 rate, 연산자 *, 괄호처럼 종류를 붙이고, 공백과 주석은 버린다. 토큰의 모양은 정규 표현식으로 적을 수 있어서 유한 오토마타로 빠르게 처리한다.

파서(구문 분석기)는 토큰 열이 문법에 맞는지 확인하며 구조를 트리로 만든다. 처음 만든 구문 트리에서 괄호·세미콜론 같은 군더더기를 걷어낸 것이 AST(추상 구문 트리)이고, 이후 단계는 모두 AST를 다룬다. 산술식에서 핵심은 우선순위와 결합 방향이다. 2 + 3 * 4는 곱셈이 먼저 묶여 14이고, 8 - 3 - 2는 왼쪽부터 묶여 3, 거듭제곱 2 ^ 3 ^ 2는 오른쪽부터 묶여 512다.

손으로 짜는 파서는 대개 재귀 하강 방식이다. 문법 규칙 하나를 함수 하나로 만들고, 규칙이 다른 규칙을 부르면 함수가 함수를 부른다(재귀와 호출 스택은 알고리즘 › 기초). 이항 연산자의 우선순위는 우선순위 오름(precedence climbing, Pratt 파서와 같은 계열)으로 깔끔하게 처리한다. 왼쪽 피연산자를 읽은 뒤, 다음 연산자의 우선순위가 지금 기준 이상이면 오른쪽을 더 높은 기준으로 재귀해 읽어 묶는다. GCC·Clang·V8도 손으로 짠 재귀 하강 파서를 쓴다. 문법 파일에서 파서를 자동으로 만들어 주는 도구(yacc·Bison, ANTLR)도 있다.

타입 시스템

타입은 값에 붙은 "무엇으로 쓸 수 있는가"의 약속이다. 정수에 문자열을 더하거나, 없는 메서드를 부르는 실수를 잡는다. 두 축으로 나눠 보면 정리가 쉽다.

• 정적 vs 동적: 타입 검사를 컴파일할 때 하느냐, 실행하면서 값마다 하느냐. 정적 타입은 실행 전에 오류를 잡고 컴파일러가 더 빠른 코드를 만들 근거가 된다. 동적 타입은 짧고 유연하게 쓸 수 있지만 오류가 그 줄이 실행될 때에야 드러난다.
• 강함 vs 약함: 타입이 맞지 않을 때 오류를 내느냐, 알아서 변환하느냐. 공식 정의가 없는 정도의 문제라 "어느 쪽에 가깝다" 정도로만 말한다.

정적 타입이라고 모든 타입을 적어야 하는 것은 아니다. 타입 추론은 컴파일러가 쓰임새에서 타입을 알아내는 것이다. ML·Haskell은 Hindley–Milner 추론으로 함수 전체의 타입까지 알아내고, Rust의 let, Kotlin의 val, C++의 auto, TypeScript는 주로 변수 하나의 초깃값에서 추론한다. 제네릭(매개변수 다형성)은 "어떤 타입 T에 대해서든"을 표현해 같은 코드를 타입마다 다시 쓰지 않게 한다.

중간 표현(IR)과 SSA

AST는 원래 언어의 모양을 너무 많이 닮았고, 기계어는 CPU에 너무 묶여 있다. 그 사이의 IR이 최적화의 작업대다. 흔한 꼴은 3주소 코드로, t1 = b * 2처럼 한 줄에 연산 하나, 피연산자 둘만 쓴다. 복잡한 식은 임시 변수로 쪼갠다. 코드는 분기 없이 이어지는 덩어리(기본 블록)와 그 사이의 화살표로 이뤄진 제어 흐름 그래프로 표현한다.

현대 컴파일러 대부분은 IR을 SSA(정적 단일 대입) 꼴로 둔다. 모든 변수가 딱 한 번만 대입되도록, 같은 변수에 다시 대입할 때마다 x₁, x₂처럼 새 이름을 붙인다. 갈래가 합쳐지는 곳에서는 어느 쪽에서 왔는지에 따라 값을 고르는 φ(파이) 함수를 둔다. 그러면 "이 값은 어디서 정의됐나"가 이름만으로 정해져, 상수 전파·죽은 코드 제거 같은 분석이 단순하고 빨라진다. LLVM IR과 GCC의 GIMPLE이 SSA다.

최적화: 상수 접기와 죽은 코드 제거

최적화는 프로그램의 뜻(관찰 가능한 동작)을 바꾸지 않으면서 더 빠르거나 작게 만드는 변환이다. 하나하나는 단순한 규칙이고, 여러 패스를 차례로, 때로는 되풀이해 적용해 서로가 서로의 기회를 만든다.

• 상수 전파·접기: 값이 이미 정해진 변수는 그 값으로 바꾸고, 피연산자가 모두 상수인 연산은 컴파일할 때 미리 계산한다.
• 죽은 코드 제거: 결과가 어디에도 쓰이지 않는 계산, 절대 실행되지 않는 분기를 지운다. 뒤에서부터 "나중에 쓰이는 변수" 집합을 들고 거꾸로 훑는다.
• 인라이닝: 작은 함수 호출을 함수 본문으로 바꿔 호출 비용을 없애고, 호출한 쪽 문맥에서 다른 최적화가 더 잘 되게 한다. 가장 효과가 큰 최적화로 꼽힌다.
• 루프 최적화: 반복마다 같은 값인 계산을 루프 밖으로 빼고(불변 코드 이동), 여러 반복을 한 번에 처리하도록 펼치거나 SIMD 명령으로 바꾼다(벡터화).

최적화는 언어 규칙이 허용하는 범위에서만 한다. C·C++에서 부호 있는 정수 넘침이나 배열 밖 접근 같은 정의되지 않은 동작은 "일어나지 않는다"고 가정해도 되므로, 그런 코드가 있으면 최적화 뒤 엉뚱한 결과가 나올 수 있다. 이것이 메모리 안전성 문제와 맞닿는 지점은 보안 › 시스템 보안에서 다룬다.

인터프리터, 바이트코드 VM, JIT

모든 언어가 미리 기계어로 컴파일되지는 않는다. 실행 방식은 시작 속도와 실행 속도 사이의 저울질이다.

• 트리 인터프리터: AST를 재귀로 걸으며 노드마다 바로 계산한다. 만들기 가장 쉽지만 노드를 오갈 때마다 포인터를 따라가야 해서 느리다.
• 바이트코드 VM: AST를 한 번 더 컴파일해 가상 기계의 명령 열(바이트코드)로 만들고, 명령을 하나씩 읽어 실행하는 루프로 돌린다. 명령이 메모리에 촘촘히 붙어 있어 트리보다 훨씬 빠르다. CPython·Lua·Java·.NET이 이렇게 시작한다. Python에서 dis 모듈로 바이트코드를 직접 볼 수 있다.
• JIT(실행 중 컴파일): 바이트코드로 돌리면서 자주 도는 함수·루프를 찾아 그때 기계어로 컴파일한다. 실행 중에 실제로 들어온 타입을 보고 그 경우에 맞게 특수화할 수 있어서, 동적 언어도 빨라진다. 가정이 깨지면 최적화된 코드를 버리고 인터프리터로 돌아온다(역최적화). V8은 Ignition 인터프리터에서 시작해 Sparkplug·Maglev·TurboFan 순으로 점점 더 공들여 컴파일한다. CPython도 3.13에서 실험적 JIT를 들였다.
• AOT(미리 컴파일): 실행 전에 기계어로 다 바꿔 둔다. 시작이 빠르고 실행 중 컴파일 비용이 없다. 대신 실행 중 정보를 쓸 수 없다.

바이트코드 VM은 대개 스택 기계다. 피연산자를 스택에 쌓고, 연산 명령이 맨 위 둘을 꺼내 계산한 결과를 다시 쌓는다. AST를 후위 순서(왼쪽, 오른쪽, 연산)로 걸으며 명령을 내보내면 그대로 바이트코드가 된다. 레지스터 번호를 명령에 적는 레지스터 기계(Lua 5, Android의 Dalvik)는 명령 수가 적어 더 빠른 대신 명령이 길다.

가비지 컬렉션

힙에 만든 객체는 언젠가 돌려줘야 한다. 가비지 컬렉터(GC)는 프로그램이 더는 쓸 수 없는 객체를 찾아 자동으로 돌려준다. "쓸 수 없다"를 판단하는 방법이 두 갈래다.

• 참조 횟수: 객체마다 자기를 가리키는 참조 수를 세다가 0이 되면 바로 해제한다. 단순하고 해제가 즉시라 메모리 사용이 고르다. 하지만 서로를 가리키는 순환은 밖에서 아무도 안 가리켜도 1 이상에 머물러 영원히 새어 나간다.
• 추적: 스택·전역 변수(루트)에서 출발해 화살표를 따라 닿는 객체만 살아 있다고 본다. 마크 앤 스윕은 닿는 객체에 표시(mark)한 뒤 힙 전체를 훑어(sweep) 표시 없는 것을 해제한다. 순환도 루트에서 닿지 않으면 함께 치운다.

단순한 마크 앤 스윕은 표시하는 동안 프로그램을 멈춰야 하고(stop-the-world), 쓸고 나면 빈칸이 흩어진다. 실제 GC는 여기에 몇 가지를 더한다. 살아남은 객체를 한쪽으로 옮겨 빈칸을 모으는 복사·압축, 프로그램과 나란히 표시하는 동시 GC(Go, Java의 ZGC·G1 일부), 그리고 가장 효과가 큰 세대별 GC다.

메모리 관리 방식 비교

메모리를 언제 누가 돌려주느냐는 언어 설계의 큰 갈림길이다. 실행 속도·멈춤 시간·안전성·쓰기 쉬움을 서로 다르게 맞바꾼다.

Rust의 소유권은 GC 없이 안전을 얻는 방법이다. 값마다 주인 변수가 하나이고, 대입하면 주인이 옮겨 가며(이동) 원래 변수는 쓸 수 없게 된다. 주인을 바꾸지 않고 잠깐 쓰려면 빌린다(&). 빌림은 "읽기 전용 여럿" 또는 "쓰기 하나"만 동시에 허용하고, 빌린 참조는 주인보다 오래 살 수 없다. 이 규칙을 컴파일러의 빌림 검사기가 확인하므로, 해제 시점이 코드 구조에 정해지고 해제 후 사용·데이터 경쟁이 컴파일 단계에서 막힌다.

링커와 로더

컴파일러는 보통 소스 파일 하나를 목적 파일(.o) 하나로 만든다. 목적 파일에는 기계어와 함께 "나는 main을 정의한다", "add와 printf가 필요한데 어디 있는지 모른다" 같은 기호 표가 들어 있다. 링커는 목적 파일과 라이브러리를 모아 필요한 기호를 정의한 곳과 짝짓고(기호 해결), 모든 코드와 데이터의 최종 주소를 정해 그 주소를 쓰는 자리를 고쳐 쓴다(재배치). 짝을 못 찾으면 익숙한 "undefined reference" 오류가 난다.

라이브러리를 실행 파일에 복사해 넣으면 정적 링크, 실행할 때 공유 라이브러리(.so·.dll·.dylib)를 찾아 잇게 하면 동적 링크다. 동적 링크는 여러 프로그램이 라이브러리 한 벌을 메모리에서 함께 쓰고 보안 패치를 한 곳에서 할 수 있지만, 배포 환경의 라이브러리 버전에 기대게 된다. Go와 Rust가 정적 링크를 기본으로 하는 이유다. 로더는 운영체제의 일부로, 실행 파일(Linux는 ELF, Windows는 PE, macOS는 Mach-O)을 읽어 주소 공간에 올리고 동적 라이브러리를 이은 뒤 시작 주소로 뛴다. 그 뒤의 이야기는 운영체제 노트의 프로세스·가상 메모리 절로 이어진다.

스코프와 클로저

이름이 어느 변수를 가리키는지 정하는 규칙이 스코프다. 대부분의 언어는 렉시컬 스코프를 쓴다. 함수가 어디서 불렸는지가 아니라 코드에서 어디에 쓰였는지로 정해지므로, 안쪽 함수는 바깥 함수의 지역 변수를 볼 수 있고, 이것은 파서가 코드 구조만 보고 정할 수 있다. 컴파일러의 의미 분석 단계가 이름마다 어느 선언인지를 이 규칙으로 묶어 둔다.

클로저는 함수와 그 함수가 만들어질 때의 바깥 환경을 함께 묶은 것이다(MDN). 바깥 함수가 이미 끝났는데도 안쪽 함수가 바깥 변수를 계속 읽고 쓸 수 있다. 문제는 지역 변수가 원래 스택에 있어 함수가 끝나면 사라진다는 점이다. 그래서 구현은 붙잡힌 변수를 스택 밖으로 옮긴다. Crafting Interpreters 25장의 바이트코드 VM은 붙잡힌 변수를 업밸류(upvalue)라는 간접 칸으로 가리키다가, 변수가 스택을 떠나는 순간 그 값을 힙으로 옮겨 닫는다. 대부분의 지역 변수는 그대로 빠른 스택에 두고, 붙잡힌 것만 대가를 치르는 방식이다.

• 루프 안의 클로저: JavaScript에서 var로 선언한 반복 변수는 루프 전체에 하나뿐이라, 반복마다 만든 콜백이 모두 같은 변수(마지막 값)를 본다. 반복마다 새 바인딩을 만드는 let을 쓰면 콜백마다 자기 값을 갖는다. MDN이 흔한 실수로 꼽는 예다.
• 클로저와 메모리: 클로저가 살아 있는 동안 붙잡힌 바깥 변수도 살아 있다. 이벤트 리스너에 큰 객체를 붙잡은 클로저를 걸고 떼지 않으면, 그 객체는 GC가 치우지 못한다(아래 흔한 오해).
• 인자 전달: 값을 복사해 넘기는 값 전달과, 호출한 쪽 변수 자체의 별칭을 넘겨 함수가 그 변수를 바꿀 수 있는 참조 전달(C++의 & 매개변수)이 있다. Python 문서는 인자가 대입으로 전달된다고 적는다. 객체를 가리키는 참조가 복사돼 넘어가므로, 함수 안에서 리스트를 고치면 밖에서도 보이지만 매개변수에 새 리스트를 대입해도 바깥 변수는 바뀌지 않는다(Python FAQ). 참조 전달이 아니다.

흔한 오해

• "컴파일 언어와 인터프리터 언어가 따로 있다": 컴파일과 인터프리트는 언어가 아니라 구현의 성질이다. Crafting Interpreters는 이를 과일과 채소에 빗댄다. 둘 다인 것도 있다. CPython은 사용자에게는 소스를 바로 실행하는 인터프리터지만 안에서는 바이트코드로 컴파일한다(2장). 위 실행 방식 절처럼 JavaScript도 인터프리터와 JIT를 오간다.
• "GC가 있으면 메모리 누수가 없다": "이 메모리가 앞으로 필요한가"는 일반적으로 판정할 수 없는 문제라, GC는 "루트에서 닿을 수 있는가"로 근사한다(MDN 메모리 관리). 다시는 쓰지 않을 객체도 전역 캐시, 떼지 않은 리스너, 위의 클로저가 붙잡고 있으면 닿을 수 있으니 치우지 않는다. 캐시처럼 남이 쥐고 있는 동안만 의미 있는 연결은 WeakMap 같은 약한 참조로 둔다.
• "정적 타입이면 강한 타입이다": 위 타입 시스템 절의 두 축은 서로 다르다. C는 정적이지만 암묵 변환이 많고, Python은 동적이지만 "1" + 1을 오류로 막는다.
• "최적화 단계를 바꿔도 동작은 같다": 정의된 동작만 쓰는 코드라면 맞다. 정의되지 않은 동작이 있는 C·C++ 코드는 최적화 수준에 따라 결과가 달라질 수 있다(위 최적화 절).

핵심 자료

직접 만들어 보며 배우려면 Crafting Interpreters가 가장 좋은 출발점이다.