LLVM으로 Dart 컴파일하기: 실험 이야기

LLVM으로 Dart 컴파일하기: 실험 이야기

LLVM 컴파일러 프레임워크로 Dart 언어를 컴파일하는 실험 이야기를 담은 글입니다. 겉보기엔 무의미해 보일 수 있는 실험이지만, Dart를 정적 타입 언어 방향으로 이끈 strong mode와 Flutter 출시라는 흐름 속에서 오히려 의미 있는 도전으로 자리잡았어요. GC 지원, 성능, 호환성까지 실험의 전 과정을 살펴볼게요.

출처: Dart on LLVM

본문

이 이야기는 LLVM 컴파일러 프레임워크를 사용해 Dart 언어를 컴파일하는 실험에 관한 거예요. 겉보기에는 꽤 무의미해 보이죠. 왜냐하면 Dart에는 이미 훌륭한 가상 머신이 있어서, JIT(just-in-time) 컴파일로 훌륭한 성능을 얻고 있거든요. Dart는 동적 타입 언어(더 정확히는 옵션 타입 언어)라서 JIT 컴파일러가 자연스러운 선택이에요. 런타임에서 사용 가능한 타입을 이용해 정적 컴파일러가 할 수 없는 최적화를 수행할 수 있으니까요.

Dart-on-LLVM이 헛된 일처럼 보이는 또 다른 이유는, 이름과 달리 LLVM이 가상 머신이 아니고, 최근까지도 가비지 컬렉션을 가진 언어에 적합하지 않았기 때문이에요. 여기서 적합하다는 말은 다음을 뜻해요:

  • 이동하는(moving), 정밀한(비-누출) GC
  • 고도로 최적화됨

그 이유는, 옵티마이저가 코드를 다듬고 나면 스택에서 GC 가능한 포인터를 찾을 방법이 더는 없어지기 때문이에요. 흔한 전략은 모든 포인터를 특별한 메모리 영역으로 옮기는 것이었지만, 이는 로컬 변수의 레지스터 할당에 의존해 마법을 부리는 현대 컴파일러의 최적화 전략 여럿을 무너뜨려요. 좋은 GC를 갖거나 완전한 성능을 갖거나, 둘 다는 아니었죠.

하지만 LLVM 세상에도 새 바람이 불고 있어요. 최근 LLVM은 실험적인 Statepoint 기능 형태로 GC 지원을 갖추기 시작했어요. 이는 여러 용감한 그룹에서 사용됐는데, LLV8 실험을 하는 사람들과, JVM용 새 탑티어 컴파일러에 이를 사용하는 Azul이 그렇죠.

LLVM 기반의 진짜 VM을 만드는 것이 '불가능한 임무'에서 '그냥 어려운 임무'로 바뀐 것처럼 보여요. 동시에 strong mode 덕분에 Dart는 더 정적으로 타입이 지정되고, 덜 동적이 됐어요. 또한 우리는 Google에서 iOS용 Flutter를 만들고 있는데, iOS에서는 JIT 컴파일이 금지되어 있어요. 이 두 발전 모두 Dart를 LLVM 프로젝트의 목표와 트레이드오프에 더 잘 맞춰줘요.

왜 LLVM인가

LLVM은 현대적이고 잘 관리되는 오픈소스 컴파일러 프레임워크예요. 많은 최적화와 플랫폼을 '공짜로' 얻을 수 있죠. 예를 들어, 어떤 함수를 다른 함수에 인라인할 수 있고 언제 그럴지에 대한 휴리스틱을 담은 완전한 인라인 패스를 갖고 있어요.

또한 열려 있고 환영하는 커뮤니티처럼 보여서, 기여도 환영받아요.

실험의 목표

  • 맥락은 AOT(ahead-of-time) 컴파일 시나리오의 Strong Mode Dart예요.
  • 정밀하고 이동하는 GC에 Statepoint 지원을 사용할 수 있는지 타당성을 평가한다.
  • 성능을 평가한다.

방법론

우리(Erik Corry와 Dmitry Olshansky)는 중단된 'Dartino' 런타임에 기반해 실험을 설계했어요. 이것은 소형 기기에 최적화된 실험용 Dart 런타임이에요. DartVM을 기반으로 하는 것보다 우리에게 몇 가지 장점이 있었죠:

  • Dartino용 실험적 LLVM 백엔드가 이미 있었어요. Martin Kustermann이 만들었고, GC 지원이 없어 메모리가 부족해지면 크래시했죠.
  • Dartino는 Dart2JS의 매커니즘을 많이 활용해서, 완전한 파서나 프론트엔드 등이 필요 없어요. 우리가 입력으로 쓰는 Dartino 바이트코드에는 어려운 Dart 기능들이 이미 많이 낮춰져(축소돼) 있어요. 예를 들어 클로저는 객체이고, 옵션 인자는 함수의 서로 다른 버전들로 바뀌어 있어요.
  • 우리 둘 다 이미 Dartino에 익숙했어요.
  • Dartino는 비교적 완전한 런타임을 갖추고, 대형 앱을 실행할 수 있어요. 예를 들어 Dart2JS를 호스팅할 수 있죠. Unix I/O 지원은 많지 않고 스레딩 모델도 달라서, drop-in 대체품은 아니에요.

Dartino의 가비지 컬렉션

기존 Dartino LLVM 실험은 한동안 전에 Dartino에서 포크됐는데, 그때 GC는 아주 단순했어요(세미스페이스 Cheney 컬렉터, 세대 없음, 큰 정지, 2배 메모리 오버헤드). 우리는 write barrier가 있는 더 전통적인 2세대 GC를 얻기 위해 메인 Dartino 브랜치의 변경 사항을 체리픽했어요. read barrier는 없고, 수집은 concurrent GC 없이 stop-the-world 방식이에요. (물론 LLVM Statepoint는 이런 기능을 지원하는 것처럼 보이고, Azul이 그들의 비공개 VM에서 거의 확실히 사용하고 있어요.)

더 새로운 Dartino 버전의 compacting old-generation 지원은 체리픽하지 않았어요.

아키텍처

위 파이프라인은 Dart 소스에서 머신 코드까지의 경로를 보여줘요. 실제 구현에서는 앞부분이 'kernel' 형식(미리 파싱된 Dart 소스 프론트엔드)에 기반한 것으로 교체될 거예요.

LLVM으로 번역과 고수준 최적화

llvm-codegen은 우리가 가진 LLVM 사본에 링크되고, 고수준 최적화를 수행해요. 이 단계에서 LLVM은 포인터가 GC 사이에서 유효하다는 허구를 유지하지만, 포인터는 비기본 '주소 공간(address space)'으로 표시되어, 이동하는 GC가 있을 때 부정확해질 방식으로 LLVM이 그 비트 패턴을 추론하는 것을 막아요. GC가 발생할 수 있는 지점을 표시하는 데는 여러 커스텀 LLVM 내장 함수(intrinsic)가 사용돼요.

태그된 포인터 때문에 LLVM 비트코드는 캐스트와 덧셈이 많은 아주 지저분한 형태예요. 그래서 이 문서는 실제 .ll 파일이 아니라 'LLVM 의사코드'를 담고 있어요. 실제 .ll 파일에 익숙하다면 이건 "아기 첫 .ll 끄적임"처럼 보일 거예요, 죄송해요! 다음은 로컬 변수를 스택에서 SSA 레지스터로 끌어올리는 mem2reg 패스 이후의 동적 디스패치를 나타낸 코드예요:

%class = load_class(%this)
%id = load_class_id(%class)
%offset = add 291, %id
%code = array_load(@dartino_vtable, %offset)
%method_result = call %code(%process, %16)
; We can still use "%this" here, even if there has been a GC in the call

옵티마이저가 실행된 후에는, 위의 상당히 번거로운 조회가 루프 밖으로 끌어올려져서 호출 명령만 남아요. 이게 가능한 이유는 Dart에서 클래스 포인터가 불변이고, 우리가 load 명령들에 여러 메타데이터를 붙였기 때문이에요. 여기엔 invariant.load와 never.faults가 포함돼요. (후자는 우리가 패치한 LLVM 버전에 추가한 것이에요.)

낮추기(Lowering)

고수준 최적화가 실행된 후, 우리는 대부분의 내장 함수를 일반 LLVM 명령으로 낮춰요. 예를 들어 write barrier는 일련의 저장(store)으로 줄어들어요. (Dartino는 Urs의 박사 논문 6.2.3절에 많은 빚을 진 card marking 기법을 사용해요.) 낮춘 후에는 모든 로컬 변수 포인터가 가능한 모든 GC 지점(기본적으로 모든 호출)에서 불투명한 내장 함수로 다시 쓰여져요. 이는 많은 최적화를 억제하지만(그래서 낮추기 전에 최적화 패스를 해야 했어요), 두 가지 목적을 제공해요:

  • 그 내장 함수는 나중에 GC 가능한 포인터의 스택 위치를 상세히 나타내는 스택 맵을 생성하는 데 사용된다.
  • SSA 값이 GC 전과 GC 후의 값으로 나뉘어, GC를 옵티마이저에게 보이게 하고 잘못된 코드 생성을 막는다.

이제 호출은 이렇게 더 보일 거예요 (디스패치가 루프 밖으로 끌어올려졌으므로 %code가 코드 포인터를 담고 있어요. 루프는 보여주지 않았어요):

%statepoint_token = call token (…) @llvm.experimental.gc.statepoint(326, 0, %code, 3, 0, %process, %this, %16)
%method_result = call @llvm.experimental.gc.result(token %statepoint_token)
%this.relocated = call coldcc @llvm.experimental.gc.relocate(token %statepoint_token, 10, 10) ; (%this, %this)
%16.relocated = call coldcc @llvm.experimental.gc.relocate(token %statepoint_token, 11, 11) ; (%16, %16)
; We now have to use %this.relocated instead of %this,
; and %16.relocated instead of %16

이 변환은 꽤 서툴러요. 변환된 호출에서 특별한 토큰을 만들고, 그걸 gc.result와 gc.relocate 호출의 인자로 사용하죠. GC 가능한 포인터는 여전히 특별히 표시되어(위 의사 LLVM엔 안 보이는 0이 아닌 주소 공간), 다음 단계에서 일부 최적화를 억제해요.

코드 생성

마지막 단계는 LLVM 프로그램 llc가 수행하는 코드 생성이에요. 이 단계는 완전히 패치되지 않은 ToT LLVM으로 llc -O3 명령으로 수행할 수 있어요. 실험적 GC 내장 함수를 지원하는 백엔드는 현재 x64뿐이지만, ARM 지원을 추가하고 상류로 올리는 데 근본적인 장벽은 없다고 봐요. 동적 디스패치 호출 지점은 이제 이렇게 생겼어요:

movq %rdx, (%rsp)
movq %rcx, 8(%rsp)
movq %rdx, 16(%rsp)
movq %rbx, %rdi
movq %rcx, %rsi
callq *%r14

이건 x64의 표준(대부분 레지스터 기반) 호출 규약을 사용해요. 매 호출 전에 많은 레지스터가 스택으로 유출(spill)되는데, 거기서 필요하면 GC가 이동시킬 수 있죠. callee-saved GC 가능 값에 대한 지원은 없어요. (V8과 DartVM도 이를 지원하지 않아요.)

성능

Dartino 바이트코드는 매우 동적 타입 환경에서 단순함과 컴팩트함에 최적화되어 있어요. 이 분석에서 우리는 strong mode가 사용되고 타입이 컴파일 시점에 알려지는 시나리오를 상상해 봐요. 그 시나리오에선 객체의 메서드 디스패치와 멤버 변수 접근이 더 단순하고 빨라질 거예요. 그 시나리오에 더 가까워지기 위해, 우리는 LLVM 코드를 생성할 때 몇 가지 전체 프로그램 분석을 활용해요.

이것의 가장 중요한 결과는, foo() 메서드를 가진 클래스가 몇 개뿐이라면 그 클래스들을 검사해서 foo() 메서드를 직접 호출한다는 거예요. 어떤 vtable류 디스패치 메커니즘과 달리, 이렇게 하면 LLVM이 타당한 곳에서 메서드를 인라인할 수 있어요. 특히 getter와 setter에서 큰 이득인데, 이 둘은 Dart의 훌륭한 기능이죠.

컴파일러는 여전히 많은 동적 언어 문제를 처리해야 하는데, 대부분 올바르게 처리해요 (아래 테스트 상태 절 참고). 특히 정수는 언제든 오버플로돼 실제 힙 할당 숫자 객체가 될 수 있어요. 연산자 오버로딩과 합쳐지면 간단한 for 루프조차 꽤 복잡해져요. 더 많은 정적 분석이 아마 이것을 개선할 수 있을 거예요.

실제 DartVM과 한 가지 다른 점은, 우리는 스택 오버플로를 검사하지 않고 루프 백엣지에서 스레드 인터럽트도 검사하지 않아요. V8 경험에 기반해 추측하건대, 고치는 데 성능의 약 10%가 들 거예요.

우리는 일반 JITing DartVM과, Flutter를 위해 DartVM에 추가된 새로운 AOT 지원과 비교해요. 벤치마크는 Dartino에서 가져왔어요.

Hello World처럼 수명이 짧은 프로그램을 실행하면 주로 시작(startup) 시간이 나와요. JIT 기반 시스템은 코드 컴파일에 시간을 쓰고, 여기서 LLVM이 아닌 두 해법은 시작 시 데이터 힙을 역직렬화해요.

성능 결론

우리는 Flutter의 기존 AOT 기술과 비슷한 성능을 냈어요. (그건 움직이는 표적이라, 이 측정은 2016년 11월 말에 육중한 64비트 Linux 워크스테이션에서 이뤄졌어요.) JIT는 여전히 한참 앞서 있어요. 우리가 실행 중인 Dartino 포크의 가비지 컬렉션 성능은 따라잡지 못하고 있어요.

시작 시간도 측정했어요. Dartino-LLVM은 클래스, 상수, 디스패치 테이블에 대한 정적 데이터를 생성해요. 이들은 고도로 최적화된 ld.linux 런타임 링커가 로드하는데, 현재 Dart AOT 데이터 힙 스냅샷보다 더 빨리 로드되어 시작에 아주 좋은 성능을 줘요. 시작 테스트에서는 CPU 거버너가 'performance'로 설정됐어요.

호환성에 대한 참고

이 연구에서 우리는 100% Dart 호환성을 얻는 데 특별히 집중하지 않았어요. '어려운 일들', 즉 GC와 예외 처리를 하는 것으로 충분하고, 그게 가능하다는 걸 증명하는 데 초점을 맞췄죠. 어떤 경우에는 실제 해법을 구현하는 데 시간을 낭비하지 않고 진짜 해법이 가능하다는 걸 보여주는 지름길을 택했어요. 우리가 타협한 곳은 이래요:

  • Dartino처럼 우리도 무한 정밀 정수가 없어요. 하지만 모든 정수 연산은 오버플로를 검사하고, 동적으로 박스형 숫자 표현으로 전환해요. (다만 박스형 표현은 64비트뿐이고 감싸기(wrap)돼요.)
  • no-such-method(본질적으로 실패한 타입 검사)에서 우리는 전체 Dart 의미론을 따르지 않아요. 여기에는 no-such-method 메서드를 호출하고, 빠진 메서드와 같은 이름을 가지며 'call' 메서드를 가진 객체를 반환하는 getter를 검사하는 것이 포함돼요. 하지만 안전한 지점(할당이 일어날 수 있는 지점)에서 예외를 던지긴 해요.
  • 호출에서 스택 오버플로를 검사하지 않고, 루프 백엣지에서 인터럽트를 검사하지 않아요. LLVM은 이에 대한 실험적 지원이 있어요. 우리가 비교하는 해법들은 이를 지원해요. V8 경험에 따르면 고치는 데 성능 저하 약 10%가 들 수 있어요.
  • 우리의 프론트엔드 컴파일러는 수정된 Dart2JS예요. Dartino가 중단됐기 때문에 언어의 최신 변경 사항을 따라잡지 못해서, 실행할 수 없는 테스트가 몇 가지 있어요.
  • no-such-method 관련 예외를 제외하면 Dart 예외 처리는 완전히 구현돼 있어요. 이를 위해 우리는 LLVM에 내장된 예외 처리 지원을 사용했는데, 이 작업에 적합하고 Dart의 예외 모델과 잘 맞아 보여요. (Dart의 예외 모델은 핵심적으로 LLVM이 설계된 C++와 그리 다르지 않아요.)

전체적으로 우리는 Dartino가 통과할 수 있는 테스트의 거의 90%를 통과해요. 실패하는 것 중 가장 큰 이유는 컴파일러 프론트엔드 문제와 no-such-method 이벤트 처리 문제예요.

실패하는 약 11.6%의 테스트 중, 실패 이유의 분류는 이래요… (이어지는 세부 분석은 다이어그램으로 제공돼요.)

결론

실험적 LLVM GC 지원은 x64에서 완전히 기능하는 것처럼 보여요. 프로토타입의 성능은 우리의 더 성숙한 DartVM 기반 AOT 해법과 맞먹었어요.

성능 분석에선 Dart strong mode를 전혀 활용하지 않았는데, strong mode는 LLVM의 강점에 잘 맞는 최적화 기회를 줄 거라 예상돼요. 하지만 우리는 현실적이라고 생각하는 몇 가지 closed world 가정을 활용하고 있어요.

우리는 마지막 단계(LLVM 비트코드에서 머신 코드로)를 패치되지 않은 LLVM ToT 빌드만으로 컴파일할 수 있었어요. (위 파이프라인 다이어그램에서 파란색으로 표시됐죠.) 이 단계에서 수행된 최적화(-O3)는 우리가 관찰한 오작동이나 GC 문제를 일으키지 않았어요.

미래

이 접근을 Dart나 Flutter에 어떻게, 그리고 쓸지 말지를 결정한 바는 없어요. 하지만 탐구할 만한 흥미로운 길에 대한 몇 가지 생각을 정리해볼게요.

  • 런타임 루틴을 작성하기 위해 C++-with-handles 외의 자체 언어를 쓰는 것. 백엔드는 LLVM-with-Statepoints가 되겠죠. (현재 브랜치에 약간의 Forth 실험이 있지만, 가장 단순한 네이티브 루틴 이상을 쓰려면 더 굵직한 무언가가 필요해요.)
  • 64비트 정수를 감싸는 것이 어떤 영향을 미칠까?
  • 대형 프로젝트의 병렬 컴파일을 허용하면서도 전체 프로그램 지식을 활용해 코드를 생성하려면 어떻게 할까?

참고자료

더 알아보기