Cranelift 컴파일러에서 ISLE DSL이 어떻게 설계되었고, 강한 타입 시스템과 외부 추출기/생성자, Rust FFI를 통해 실용적인 규칙 기반 로워링 및 최적화 재작성을 가능하게 하는지 설명한다.
URL: https://cfallin.org/blog/2023/01/20/cranelift-isle/
오늘은 ISLE(“instruction selection/lowering expressions”, 명령 선택/로워링 표현)라는 도메인 특화 언어(DSL)에 대해 글을 쓰려 한다. 우리는 지난 1년 동안 Cranelift 컴파일러 프로젝트에서 ISLE을 설계하고 개선했으며, 완전히 채택했다. ISLE는 이제 네 가지 대상 아키텍처 각각에 대한 명령 로워링 패턴과, 머신 독립적인 최적화 재작성(rewrite)을 모두 표현하는 데 사용된다. 이 덕분에 우리는 컴파일러의 이 부분들을 극도로 생산적인 방식으로 개발할 수 있다. 즉 “어떤 opcode/명령은 다른 것으로 매핑되어야 한다”라는 핵심 아이디어를 간결하게 적으면서도, 표현력 있는 타입 시스템을 통해 타입 안정성을 유지하고, 선언적 패턴을 다양한 목적에 활용할 수 있다.
이 글의 목표는 ISLE의 핵심 아이디어에 이르게 된 요구사항과 설계 공간(design-space)을 보여 주는 것이다. 특히 다른 “항 재작성 시스템”들과의 차이점, 그리고 Prolog 같은 백트래킹 언어의 아이디어를 혼합한 부분을 다룰 것이다. 구체적으로는 ISLE이 강한 타입 시스템을 가지고 있으며(하나의 “값” 타입이 아니라 서로 다른 타입의 항(term)을 가짐), 임베딩 환경이 제공하는 추상적 “추출기(extractor)”에 대해 매칭한다는 점(실제로 입력 항을 구체화하지 않고도 가상의 “입력 항”을 정의하는 효과), 그리고 Rust와의 단순한 “FFI”를 명시적으로 설계하여 컴파일러의 나머지 부분과 “마법 없는”, 이해하기 쉬운 상호작용을 제공한다는 점을 논한다. 이러한 성질들은, 완전히 수작업으로 작성된 컴파일러 백엔드에서 DSL로 모든 로워링 로직을 옮기는(DSL 코드 2만7천 줄) 점진적 경로를 가능하게 했고, 1년에 걸친 마이그레이션 동안 비교적 낮은 결함률과 함께 중간중간 큰 정확성 개선을 얻을 수 있었다.
ISLE 프로젝트는 개인적으로도 내 커리어에서 꽤 흥미로운 순간이었다. 기존 접근을 종합하고 도메인/요구사항을 신중히 사고해, 오래된 아이디어를 약간 새롭게 비틀어 실용적으로 만드는 과정이 필요했다는 점에서 매우 “연구 프로젝트”에 가까웠다. 동시에 설계의 점진성 및 실용성 측면(이 부분은 regalloc2에 대한 이전 글에서도 언급했다)에도 많은 공이 들었고, 12개월짜리 마이그레이션 노력의 유지·보수, 언어와 사용법에 대한 이해의 정리, 지속적인 개선 아이디어의 육성에도 신경을 많이 썼다. (i) 문제 공간을 핵심으로 압축하고 작동하는 설계를 찾아내도록 충분한 시간과 자율을 받았고, (ii) 이를 받아 실제로 만들어 낸 훌륭한 동료들이 있었다는 점에서 운이 좋았다고 느낀다. (특히 Cranelift에 ISLE을 통합했고, Cranelift에서 재작성 DSL의 아이디어를 Peepmatic 프로젝트로 개척해 ISLE의 많은 부분에 영감을 주고 이번 노력을 위한 토양을 만든, 뛰어난 동료 Nick Fitzgerald (@fitzgen)에게 특별히 감사한다.) ISLE로부터 지금까지 본 이점과 앞으로 기대하는 이점에 대해서는 여기에서 더 썼다. 요약하면, 우리는 이 방향을 선택한 것에 만족하고 있으며, 이 작업이 가능하게 한 추가 성과들을 기대하고 있다.
이 글은 ISLE의 pre-RFC와 RFC 초기 문서에서 내가 했던 주장과 내용을 다루고 일부 반복한다. 배경이 더 필요하면 그 문서들도 함께 읽기를 권한다. ISLE 언어 레퍼런스가 DSL의 정식 정의이다.
먼저 Cranelift의 배경과 컴파일러 DSL 전반을 간단히 살펴보고, Cranelift에서 DSL이 필요한 이유를 동기부여한 뒤, ISLE 자체의 세부로 들어가겠다.
Cranelift 프로젝트에서는 2020년부터 머신 백엔드(최종 최적화된 머신 독립 IR(중간 표현)을 대상 ISA의 명령으로 변환하고, 레지스터를 할당하고, 제어 흐름을 로워링하고, 머신 코드를 방출하는 컴파일러의 부분)를 위한 새로운 프레임워크를 개발했다. (자세한 내용은 예전 글 시리즈: 첫 번째, 두 번째, 세 번째에 설명했다.)
ISLE을 도입하기 전에는 이 프레임워크로 세 가지 백엔드를 만들었다: AArch64, x86-64, s390x(IBM Z). 전반적인 경험은 상당히 좋았다. “간단한 수작업 로워링 패스” 설계를 지향해 단순성을 확보함으로써, WebAssembly(코어 및 SIMD) 지원을 빠르게 거의 완전하게 구현했고, cg_clif 같은 다른 Cranelift 사용자도 지원할 수 있었다. 2021년 3월에는 새 x86-64 백엔드를 기본으로 만들었고, 2021년 9월 말에는 레거시의 복잡하고 느린 프레임워크를 가진 기존 x86 백엔드를 제거할 수 있었다.
하지만 많은 엔지니어링 문제와 마찬가지로 설계 공간에는 트레이드오프가 있다. “opcode에 대해 match를 쓰고 명령을 방출하면 된다”는 접근의 단순성은, 어느 순간부터 단점이 되었다. 타입, 부분식, 특수 케이스에 대한 조건들이 많은 점점 더 깊게 중첩된 로워링 함수가 생겼고, 이를 추적·관리하기가 갈수록 어려워졌다. 전체적으로 보면 세 가지 주요 문제에 부딪혔다:
본질적으로 “로워링 패턴 목록”의 장황한 수기 버전을 작성하는 일이 매우 _지루_해졌다. IR 연산자 조합에 대한 특수 로워링을 추가하려면, 수작업 코드의 제어 흐름을 이해하고, 특수 조건 검사나 다른 결합 연산자 탐색을 손수 작성해야 한다. 그러면 백엔드를 개선하려는 동기가 크게 줄어든다. 오히려 코드를 가능한 단순하고 최소한으로 유지해 변화를 억제하는 쪽으로 유인이 생긴다.
코드 리팩터링이 어려워졌다. 더 많은 수작업 백엔드 코드가 로워링 API의 미묘한 디테일에 의존하게 되면서, 컴파일러의 “로워링 API”가 굳어(ossify) 버렸고, 리팩터링이 매우 어렵거나 불가능해졌다. 이는 regalloc2 작업에서 특히 두드러졌다.
정확성을 유지하고 백엔드가 기대한 코드를 생성하는지 보장하기가 갈수록 어려워졌다. 로워링 API를 사용해 코드를 작성할 때는 언제 명령을 “결합(combine)”할 수 있는지, 언제 연산을 “내릴(sink)” 수 있는지 등의 미묘한 정합성 불변식(invariant)과 레지스터/임시값을 올바르게 사용하는 규칙을 염두에 두어야 했다. 어떤 식으로든 “정상 동작하는 코드”를 생성하더라도, 상태 공간의 한 구석을 놓쳐 특정 입력 타입 조합에 대한 로워링을 빠뜨리거나, 의도한 최적화 로워링을 건너뛰고 일반 로워링을 사용하는 일이 복잡한 제어 흐름 때문에 우발적이고 추론하기 어려운 방식으로 발생하기 쉬웠다. 아래에서 보겠지만 DSL은 (i) DSL 안의 원칙적이고 강한 타입의 추상화, (ii) “중첩/겹침(overlap) 검사”를 통해 각각 이 문제들을 해결한다.
이런 이유로 어떤 메타-기술로부터 로워링 패턴을 생성하면 컴파일러 소스가 전반적으로 더 명확하고 유지보수 가능해지고, 번역 세부를 바꾸거나 최적화하고 싶을 때 더 유연해질 것임이 분명해졌다. 그래서 Cranelift의 이 부분을 생성하기 위한 도메인 특화 언어(DSL)가 필요하다는 결론에 이르렀다.
컴파일러를 기술하기 위한 DSL(“메타컴파일러”, “컴파일러-컴파일러”)에는 1970년대까지 거슬러 올라가는 긴 역사가 있다. DSL 기반 명령 선택 단계의 일반적인 아이디어는, 프로그램 내 연산자 조합인 패턴 목록을 선언적으로 기술하고, 각 패턴이 매칭될 때 이를 구현할 수 있는 일련의 명령을 지정하는 것이다. 이는 컴파일러가 무엇을 하는지 더 쉽게 이해하고, 수정·개선하며, DSL을 이용해 백엔드 생성 방식을 바꿈으로써 체계적인 최적화를 적용하기 쉽게 해 준다.
컴파일러 백엔드에서의 “패턴 재작성” 접근은 항 재작성 시스템의 한 형태로 볼 수 있다. 즉 어떤 데이터 표현(여기서는 컴파일할 프로그램)에 대해 규칙이 작동하는 형식적 프레임워크다. 항 재작성은 오래된 아이디어다. 계산의 수학적 모델 중 원초적 모델인 람다 계산은 항 재작성으로 동작한다. 구조화된 데이터를 변환하는 것이 목표일 때, 유용할 만큼 일반적이면서도 간결하고 표현력이 좋아 생산성이 높다.
항 재작성이 특히 컴파일러에 잘 맞는 한 가지 이유는, “항”(AST의 노드)이 컴파일되는 프로그램의 값을 표현하기 때문이다. 그러면 재작성 규칙은 _동치성_을 표현한다. 컴파일러 IR의 “정수 덧셈” 연산은 특정 CPU ISA의 정수 덧셈 명령과 _동등_하므로(동등한 결과를 생성하므로) 하나를 다른 것으로 바꿀 수 있다. 예를 들어 (add x y) => (x86_add x y) 같은 규칙을 쓸 수 있다. 많은 컴파일러 최적화도 학생들이 대수에서 익숙한 방식으로 규칙으로 표현할 수 있다. 예를 들어 x + 0 == x, AST 표기로는 (add x 0) => x.
이런 패턴 규칙의 예는 실제 컴파일러에 풍부하다. 예를 들어 Go 컴파일러에서는 IR 연산자가 x86-64 명령으로 변환되는 방식을 규칙들로 정의한다:
// Lowering arithmetic
(Add(64|32|16|8) ...) => (ADD(Q|L|L|L) ...)
// combine add/shift into LEAQ/LEAL
(ADD(L|Q) x (SHL(L|Q)const [3] y)) => (LEA(L|Q)8 x y)
// Merge load and op
((ADD|SUB|AND|OR|XOR)Q x l:(MOVQload [off] {sym} ptr mem)) &&
canMergeLoadClobber(v, l, x) &&
clobber(l) =>
((ADD|SUB|AND|OR|XOR)Qload x [off] {sym} ptr mem)
비슷한 기술은 LLVM x86 백엔드와 GCC x86 백엔드에도 있으며, 각각 TableGen 언어(LLVM)와 Machine Description DSL(gcc)을 사용한다.
이런 규칙들로부터 자동 생성되는 컴파일러 백엔드에는 크고 잘 탐구된 설계 공간이 있다. 고전적 설계로 BURS(bottom-up rewrite system) 기법이 있다. 여기서는 깊은 소개를 하지 않겠다. 더 자세한 설명은 드래곤 북1이나 Muchnick의 교과서2에서 찾을 수 있다. 이 글에서는 이런 시스템이 입력 표현 트리 위에서 위와 같은 트리 패턴의 “커버링(covering)”을 찾는다는 것만 알면 충분하다.
위와 같은 선례(여러 주류 컴파일러가 패턴 매칭 기반 체계를 채택해 명확한 이점을 얻음)를 보면, 앞으로의 길이 잘 정해져 있는 것처럼 보인다. 그런데 왜 이 글은 아직 이렇게 많이 남아 있을까? 더 무엇을 말할 수 있을까?
전형적인 항 재작성 체계를 도입하려고 하면 세 가지 주요 문제가 나타난다.
첫째, 기본 질문이 있다. 입력 트리를 실제로 트리로 구체화(reify)할 것인가? 예를 들어 다음과 같은 패턴이 있을 때:
(add x y) => (x86_add x y)
두 피연산자의 add 연산이 x86 ADD로 로워링된다는 의미인데, 이것이 IR에 add에 해당하는 노드가 문자 그대로 들어 있다는 뜻일까?
이는 어리석은 질문처럼 보일 수 있다. Cranelift의 IR인 CLIF에는 실제로 add(정확히는 “integer add”인 iadd) 연산자가 있고 두 인자를 받는다.
하지만 “연산자 트리”에 직접 매칭한다는 것은 IR의 몇 가지 속성을 함의하며, 이는 깊은 영향을 준다. 그중 하나는 연산자의 “값” 혹은 “결과”가 그 노드의 유일 식별자라는 성질이다. CLIF에서는 그렇지 않다. 각 명령(instruction)은 자체 식별자(Inst)가 있고, 각 Inst는 여러 개의 Value 결과를 가질 수 있다. 또 다른 성질은 매칭 과정이 보아야 하는 트리가 IR에 있는 그대로의 트리라는 점이다. 하지만 백엔드가 더 깊이 내려가서 연산자를 “병합(merge)” 처리하려 할 때는 여러 고려사항이 관련된다. 이런 비정합(impedance mismatch)들은 치명적이지는 않지만, “매칭되는 형태의 트리”를 메모리 상에 구성하기 위한 추가 작업을 시사한다.
둘째, 원시 연산자 트리 외에 _추가 정보_를 어떻게 포함할 것인가라는 문제가 있다. 이는 “사이드 테이블/보조 정보”, 혹은 입력 트리에 대한 여러 “질의(query)”를 지원하는 문제로 볼 수 있다.
예를 들어 어떤 ISA에만 있는 특정 즉시값(immediate) 인코딩 형태를 항으로 표현하고 싶을 수 있다. AArch64에는 여러 형태가 있는데, “일반적인” 12비트 즉시값과, 13비트만으로 흔한 비트마스크를 효율적으로 표현하도록 설계된 영리한 “logical immediate” 포맷이 있다. 이를 항으로 나타내고 (iconst K)를 (aarch64_imm12 bits) 또는 (aarch64_logicalimm bits)로 번역하는 규칙, 그리고 이후 이러한 항에 매칭해 즉시값 사용 명령 형식을 인코딩하는 규칙을 둘 수 있다. 그러면 문제는, 어떤 중간 재작성을 먼저 수행해야 실제 명령 형식과 매칭을 시도할 수 있는가이다. 둘 다 수행해 두 형태를 모두 표현해야 할까?
이 요구사항의 결과로 재작성 규칙의 매칭 패턴은 항의 트리라기보다 커스텀 질의의 열(sequence)처럼 보이기 시작한다. Go 컴파일러의 규칙은 이런 케이스를 처리하기 위해 규칙에 술어(predicate)를 추가하지만, 이는 어색하고 언어를 추론하기 어렵게 만든다. ISA 개념도 항 재작성 레벨에서 표현할 수 있다면 더 좋을 것이다.
셋째, 입력 표현에 대해 이런 질의를 수행할 때 컴파일러의 다른 부분과 어떻게 상호작용할 것인가의 문제다. 가장 단순한 구현에서 재작성 시스템은 패턴의 항이 매칭하는 “트리 노드”와 재작성 표현이 생성하는 노드를 알고 있다. 그러나 재작성 시스템과 IR 데이터 구조 사이의 접착(glue)을 만드는 일은 사소하지 않을 수 있으며, 앞서 말한 커스텀 질의까지 포함되면 더 어려워진다.
이 모든 것이 질문을 던진다. 재작성 규칙의 실행 의미를 더 나은 방식으로 볼 수는 없을까? DSL이 AST나 재작성에 전혀 직접 관여하지 않는다면 어떨까?
이 지점에서 ISLE의 첫 번째 핵심 아이디어가 떠올랐다. 컴파일러의 나머지 부분과의 모든 상호작용을, Rust 함수로 구현된 “가상(virtual)” 항을 통해서만 하도록 하면 어떨까? 즉, 리터럴 AST 자료구조에 매칭하고 이를 재작성하거나 새로운 출력 AST를 만드는 시스템 대신, 패턴 매칭은 일종의 FFI에서 “바닥을 치며” 나머지 컴파일러를 수작업 Rust로 호출한다. DSL 자체는 컴파일러의 나머지 부분이나 “AST”, 기타 IR-특화 개념을 전혀 모른다. (이것이 ISLE의 핵심 비밀이다. ISLE은 사실 명령 선택 DSL이 아니라, 실제로는(적어도 지향적으로는) 더 일반적인 언어다.)
예를 들어 다음 규칙이 있다고 하자:
(iadd (imul a b) c) => (aarch64_madd a
b c)
이는 아래와 같은(가상의) 매칭 엔진용 “매칭 연산” 시퀀스로 컴파일될 수 있다고 상상할 수 있다:
$t0, $t1 := match_op $root, iadd
$t2, $t3 := match_op $t0, imul
$t4 = create_op aarch64_madd, $t2, $t3, $t1
return $t4
이 “매칭 VM”에서 match_op는 기대한 연산자에 따라 트리 노드를 자식(인자)으로 분해하려고 시도한다. 이 매칭 연산들의 어느 단계든 “실패”할 수 있으며, 실패하면 다음 재작성 규칙을 시도한다. 입력 트리의 루트에서 iadd를 매칭하고, 그 첫 번째 인자에서 imul을 매칭할 수 있다면, 이 규칙의 컴파일 결과는 aarch64_madd(multiply-add) 항을 만든다.
match_op 같은 고정된 연산 집합 대신, 환경이 정의하는 연산을 허용한다면 어떨까? 위에서 말한 aarch64_logicalimm 같은 연산자도 “매칭 연산”이 되어, 주어진 u64가 원하는 형태로 인코딩될 수 있으면 매칭에 성공하고 아니면 실패하도록 할 수 있다면?
이것이 ISLE에서의 “외부 추출기(external extractor)” 아이디어(그리고 이에 대응하는 “외부 생성자(external constructor)”)의 핵심이다. 좌변(매칭 패턴)에서 사용자 정의 연산자를 허용하면, AST 매칭에 대한 내장 개념 자체가 더 이상 필요하지 않다. 이는 DSL의 “표준 라이브러리”나 “프렐류드(prelude)”에서 정의할 수 있는 또 하나의 기능이 된다
기본 아이디어는 iadd나 imul 같은 항을 _정의_하고, 그에 외부 Rust 함수를 연결(associate)할 수 있게 하는 것이다. 재작성 규칙의 좌변에 나타날 때, 항은 “바깥에서 안으로(outside-in)” 매칭한다. 즉 (iadd (imul a b) c)는 입력의 루트를 잡고 iadd로 이를 두 인자로 분해하려 시도한 뒤, imul로 더 분해하려 한다. (이 바깥→안 매칭 순서는 함수 호출 트리로 생각하면 직관과 반대일 수 있는데, 우리는 _구성(construct)_이 아니라 _분해(destructure; extract)_를 하고 있기 때문이다. 아래에서 함수와의 비유를 더 살펴보겠다.)
이제 실제 ISLE 문법으로 넘어가자. 다음과 같이 iadd 항을 정의할 수 있다:
(decl (iadd Value Value) Value)
그리고 이에 Rust 함수를 연결한다:
(extern extractor iadd my_iadd_impl)
그러면 생성된 매칭 코드가 호출할 Rust 함수가 존재해야 한다:
fn my_iadd_impl(&mut self, input: Value) -> Option<(Value, Value)>;
마찬가지로 우변에서 사용할 항을 정의하고 구현을 연결할 수 있다:
(decl (aarch64_madd Value Value Value) Value)
(extern constructor aarch64_madd my_madd_impl)
Rust 함수는 다음과 같다:
fn my_madd_impl(&mut self, a: Value, b: Value, c: Value) -> Value;
그리고 규칙은 이렇게 쓴다:
(rule (iadd (imul a b) c)
(aarch64_madd a b c))
생성된 코드는 외부 추출기 my_iadd_impl을 호출하고, Some을 반환하면(매칭 성공) imul에 연결된 외부 추출기를 호출하며, 그것도 Some이면 aarch64_madd를 호출해 결과를 “구성”한다. 이 Rust 함수들은 무엇이든 할 수 있다. 실제로 구체화된 AST를 질의하고 변형해야 한다는 필요를 추상화해 버렸다.
이 설계의 또 다른 중요한 결과는, 임의의 추출기와 생성자를 정의할 수 있고, 그것들이 임의의 타입을 가질 수 있다는 점이다. (ISLE은 강한 타입을 가지며, 합(sum) 타입은 Rust enum으로 1:1로 내려간다.) 이는 앞의 “메타데이터/사이드 테이블” 문제를 깔끔하게 해결한다. 값에 대한 정보를 표현하기 위해 실제 AST에 보조 노드를 만들 필요도 없고, 언제 계산해야 하는지 미리 알 필요도 없다. 이런 계산은 좌변 매칭 쪽에서의 수요(demand)에 의해 구동될 수 있고, 어떤 실제 노드도 구체화할 필요가 없다.
여기서 한 걸음 물러나 우리가 한 일을 이해해 보자. 우리는 다음과 같은 트리 재작성 규칙을:
(iadd (imul a b)
c) => (madd a b c)
좌변과 우변의 항들이 Rust 함수 호출로 컴파일되도록 허용했고, 그 의미가 명확해졌다. DSL은 패턴 매칭만 다루며, AST와 컴파일러 IR은 DSL의 이해 밖에 있다. 그럼에도 iadd, imul, madd에 형식적 의미를 부여할 수 있다면, 우리는 여전히 항 재작성 시스템 레벨에서 이 재작성을 추론할 수 있고, 이는 백엔드에 대한 형식 검증 노력에서 필수적이다(아래 참조!). 즉 기존 수작업 Rust 코드와 통합하면서도, 더 선언적으로 추론할 수 있도록 추상화 수준을 올렸다.4
명시적 AST 자료구조를 재작성 엔진이 순회하며 구축하는 방식에서, 외부 추출기/생성자 호출로 이동한 변화는 잠시 음미할 가치가 있다. 이 변화의 결과로 추출기 매칭에 해당하는 항 노드는 메모리에 실제로 존재할 필요가 없다. ISLE의 재작성 흐름은 “비지터 패턴”과 비슷한 방식으로 동작한다. 데이터의 소비/생산을 표현과 분리해 더 큰 유연성을 제공한다.
또한 실행 주도 관점은 재작성 절차 자체도 공짜로 준다. 패턴과 재작성을 기술한 스펙을 받아 동작하는 엔진 대신, 규칙을 추출기/생성자를 호출하는 순차 코드로 컴파일한다. 최상위 항을 “재작성”하는 것은 Rust 함수를 호출하는 것과 같다. 명령 로워링에 해당하는 lower라는 항을 정의하면,
(lower (iadd
...))
는 규칙이 지정한 ISA-특화 항으로 재작성될 항이다. 이 재작성은 lower를 _구현_하는 _Rust 함수_가 수행한다. 이 함수는 인자를 받아 필요에 따라 추출기에 매칭하고, 생성자를 호출해 재작성된 표현을 만든다.
ISLE이 대부분의 다른 항 재작성 시스템과 비교해 두 번째로 차별화되는 점은 _강한 타입 시스템_이다. Rust로 컴파일되는 DSL이라면 enum 같은 합 타입을 포함해 Rust 타입 시스템을 어느 정도 반영하는 타입 시스템을 갖는 것이 그리 놀랍지 않을 수 있다. 하지만 이는 전통적인 컴파일러 백엔드 규칙 시스템과는 약간 다르며, 아래에서 보겠지만 표현력과 안전한 캡슐화에 큰 이점을 준다.
전통적 재작성 시스템은 프로그램의 값을 나타내는 AST 위에서 작동한다. 즉 DSL 레벨에서 모든 항은 같은 타입을 가진다. iadd를 x86_add로 바꿀 수 있는 이유는 둘 다 Value 타입이기 때문이다.
이는 단순 치환에는 잘 동작하지만 ISA의 복잡성을 고려하면 금방 한계가 온다. 예를 들어 주소 지정 모드(addressing mode)를 어떻게 모델링할까? x86는 피연산자로 “레지스터 또는 메모리”를 받을 수 있다. 메모리 피연산자라면 주소는 [reg], [reg + offset],
[reg + reg +
offset]
, [reg + scale*reg + offset] 같은 여러 형태를 가질 수 있다.
이를 모델링하기 위해 AST에 임의의(adhoc) 구조를 강제할 수도 있다. 예컨대 x86_add의 두 번째 인자에 x86_load를 넣거나(혹은 별도의 x86_add_from_memory opcode), 주소 표현식을 위한 규칙을 두는 식이다. 어떤 x86_add 노드(단 레지스터 인자만!)를 만나면 이를 명령의 주소 지정 모드로 흡수할 수 있도록 말이다.
하지만 이런 임의 구조는 최적화 패스에 의해 변환될 때 특히 취약하다. 일반적으로 프로그램 불변식을 타입 시스템(어떤 레벨에서든)에 더 많이 담을수록, 리팩터링이나 예상치 못한 상호작용에서도 구조를 유지할 가능성이 커진다.
그래서 ISLE은 함수 타입과 유사한 방식으로 항에 타입을 줄 수 있다. 예를 들어 다음 항을 정의할 수 있다:
(decl lower_amode (Value) AMode)
이는 인자 하나 Value를 받아 AMode를 만든다. 그리고 AMode 타입은 다음처럼 정의할 수 있다:
(type AMode (enum (Reg (reg Reg))
(RegReg (ra Reg)
(rb Reg))
(RegOffset (base Reg)
(offset u32))))
등등. AMode는 지정한 변형(variant)을 가진 Rust enum으로 컴파일된다. 그래서 외부 추출기/생성자에서 이런 풍부한 타입을 사용해 Rust 코드와 상호운용하기가 쉽다. Cranelift의 머신 백엔드에서는 머신 명령 자체도 enum으로 정의되어 ISLE에서 직접 구성된다.
항에 “시그니처”를 부여하는 방법을 보았으니, 추출기와 생성자를 함수처럼(단, 반대 방향으로) 볼 수 있다는 점을 논해보자. 특히 다음과 같은 항이 있을 때:
(decl F (A B C) R)
인자(혹은 AST 자식 노드) 타입이 A, B, C, 항 자체의 타입이 R이면:
F는 A, B, C에서 R로 가는 함수로 볼 수 있고,F는 R에서 A, B, C로 가는 함수로 볼 수 있다.즉 좌변 패턴에서(항이 추출기로 해석될 때) 항 트리를 보면, 각 항을 “바깥 타입(분해 대상)”에서 “안쪽 타입(분해 결과 조각)”으로 가는 함수 호출로 볼 수 있다. 반대로 우변 표현에서(항이 생성자로 해석될 때) 항 트리는 “안쪽 타입(새로 만들 것의 인자)”에서 “바깥 타입(반환값)”으로 가는 함수로 볼 수 있다. 이는 앞서 설명한 ISLE 의미론의 “실행 주도” 관점을 다른 방식으로 보는 것이다.
여기서 F의 추출기 형태는 보통 _부분 함수(partial function)_다. 즉 어떤 값에 대해서는 매핑이 없을 수 있다. 이것이 AST에서 특정 노드 형태를 찾으려 할 때 “매칭 실패” 케이스를 형식적으로 생각하는 방식이다. 반면 생성자는(명시적으로 partial로 선언하지 않는 한) 보통 _전함수(total)_이며 실패할 수 없다. (partial 생성자는 if-let 절에 유용하다.)
임의 타입을 지원하면 불변식을 훨씬 더 풍부하게 포착할 수 있다. 입력 측 값이나 출력 측 머신 명령을 캡슐화해 합법적인 방식으로만 사용/결합하도록 만들 수 있기 때문이다. 예를 들면:
많은 ISA에는 특정 연산이 설정하고(0 결과, 음수 결과 등) 조건 분기나 조건 이동에서 사용하는 “플래그(flags)” 레지스터가 있다. 이는 “전역/주변(ambient)” 상태이므로 중간에 덮어쓰지 않고 생성 직후에 소비해야 하는 등 주의가 필요하다. 특정 플래그 생성자와 소비자의 정확한 대응을 보장하기 위해, 일부 명령 생성자는 원시 명령 대신 ProducesFlags와 ConsumesFlags 값을 만든다. 그리고 with_flags 생성자로 둘을 함께 방출해, 중간에 clobber가 없도록 한다.
IR 레벨의 Value와 머신 레벨(레지스터)에 있는 값을 구분해야 하는데, 이를 Reg로 표기한다. 로워링 규칙이 입력이 레지스터에 있어야 함을 요구하면 put_in_reg 생성자를 사용할 수 있다. 이는 Value를 받아 Reg를 만든다(재작성한다). 이를 통해 (해당 값이 사용되었음을 기록하고, producer를 코드 생성하도록 보장하는) bookkeeping을 할 수 있고, 값을 레지스터에 배치하는 _방법_도 구분할 수 있다. 예를 들어 값들을 부호 확장(sign-extend) 또는 0 확장(zero-extend)해야 할 수 있다.
IR 레벨 Value와 그것을 생성한 명령을 구분해야 한다. 모든 Value가 명령에 의해 정의되는 것은 아니다. 일부는 블록 파라미터다. 더 나아가 로워링 과정의 특정 시점에서는, 값을 생성한 producer를 볼 수 없어야 할 때도 있다. 현재 지점에서의 효과를 “내릴(sink)” 수 없어 현재 생성하는 명령에 병합할 수 없는 경우가 있기 때문이다. 그래서 명령은 피연산자로 Value를 갖지만, Value에서 Inst(명령 ID)로 가려면 def_inst를 사용해야 하며, Inst가 존재하고 우리가 그것을 볼/병합할 수 있을 때만 매칭된다.
타입 안전한 추상화는 잘 정의된 안전한 인터페이스를 주지만, 코드가 장황해질 수 있다. ISLE을 몇 달 사용한 뒤 우리는 다음과 같은 규칙을 쓰고 있음을 발견했다:
(rule (lower (iadd (def_inst (imul x y)) z))
(madd
(put_in_reg x)
(put_in_reg y)
(put_in_reg z)))
하지만 원래의 항 재작성 예에서처럼 더 자연스럽게:
(rule (lower (iadd (imul x y) z))
(madd x y z))
라고 쓰고 싶었다. 처음에는 둘 중 하나를 택해야 한다고 보였다. 짧은 형태를 위해 타입 구분을 포기해야 하는 것 같았다. 하지만 실제로는 중복이 있다. 좌변 패턴의 타입체크를 생각해보자. iadd의 인자(추출기가 Inst 타입을 분해할 수 있다면 생산하는 것)는 Value 타입이다. 그런데 내부 imul은 Inst를 기대한다. 프렐류드에는 이 변환을 수행하는 표준 항 def_inst가 있다. 우변에서도 바인딩 x, y, z는 Value 타입이지만, 머신 명령을 만드는 madd 생성자는 Reg 타입(레지스터 할당 전 머신 코드의 가상 레지스터)을 요구한다. 이 변환을 하는 표준 항 put_in_reg도 있다. 변환 방법이 _하나_로 정해져 있거나 일반적이고, 변환의 양쪽 타입이 이미 알려져 있다면, 필요한 변환을 자동으로 삽입해 타입을 맞출 수 있지 않을까?
그래서 ISLE에는 사용성을 높이는 마지막 비장의 카드가 있다: 암시적 변환(implicit conversions). 다음처럼 타입 쌍에 대한 변환 항을 지정하면:
(convert Inst Value def_inst)
(convert Value Reg put_in_reg)
typechecking 단계가 패턴과 재작성 표현 AST를 필요에 따라 확장할 수 있다. 이로써 로워링 규칙을 보일러플레이트 없이 더 자연스럽게 작성할 수 있고, 우리는 이를 위해 프렐류드에 상당히 풍부한 암시적 변환 집합을 정의해 두었다.
ISLE의 여러 기능을 둘러보았으니, 우리가 무엇을 만들었는지 정리해 보자. 우리는
(iadd (imul
x y) z)
와 (madd x y z) 같은 AST 노드의 동치를 나타내는 고수준 재작성 규칙을 표현하고, 이를 수행하는 시스템을 만들고자 했다. 또한 기존 컴파일러 인프라와 상호운용하고, 예측 가능하며 이해하기 쉬운 동작을 원했다.
ISLE은 고수준 패턴을 간단한 Rust 패턴 매칭 코드로 컴파일한다. 합 타입(enum)을 가진 강한 타입 시스템은 패턴과 재작성의 항들이 기대하는 스키마에 맞는지 보장하고, 고수준 불변식을 표현하도록 돕는다. 암시적 변환은 이 타입 정보를 활용해 패턴의 중복을 제거하고, 유용한 타입 구분을 유지하면서도 더 자연스러운 고수준 형태를 가능하게 한다. 그리고 패턴에서 사용할 “추출기”를 임의로 정의할 수 있기 때문에 프렐류드에서 풍부한 패턴 언어를 구축할 수 있다. 이는 연산자, 값, 입력 프로그램의 조각을 다양한 속성과 함께 프로그래머블하게 매칭한다. 마지막으로 Rust로의 명확한 매핑과, 항을 직접 함수 호출로 내리는 실행 체계(점진적으로 재작성되는 AST가 아니라)는 사람이 손으로 쓰는 만큼 효율적인 코드를 가능하게 한다.
그래서 우리는 (iadd (imul x y) z) => (madd x y z)에서 출발해 대략 다음으로 내려갔다:
Inst가 iadd enum 변형인지 매칭하고, 그렇다면 인자 Value를 얻는다.def_inst로 첫 번째 Value를 생산한 Inst를(병합이 허용된다면) 얻는다.Inst가 imul enum 변형인지 매칭하고, 그렇다면 인자 Value를 얻는다.Value 모두를 put_in_reg 호출로 레지스터에 둔다.madd 명령을 방출한다.이 모든 것을 ISLE 자체의 바인딩으로, 그리고 ISLE DSL 컴파일러가 “명령 로워링”이라는 개념을 전혀 몰라도 수행한다. 이 마지막 점이 가치 있다는 구체적 증거로, 우리는 새로운 프렐류드를 정의해(아래 참조) ISLE을 백엔드 로워링뿐 아니라 새로운 미드엔드 최적화 프레임워크에서 CLIF→CLIF 재작성 규칙에도 사용할 수 있었다!
로워링 규칙을 선언적으로 작성하는 것의 다음으로 흥미로운 점은, 규칙을 데이터로서 다룰 수 있어 다양한 분석을 하고 바람직한 속성을 만족하는지 검사할 수 있다는 것이다.
예를 들어 규칙 집합을 개발하는 동안, 어떤 규칙이 먼저 발화(fire)하는지 직관적이지 않은 경우가 있었다. 우리는 이를 임의로 제어할 수 있는 우선순위(priority) 메커니즘을 갖고 있지만, 기본 휴리스틱(대략 “더 구체적인 규칙이 먼저”)이 때때로 반직관적이었다.
그래서 우리는 overlap checker라는 아이디어를 만들었다. 초기 구현은 뛰어난 동료 Trevor Elliott가 했고, 이후 새 내부 표현과 알고리즘으로 재설계한 것은 다른 뛰어난 동료 Jamey Sharp였다. 핵심 아이디어는 두 규칙이 overlap한다는 것을 “어떤 입력이 패턴 매칭에 들어왔을 때 두 규칙 중 어느 쪽이든 발화할 수 있는” 경우로 정의하는 것이다. 이런 경우(그리고 이런 경우에만) 우선순위 및/또는 기본 정렬 휴리스틱이 실제로 어떤 규칙이 발화하는지 결정한다. 그리고 이런 경우에는 ISLE 작성자가 우선순위 메커니즘으로 두 규칙 중 하나를 명시적으로 선택하도록 _강제_하기로 했다. 즉 overlap하는 두 규칙은 같은 우선순위를 가질 수 없다. 기존 규칙들을 고치는 일련의 PR을 통해, 더 일반적인 규칙이 항상 먼저 발화해 어떤 규칙이 완전히 가려져(shadowed) 도달 불가능한 사례를 여러 개 실제로 찾을 수 있었다. 여러 사례를 수정한 뒤 같은 우선순위 규칙 간 비-overlap 강제와 더 높은 우선순위 규칙에 의한 비-shadowing 강제를 켰고, 그 결과 규칙 집합의 정합성에 더 자신감을 갖게 되었다.
더 큰 관점에서는 규칙을 한 AST에서 다른 AST로의 동치로 작성하면, 두 변환이 실제로 동치인지 검증할 수 있다. 현재 형식 검증 연구자들과의 협업이 진행 중인데, 외부 추출기/생성자에 그 의미를 기술하는 _주석(annotation)_을 추가하고 있다(대부분 SMT 솔버의 비트벡터 이론 프리미티브로 표현). 이런 “스펙(spec)”이 있으면 각 ISLE 규칙을 실행 가능한 Rust 코드가 아니라 SMT 절(clause)로 내리고, 그 규칙이 틀리는 경우를 탐색할 수 있다. 여기서 자세한 내용을 말하진 않겠다. 이 작업은 정말 흥미롭고(그리고 아직 진행 중) 연구자들이 적절한 시기에 발표할 것이다. 하지만 선언적 DSL이 무엇을 가능하게 하는지 보여주는 예다.
ISLE→Rust 컴파일러(메타컴파일러) 자체도 꽤 복잡한 도구이며 과거에 버그가 있었다. 규칙 자체가 검증되었다고 해도, 생성된 코드가 규칙을 올바르게 구현한다는 것을 무엇으로 확신할 수 있을까? 이를 위해 우리는 ISLE 규칙 번역을 검증하는 방법을 고려했다. 현재 계획은 ISLE 컴파일러를 수정해, 지능적으로 스케줄된 매칭 연산을 갖는 프로덕션 백엔드와, 우선순위 순으로 규칙을 순차적으로 훑는 “순진한(naive)” 버전을 둘 다 생성하도록 하는 것이다. 후자가 전자와 같은 규칙을 선택한다면, 좌변 매칭의 충실한 구현임을 알 수 있다(우변 표현을 생성자 호출로 번역하는 것은 비교적 직관적이므로 이미 신뢰하고 있다). 그러면 검증된 규칙이 작성한 대로 적용된다고 믿을 수 있다.
다음으로 동료 Jamey는 ISLE 규칙을 더 효율적인 매칭 연산 시퀀스로 내리는 새 ISLE 메타컴파일러 백엔드를 작업 중이다. IR 매칭 방식(즉 컴파일러 백엔드 코드가 IR을 매칭하는 방식을) DSL 기반 접근으로 바꿀 수 있다는 것은 ISLE의 장단점을 따질 때 이론적 이점으로 인식하고 평가했던 부분이지만, 솔직히 다소 추측적이었다. 초기 ISLE 컴파일러의 “트라이(trie)” 기반 접근보다 더 나은 코드 생성 전략을 실제로 찾을 수 있을지 아무도 확신하지 못했다. Jamey가 실제로 이를 해냈다는 점이 나는 매우 흥분된다(그리고 언젠가 그가 더 자세히 설명하는 블로그 글을 써주길 기대한다!).
마지막으로, 위에서 언급했듯이 우리는 egraph 기반 미드엔드 옵티마이저 작업의 일환으로 ISLE의 두 번째용도를 찾았고, 이를 최근 기본으로 활성화했다. (이것도 곧 블로그 글로 쓰고 싶다!) 이것은 ISLE이 단지 Cranelift 백엔드에만 국한되지 않고 더 일반적이라는 개인적 검증으로서 매우 만족스러웠다. 우리는 새 프렐류드를 작성했고(많은 추출기를 공유하기도 했다), 그 결과 규칙이 IR→머신 명령 로워링뿐 아니라 IR→IR 재작성을 기술할 수 있게 되었다. 이는 앞으로 컴파일러의 최적화 모음을 더 쉽게 반복·개선할 수 있게 해주고, 공유 인프라의 후속 이점도 있다. 백엔드 로워링 규칙을 위한 검증 도구는 미드엔드 규칙 검증에도 적용할 수 있다. 또한 컴파일러의 핵심 프로그램 변환 로직을 같은 DSL에 넣어두면, 단계 간 경계를 흐리거나, 단계를 결합하거나, 로직을 이동하는 등 오늘은 예측하지 못하는 방식으로 활용될 가능성도 있다. 어쨌든 가치 있는 투자처럼 보인다. 어떤 경우든 ISLE은 예전보다 보일러플레이트와 지루함이 적은 패턴 매칭 Rust 코드를 작성하는 데 꽤 유용한 도구임이 입증되었다!
ISLE은 설계하고 만들고 사용하는 과정이 매우 즐거웠다. 지난 1년 동안 많은 것을 배우며 몇 가지 언어 조정과 확장을 했지만, 전반적으로 백엔드를 다루기 더 쉬워졌다는 데 합의가 있다고 생각한다. 진행 중인 작업(검증, 새로운 ISLE 코드 생성 전략)이 어떻게 마무리될지, 그리고 언어가 전반적으로 어떻게 진화할지 기대된다. 그리고 위에서 말했듯 ISLE의 비밀은, 이것이 사실 명령 선택이나 Cranelift에 국한되지 않고 더 일반적이라는 점이다. 만약 다른 방식으로 이를 활용한다면, 꼭 듣고 싶다!
이 블로그 글 초안을 읽고 매우 유용한 피드백을 준 Jamey Sharp와 Nick Fitzgerald에게, 그리고 출판 후 피드백과 오타 수정을 준 bjorn3와 Adrian Sampson에게 감사한다.
A Aho, R Sethi, J Ullman, M S Lam. Compilers: Principles, Techniques, and Tools. 2006.↩
S Muchnick. Advanced Compiler Design and Implementation. 1997.↩
ISLE은 Rust enum에 대한 특별한 지식을 갖고 있으며, 생성된 Rust 코드에서 match 표현식으로 이를 효율적으로 매칭할 수 있다. 이 최적화를 놓치면 비용이 매우 크기 때문이다. 하지만 원칙적으로는 Rust 함수 호출과 그 주변의 제어 흐름만으로도 구현할 수 있었다.↩
여기에는 Prolog와의 유사성이 있다. Prolog 역시 백트래킹을 통한 고수준 선언적 규칙 매칭을 허용하면서, 명령형 세계로의 FFI를 갖춘 잘 정의된 순차 실행 의미를 갖는다. 사실 Prolog는 ISLE 설계의 중심 영감이었다. 주요 차이점은 (i) ISLE은 완전한 백트래킹이 없다(좌변이 매칭되면 되돌아갈 수 없다. 우변은 실패하지 않기 때문), (ii) 유니피케이션(unification)이 없고 항 내 데이터 흐름이 입력(분해 대상 값)에서 출력(인자)으로 단방향이라는 점이다. 예전에는 각 추출기 인자에 대해 고정된 입력/출력 방향을 설정하는 “argument polarity”가 있었는데, 이는 유니피케이션에 더 가까웠다. 그러나 우리는 이를 더 일반적인 if-let 절을 위해 폐기했다.↩