프로그래밍 언어용 고속 컴파일러를 작성하기 위해 사용한 기법과 설계 선택을 설명합니다.
2024-02-04
프로그래밍 언어용으로 빠른 컴파일러를 작성하기 위해 사용한 여러 기법을 설명하겠다. 여기서 빠른 컴파일이란 단일 CPU 코어에서 초당 최소 500,000줄의 코드(빈 줄과 주석 제외)를 컴파일하는 것을 뜻한다.
컴파일 시간은 중요하지 않다고 주장할 수도 있다. 결국 출시된 뒤에는 프로그램을 빌드하는 데 몇 시간이 걸렸는지는 누가 신경 쓰겠는가? 사용자로서는 그저 제대로 동작하고 빠르게 동작하기만 바라기 때문이다. 마지막 Pixar 영화의 최종 렌더링에 며칠이 걸렸다고 불평하는 것과 비슷하다.
하지만 이는 개발 주기에 심각한 영향을 미칠 수 있으며 개발자를 화나게 할 수 있다. 2024년인 지금도 Rust에 대한 가장 흔한 불만은 여전히 컴파일 시간이라는 것을 볼 수 있다.
속도는 컴파일러의 설계에도 영향을 준다. 가장 큰 프로그램이 100K SLOC보다 작고 초당 500K SLOC를 컴파일할 수 있다면, 전체 빌드가 200ms도 걸리지 않으므로 별도 컴파일을 크게 걱정할 필요가 없다. 그리고 제네릭을 사용할 때 별도 컴파일은 까다로울 수 있으므로 이는 좋은 일이다.
기존 언어, 예를 들어 C++용 컴파일러를 작성한다면 여기에는 통제권이 없다. LL(k) 문법, 전처리기, 형편없는 모듈 시스템을 감당해야 한다. 반대로 자신만의 프로그래밍 언어용 컴파일러를 작성한다면 신중한 설계 선택이 큰 도움이 될 수 있다.
나는 언제나 단순한 재귀 하강 파서로 쉽게 파싱할 수 있는 문맥 자유 문법을 사용했다. 컴퓨터가 파싱하기 쉬운 문법은 인간도 파싱하기 쉽다.
단순한 문법은 독립적인 도구(정적 분석기, 포매팅 도구, 리팩터링, 문법 강조 등)의 개발도 쉽게 만든다.
실행할 코드가 적고 메모리 접근이 적으면 대체로 실행이 빨라진다. 현대 아키텍처에서는 이 원칙이 엄밀하게 항상 참은 아니지만, 여전히 따르기 좋은 규칙이다.
나는 가능한 한 데이터 복사를 피한다. 많은 언어는 널 종료 문자열을 사용한다. 대신 (시작 포인터, 크기) 또는 (시작 포인터, 끝 포인터) 쌍을 사용하는 편을 선호한다. 예를 들어 이렇게 하면 복사 없이 입력 버퍼의 임의의 부분 문자열을 직접 참조할 수 있다.
메모리를 적게 사용할수록 더 많은 것이 캐시에 들어간다.
컴파일러 작업의 상당 부분은 오류 검사이지만, 프로그램에는 보통 오류가 없거나 아주 적다. 따라서 오류는 예외적인 경우라는 점을 고려해 코드를 최적화해야 한다.
메모리 영역은 일부를 할당할 수 있지만 개별 해제할 수는 없는 연속된 메모리 블록이다(전체 영역을 해제해야 한다). 할당은 포인터를 전진시키는 것뿐이며, 영역이 가득 찬 경우에만 새 영역을 만든다. 따라서 할당이 매우 빠르다. 해제 역시 영역의 모든 객체를 한 번에 해제하므로 매우 빠르다.
이런 종류의 메모리 관리는 컴파일러와 아주 잘 맞는다. 하나의 컴파일 단위에 단일 영역을 사용할 수 있다. 실제로 나는 3개의 영역을 사용한다.
하지만 함수를 컴파일할 때는 주로 각 어휘 스코프의 이름 사전처럼 많은 임시 객체가 생성된다. 이를 처리하기 위해 영역 풀을 만든다. 영역을 생성하고 파괴하는 대신 풀에서 하나를 가져오고 끝나면 다시 풀에 넣는다.
크기 조절 배열과 개방 주소법 해시 테이블은 많은 해제와 재할당이 필요하므로 메모리 영역에 적합한 자료 구조가 아니다.
요소 목록을 저장할 때는 가능하면 먼저 요소 수를 세고 고정 크기 배열을 할당한다. 불가능하면 단순히 연결 목록을 사용한다.
이름에 많이 사용되는 해시 테이블을 처리하기 위해 개방 주소법 대신 분리 연결법을 사용한다. 배열 재할당은 없어지지만 해시 크기를 신중하게 선택해야 한다. 전역 네임스페이스에는 함수의 내부 스코프보다 더 큰 해시 테이블이 필요하다.
CPU는 문자열을 다루도록 설계되지 않았으며, 고정 크기 정수를 다루도록 설계되었다.
컴파일 과정의 중요한 부분은 식별자에 어떤 엔티티가 연결되어 있는지 찾는 것이다. 식별자가 문자열로 저장되어 있다면 느릴 것이다.
컴파일러는 오류가 발생했을 때 사용자에게 보여 주거나 객체 파일의 디버그 심볼 테이블에 저장할 때를 제외하고 식별자의 내용을 알 필요가 없다. 식별자 간 동등성만 검사하면 되므로, 내부적으로는 서로 다른 각 식별자에 할당된 정수를 사용할 수 있다.
렉서는 이미 키워드를 위해 사전에서 조회해야 하므로, 어휘 분석 중 식별자를 고유 정수로 변환하는 추가 비용은 매우 작다.
다음 소스 코드
func main(args)
if args.size < 2
는 다음과 같은 어휘 단위 흐름을 만든다.
여기서:
main에 해당하고,args에 해당하며size에 해당한다.나는 컴파일러에 단순하고 고전적인 아키텍처를 사용한다.
Lexical Analysis ---> Syntax Analysis ---> Build ---> Code Generation
여기서:
신중하게 설계된 문법에서는 어휘 분석기가 입력 문자를 처리하는 거대한 switch 문을 갖춘 단순한 루프에 불과하며, 구문 분석기는 중위 표현식을 위한 연산자 문법과 결합된 직접 작성한 재귀 하강 파서다.
재귀 하강 파서는 다음과 같은 함수들로 구성된다.
e = parseExpression
i = parseInstruction
b = parseBlock
id = parseIdentifier
...
오류를 처리하는 자연스러운 방법은 구문 오류가 발생했을 때 특수 값을 반환하는 것이다. 예를 들어 널 값을 반환할 수 있지만, 그러면 모든 호출자가 반환값을 검사해야 한다.
e = parseExpression
if e == nil
return nil
end
비결은 대신 오류를 보고하고 더미 표현식을 반환하는 것이다. 예를 들어 '0' 표현식을 반환한다. 구문 오류 함수는 첫 번째 오류를 표시하고, 그 뒤의 오류는 입력과 전혀 관련이 없을 수 있으므로 버린다.
많은 검사를 제거하므로 코드가 더 빠를 뿐 아니라 더 단순해진다. 매 줄의 검사로 어수선하지 않고, 예외의 장점은 얻으면서 단점(숨겨진 종료 지점, 스택 해제 비용)은 없다.
이 기법에는 대가가 있다. 첫 번째 구문 오류에서 중단한다(가능한 한 많은 오류를 보고하려는 빌드 단계와는 다르다).
라이브러리를 가져오면 보통 사용하지 않는 수많은 상수, 구조체, 함수가 딸려 온다.
필요한 것만 분석하는 것이 좋은 생각이다.
구문 분석은 AST를 만들기 위해 전체 입력을 읽고 파싱해야 한다.
class Label: Widget
attr caption: String
attr color: Color
def init(caption: String)
...
// ... hundreds of lines of code ...
end
하지만 빌드 단계에서는 그저 다음과 같다.
class Label
클래스의 내용과 부모는 필요해질 때까지 완전히 무시할 수 있다. 컴파일러는 필요할 때 찾을 수 있고 같은 이름으로 다른 엔티티가 정의되지 않도록 보장하기 위해 _Label_을 아직 정의되지 않은 엔티티와 연결하기만 하면 된다.
이는 사용될 때까지 컴파일러가 코드를 검증하지 않는다는 뜻이다. 경우에 따라 성가실 수 있다. 예를 들어 라이브러리를 작성할 때는 모든 것이 컴파일되는지 확인하고 싶다. 명령줄 옵션으로 모든 항목의 컴파일을 강제할 수 있다.
언어 설계 역시 여기서 도움이 될 수 있다. 모든 것을 전역 네임스페이스에 넣지 않으면 정의해야 하는 선언의 수를 상당히 줄일 수 있다. 예를 들어 GTK+는 C API를 가진 라이브러리지만, 내 언어에서는 많은 함수를 각자의 Widget 클래스에 메서드로 노출할 수 있다.
원래 C API
typedef struct _GtkLabel GtkLabel;
GtkWidget* gtk_label_new (const gchar *str);
void gtk_label_set_text (GtkLabel *label, const gchar *str);
const gchar* gtk_label_get_text (GtkLabel *label);
...
Copper에서
class GtkLabel: GtkMisc
import func "gtk_label_new" new(String): Self
import def "gtk_label_set_text" set_text(String)
import def "gtk_label_get_text" get_text: String
...
end
GtkLabel을 사용하지 않으면 중첩된 모든 엔티티는 선언조차 되지 않는다.
몇 개의 요소만 사용하는 거대한 라이브러리에서는 많은 시간을 절약할 수 있다.
LLVM 및 C 백엔드에 더해, 나는 자체 x64 코드 생성기를 개발했다.
LLVM은 훌륭하다. 사용하기 매우 쉽고, 고도로 최적화된 코드를 생성하며, 많은 플랫폼을 지원한다. 하지만 느리다. 자체 x64 백엔드를 개발하여 30배의 속도 향상을 관찰했다.
내 LLVM 백엔드는 직관적인 코드 2000줄로 이루어져 있지만, 자체 x64 백엔드는 복잡한 코드가 10,000줄이 넘고 부동소수점 수도 지원하지 않는다. 자체 x64 생성기를 개발하는 일은 엄청난 노력이었지만 그만한 가치가 있었다. 빠른 컴파일러 구현을 가능하게 하려면 누군가 LLVM의 비 SSA 대안을 개발해야 할지도 모른다.
내 코드 생성기는 주로 다음으로 구성된다.
중간 의사 코드를 생성하면 일부 최적화가 쉬워진다. 이를 기계 코드로 직접 어셈블할 수 있으므로, 어셈블러에 넘기기 위해 어셈블리 코드로 변환할 필요가 없다.
대체로 변수가 있는 x64 어셈블리와 같다. 레지스터 할당 후 변수는 레지스터 또는 메모리 접근으로 대체된다. 이 의사 코드는 LLVM의 IR처럼 범용적이지 않고 x64에 최적화되어 있다. 예를 들어 인덱스가 지정된 메모리 접근이 사용된다.
이 부분은 서로 다른 데이터 타입을 가진 많은 함수를 만들지만 동일한 코드를 생성하는 내 언어의 제네릭 때문에 필요하다. 한편으로 재귀 가능성이 있는 그래프에서 중복을 찾는 일은 까다로울 수 있어 이 중복 탐색기는 성능 비용이 크다. 다른 한편으로 어셈블할 함수를 많이 제거한다.
레지스터 할당에는 선형 스캔 알고리즘(PDF)을 사용한다. 원 논문은 이를 JIT 컴파일러용이라고 설명하지만, 합리적으로 빠른 코드를 생성하려는 빠른 컴파일러에도 완벽하게 적합하다고 생각한다.
두 단계로 어셈블하면 처음에는 더 느려 보이지만, 첫 번째 단계에서는 아무것도 쓰지 않는다. 크기가 늘어나는 가변 버퍼를 사용할 필요 없이 오프셋을 계산하기 위해 바이트만 세면 된다. 두 번째 단계에서는 정확한 크기를 알고 있으므로 올바른 크기의 버퍼를 미리 할당하고 한계 검사 없이 쓸 수 있다. 비용은 쓰기 함수가 가상 함수라는 점이다. 실제 벤치마크 없이는 두 단계 방식이 한 단계 방식보다 빠른지 말할 수 없지만, 두 단계 방식도 그리 나쁘지 않다는 것을 알았다.
내 프로젝트를 100ms에 컴파일하는 것으로 충분하므로 지금은 더 이상의 최적화가 필요하지 않다. 어쨌든 위에서 설명한 기법은 모두 기본 기술과 상식일 뿐이며, 여전히 개선과 실험의 여지가 많다.
컴파일러를 작성할 계획이 있거나 기존 컴파일러를 더 빠르게 만들고 싶다면 이것이 도움이 되기를 바란다.