유니온-파인드에서 출발해 매칭과 추출을 더해가며 e-graph 데이터 구조가 어떻게 만들어지는지 단계적으로 살펴본다.
URL: https://bernsteinbear.com/blog/whats-in-an-egraph/
Title: e-graph에는 무엇이 들어 있을까?
이 글은 CF Bolz-Tereick, Philip Zucker, Chris Fallin, Max Willsey와의 여러 대화에서 이어진 것입니다.
컴파일러는 프로그램 표현(representation)에 관한 모든 것입니다. 한 언어로 된 프로그램을 입력으로 받아, 여러 내부 언어를 거치며 다양한 방식으로 변환한 뒤, 다른 언어로 된 프로그램을 출력합니다1.
언어 간 변환의 가치 중 일부는 프로그램을 최적화하는 데 있습니다. 이는 더 빠르게 만들거나, 더 작게 만들거나, 혹은 다른 무언가일 수도 있습니다. 최적화는 프로그램을 변경하는 일을 필요로 합니다. 예를 들어, 가상의 IR로 아래 코드를 생각해 봅시다:
v0 = ...
v1 = Const 8
v2 = v0 * v1
컴파일러가 v2에 대한 명령을 최적화하려면, v2의 모든 사용을 대체 명령으로 논리적으로 바꿔치기해야 합니다. 이것이 리라이트(rewrite)입니다.
많은 컴파일러는 모든 명령을 순회하면서, 어떤 명령 op가 원래 명령 v2를 사용하는지 확인합니다. 사용한다면, 그 명령 안의 v2 사용을 모두 대체 명령으로 바꿉니다.
void very_specific_optimization(Instr* instr) {
if (instr->IsMul() && instr->Operand(1)->IsConst() &&
instr->Operand(1)->AsConst()->Value() == 8) {
Instr* replacement = new LeftShift(instr->Operand(0), new Const(3));
for (auto op : block.ops) {
if (op->uses(instr)) {
op->replace_use(instr, replacement);
}
}
}
}
이 방식은 괜찮습니다. 아주 전통적이죠. 프로그램의 크기와 복잡도에 따라 충분히 잘 작동합니다. Cinder JIT이 두 개의 IR에서 이런 방식으로 동작합니다. 컴파일러에서 성능 문제가 될 만큼 멀리 가지도 않습니다. 하지만 다른 제약을 가진 다른 컴파일러들은, 따라서 이러한 리라이트를 수행하기 위해 다른 접근을 하기도 합니다.
이 글에서는 조금은 구불구불한 산책을 해보려 합니다. find-and-replace의 대안인 _유니온-파인드(union-find)_에서 시작해, 기능을 하나씩 더하다 보면, 어느새 _e-graph_라는 또 다른 데이터 구조를 우연히 만들어버리게 됩니다. 이 글이 e-graph의 신비함을 조금 덜어주길 바랍니다.
저는 유니온-파인드를 정말 좋아합니다. 이는 컴파일러 작성자가 빠르고 쉽게, 그리고 in-place로 IR 리라이트를 할 수 있게 해줍니다. API는 주요 함수 두 개 union과 find로 이루어져 있습니다. 최소 구현은 15줄 정도이며 IR에 직접 끼워 넣을 수도 있습니다.
기본 블록의 모든 연산을 순회하며 포인터를 바꾸는 대신, IR 노드가 다른 노드를 “가리키도록” 표시합니다. 아래 스니펫은 앞 예제의 전체 루프를 대체합니다:
instr->make_equal_to(new LeftShift(instr->Operand(0), new Const(3)));
이 포워딩 포인터(forwarding pointer) 개념은 IR 노드 자체에 내장할 수도 있고, 보조 테이블에 둘 수도 있습니다. 각 노드는 자신의 진실의 원천(source of truth)을 유지하고, 각 리라이트는 포인터 스왑 한 번만 필요합니다(물론 포인터를 따라가긴 하지만, 아주 조금 따라갈 뿐입니다2). 다만 이는 전형적인 시간-공간 트레이드오프입니다. IR 노드당 추가로 포인터 하나 정도의 공간이 필요합니다.
아래는 CF의 toy optimizer 시리즈 구현3을 바탕으로 한 변형입니다:
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
@dataclass
class Expr:
forwarded: Optional[Expr] = dataclasses.field(
default=None,
init=False,
compare=False,
hash=False,
)
def find(self) -> Expr:
"""`self`가 속한 집합의 대표(representative)를 반환한다."""
expr = self
while expr is not None:
next = expr.forwarded
if next is None:
return expr
expr = next
return expr
def make_equal_to(self, other) -> None:
"""`self`가 속한 집합을 `other`가 속한 집합과 합친다(union)."""
found = self.find()
if found is not other:
found.forwarded = other
유니온-파인드가 아주 빠를 수 있는 이유는 표현력이 제한적이기 때문입니다:
(더 읽고 싶다면 제 다른 글 Vectorizing ML models for fun의 앞부분과 toy optimizer, toy optimizer에서의 할당 제거, toy optimizer에서의 추상 해석을 보세요.)
이는 위에서 했던 강도 감소(strength reduction) 같은 최적화에 정말 좋습니다. IR 스니펫을 다시 보죠:
v0 = ...
v1 = Const 8
v2 = v0 * v1
강도 감소 패스는 v2를 곱셈 대신 왼쪽 시프트로 리라이트할 수 있습니다(v2.make_equal_to(LeftShift(v0, Const(3)))). 보통 시프트가 곱셈보다 빠르니까요. 좋습니다. 작은 속도 향상을 얻었네요.
하지만 겉보기에는 자명한 로컬 리라이트도 더 비로컬한 결과를 가져올 수 있습니다. (a * 2) / 2라는 표현을 생각해 봅시다. 이는 e-graphs good 웹사이트와 논문에 나오는 예제입니다. 만약 강도 감소 패스가 a * 2를 성급하게 a << 1로 리라이트해버리면, 우리는 어떤 정보를 잃게 됩니다.
이 리라이트는 또 다른 가상의 패스가 (a * b) / b 형태의 표현이 a * (b / b)와 동치이며, 따라서 a와 동치임을 인식하는 것을 막습니다. 유니온-파인드 기반 리라이트는 파괴적(destructive)이기 때문입니다. 곱셈을 없애버렸으니 말이죠. 그걸 다시 어떻게 찾을 수 있을까요?
좀 더 구체적으로 만들어 봅시다. 작은 수학 IR을 하나 만들어 보죠. 유니온-파인드로 리라이트 가능하다는 점에서 Expr 베이스 클래스를 기반으로 할 겁니다.
@dataclass
class Const(Expr):
value: int
@dataclass
class Var(Expr):
name: str
@dataclass
class BinaryOp(Expr):
left: Expr
right: Expr
@dataclass
class Add(BinaryOp):
pass
@dataclass
class Mul(BinaryOp):
pass
@dataclass
class Div(BinaryOp):
pass
@dataclass
class LeftShift(BinaryOp):
pass
상수, 변수, 이항 연산뿐이지만 데모로는 충분합니다.
제한적인 상수 폴딩, 단순화, 강도 감소를 하는 작은 최적화 패스도 하나 써봅시다. 개별 연산을 보고 단순화하려는 optimize_one 함수와, 연산 리스트(기본 블록이라고 생각해도 됩니다)에 optimize_one을 적용하는 optimize 함수가 있습니다.
def is_const(op: Expr, value: int) -> bool:
return isinstance(op, Const) and op.value == value
def optimize_one(op: Expr) -> None:
if isinstance(op, BinaryOp):
left = op.left.find()
right = op.right.find()
if isinstance(op, Add):
if isinstance(left, Const) and isinstance(right, Const):
op.make_equal_to(Const(left.value + right.value))
elif is_const(left, 0):
op.make_equal_to(right)
elif is_const(right, 0):
op.make_equal_to(left)
elif isinstance(op, Mul):
if is_const(left, 1):
op.make_equal_to(right)
elif is_const(right, 1):
op.make_equal_to(left)
elif is_const(right, 2):
op.make_equal_to(Add(left, left))
op.make_equal_to(LeftShift(left, Const(1)))
def optimize(ops: list[Expr]):
for op in ops:
optimize_one(op.find())
이제 실행해 보고, 두 상수를 더하는 초기의 작은 IR 스니펫4에 무엇을 하는지 봅시다:
ops = [
a := Const(1),
b := Const(2),
c := Add(a, b),
]
print("BEFORE:")
for op in ops:
print(f"v{op.id} =", op.find())
optimize(ops)
print("AFTER:")
for op in ops:
print(f"v{op.id} =", op.find())
# BEFORE:
# v0 = Const<1>
# v1 = Const<2>
# v2 = Add v0 v1
# AFTER:
# v0 = Const<1>
# v1 = Const<2>
# v2 = Const<3>
좋습니다. 1+2를 3으로 접을 수 있네요. 만세. 하지만 이 섹션의 요점은 유니온-파인드 구조가 암묵적으로 구성한 동치류를 찾아내는 것입니다. 이를 위한 함수를 작성해 봅시다.
그런 함수를 만들려면 생성된 모든 연산을 순회해야 합니다. 저는 모든 연산을 리스트에 명시적으로 기록하기로 했지만, forwarded 체인을 따라 도달 가능한 연산을 모두 걷는 함수를 작성할 수도 있습니다.
every_op = []
@dataclass
class Expr:
# ...
def __post_init__(self) -> None:
every_op.append(self)
# ...
def discover_eclasses(ops: list[Expr]) -> dict[Expr, set[Expr]]:
eclasses: dict[Expr, set[Expr]] = {}
for op in ops:
found = op.find()
if found not in eclasses:
# 대표로 키를 잡는다
eclasses[found] = set()
eclasses[found].add(op)
if op is not found:
# 대표가 아닌 것들을 조회해도 동치 연산을 찾을 수 있도록
# 엔트리를 alias한다
eclasses[op] = eclasses[found]
return eclasses
# ...
print("ECLASSES:")
eclasses = discover_eclasses(every_op.copy())
for op in ops:
print(f"v{op.id} =", eclasses[op])
# BEFORE:
# v0 = Const<1>
# v1 = Const<2>
# v2 = Add v0 v1
# AFTER:
# v0 = Const<1>
# v1 = Const<2>
# v2 = Const<3>
# ECLASSES:
# v0 = {Const<1>}
# v1 = {Const<2>}
# v2 = {Const<3>, Add v0 v1}
이제 egg 웹사이트의 더 복잡한 IR 예제로 돌아가 봅시다. 이번엔 우리의 작은 IR로 표현해 보겠습니다:
ops = [
a := Var("a"),
b := Const(2),
c := Mul(a, b),
d := Div(c, b),
]
지금 상태로 옵티마이저를 돌리면, 우리는 곱셈을 성급하게 왼쪽 시프트로 리라이트할 겁니다. 하지만 동치류 안에서 곱셈을 다시 발견할 수 있습니다(여기선 각 동치류의 유니온-파인드 대표를 나타내기 위해 작은 *를 추가했습니다):
BEFORE:
v0 = Var<a>
v1 = Const<2>
v2 = Mul v0 v1
v3 = Div v2 v1
AFTER:
v0 = Var<a>
v1 = Const<2>
v2 = LeftShift v0 v5
v3 = Div v6 v1
ECLASSES:
v0 = * {Var<a>}
v1 = * {Const<2>}
v2 = {LeftShift v0 v5, Add v0 v0, Mul v0 v1}
v3 = * {Div v6 v1}
v4 = {LeftShift v0 v5, Add v0 v0, Mul v0 v1}
v5 = * {Const<1>}
v6 = * {LeftShift v0 v5, Add v0 v0, Mul v0 v1}
이로써 한 문제는 해결됩니다. 어느 시점이든, 유니온-파인드 구조에 저장된 동치류를 열거할 수 있습니다. 하지만 모든 데이터 구조가 그렇듯, 우리가 선택한 유니온-파인드 표현에는 트레이드오프가 있습니다. 리라이트는 빠르지만, 열거는 느립니다. 일단은 이를 받아들이죠.
하지만 이 열거 기능만으로는 e-graph의 API가 되지 않습니다. 유니온-파인드에 e-매칭(e-matching)을 덧붙이려면 한 단계가 더 필요합니다. 바로 탐색입니다. 어떤 사람들은 이를 match라고 부를 겁니다.
좋습니다. 강도 감소로 왼쪽 시프트로 바꾼 뒤에도 곱셈을 다시 찾아낼 수 있네요. 멋집니다. 하지만 이 데이터 표현에서 패턴 매칭은 어떻게 할까요?
(a * b) / b로 돌아갑시다. 이는 어떤 표현 a, b에 대해 IR-세계 파이썬 표현 Div(Mul(a, b), b)에 해당합니다(그리고 b들이 같아야 하는데, 이는 파이썬 match 패턴의 기본 동작은 아닙니다).
주어진 연산에 대해, 그 동치류에 Div가 있는지 보려면 동치류 전체를 루프 돌면 됩니다:
def optimize_match(op: Expr, eclasses: dict[Expr, set[Expr]]):
# a / b 형태를 찾는다
for e0 in eclasses[op]:
if isinstance(e0, Div):
# ...
좋습니다. 그럼 Mul의 Div인지—즉 Div의 왼쪽이 Mul인지—는 어떻게 찾을까요? 또 루프를 돕니다!
def optimize_match(op: Expr, eclasses: dict[Expr, set[Expr]]):
# (a * b) / c 형태를 찾는다
for e0 in eclasses[op]:
if isinstance(e0, Div):
div_left = e0.left
div_right = e0.right
for e1 in eclasses[div_left]:
if isinstance(e1, Mul):
# ...
여기서 편의를 위해 eclasses 딕셔너리에서 대표가 아닌 키도 alias해두었으므로, .find()를 호출할 필요가 없다는 점에 주목하세요.
그럼 b들이 같다는 조건은 어떻게 유지할까요? 일치하는지 확인하면 됩니다:
def optimize_match(op: Expr, eclasses: dict[Expr, set[Expr]]):
# (a * b) / b 형태를 찾는다
for e0 in eclasses[op]:
if isinstance(e0, Div):
div_left = e0.left
div_right = e0.right
for e1 in eclasses[div_left]:
if isinstance(e1, Mul):
mul_left = e1.left
mul_right = e1.right
if mul_right == div_right:
# ...
그리고 이제 Div를 Mul의 왼쪽 자식으로 리라이트할 수 있습니다:
def optimize_match(op: Expr, eclasses: dict[Expr, set[Expr]]):
# (a * b) / b 형태를 찾아 a로 리라이트한다
for e0 in eclasses[op]:
if isinstance(e0, Div):
div_left = e0.left
div_right = e0.right
for e1 in eclasses[div_left]:
if isinstance(e1, Mul):
mul_left = e1.left
mul_right = e1.right
if mul_right == div_right:
op.make_equal_to(mul_left)
return
이 최적화 함수를 기본 블록의 모든 노드에 대해 실행하면 결과는 다음과 같습니다:
AFTER:
v0 = Var<a>
v1 = Const<2>
v2 = LeftShift v0 v5
v3 = Var<a>
여기서 v3는 원래의 큰 표현에 해당합니다. 축하합니다. 시간 여행하는 컴파일러 패스를 성공적으로 구현했습니다!
하지만 아쉽게도 이 매칭은 매우 특수합니다. 매칭 조건은 루프 구조에 하드코딩되어 있고, 루프 구조(중첩 레벨)는 함수에 하드코딩되어 있습니다. 이런 종류의 문제를 풀기 위해 프로그래밍의 거장들은 SQL을 발명했죠5.
완전한 쿼리 언어를 구현할 시간도 두뇌도 없고6, 작은 내장 매칭 DSL을 만드는 아이디어도 바닥나서, 여기서는 “가능하다”는 제 말을 믿어야 합니다.
한 가지 주의할 점: make_equal_to로 쓰기(write)를 한 뒤에는, 다시 읽어야 한다면 eclasses를 재발견(rediscover)해야 합니다. egg 사람들이 말하는 “rebuild”가 아마 이거일 것이고, 그들의 논문이 흥미로웠던 부분은 이를 더 자주 하지 않거나 더 빠르게 하는 방법을 찾은 것이었다고 생각합니다.
또 하나 해야 하는 일은 (제 생각엔) 수렴(convergence)할 때까지 반복하는 것입니다. 모든 연산을 한 번 순회하며 매칭과 리라이트를 했다고 해서 항상 이른바 “합동 폐포(congruence closure)”에 도달한다는 보장은 없습니다. 어떤 경우(어떤 경우일까요?)에는 그래프가 아예 수렴하지 않을 수도 있습니다!
이제 우리가 가진 것은 기본 블록에 대한 여러 개의 평행 세계들인데, 각 연산이 사실상 동치 연산들의 집합이 된 셈입니다. 그런데 그 집합에서 어떤 원소를 골라야 할까요? 한 접근은, 앞에서 해왔듯 각 동치류의 대표를 각 연산의 최종 형태로 선택하는 것입니다. 이는 매우 유니온-파인드스러운 접근입니다. 단순하고 빠르며, 강도 감소 유형의 리라이트만 하는 상황에서는 잘 동작합니다.
하지만 e-graph가 등장한 이유는 더 큰 상태 공간을 탐색하고 싶었기 때문입니다. 동치류의 대표가 국소적으로는 최적이지만 전역적으로는 최적이 아닐 수도 있습니다. 최적성 함수—비용 함수—가 전체 프로그램을 고려한다면, 탐색을 확장할 방법이 필요합니다.
e-graph API의 마지막 조각은 extract 함수입니다. 이 함수는 e-graph 안에서 “최저 비용” 또는 “가장 최적”인 프로그램 버전을 찾아냅니다.
가장 단순한 추출 함수는 각 IR 노드의 모든 동치류에 대한 데카르트 곱(cartesian product)을 순회하면서 전체 프로그램 비용을 최소화하는 것을 찾는 것입니다.
import itertools
def extract(program: list[Expr], eclasses: dict[Expr, set[Expr]]) -> list[Expr]:
best_cost = float("inf")
best_program = program
for trial_program in itertools.product(*[eclasses[op] for op in program]):
cost = whole_program_cost(trial_program)
if cost < best_cost:
best_cost = cost
best_program = trial_program.copy()
return best_program
하지만 이는 느립니다. 노드 수가 늘면 밑(base)이 커지고, 리라이트 수가 늘면 지수(exponent)가 커집니다. 정말 안 좋은 소식이죠. 완전 탐색을 하지 않는 여러 접근이 있지만, 항상 전역 최적 프로그램을 산출하는 것은 아닙니다. 이 분야는 활발한 연구 주제입니다.
또 하나 주의할 점은, 비용 함수는 보통 e-graph 구현에 내장되어 있지 않다는 것입니다. 대개 라이브러리 사용자가 최소한 자신의 비용 함수를 제공할 수 있게 하며, 심지어 extract 전체를 사용자에게 맡기기도 합니다.
이로써 완전한 e-graph 구현에 도달했습니다. 단순한 유니온-파인드에서 시작해, match와 extract를 점진적으로 추가함으로써 완전한 e-graph에 이르렀습니다.
여기서 약간 미묘한 점은, 우리가 수동 make_equal_to로 절차적/함수적 패턴 매칭을 했던 것과 달리, 많은(대부분?) e-graph 구현은 라이브러리 사용자가 선언적(declarative) 구문 리라이트 규칙 집합을 제공하도록 유도한다는 것입니다. egglog는 Datalog 비슷한 커스텀 DSL을 사용하고, Cranelift는 ISLE이라는 DSL을 사용하며, Ego는 내장 DSL을 사용합니다.
;; egglog 예제에서 가져온 Datalog 유사 규칙 쌍
(rewrite (If T t f) t)
(rewrite (If F t f) f)
이 방식은 컴파일러의 프로그램 개념을 라이브러리의 도메인으로 임베딩한 다음, 다시 라이브러리 도메인에서 자신의 IR로 추출해오는 과정을 요구합니다.
이 블로그 글의 동기 중 하나는, 이렇게 왕복 매핑 없이도 컴파일러 프로젝트에 직접 끼워 넣을 수 있는 종류의 e-graph를 제시하는 것이었습니다.
Cranelift는 aegraph라는 e-graph의 수정 형태를 사용합니다. 전체 e-graph를 위상 정렬(toposort)할 수 있고, equality 화살표가 더 이른 노드만 가리킬 수 있다는 점이 다릅니다. 여기에 흥미로운 트레이드오프가 분명 있겠지만, 저는 전문가가 아니므로 Chris Fallin의 훌륭한 글을 읽는 편이 좋습니다.
Zulip 스레드에서 Chris는 이렇게 씁니다:
aegraphs는 정말로 세 가지 핵심에 관한 것입니다:
eclass를 직접 인코딩하는 영속(persistent) 불변(immutable) 데이터 구조 — 두 다른 노드를 가리키는 “union node”를 사용합니다. 이를 통해 eclass에 더 많은 것을 union하기 전 시점의 “시간 스냅샷”을 참조할 수 있는데, 이게 비순환성(acyclicity)에 중요합니다.
eager(“bottom-up”)한 리라이트 전략: 노드를 만들자마자 그 노드에만 리라이트 규칙을 적용합니다. 사실 이게 제가 egg와 “다른” 무언가를 하게 된 진입점이었습니다. “모든 노드를 순회하며 모든 규칙을 적용”하는 것보다 더 효율적으로 규칙을 적용할 방법이 없을까 고민했는데, 음, 리라이트를 한 번만 하는 게 할 수 있는 최선에 가깝죠.
비순환성: 고전적인 egraph에서는 입력에 사이클이 없어도 노드를 병합할 때 사이클이 생길 수 있습니다.
x + 0과 이를x로 리라이트하는 규칙을 생각해보세요. 그러면 자기 자신을 참조하는 eclass 하나가 생깁니다 — 본질적으로 양방향으로 동치를 인코딩하기 때문에(((x + 0) + 0) + 0)같은 더 긴 것들도 무한대로 가능하다는 뜻이며, 그것이 사이클이 의미하는 바입니다. 이를 피하려면, 인자에서 우리가 알고 있는 eclass의 _스냅샷_을 참조해야 하고, (union된) 인자 eclass로 새로운 value 노드를 다시 intern하지 않아야 합니다. 이것이 영속 불변 데이터 구조를 가능하게 하고, eager 리라이트가 작동하도록 요구합니다.(이에 대한 제 발표에서는 이 세 개의 개념이 서로를 강화한다는, 좀 이상한 삼면 도형이 나옵니다…)
놀라웠던 것 중 하나는 단일 패스 eager 리라이트가 실제로 _동작한다_는 점이었습니다 — 규칙이 특정 방식으로 구조화되어 있으면 동작합니다. 피하고 싶은 경우는 A가 B로 리라이트되고, C가 B로 리라이트되는데, A의 더 좋은 버전이 실제로는 C인 경우(하지만 직접적인 리라이트가 없는 경우)입니다 — 완전한 egraph에서는 이후의 unify가 A와 C를 같은 그룹으로 묶었고 그 동치가 보였겠지만, 스냅샷된 eclass로 eager 리라이트를 하면 그렇지 않습니다. 다행히 Cranelift에서 규칙을 쓰는 방식은 충분히 “방향성”이 있어서 실제로는 이런 일이 없었습니다(그런 일이 있으려면, C가 B보다 더 좋아야 하는데도 C->B 리라이트가 존재해야 합니다).
Cranelift에서 aegraph를 사용하는 데에는 제어 흐름, “elaboration”, (부분 중복 없이) GVN과 LICM을 수행하는 방식, 부작용을 올바른 위치에 유지하는 것, 그리고 재구성/재직렬화된 계산 시퀀스가 지배 관계(dominance)에 대해 올바른지 보장하는 것(추출은 domtree를 걱정해야 합니다!) 등과 관련된 또 다른 측면이 잔뜩 있습니다.
[…]
그러니까, 조금 더 자세히 말하면: aegraph의 eclass 표현은 정확히는 유니온-파인드가 아닙니다; enode를 정준(canonical) enode로 매핑하고, enode들이 같은 eclass에 있는지 테스트하기 위한 별도의 (전통적인) 유니온-파인드 자료구조도 함께 유지합니다. union-node의 목적은 클래스 내 모든 enode에 도달하는 트리를 만드는 것입니다. 다른 말로: 유니온-파인드의 링크를 따라가면 정준/최초 enode로 도달합니다(모든 enode가 한 점으로 “팬인”); union-node의 링크를 따라가면 모든 enode로 도달합니다(모든 union-node가 이진 트리로 “팬아웃”).
유도 과정을 이렇게 생각할 수도 있습니다:
- value 노드를 가진 SSA IR에서 시작합니다; 각 value는 일반 연산자, alias(모든 사용을 편집하지 않고 리라이트하기 위해), 또는 blockparam(우리의 phi 노드 버전)입니다.
- value 노드의 새 종류 하나를 추가합니다: union.
- aegraph 리라이트 단계에서는, SSA IR 위에 논리적으로(물리적으로가 아니라!) 암시된 aegraph가 있습니다:
- SSA value들의 동치류를 추적하기 위해 유니온-파인드를 유지합니다;
- 새 value 노드만 만들고, 노드를 리라이트하지 않습니다;
- 새 노드를 만들 때,
- GVN 맵을 확인하고 가능하면 dedup합니다;
- 없으면, 일반 value 노드를 생성합니다(그리고 끝).
- 어떤 노드를 eclass로 union할 때,
유니온-파인드에서 해당 SSA value number를 eclass의 다른 enode SSA value number와 병합합니다;
자식이 새 노드와 최신 eclass ID인 새로운 union 노드를 만듭니다;
이 union 노드가 새로운 eclass ID입니다.
몇 가지 귀결:
- 인덱스 공간은 SSA value 인덱스 공간 하나뿐입니다. “Enode”는 개별 SSA value이고, “Eclass” 또한 SSA value인데, 일반 연산자 노드(단일 원소 eclass)거나 union 노드입니다.
- aegraph를 구성하는 동안 eclass마다 두 개의 값을 유지합니다: “정준 ID”(가장 오래된 노드이며 유니온-파인드가 매핑하는 대상)와 “최신 ID”(모든 eclass 구성원을 도달하는 union-node spine의 현재 헤드)입니다.
- 어느 시점에 “최신 ID”를 기록하면(예: eclass 값의 사용을 볼 때), 그 시점의 모든 eclass 구성원을 도달하는 트리를 캡처합니다. 이후에 병합된 새 구성원은 유니온-파인드에서는 union되지만, 그것들에 도달하는 트리는 우리의 참조 “위”에 쌓이므로 우리는 보지 못합니다.
PyPy는 옵티마이저에 “유니온-파인드”를 가지고 있지만, 일반 유니온-파인드보다 똑똑합니다. 스마트 생성자(smart constructor)와 다른 기능들도 있어서, 그 옵티마이저는 유니온-파인드라기보다 e-graph에 더 가깝습니다. 언젠가 CF가 이에 대해 블로그 글을 써주면 좋겠네요.
물론 e-graph 라이브러리의 대표격인 egg와 egglog도 확인해 보세요. Metatheory.jl도요.
생각이 있다면 꼭 들려주세요! 저에게도 아주 새로운 주제입니다.
이 글 초안을 리뷰해 준 Kartik Agaram, Max Willsey, Chris Fallin에게 감사합니다.
언어들이 반드시 서로 달라야 한다는 뜻은 아닙니다. 예를 들어 컴파일러가 C로 된 프로그램을 입력받아 C로 된 프로그램을 출력할 수도 있습니다. 그리고 “언어”라는 용어는 때때로 모호해지는데, 예컨대 C23은 기술적으로 C99와 다른 언어지만 둘 다 C로 알아볼 수 있습니다. 하지만 C23에서 C99로 가는 컴파일러는 가치가 있는데, 아직 모든 컴파일러의 프런트엔드가 C23 입력을 받을 수 있는 건 아니기 때문입니다. 또한 “컴파일러”라는 말에는 입력 언어가 어떤 의미에서 “더 고수준”이고 출력 언어가 “더 저수준”일 것이라는 뉘앙스가 붙는 경우가 있는데, 이 분위기가 “트랜스파일러(transpiler)”라는 용어를 낳기도 했죠. 하지만 뭐, 컴파일러는 프로그램을 받고 컴파일러는 프로그램을 내보냅니다.↩
이 글에 나온 순진한 구현들은 사람들이 감탄하는 최적 구현이 아닙니다. 최적 구현에는 경로 압축(path compression) 같은 것이 있습니다. 좋은 점은 경로 압축이 API를 전혀 바꾸지 않는 추가 기능이라는 것입니다. 그리고 역 아커만 함수(inverse Ackermann function)에 발목 잡힐 정도라면, 여러분의 IR 그래프 크기 쪽에 다른 문제가 있는 겁니다.↩
Phil이 블로그 글에서 보여준 깔끔한 유니온-파인드 구현도 참고하세요:
uf = {}
def find(x):
while x in uf:
x = uf[x]
return x
def union(x,y):
x = find(x)
y = find(y)
if x != y:
uf[x] = y
return y
마치 여백에 적어둔 메모처럼 읽혀서 정말 마음에 듭니다. 제 생각에 유일한 단점은 IR 연산이 해시 가능하고 비교 가능해야 한다는 것(__hash__, __eq__)입니다.↩
Expr 클래스에 제가 살짝 출력용 편의 기능을 넣었는데, 여기서는 보여주지 않았습니다. 제가 전달하려는 요점에는 중요하지 않고 전체 코드 목록에 등장합니다.↩
이는 egg와 egglog를 만드는 훌륭한 분들(컴파일러 사람들과 데이터베이스 사람들로 구성된 팀)에 대한 가벼운 고개 끄덕임입니다. 그들은 e-graph와 관계형 데이터베이스가 매우 유사하다는 점을 깨닫고, 멋진 도메인 크로스오버를 하는 도구를 만들고 있습니다. 더 알고 싶다면 논문(오픈 액세스)을 읽어보세요!
Yihong Zhang은 Racket으로 egraph-sqlite를 구현했는데, 즐겁게도 아주 작습니다. 재미와 학습을 위해 다른 언어로 포팅되는 것도 보고 싶네요