IR(중간 표현)을 단순화하는 최적화 패스를 구현하기 위해 발생(occurrence) 분석, 인라이닝, 재구성(rebuild)으로 구성된 종료 보장형 단순화 알고리즘을 설계하고 구현한다.
언어 만들기 시리즈
이 글은 언어 만들기 시리즈의 일부입니다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈입니다.
오늘 글은 base lowering pass에 이어집니다. 그 글에서 사용할 IR과 그에 딸린 데이터 타입들이 필요합니다. 아래에서 간단히 복습하겠습니다.
오늘은 컴파일의 마법 같은 측면인 최적화에 대해 이야기합니다. 최적화는 추상화를 벗겨 효율적인 머신 코드만 남길 수 있다는 점에서 마법 같고, 동시에 그 동작이 불가해하다는 점에서도 마법 같습니다. 최적화기는 흔히 수많은 노브가 달린 블랙박스로 알려져 있으며, 각 노브는 최종 결과를 향해 나비효과처럼 미세하게 영향을 미칩니다.
최적화의 궁극적 목표인 “코드의 런타임 성능 향상”은 이런 신비로운 성격의 큰 원인입니다. 코드의 런타임 성능은 정말, 정말 많은 요소에 의존합니다. 최적화는 가능한 한 많은 요소를 고려하려 하지만, 이는 결국 허사입니다. 성능은 종종 프로그램의 동적 입력에 달려 있는데, 이는 컴파일 시점에는 알 수 없습니다.
최적화가 모든 요소를 고려할 수 없으니, 가지고 있는 정보로부터 어떤 변화가 가장 좋은 결과를 낼지 추정해야 합니다. 당연히 완벽할 수 없는 과정입니다. 그렇다고 최적화가 가치 없다는 뜻은 아닙니다. 오히려 컴파일러가 존재하는 이유라고 해도 과언이 아닙니다. 다만, 이번 패스의 목표는 이전 패스들보다 덜 명확하다는 점을 말하고 싶습니다. 이전 패스들은 정확히 도달해야 하는 목적지가 있었고, 실패하면 에러였습니다. 하지만 최적화에서는 “최종 목적지에 도달했는지”를 판단하기가 훨씬 어렵습니다.
컴파일러는 다양한 종류의 최적화를 수행합니다. 오늘의 최적화는 lowering에서 얻은 IR(중간 표현) 위에서 수행되며, 새로운 최적화된 IR 항을 만들어냅니다. 저는 이 패스를 단순화(simplification)라고 부르겠습니다. 컴파일러가 수행하는 다른 최적화(명령어 특화 최적화, 메모리 레이아웃 최적화 등)와 구분하기 위해서입니다.
lowering에서 우리는 Ast를 IR로 바꿨습니다:
enum IR {
Var(Var),
Int(i32),
Fun(Var, Box<Self>),
App(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
TyApp(Box<Self>, Type),
Local(Var, Box<Self>, Box<Self>),
}
우리 IR은 명시적으로 타입이 있고, 제네릭은 타입 함수(type function)와 타입 적용(type application)으로 표현합니다. 또한 Local을 도입하는데, 이는 엄밀히 필수는 아니지만 단순화에서 매우 유용하다는 것을 보게 될 것입니다. 단순화는 IR만을 대상으로 동작하며(이후의 하류 패스들도 마찬가지), 이해하려면 IR에 익숙해지기만 하면 됩니다.
새 IR과 함께 AST 타입에서 lowering된 새로운 Type도 도입했습니다:
enum Type {
Int,
Var(TypeVar),
Fun(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
}
TyFun만이 AST 타입과 비교해 새로 추가된 것입니다. 이는 타입 함수의 타입입니다. 타입 함수는 타입 변수 대신 kind를 담습니다. 타입 변수는 DeBruijn 인덱스를 사용하므로, 각 변수는 자신을 바인딩하는 타입 함수를 가리키고, 그 함수 자체는 변수를 포함하지 않기 때문입니다.
변수 대신, 타입 함수는 자신이 바인딩하는 변수의 kind를 추적합니다. base에서 Kind는 하나뿐입니다:
enum Kind {
Type
}
kind는 타입 함수에 올바른 kind의 타입을 적용하는지 보장하는 데 도움이 됩니다. 타입이 함수에 올바른 값의 타입을 적용하는지 보장하는 것과 같은 역할입니다.
IR에 대해 필요한 것은 이것이 전부입니다. 다시 단순화로 돌아갑니다.
단순화는 IR을 살펴 최적화 기회를 찾는 패스입니다. 예를 들어, 어떤 함수가 인자에 바로 적용되는 것을 보면:
let x = Var { ... };
IR::app(IR::fun(x, IR::Var(x)), IR::Int(3))
이를 로컬로 최적화할 수 있습니다:
let x = Var { ... };
IR::local(x, IR::Int(3), IR::Var(x))
이는 성능상 이득입니다. 함수는 클로저를 할당해야 하는 반면, 로컬은 스택에 둘 수 있기 때문입니다.
그런데 실제로 이런 코드가 얼마나 자주 나타날까요? 우리 같은(당신과 저 같은) 고수라면 인자에 즉시 적용되는 함수를 직접 쓰지 않을 겁니다. 사람이 손으로는 이런 코드를 거의 쓰지 않지만, 단순화의 또 다른 측면인 인라이닝으로 인해 흔히 생겨납니다.
인라이닝은 변수를 그 정의로 대체합니다. 그 자체로는 작은 최적화일 수 있습니다. 변수를 없애면 잠재적 메모리 로드가 하나 줄어드니까요. 하지만 진짜 이점은 인라이닝이 추가 최적화를 열어주는 잠재력에 있습니다. Rust 코드로 이를 보겠습니다:
impl Option<T> {
fn is_none<T>(&self) -> bool {
match self {
Some(_) => false,
None => true
}
}
}
enum LinkedList<T> {
Cons(T, Box<LinkedList<T>>),
Nil
}
impl LinkedList<T> {
fn head(&self) -> Option<&T> {
match self {
Cons(x, _) -> Some(x),
Nil -> None
}
}
fn is_empty(&self) -> bool {
self.head()
.is_none()
}
}
is_empty의 정의는 읽기 좋습니다. 두 개의 고수준 연산을 조합해 기능을 표현합니다. 하지만 런타임에서는 두 번의 함수 호출과 두 번의 match를 수행합니다. 정의들을 인라인하면 함수 호출은 제거됩니다:
fn is_empty(&self) -> bool {
match (match self {
Cons(x, _) => Some(x),
Nil => None
}) {
Some(_) => false,
None => true,
}
}
좋아졌다고 하긴 어렵습니다. 호출은 없어졌지만 match는 두 번이고 읽기도 어렵습니다. 하지만 이제 컴파일러는 이전엔 함수 호출 뒤에 숨어 있던 최적화 기회를 볼 수 있습니다. Option<T>를 만들고 곧바로 검사하고 있기 때문입니다. 두 match를 모두 볼 수 있게 됐으니 컴파일러는 이를 제거할 수 있습니다:
fn is_empty(&self) -> bool {
match self {
Cons(x, _) => false,
Nil => true,
}
}
처음이나 중간 단계보다 훨씬 낫습니다. 인라이닝은 이런 황금 같은 최적화를 코드에서 캐내는 곡괭이입니다. 프로그래머가 직접 인자를 즉시 함수에 적용하진 않더라도, 인라이닝은 그런 경우를 자주 드러냅니다. 특히 작은 함수를 많이 조합하는 것이 기본인 함수형 언어에서는 더욱 그렇습니다.
이제 왜 단순화하는지 감이 왔습니다. 이제는 어떻게 단순화하는지 이야기할 차례입니다. 단순화는 근본적으로 휴리스틱(heuristic)에 기반한 작업임을 이해하는 것이 중요합니다. 컴파일러 프런트엔드 패스(타입체킹 등)와 달리, 단순화는 반드시 해야 하는 일이 아닙니다. 완전히 유효한 구현은 이런 것도 가능합니다:
fn simplify(ir: IR) -> IR {
ir
}
물론 유효하지만 제 마음은 슬픕니다. 그리고 이 코드는 문제도 드러냅니다. “언제 단순화가 끝났는지”는 어떻게 알죠?
순진하게는, 항(term)이 더 이상 변하지 않을 때까지, 즉 고정점(fixed point)에 도달할 때까지 단순화를 반복할 수 있습니다. 우리의 단순한 언어에선 이것으로도 충분합니다. 하지만 재귀를 추가하면, 고정 상태에 결코 도달하지 않는 항을 만들 수 있고, 심지어 만들기 쉽습니다.
언젠가 재귀를 지원할 꿈을 갖고, 우리는 고정점에 도달하지 않더라도 종료하는 단순화기를 설계할 것입니다. 불행히도 이는 어떤 항들은 최대로 최적화하지 못할 수 있음을 의미합니다. 진행 중인 항과 끝없이 제자리만 도는 항을 구별할 수 없으므로, 어딘가에 선을 그어야 합니다.
이 목표는 단순화기를 긴장 상태에 둡니다:
대부분의 컴퓨터 프로그램이 공유하는 용감한 목표입니다. 또한 IR의 성능을 개선하고 싶습니다. 그 과정에 인라이닝이 일부 포함되지만, 모든 것을 무작정 인라인할 수는 없습니다.
인라이닝의 단점은 변수의 장점에서 발견됩니다. 변수는 공유(sharing)를 나타냅니다. 같은 일을 여러 곳에서 반복하기보다, 변수를 통해 저장해 재사용합니다. 따라서 인라이닝은 그 공유를 줄이는 셈입니다. 무분별한 인라이닝은 작업을 중복시켜, 드러난 최적화 이득을 압도할 수 있습니다.
인라이닝이 가치 있는지를 결정하기 위한 휴리스틱이 필요합니다. 하지만 휴리스틱의 본성상, 서로 다른 인라이닝 선택은 프로그램에 따라 더 좋거나 나쁠 수 있습니다. 모든 입력을 완벽히 처리하는 하나의 알고리즘을 만들 수는 없습니다. 트레이드오프를 해야 합니다.
단순화의 내재적 트레이드오프 때문에, 알고리즘은 튜닝 가능해야 합니다. 사용자가 컴파일하는 코드에 맞게 최적화를 최대한 잘 조정할 수 있어야 하니까요. 가장 넓은 프로그램 집합에서 잘 동작하도록 단순화기를 튜닝하는 것은 컴파일러에서 계속되는 과제입니다. 우리는 몇 가지 조정 노브를 도입하겠지만, 실제 컴파일러를 보면 최적화 튜닝을 위한 노브가 수십, 수백 개에 달하기도 합니다.
튜닝과 함께, 알고리즘이 무한 루프에 빠지지 않도록 구성하는 것도 주의해야 합니다. 이를 위해 단순화를 3개 구성요소로 나눕니다:
첫 단계인 발생 분석은 IR을 순회하며 각 변수가 얼마나 자주 나타나는지 결정합니다. simplify는 이 발생 정보를 받아 항을 따라 내려가며 인라이닝 결정을 내립니다. IR 트리의 잎(leaf)에 도달하면 rebuild를 호출해 단순화된 항을 다시 위로 조립하기 시작합니다.
rebuild는 단순화된 항을 아래에서 위로 재조립하며 최적화 기회를 찾습니다. 함수가 인자에 적용된 것을 찾아 로컬로 바꾸는 일은 simplify가 아니라 rebuild에서 합니다. 또한 IR의 다른 서브트리에 대해 simplify를 호출하는 책임도 rebuild에 있습니다. simplify는 rebuild를 호출하기 전까지 IR 트리의 단 하나의 경로만을 따라 내려갑니다.
종료를 보장하기 위해 rebuild에서 느슨한 불변조건을 유지합니다: rebuild는 각 서브트리마다 simplify를 한 번만 호출합니다. App 노드의 함수 부분을 한 번 단순화했다면, (같은 패스 내에서) 다시는 그 부분에 simplify를 호출하지 않습니다. 결국 IR 전체를 단순화하고 재구성하면 종료합니다. 아래 다이어그램은 단순화기가 어떻게 구조화되는지 높은 수준에서 보여줍니다:
이 구조가 제가 열병 속에서 단순화를 미친 듯이 해킹하다 떠올린 건 아니고(아쉽게도 제 체온은 정상입니다), 사실 함수형 프로그래밍의 거인 두 언어, Haskell과 OCaml에서 가져온 것입니다. 단순화기를 구성할 때 두 자료를 참고했습니다:
둘 다 접근하기 쉽고 훌륭한 자료로 강력 추천합니다. 우리는 언어의 특수성에 맞게 몇 가지 주의점을 두고, 이들에서 아이디어를 많이 빌립니다. 우리의 base 언어는:
이 특성 조합은 단순화에 꽤 유리합니다(물론 실용적인 언어로서는 이상적이지 않지만요). 부작용이 없으니 식을 재정렬할 자유가 있고, 참조되지 않는 로컬 변수는 언제든 삭제할 수 있습니다. 엄격 평가이므로 단순화가 실수로 lazy 코드를 eager로 만들어버리는 걱정도 없습니다. Secrets of the GHC Inliner의 상당 부분은 laziness 처리에 할애되는데, 그 부담이 없으니 복잡도가 줄어듭니다.
이 요인들 때문에 여기서 제시하는 단순화기는… 더 단순합니다. 하지만 핵심 아키텍처는 선배들의 것과 동일합니다. 동등한 수준이 되려면 아키텍처의 근본 변화가 아니라 기능을 추가하면 됩니다. 또한 앞으로 추가할 기능들이 요구하는 복잡도 없이 기반을 더 직접적으로 볼 수 있습니다.
이제 첫 단계인 발생 분석 구현을 이야기할 수 있습니다. 목표는 항을 분석해 변수가 얼마나 자주 발생하는지 결정하는 것입니다. 이 정보는 인라이닝에 사용됩니다. 변수는 몇 가지 방식으로 발생할 수 있습니다:
enum Occurrence {
/// 변수는 전혀 발생하지 않음
Dead,
/// 변수가 한 번 등장함.
Once,
/// 변수가 Fun 노드 내부에서 한 번 등장함.
OnceInFun,
/// 변수가 여러 번 등장함.
Many
}
Dead, Once, Many는 단순히 발생 횟수(0, 1, 2회 이상)입니다. OnceInFun은 변수가 함수 본문 안에서 한 번 발생하는 경우를 나타냅니다. 함수 본문 안에서 변수가 캡처되면 작업 중복을 걱정해야 합니다. 예를 들어:
let x = fib(100);
|y| x + y
여기서 x를 인라인하면 fib(100)을 한 번만 계산하던 것이 함수 호출마다 계산되게 됩니다. OnceInFun은 중복 작업에 주의하라고 알려줍니다. Many(또는 Dead)에는 따로 이 표시가 필요 없습니다. 이미 어디에 있든 중복을 고려해야 하기 때문입니다. 이 문제는 “조건 없이 인라인되는” Once 변수에만 해당합니다(함수 밖에서 발견되면 항상 인라인되므로).
이 정보는 Occurrences에 저장합니다:
struct Occurrences {
vars: HashMap<VarId, Occurrence>,
}
occurrence_analysis가 이를 계산해 줍니다:
fn occurrence_analysis(ir: &IR) -> (HashSet<VarId>, Occurrences) {
match ir {
// ...
}
}
occurrence_analysis는 ir의 자유 변수 집합과 발생 정보를 반환합니다. 분석 이후 자유 변수 집합 자체는 필요 없지만, 발생을 결정하는 과정에서 사용합니다. 첫 케이스는 Var입니다:
IR::Var(var) => {
let mut free = HashSet::default();
free.insert(var.id);
(free, Occurrences::with_var_once(var.id))
}
변수는 자유 변수이며 한 번 발생합니다. 쉬운 케이스죠. Int도 쉽습니다:
IR::Int(_) => (HashSet::default(), Occurrences::default()),
정수는 변수 발생이 없고 자유 변수도 없습니다. Fun부터 난이도가 올라갑니다:
IR::Fun(var, ir) => {
let (mut free, occs) =
occurrence_analysis(ir);
free.remove(&var.id);
let occs = occs.in_fun(&free);
(free, occs)
}
Fun은 먼저 본문을 분석합니다. 함수는 변수를 바인딩하므로 자유 변수 집합을 갱신합니다. 갱신된 자유 변수 집합을 이용해 in_fun으로 함수 내부 발생을 표시합니다:
impl Occurrences {
fn in_fun(self, free: &HashSet<VarId>) -> Self {
Self {
vars:
self.vars
.into_iter()
.map(|(id, occ)| {
( id
, match occ {
Occurrence::Once
if free.contains(&id)
=> Occurrence::OnceInFun,
occ => occ,
})
})
.collect()
}
}
}
in_fun은 적절한 경우 Once를 OnceInFun으로 바꿉니다. Fun이 캡처하는 자유 변수만 OnceInFun으로 표시합니다. 바운드 변수는 작업 중복 가능성이 없으므로 그대로 둡니다. 바운드 변수는 함수가 적용될 때마다 어차피 다시 평가되므로, 인라인 여부와 무관하게 작업이 중복됩니다.
다시 occurrence_analysis로 돌아와 App를 처리합니다:
IR::App(fun, arg) => {
let (mut fun_free, fun_occs) =
occurrence_analysis(fun);
let (arg_free, arg_occs) =
occurrence_analysis(arg);
fun_free.extend(arg_free);
(fun_free, fun_occs.merge(arg_occs))
}
App은 fun과 arg의 Occurrences를 얻어 합칩니다. merge는 두 Occurrences를 합치며 변수 발생을 갱신합니다:
impl Occurrences {
fn merge(mut self, other: Self) -> Self {
for (var, occ) in other.vars {
self
.vars
.entry(var)
.and_modify(|self_occ| {
self_occ = match (*self_occ, occ) {
// ...
};
})
.or_insert(occ);
}
self
}
}
other.vars의 각 변수에 대해 self.vars에 삽입을 시도합니다:
매치의 한쪽이 Dead이면 다른 쪽을 취합니다.
(Occurrence::Dead, occ) | (occ, Occurrence::Dead) => occ,
0 + x(및 x + 0)가 x인 것과 같습니다. 마찬가지로 한쪽이 Many면 결과는 Many입니다:
(Occurrence::Many, _) | (_, Occurrence::Many) => Occurrence::Many,
두 Once가 만나면 실제로 갱신됩니다:
(Occurrence::Once, Occurrence::Once) => Occurrence::Many,
merge는 서로 다른 IR 부분항에서 나온 발생을 합칩니다. 같은 변수가 두 부분항에서 각각 한 번씩 나타나면 전체로는 두 번이므로 Many입니다. 나머지는 한 가지 분기로 Many로 처리할 수 있습니다:
(Occurrence::Once, _) | (Occurrence::OnceInFun, _) => Occurrence::Many,
기술적으로는 (Occurrence::Once, Occurrence::Once)도 여기 포함되지만, 그 케이스를 명확히 강조하고 싶었습니다. 이것으로 모든 케이스를 다뤘습니다. 다시 occurrence_analysis로 돌아가 TyFun과 TyApp는 한 번에 처리합니다:
IR::TyFun(_, ir) => occurrence_analysis(ir),
IR::TyApp(ir, _) => occurrence_analysis(ir),
타입 함수는 함수와 달리 런타임에 나타나지 않으므로 발생에 영향을 주지 않습니다. 마지막으로 Local입니다:
IR::Local(var, defn, body) => {
let (mut free, occs) =
occurrence_analysis(body);
let (defn_free, defn_occs) =
occurrence_analysis(defn);
free.extend(defn_free);
free.remove(&var.id);
(free, defn_occs.merge(occs))
}
정의와 본문의 발생을 합쳐 Local의 발생을 구합니다. 이렇게 해서 발생 계산이 끝났습니다.
occurrence_analysis 출력으로, 단순화 상태를 담는 Simplifier를 만듭니다.
struct Simplifier {
occs: Occurrences,
subst: Subst,
saturated_fun_count: usize,
saturated_ty_fun_count: usize,
locals_inlined: usize,
inline_size_threshold: usize,
}
Simplifier는 IR 항을 단순화하기 위한 모든 상태를 유지합니다. 다음 카운터로 이번 패스에서 얼마나 단순화를 수행했는지 추적합니다:
saturated_fun_count - 인자 적용된 함수를 줄인(축약한) 횟수.satured_ty_fun_count - 타입 인자를 적용한 타입 함수를 줄인 횟수.
locals_inlined - 인라인된 로컬 수. 이 값들은 이번 패스에서 일이 있었는지 판별하는 데 사용됩니다.inline_size_threshold - 어떤 항을 인라인할지 결정하는 데 도움을 주는 설정 값입니다.subst는 Subst 타입의 치환(substitution)입니다. 어떤 변수를 인라인할지, 무엇으로 인라인할지 추적합니다. 어떤 바인딩을 만났을 때 인라인할 가치가 있다고 판단하면 변수에서 정의로 매핑합니다. 더 이상 인라인하지 않으려면 치환에서 제거합니다. HashMap처럼 들린다면, 맞습니다. Subst는 HashMap입니다:
type Subst = HashMap<VarId, SubstRng>;
여기서 SubstRng는 두 케이스 중 하나입니다:
enum SubstRng {
Suspend(IR, Subst),
Done(IR),
}
Done은 이미 최적화된 IR 항입니다. 이를 인라인할 때는 simplify를 다시 호출하지 않아야 합니다. 사실 다시 단순화하면 지수적 실행 시간을 유발할 수 있습니다. 이는 두 번 이상 발생하는 변수(Many 및 OnceInFun 포함)에 해당합니다.
Suspend는 아직 최적화되지 않은 IR 항입니다. 이를 인라인할 때는 그 항을 최적화하기 위해 simplify도 호출합니다. Once 변수만 suspend되므로, 동일한 항을 여러 번 단순화하는 문제는 걱정할 필요가 없습니다.
그렇다면 Once 변수도 정의 시점에서 미리 단순화하고 Done만 쓰면 안 되나요? 가능하지만, 변수가 놓인 주변 문맥을 이용해 더 최적화할 수 있는 기회를 놓칩니다. 예를 들어:
let x = |y| 1 + y;
x(10)
정의를 미리 단순화하면 |y| 1 + y가 되어 원래와 성능 차이가 거의 없습니다. 단순화를 지연하면 인라인되어 (|y| 1 + y)(10)가 되고, 이는 11로 단순화됩니다. 꽤 매력적이죠. 그렇다면 왜 Suspend만 쓰지 않느냐는 질문이 남습니다.
시간이 충분하다면, 인라이닝 이후까지 모든 단순화를 지연하고 싶을 수도 있습니다. 하지만 Many 변수를 지연하면 지수적 실행 시간이 생깁니다. 같은 IR을 항의 크기당 한 번이 아니라, 발생 횟수만큼 단순화하게 되기 때문입니다. 결국 런타임 폭발이 없다고 확신할 수 있는 Once 변수에 한해서만 지연을 허용해야 합니다.
Simplifier는 공개 API로서 단 하나의 메서드 simplify를 제공합니다:
impl Simplifier {
fn simplify(
&mut self,
mut ir: IR,
in_scope: InScope,
mut ctx: Context
) -> IR {
todo!()
}
}
구현에 들어가기 전에 새로 도입되는 데이터 타입들을 설명해야 합니다. IR은 lowering에서 봤고, InScope는 지금 고려 중인 ir 항에 대해 스코프 안(in-scope)에 있는 변수 집합을 추적합니다:
type InScope = HashMap<VarId, Definition>;
InScope는 Subst와 비슷해 보입니다. VarId에서 어떤 enum으로 가는 HashMap이며(곧 Definition이 두 케이스의 enum임을 보게 됩니다), 하지만 둘은 미묘하게 다른 역할을 합니다. Definition은 각 스코프 내 변수에 대해 “알려진 항에 바인딩됐는지” 또는 “알 수 없는 파라미터인지”를 알려줍니다:
enum Definition {
Unknown,
BoundTo(IR, Occurrence),
}
함수 파라미터는 unknown입니다. 로컬 변수는 알려진 IR 항에 바인딩됩니다. Subst는 인라인하려는 변수만 담지만, InScope는 인라이닝 여부와 상관없이 모든 변수를 담습니다.
마지막 데이터 타입 Context는 현재 항 ir의 주변 문맥을 추적합니다. 단순화 과정에서 ir 안으로 내려가는데, Context는 우리가 내려온 경로를 추적해 최종 항을 재구성할 수 있게 합니다. 예를 들어 이런 IR이 있다면:
IR::Local(
Var(...), <defn>,
IR::App(
IR::TyApp(
<ir>,
<ty>),
<arg>)
)
우리는 내려가서 결국 <ir>에 도달할 것입니다. 그때의 context는 내려온 경로가 됩니다:
vec![IR::Local(Var(...), <defn>, _), IR::App(_, <arg>), IR::TyApp(_, <ty>)]
_는 나중에 IR을 끼워 넣을 수 있는 구멍(hole)입니다. TyFun 최적화를 마치면 context를 따라가며 최종 IR을 재구성합니다.
왜 context를 굳이 파라미터로 추적하나요? 재귀로도 이 정보를 추적할 수 있습니다. 예를 들어 재귀적 simplify 구현을 상상해 봅시다:
// imagine we're in simplify().
match ir {
IR::App(fun, arg) => {
let fun = self.simplify(fun, ...);
let arg = self.simplify(arg, ...);
IR::app(fun, arg)
}
// ...
}
이는 여러 번 잘 써온 패턴입니다. 하지만 context를 쓰는 방식은 더 복잡한 대신 중요한 것을 얻습니다. fun으로 내려갈 때, context는 그것이 App으로 둘러싸여 있다는 사실을 기억합니다. 이 정보를 이용해 더 나은 인라이닝 결정을 내릴 수 있습니다.
구체적으로 Context는 벡터입니다:
type Context = Vec<(ContextEntry, Subst)>;
벡터를 스택처럼 써서 끝에서 push/pop 합니다. ContextEntry는 구멍이 있는 IR입니다:
enum ContextEntry {
App(IR),
TyApp(Type),
TyFun(Kind),
Local(Var, Occurrence, IR),
}
ContextEntry::App(arg)를 보면, 어떤 ir과 결합해 IR::App(ir, arg)를 재구성할 수 있습니다. Context는 각 엔트리마다 저장된 Subst도 갖는데, rebuild에서 항을 재구성할 때 복원합니다. rebuild가 simplify를 호출할 때 올바른 치환 아래에서 호출하고 싶기 때문에, context에 저장된 subst를 복원하면 올바른 것을 쓰게 됩니다.
이제 simplify 구현을 시작할 만큼 설명이 됐습니다:
fn simplify(
&mut self,
mut ir: IR,
in_scope: InScope,
mut ctx: Context
) -> IR {
loop {
ir = match ir {
// ...
}
}
}
simplify는 트리 순회이며 본질적으로 재귀 알고리즘입니다. 하지만 여기서는 반복(iterative) 알고리즘으로 작성했습니다. 이는 취향의 문제입니다. Rust는 변경(mutation)을 지원하므로, 저는 변경을 활용한 반복 형태가 더 표현하기 쉬웠습니다. Haskell로 쓴다면 재귀가 더 매력적일 수 있습니다.
각 반복에서 ir을 매칭하고, 매치 결과를 새 ir로 돌려줍니다. 처음 두 케이스는 단순합니다:
IR::App(fun, arg) => {
ctx.push(
( ContextEntry::App(*arg)
, self.subst.clone()
));
*fun
}
IR::TyApp(ty_fun, ty_app) => {
ctx.push(
( ContextEntry::TyApp(ty_app)
, self.subst.clone()
));
*ty_fun
}
App이나 TyApp를 만나면, 아직 아무 것도 하지 않습니다. 나중을 위해 context에 쌓아두고 각각 fun 또는 ty_fun으로 내려갑니다. 타입 함수도 같은 방식입니다:
IR::TyFun(kind, body) => {
ctx.push(
( ContextEntry::TyFun(kind)
, self.subst.clone()
));
body
}
그 다음은 첫 번째 종단(terminal) 케이스 Int입니다:
IR::Int(i) =>
break self.rebuild(IR::Int(i), in_scope, ctx),
정수는 최적화할 것도, 더 내려갈 서브항도 없습니다. 이제 rebuild를 시작할 시간입니다. rebuild가 IR의 나머지 부분에 대해 simplify를 호출할 책임이 있으므로, 이 simplify 호출은 여기서 끝입니다. 루프를 break하고 rebuild된 IR을 반환합니다. 다음은 함수입니다:
IR::Fun(var, body) => {
let body =
self.simplify(*body, in_scope.update(var.id, Definition::Unknown), vec![]);
break self.rebuild(IR::fun(var, body), in_scope, ctx);
}
여기서 이렇게 쓰지 않은 것이 놀랍게 보일 수 있습니다:
IR::Fun(var, body) => {
ctx.push(
( ContextEntry::Fun(var)
, self.subst.clone()
));
*body
}
이는 더 단순해 보이지만, 우리의 코드는 추가 재귀 호출과 break를 통해 사실상 같은 일을 합니다. 이 추가 재귀 호출이 필요한 이유는 함수 파라미터를 in_scope에 업데이트해야 하기 때문입니다. 파라미터이므로 Unknown 정의로 넣습니다.
지금까지는 내려가고 재구성했는데, 그 목적은 무엇일까요. Local에서 진짜 작업이 시작됩니다:
IR::Local(var, defn, body) =>
self.simplify_local(
var,
*defn,
*body,
&mut ctx),
에헴, simplify_local 안에서야말로 진짜 작업이 시작됩니다:
fn simplify_local(
&mut self,
var: Var,
defn: IR,
body: IR,
ctx: &mut Context
) -> IR {
match self.occs.lookup_var(&var) {
// ...
}
}
바인딩의 운명은 정의된 var의 발생 정보로 결정됩니다. 먼저 Dead 변수:
Occurrence::Dead => {
self.locals_inlined += 1;
body
}
쉽습니다. 변수가 참조되지 않으니 바인딩을 버리고 body를 바로 반환합니다. 부작용이 없으므로 죽은 바인딩은 자유롭게 버릴 수 있습니다. 부작용이 있는 언어라면 더 조심해야 합니다.
Once 케이스도 Dead와 비슷합니다:
Occurrence::Once => {
self.locals_inlined += 1;
let subst = self.subst.clone();
self.subst.insert(var.id, SubstRng::Suspend(defn, subst));
body
}
다만 body를 반환하기 전 subst를 수정합니다. 업데이트된 subst는 다음 루프에서 body가 분석될 때 적용되므로, 지금은 여기서 끝입니다. 어차피 이 변수의 유일한 발생을 인라인할 것이고 그렇게 되면 변수가 dead가 되므로, 지금 바인딩을 버려 약간의 일을 절약합니다.
한 번만 발생하는 변수는 항상 인라인해도 이득입니다(혹은 최악에도 해가 없습니다). 역시 부작용이 없기 때문에 가능한 결론입니다. 부작용이 있다면 식 재정렬이 효과 순서를 바꿀 수 있어 조심해야 합니다. 마지막 케이스는 나머지 발생을 처리합니다:
occ => {
ctx.push(
( ContextEntry::Local(var, occ, body)
, self.subst.clone()
));
defn
}
Once와 Dead가 아닌 발생이라면 let 바인딩을 유지합니다. 바인딩이 계속 존재할 것이므로 정의를 단순화해야 합니다. 이를 위해 var와 body를 context에 저장하여 나중에 let을 재구성할 수 있게 하고, defn을 다음에 단순화할 항으로 반환합니다. 또한 편의를 위해 occ도 context에 저장합니다. 바인딩을 재구성할 때 다시 lookup하는 수고를 덜어줍니다.
로컬 단순화는 여기까지입니다. 다시 simplify로 돌아와 마지막 케이스인 변수입니다.
IR::Var(var) =>
match self.simplify_var(
var,
in_scope.clone(),
&ctx)
{
ControlFlow::Continue(ir) =>
ir,
ControlFlow::Break(var) =>
break self.rebuild(IR::Var(var), in_scope, ctx),
},
변수 케이스는 표준 라이브러리의 덜 알려졌지만 유용한 타입인 ControlFlow를 사용합니다. 보이듯이 Continue 또는 Break 둘 중 하나입니다. 이를 통해 변수 로직을 simplify_var 헬퍼로 캡슐화하면서도, 필요하면 simplify 루프를 break할 수 있습니다.
simplify_var는 변수를 치환에서 찾아 어떻게 처리할지 결정합니다:
fn simplify_var(
&mut self,
var: Var,
in_scope: InScope,
ctx: &Context
) -> ControlFlow<Var, IR> {
match self.subst.remove(&var.id) {
Some(SubstRng::Suspend(payload, subst)) => {
self.subst = subst;
ControlFlow::Continue(payload)
}
Some(SubstRng::Done(payload)) => {
self.subst = Subst::default();
ControlFlow::Continue(payload)
}
None => self.callsite_inline(var, in_scope, ctx),
}
}
첫 케이스는 simplify_local에서 설정한 것입니다. Once 변수는 suspend된 IR로 치환에 추가됩니다. 여기서는 그 suspend된 IR을 재개(resume)하고, 복원된 치환으로 계속 단순화합니다.
둘째 케이스는 여러 번 나타나는 변수를 인라인하려는 경우입니다. 정의가 충분히 사소(trivial)하여 여러 곳(또는 함수 내부에서 작업 중복 위험이 있는 곳)에서도 인라인하는 편이 이득일 때 이런 결정을 합니다. let 바인딩을 rebuild할 때 “사소함”을 어떻게 판단하는지 보게 됩니다. Done 변수를 인라인할 때 치환을 비우는 점에 주목하세요. 이는 완료된 정의를 더 이상 단순화하지 않도록 보장합니다.
변수가 치환에 없다면 callsite_inline로 넘어갑니다:
fn callsite_inline(
var: Var,
in_scope: InScope,
ctx: &Context,
) -> ControlFlow<Var, IR> {
todo!()
}
simplify_var의 앞 두 케이스는 정의를 보고 인라인 가치가 있다고 판단한 상황이었습니다. 하지만 정의만으로 판단하지 못하더라도, 항 안에서 변수가 나타나는 “위치”를 보고 인라인이 가치 있을 수 있습니다. callsite_inline이 이를 수행합니다.
결국 단순화는 실행 없이 정적 분석만으로 미래를 예측하는 데 한계가 있습니다. 여기서 그 경계에 도달하며, 이전보다 더 임의적인 결정을 할 수밖에 없습니다. callsite_inline은 먼저 스코프 내에서 변수의 정의를 봅니다:
in_scope
.get(&var.id)
.map(|bind| match bind {
Definition::BoundTo(definition, occ)
if self.should_inline(definition, *occ, &in_scope, ctx)
=> {
todo!()
}
_ => ControlFlow::Break(var),
})
.expect("ICE: Unbound variable encountered in simplification")
스코프 내 변수가 정의되어 있고 should_inline이 인라인 가치가 있다고 판단할 때만 진행합니다. 인라인하기로 하면 정의를 반환합니다:
self.subst = Subst::default();
if let Occurrence::OnceInFun = occ {
self.occs.mark_dead(&var.id);
}
ControlFlow::Continue(definition.clone())
여기엔 특수 케이스가 있습니다. OnceInFun 변수를 인라인하기로 했다면, 그 변수는 함수 안에서 한 번만 발생합니다. 이제 인라인했으니 참조가 0이 됩니다. 그 경우 곧바로 변수를 dead로 표시합니다.
여기서 dead로 표시하면, rebuild에서 다시 바인딩을 청소하기 위해 또 한 번 단순화를 돌리지 않고도 이제 죽은 바인딩을 버릴 수 있습니다. 이런 식으로 발생 정보를 라이브 업데이트하는 일은 꽤 복잡합니다. Secrets of the GHC Inline은 여러 변형을 시도했지만 모두 너무 복잡하고 버그가 많아 가치가 없었다고 말합니다. 저는 그들의 경험을 제 것보다 믿고 배우겠습니다. 다만 이 케이스는 실제로도 자주 나타나고 구현도 단순하므로 할 만합니다.
그런데 언제 인라인해야 할까요? 답은 should_inline에 있습니다:
fn should_inline(
&self,
ir: &IR,
occ: Occurrence,
ctx: &Context
) -> bool {
match occ {
//...
}
}
should_inline는 변수 발생에 따라 결정을 내립니다. 처음 두 케이스는 놀랍습니다:
Occurrence::Dead | Occurrence::Once =>
panic!("ICE: should_inline encountered unexpected dead or once occurrence. This should've been handled prior"),
Once와 Dead는 simplify_var에서 처리했습니다. should_inline에서 보이면 로직 에러입니다. 누군가 컴파일러를 고쳐야 합니다. OnceInFun에서 실제 의사결정이 시작됩니다:
Occurrence::OnceInFun =>
ir.is_value()
&& self.some_benefit(ir, ctx),
정의가 값(value)이고 인라인에 어떤 이득이 있을 때만 인라인합니다. “이득이 있을 때 인라인한다”는 말은 그럴듯하지만, 사실상 문제를 뒤로 미룬 느낌이죠. 그 전에 “IR이 값이다”가 무슨 뜻인지부터 봅시다.
우리의 단순 언어에서 작업(work)은 App뿐입니다. IR에 App가 포함되면 값이 아니고, 그렇지 않으면 값입니다. 단, Fun은 본문에 App가 있어도 값으로 취급합니다. 함수 본문은 함수가 적용되기 전에는 실행되지 않기 때문입니다. is_value는 재귀 매치를 통해 적용을 찾습니다:
impl IR {
fn is_value(&self) -> bool {
match self {
IR::Var(_)
| IR::Int(_)
| IR::Fun(_, _) => true,
IR::TyFun(_, ir) =>
ir.is_value(),
IR::TyApp(ir, _) =>
ir.is_value(),
IR::Local(_, defn, body) =>
defn.is_value()
&& body.is_value(),
IR::App(_, _) => false,
}
}
}
이제 some_benefit를 보겠습니다:
fn some_benefit(
&self,
ir: &IR,
ctx: &Context
) -> bool {
todo!()
}
some_benefit는 context를 활용해 인라이닝이 새로운 최적화 기회를 여는지 판단합니다. 우리 언어에서는 “함수에 인자를 적용하는 문맥”을 찾는 것입니다. 먼저 ir이 몇 개의 파라미터를 가지는지 구합니다:
let (params, _) = ir.clone().split_funs();
split_funs는 연쇄된 Fun 노드들의 파라미터를 모으고, 함수 본문과 함께 반환하는 헬퍼입니다. 예를 들어 IR::App(IR::Fun(...), IR::Int(3))처럼 최상위에 Fun이 없으면, ir 자체와 빈 params를 반환합니다. 파라미터를 구했으면, 이제 context에서 인자들을 준비합니다:
let args = ctx
.iter()
.rev()
.map_while(|entry| match entry {
(ContextEntry::App(arg), _) => Some(Arg::Val(arg)),
(ContextEntry::TyApp(ty), _) => Some(Arg::Ty(ty)),
_ => None,
})
.collect::<Vec<_>>();
스택인 context를 역순으로 순회하며 연속된 인자들을 모두 모읍니다. 인자들이 연속되어야 하는 것이 중요합니다. TyFun이나 Local 엔트리를 만나면, 그 이후의 인자들은 현재 검사 중인 변수에 적용되는 것이 아니기 때문입니다.
첫 번째 이득 체크는 현재 함수를 포화(saturate)시키기에 충분한 인자가 있는지입니다. 길이 비교로 간단합니다:
if args.len() >= params.len() {
return true;
}
이 체크는 두 가지를 동시에 합니다:
모든 파라미터가 포화되면 함수를 제거할 수 있습니다. 함수는 할당을 필요로 하는데(코드 생성 단계에서 그 이유를 배우게 됩니다), 함수를 제거하면 할당이 줄어 성능상 이득입니다. 또한 모든 호출 지점이 함수를 포화한다면, 전부 인라인해 변수 바인딩 자체를 없앨 수도 있습니다.
파라미터 수보다 많은 인자를 적용한다는 것은, 함수가 작업을 한 뒤 추가 함수를 반환한다는 뜻입니다. 이 경우 인라이닝은 그 추가 함수를 “여분 인자”에 노출시키고 싶어합니다. 예를 들어:
let x = |y| {
let a = (y * 10) / 2;
|b| a * b
};
x(10)(2)
Rust 문법이라 관용적이진 않지만, x를 인라인하면 |b| a * b가 인자 2를 직접 받게 되어 이득이 있음을 알 수 있습니다:
(|b| 50 * b)(2)
인자가 충분치 않더라도, 인자 중 하나가 흥미롭다면 인라인할 가치가 있을 수 있습니다.
args
.iter()
.take(params.len())
.any(|arg| match arg {
Arg::Val(arg) => {
!arg.is_trivial()
|| match arg {
IR::Var(var) =>
matches!(in_scope.get(&var.id),
Some(Definition::BoundTo(_, _))),
_ => false,
}
}
Arg::Ty(_) => false,
})
인자가 흥미롭다고 보는 조건:
이유는 늘 그렇듯, 이것들이 미래의 최적화 기회를 열 가능성이 크기 때문입니다. 비사소 인자를 이해하려면 먼저 사소(trivial) 인자가 무엇인지 봐야 합니다. IR이 변수나 정수면 trivial입니다:
impl IR {
fn is_trivial(&self) -> bool {
matches!(self, IR::Var(_) | IR::Int(_))
}
}
trivial 인자는 대체로 추가 최적화를 열지 못합니다. 정수 리터럴보다 더 최적화하기는 어렵습니다. 그래서 비사소 IR을 더 흥미롭게 봅니다. 또한 변수가 알려진 정의를 가진다면, 그 변수를 인라인하는 것이 최적화를 열 수 있으므로 흥미롭게 취급합니다. 이것으로 some_benefit가 마무리됩니다. 다시 simplify_var로 돌아가 마지막 케이스를 보겠습니다:
Occurrence::Many => {
let small_enough =
ir.size() <= self.inline_size_threshold;
ir.is_value()
&& small_enough
&& self.some_benefit(ir, in_scope, ctx)
},
Many는 인라이닝에 가장 조심해야 하는 경우입니다. OnceInFun 체크와 비슷하지만 small_enough가 추가됩니다. 정의가 무제한으로 여러 번 인라인될 수 있으니, 충분히 작을 때만 허용합니다.
IR의 size는 트리 노드 수의 느슨한 카운트입니다. 단순 노드 수가 아니라, 노드의 런타임/인라이닝 비용을 고려해 조정합니다. 예를 들어 단순 변수는 size를 0으로 둡니다. 타입 함수와 타입 적용은 런타임에 영향을 주지 않으므로 size에 반영하지 않습니다. 여기서는 다루지 않지만 size()의 전체 정의는 소스 코드에서 볼 수 있습니다.
size를 구한 뒤 inline_size_threshold와 비교해 충분히 작은지 판단합니다. 이 값은 그냥 임의로 정한 숫자입니다. 기본값은 60인데, GHC가 그렇게 쓰고 있고 그들은 똑똑해 보이니까요. 완전한 컴파일러라면 조정 가능한 설정 옵션이 될 것입니다.
이제 Many 체크도 끝입니다. 우리의 체크 중 문맥에 의존하는 것은 some_benefit뿐입니다. 나머지는 ir만으로 결정되며 한 번 계산해 캐시할 수 있습니다. 실제로 GHC는 그렇게 하고, some_benefit만 발생마다 계산합니다. 여기서는 단순화를 위해 캐싱을 생략했지만, 알아두면 좋습니다.
callsite_inline까지 완료했으니 simplify 파트는 끝입니다. 이제 나머지 절반인 rebuild로 갑니다. simplify는 context를 쌓으며 항 안으로 내려갔고, rebuild는 그 context를 소비하며 단순화된 항을 위로 조립합니다:
fn rebuild(&mut self, mut ir: IR, in_scope: InScope, mut ctx: Context) -> IR {
while let Some((entry, subst)) = ctx.pop() {
self.sbust = subst;
match entry {
// ...
}
}
ir
}
항을 조립하면서 최적화 기회를 찾습니다. 사실 모든 최적화는 rebuild에서 일어납니다. simplify는 인라이닝만 담당합니다. 각 context 엔트리는 저장된 치환을 복원합니다. 엔트리 종류에 따라 처리합니다. 먼저 App:
ContextEntry::App(arg) => {
if let IR::Fun(var, body) = ir {
self.saturated_fun_count += 1;
return self.simplify(IR::local(var, arg, *body), in_scope, ctx);
} else {
let arg = self.simplify(arg, in_scope.clone(), vec![]);
ir = IR::app(ir, arg);
}
}
App을 재구성할 때, 현재 ir이 Fun인지 확인합니다. 그렇다면 최적화로 이를 로컬 바인딩으로 바꿉니다. 이 변환은 새로운 단순화 기회를 열 수 있으므로, 새 local에 대해 simplify를 호출하고 루프에서 빠져나옵니다.
파라미터를 곧바로 본문에 치환하지 않는 이유는, 모든 변수를 무조건 인라인하지 않는 이유와 같습니다. 변수가 얼마나 자주/어디서 발생하는지 고려해야 하기 때문입니다. 로컬에 대한 그 고려 로직은 이미 작성했으니, 여기서 재사용합니다. 인자가 한 번만 쓰이면 단순화가 이를 감지해 로컬을 제거할 것입니다.
ir이 Fun이 아니라면 App을 구성하고 계속합니다. context에 넣을 때는 인자를 단순화하지 않았으므로, 지금 단순화합니다. 이때 context는 비어 있어야 합니다. simplify는 결국 인자에 대해 rebuild를 호출하는데, 인자 자체의 context만 재구성해야지 ir의 context까지 함께 재구성하면 안 되기 때문입니다. 그리고 새 ir로 쓸 App을 만듭니다. 다음 케이스 TyApp도 비슷합니다:
ContextEntry::TyApp(ty) => {
ir = if let IR::TyFun(_, body) = ir {
self.saturated_ty_fun_count += 1;
subst_ty(*body, ty)
} else {
IR::ty_app(ir, ty)
}
}
App과 마찬가지로 ir이 TyFun이면 단순화합니다. 하지만 App과 달리, 여기서는 즉시 타입을 본문에 치환합니다. 타입은 런타임 비용이 없으므로 여기저기 인라인되는 것을 걱정할 필요가 없습니다. TyFun을 rebuild하는 것은 간단합니다:
ContextEntry::TyFun(kind) => {
ir = IR::ty_fun(kind, ir);
}
여기서는 최적화할 것도 단순화할 것도 없습니다. 노드를 만들고 넘어갑니다. 마지막으로 가장 흥미로운 케이스, Local입니다:
ContextEntry::Local(var, occ, body) => {
if ir.is_trivial() {
self.locals_inlined += 1;
self.subst.insert(var.id, SubstRng::Done(ir));
return self.simplify(body, in_scope, ctx);
} else {
let body = self.simplify(
body,
in_scope.update(var.id, Definition::BoundTo(ir.clone(), occ)),
vec![],
);
ir = if let Occurrence::Dead = self.occs.lookup_var(&var) {
self.locals_inlined += 1;
body
} else {
IR::local(var, ir, body)
};
}
}
로컬을 내려갈 때 우리는 본문이 아니라 정의로 내려갔습니다. 이는 로컬의 “단순화된 정의”를 기반으로 인라이닝 결정을 내리기 위함입니다.
정의가 trivial이면(변수 또는 정수), 작고 작업이 없으므로 인라이닝이 공짜입니다. 정의를 치환에 추가하고 본문을 단순화합니다. 정의는 이미 단순화했으므로, 인라인할 때 더 단순화하지 않도록 Done으로 넣습니다.
정의가 비trivial이면 바인딩을 만들 것이라 가정합니다. in_scope를 바인딩으로 갱신하고 본문을 단순화합니다. 본문 단순화 과정에서 변수가 모두 인라인될 수 있으므로, 바인딩을 만들기 전에 발생 정보를 확인합니다. 변수가 dead면 로컬을 버릴 수 있습니다.
이것으로 rebuild도 끝입니다.
모든 구성요소를 합치면, 전체 진입점인 simplify 메서드를 만들 수 있습니다:
fn simplify(
&mut self,
mut ir: IR
) -> IR {
for _ in 0..2 {
let (_, occs) = occurrence_analysis(&ir);
let mut simplifier = Simplifier::new(occs);
ir = simplifier.simplify(ir, InScope::default(), vec![]);
if simplifier.did_no_work() {
break;
}
}
ir
}
ir에 대한 발생을 생성하고, 그로 Simplifier를 만든 뒤 ir에 대해 simplify를 호출합니다. 단순화된 ir을 만든 다음 did_no_work로 아무 일도 하지 않았는지 확인합니다:
fn did_no_work(&self) -> bool {
self.saturated_fun_count == 0
&& self.saturated_ty_fun_count == 0
&& self.locals_inlined == 0
}
이는 ir에서 단순화를 하나라도 수행했는지 확인하는 헬퍼입니다. 수행한 게 없다면 조기 종료합니다.
이 모든 것을 하드코딩된 횟수(현재 2)만큼 루프로 돕니다. “2”는 과학이라기보다 예술에 가깝습니다. 테스트하면서 한 번의 패스로는 아직 작업이 남는 항을 찾을 수 있었습니다. 하지만 두 번 패스 이후에도 안정되지 않는 항은 찾지 못했습니다.
물론 그런 항은 거의 확실히 존재할 겁니다. 단순화기를 영원히 돌리지 않기 위해 어딘가에 선을 그어야 하고, 오늘은 그 선을 2로 그었습니다. 앞으로 기능을 더 추가한 뒤에는 다른 숫자가 더 적절하다는 것을 발견할 수도 있습니다. 우리는 처음의 단순화 함수에서 아주 멀리 왔습니다:
fn simplify(
&mut self,
ir: IR
) -> IR {
ir
}
이제 성과를 즐길 시간입니다. 아주 복잡한 IR 항을 하나 봅시다:
((fun [V0]
((fun [V1]
((fun [V2]
((fun [V3]
((fun [V4] (V4 V0 V1 V2 V3))
(fun [V5, V6, V7, V8] V5)))
4))
3))
2))
((fun [V9] V9)
((fun [V10] V10)
((fun [V11] V11)
((fun [V12] V12) 1)))))
여기에는 여러 인자에 적용되는 깊게 중첩된 함수들이 잔뜩 있습니다. 하지만 우리의 온갖 장치에도 불구하고 각 변수는 한 번만 사용됩니다. 단순화 이후 결과는:
1
모든 간접성이 제거되어 프로그램의 핵심인 값 1만 남았습니다. 이런 인위적인 예제라도 단순화기가 잘 동작하는 것을 보면 기쁩니다.
이로써 기본 단순화기가 완성됐습니다. 최적화가 코드의 미래를 추측하는 허무한 노력일 수 있고, 정적 분석이 실패하는 지점에서는 휴리스틱을 써야 한다는 것을 배웠습니다. 그럼에도 우리의 최적화기는 코드를 잘 씹어 성능을 개선합니다. 입력과 출력 IR을 비교하면 이미 차이가 보입니다. 이 차이는 컴파일러를 더 내려갈수록 더 커질 것입니다. 결국 코드 생성에 도달하면, 단순화된 IR은 초기 lowering된 IR보다 더 작고 효율적인 코드를 만들 것입니다. 전체 소스 코드는 언제나처럼 동반 레포지토리에서 확인할 수 있습니다. 다음 할 일은 모노모피제이션입니다.