Cranelift의 미드엔드 최적화기의 핵심인 비순환 e-그래프(aegraph)의 동기, 설계, 구현, 추출 문제, 그리고 성능 평가를 살펴본다.
Chris Fallin- [x]
BlogAboutProjectsAcademics & Publications
2026년 4월 9일
오늘은 Cranelift의 미드엔드 최적화기의 핵심 데이터 구조인 aegraph, 즉 _비순환 e-그래프_에 대해 이야기하려고 합니다. 저는 2022년에 이 접근법을 소개했고, 이후 전체 재작성 한 번을 포함한 다소 우여곡절 많은 과정을 거치며, 초기 아이디어에 대한 여러 흥미로운 깨달음과 “패치”, 더 넓은 e-그래프 커뮤니티와의 다양한 논의(여기에는 PLDI 2023의 EGRAPHS 워크숍에서의 발표 (슬라이드)와 최근 e-graphs Dagstuhl 세미나에서의 발표 및 토론이 포함됩니다), 그리고 지난 3년간 기여된 아주 많은 재작성 규칙들을 거쳐, 이제는 왜 (왜 e-그래프인가? 어떤 이점이 있는가?), 어떻게 (완전한 equality saturation의 함정을 어떻게 피했는가? Cranelift에 실제 투입할 만큼 어떻게 효율적으로 만들었는가?), 그리고 얼마나 (실제로 도움이 되는가? 대안과 비교해 어떻게 평가할 수 있는가?)를 설명할 때가 되었다고 생각합니다.
이미 Cranelift의 미드엔드와 그 aegraph에 익숙한 분들을 위해 덧붙이자면, 이번 글에서는 약간 다른 접근을 취합니다. 저는 이제 우리 aegraph의 “sea-of-nodes” 측면과, 그 안팎으로 변환하기 위해 설계한 번역 패스들(그 과정에서 최적화가 함께 융합됨)이, aegraph의 “다중 표현” 부분, 다시 말해 “동치 클래스” 그 자체보다 사실 더 근본적이라는 관점에 이르렀습니다. 그래서 이번 글에서는 sea-of-nodes를 먼저 소개하는 방식으로 아이디어를 전개하려고 합니다. 즉 먼저 aegraph의 “하나의 enode만 가진 자명한 eclass” 버전(유니온 노드 없음)을 보고, 그다음에 나중에 유니온의 동기를 설명하겠습니다. 실제로는 제가 2022년에 Cranelift에서 이 기능을 실험하고 구축할 때는 e-그래프를 통합하려는 욕구가 먼저 있었고, aegraph는 그것을 실용적으로 만들기 위해 만들어졌습니다. 교육적인 설명 방식과 설계 분류는 시간이 지나면서 제게 더 분명해졌습니다. 그럼 시작해봅시다!
2022년 5월 무렵, 저는 단순한 alias analysis와 관련 최적화들 (중복 로드 제거와 store-to-load forwarding)을 도입했습니다. 예상한 테스트 케이스들에서는 잘 동작했고, 몇몇 벤치마크에서는 실제 속도 향상도 있었습니다(예를 들어 meshoptimizer에서 5% 향상여기). 하지만 동시에 새로운 질문도 생겼습니다. 당시 GVN(global value numbering), LICM(loop-invariant code motion), 상수 전파, 그리고 일부 대수적 재작성을 포함하고 있던 다른 최적화 패스들과 이 패스를 어떻게 통합해야 할까?
왜 이것이 흥미로운 질문인지 보려면, 값을 정규화하는 GVN과 중복 로드 제거가 다음 IR 조각에서 어떻게 상호작용하는지 생각해봅시다:
v2 = load.i64 v0+8
v3 = iadd v2, v1 ;; 예: 배열 인덱싱
v4 = load.i8 v3
;; ... (여기에는 store나 다른 부작용이 없음) ...
v10 = load.i64 v0+8
v11 = iadd v10, v1
v12 = load.i8 v11
중복 로드 제거(RLE)는 한 번의 패스에서 v10을 정의하는 로드를 제거할 수 있고, v10을 v2의 별칭으로 만들 수 있다는 것을 알아낼 수 있습니다. 이상적인 세상이라면, 그다음에는 GVN의 정규화를 통해 v11이 v3와 같아지고, 이어서 v12가 v4의 별칭이 되는 것도 볼 수 있어야 합니다. 하지만 마지막 두 단계는 서로 다른 두 최적화 패스 사이의 긴밀한 협력을 의미합니다. 즉, 전체 RLE 패스를 한 번 돌리고(결과: v10 재작성), 그다음 전체 GVN 패스를 한 번 돌리고(결과: v11 재작성), 그다음 다시 전체 RLE 패스를 한 번 더 돌려야 합니다(결과: v12 재작성). 이렇게 서로 다른 패스들을 오가며 이루어지는 추론 단계의 사슬이 임의로 길어질 수 있고, 완전한 단순화를 위해 임의로 긴 패스 호출 시퀀스가 필요할 수 있다는 점을 알 수 있습니다. 좋지 않죠!
이것은 컴파일러 연구에서 _패스 순서 문제_로 알려져 있으며, 패스들이 별개의 거친 알고리즘(즉, 서로 엮여 있지 않은 상태)으로 남아 있는 한 쉬운 해답이 없는 고전적 휴리스틱 문제입니다. Cranelift에서 alias analysis 기반 재작성의 초기 통합에서 몇몇 흥미로운 경우가 동작하도록 하기 위해, 저는 alias-analysis 재작성 패스 뒤에 GVN을 한 번 호출하는 다소 임시방편적인 선택을 했습니다.
하지만 이것은 명백히 임의적이고, 일반적인 경우에 컴파일 노력을 낭비하며, 우리는 더 잘할 수 있어야 합니다. 일반적으로 해법은 모든 패스의 가능한 재작성을 통합된 틀 안에서 추론하고, 그것들을 세밀한 단위로 교차 배치해야 합니다. 예를 들어, 하나의 국소적 표현식에 대해서만 RLE와 GVN을 다섯 번 연속 적용할 수 있다면, 함수 본문 전체에 대해 각각의 패스를 돌리지 않고도 그렇게 할 수 있어야 합니다. 즉, 우리는 최적화가 세밀한 단위에서 끝날 때까지 반복하는 “단일 고정점 루프”를 원합니다.
이 시점에서 우리가 가지고 있던 최적화들을 다시 살펴봅시다:
GVN(global value numbering): 이것은 정규화 연산입니다. 주어진 값이 정의되는 어떤 범위 내에서(SSA IR에서는 주어진 정의 아래 지배 트리의 서브트리), 그 값을 계산하는 모든 동일한 계산은 원래의 하나로 정규화되어야 합니다.
LICM(loop-invariant code motion): 이것은 코드 이동 연산입니다. 루프 안에서 발생하지만 각 반복마다 값이 같음이 보장되는 계산은 루프 밖으로 이동되어야 합니다. 루프 불변성은 재귀적으로 정의할 수 있습니다. 이미 루프 밖에 있는 값이거나, 루프 안에 있으면서 인자들이 모두 루프 불변인 순수 연산자입니다. 이 변환은 어떤 연산자도 바꾸지 않고, 단지 그것이 발생하는 위치만 옮깁니다.
상수 전파(cprop)와 대수적 재작성: 1 + 2를 3으로 바꾸는 것(cprop)이나 x + 0을 x로 바꾸는 것(대수적 재작성) 같은 변환입니다. 이들은 모두 주어진 패턴에 맞는 표현식을 다른 표현식으로 치환하는 것으로 표현할 수 있습니다.
중복 로드 제거와 store-to-load forwarding: 이 둘은 모두 load 연산자를 그 연산자가 읽는다고 알려진 SSA 값으로 대체합니다.
그리고 우리가 구현하고 싶었던 하나: _재물질화(rematerialization)_입니다. 이것은 필요할 때 다시 계산하기 쉬운 값들(예: 정수 상수)에 대해 새로운 계산으로 다시 정의함으로써 레지스터 압박을 줄입니다. 이것도 일종의 코드 이동으로 볼 수 있습니다.
프레임워크를 고민하는 출발점으로, 위의 것들을 코드 이동, 정규화, _재작성_으로 분류할 수 있습니다. 코드 이동은 말 그대로입니다. 계산이 발생하는 위치를 옮기지만, 그 외에는 바꾸지 않습니다. 정규화는 하나 이상의 계산 인스턴스를 하나의 (“정규”) 인스턴스로 통합하는 것입니다. 그리고 재작성은 한 표현식을 같은 값을 계산해야 하는 다른 표현식으로 바꾸는 모든 최적화입니다. 좀 더 직관적으로 말하면, 이 세 범주는 “단순한” 최적화의 전체 가능성 공간을 포괄하려는 시도입니다. 코드를 움직일 수도 있고, 동일한 코드를 합칠 수도 있고, 동등한 코드로 바꿀 수도 있습니다. (여기에서 눈에 띄게 빠진 가능성은 제어 흐름을 바꾸거나 제어 흐름 관련 추론을 활용하는 능력인데, 이에 대해서는 나중 절에서 더 다루겠습니다.) 따라서 이런 종류의 변환을 처리하는 프레임워크를 만들 수 있다면, Cranelift의 다음 진화를 위한 좋은 기반 인프라를 얻게 될 것입니다.
원리적으로 생각해보면, 이런 관심사들을 통합하는 프레임워크는 어떻게 생겨야 할까요? 코드 이동과 정규화를 함께 생각하면, 아마도 계산(연산자 노드)은 가능하다면 프로그램 안에서 “위치”를 가지지 않아야 한다는 뜻일 수 있습니다. 다시 말해, 제어 흐름 안의 구체적인 어딘가에 두지 않고도 add v1, v2를 IR에서 표현할 방법을 찾아야 할지도 모릅니다. 그러면 같은 계산의 모든 인스턴스는 병합될 것입니다(중복은 위치만 달랐는데 그 위치를 제거했으니까요). 그리고 코드 이동은… 적용되지 않게 됩니다. 코드에 위치가 없으니까요?
음, 완전히 그렇지는 않습니다. 아이디어는 기존의 전통적인 IR(제어 흐름이 있는)에서 _시작_하고, 역시 그것으로 끝나지만, _중간_에서는 가능한 경우 위치를 제거할 수 있다는 것입니다. 따라서 이 표현으로 들어가는 전환에서는 위치를 지우고 정규화하고, 이 표현으로부터 나오는 전환에서는 위치를 다시 할당하며, 우리가 그 일을 수행하는 방식의 부수 효과로 코드 이동이 일어날 수 있습니다.
방금 위에서 설명한 것이 바로 sea-of-nodes IR입니다. Sea-of-nodes IR은 프로그램의 모든 명령어나 연산자에 대해 고전적인 “순차적 순서”를 버리고, 대신 연산자들의 그래프(“바다”)를 만들고, 실제 의존성—데이터 흐름이든 제어 흐름이든—을 나타내는 간선으로 연결하는 표현입니다.
이 설계의 가장 순수한 형태에서는, 그래프가 전부이기 때문에 _모든 IR 변환_을 그래프 재작성으로 표현할 수 있습니다. 예를 들어, 루프에서 계산을 끌어올리는 코드 이동의 한 형태인 LICM은 루프 본문을 나타내는 부분 그래프에 대한 순수한 대수적 재작성입니다. 이는 루프 자체가 sea-of-nodes 안의 하나의 노드이며, 제어 흐름 간선도 다른 간선과 마찬가지로 존재하기 때문입니다. 코드 이동은 표현식 언어(노드와 피연산자)의 범위 밖에 있는 “특별한” 동작이 아닙니다.
그런 유연성은 매력적이지만, 상당한 복잡성 비용도 함께 옵니다. IR이 전통적인 자료구조(기본 블록의 CFG)와 너무 다르기 때문에, 적어도 기존의 경험을 가진 컴파일러 엔지니어들에게는 고전적인 분석과 변환을 이해하고 구현하는 일이 더 어려워집니다. V8 팀은 최근 순수한 Sea-of-Nodes 표현에서 벗어나기로 한 결정을 뒷받침하며 이 어려움에 대해 글을 썼습니다.
하지만 sea-of-nodes가 순수한 (부작용이 없는) 연산자를 다루는 방식과, 실제 입력 및 출력(데이터 흐름 간선) 외에는 어떤 앵커에도 묶이지 않은 채 바다 안에서 “떠다닐” 수 있다는 점에서 영감을 얻는다면, 우리의 목표—재작성, 코드 이동, 정규화를 위한 일반 프레임워크 제공—를 향해 어느 정도 진전을 이룰 수 있을지도 모릅니다. 간단히 말해보죠. 부작용이 있는 명령어들에 대해서는 CFG를 유지하고(이를 “부작용 스켈레톤”이라 부르겠습니다), 나머지에 대해서만 sea-of-nodes를 사용하면 어떨까요?
이렇게 하면 위에서 설명한 대로 코드 이동, 정규화, 재작성을 통합할 수 있습니다. 위치에 기반한 구분을 제거하므로 정규화는 순수 연산자에서 작동하고, 순수 연산자를 다시 CFG에 집어넣을 때 코드 이동이 일어날 수 있으며, 재작성도 순수 연산자에 대해 일어날 수 있습니다. 사실 이제 재작성은 (i) 표현식 노드를 IR의 위치에 놓을 필요 없이 그저 “공중에 떠 있는 채로” 만들기만 하면 되므로 더 추론하기 쉬워지고, (ii) 표현식의 모든 인스턴스 각각에 대해 일어나는 것이 아니라 정규화된 하나의 인스턴스에 대해 한 번만 일어나므로 더 효율적입니다.
이 표현을 “CFG를 가진 sea-of-nodes”라고 부르겠습니다.
이제 실용적인 구현으로 들어가 봅시다. 순수 연산자에 대해 컴파일러 전체를 sea-of-nodes 중심으로 설계하는 것은 원리적으로는 타당할지 몰라도, 기존 Cranelift 컴파일러 파이프라인의 수정이라는 관점에서는 그렇게 급진적인 변화를 한 번에 도입하고 싶지도 않고, 할 수도 없었습니다. 대신 저는 이것을 미드엔드의 대체물로 만들고 싶었습니다. 입력은 CLIF(기존의 CFG 기반 SSA IR)이고 출력도 CLIF여야 합니다. 따라서 세 단계 최적화기가 필요합니다:
모든 순수 연산자를 CFG에서 끌어내 스켈레톤만 남깁니다. 이 연산자들은 순수 계산 노드의 “바다”에 넣고, 진행하면서 중복 제거(hash-consing)를 합니다.
이 연산자들에 대해 재작성을 수행하여, 값 동치를 보존하는 규칙들에 따라 어떤 값들을 다른 값으로 대체합니다.
이 순수 노드의 바다를 노드들을 CFG에 스케줄링함으로써 다시 순차적인 IR로 변환합니다. 이 과정을 계산의 “elaboration”이라고 부르겠습니다.
실제로 이것이 현재 Cranelift 미드엔드의 핵심이 동작하는 방식이며, 위의 각 부분을 차례로 살펴보겠습니다.
먼저 sea-of-nodes 표현으로 들어가는 방법을 이야기해봅시다. 가장 직관적인 답은 물론 단순히 “노드들을 CFG에서 제거”하고, 스켈레톤에 남아 있는 사용들이 참조하는 채로 자유롭게 떠다니게 두는 것일 겁니다. 그러면 끝입니다. 하지만 이것은 이 연산자들이 _순수하다_는 사실(부작용이 없고, 외부 세계에 대한 암묵적 의존성이 없다는 뜻)이 제공하는 명백한 기회를 포기하는 셈입니다. 연산자 op v1, v2는 같은 입력이 주어지면 항상 같은 값을 만들고, 이 노드의 서로 다른 두 인스턴스에는 다른 결과를 만들어야 할 어떤 구별 특성이나 성질도 없습니다. 따라서 우리는 노드를 정규화, 즉 hash-cons 해야 합니다.
Hash-consing은 값 노드나 연산자 노드를 가진 시스템에서 표준적인 기법입니다. 아이디어는 각 값이나 연산자의 내용으로 인덱싱된 조회 테이블을 유지하고, 새 노드를 만들 때 이 테이블을 조회해서 일치하는 기존 노드가 있으면 재사용하는 것입니다.
우리가 중복 제거할 때의 _동치 클래스_는 무엇일까요? (다시 말해, sea-of-nodes 값에 대해 Eq와 Hash를 더 구체적으로 어떻게 정의할까요?) 우리는 아주 단순한 답을 채택합니다(그리고 미묘한 부분은 나중에 처리합니다. 늘 그렇듯이요!). 어떤 노드의 (얕은) 내용이 그 노드의 정체성입니다. 즉, iadd v1, v2가 있다면, 그것은 다른 어떤 동일한 연산자와도 “같다”고 간주되어 중복 제거됩니다.
이 얕은 동치 개념만으로는 같은 표현식 트리의 모든 인스턴스를 정규화하기에 충분하지 않아 보일 수 있습니다. 다음을 생각해봅시다:
v0 = ...
v1 = ...
v2 = iadd v0, v1
v3 = iconst 42
v4 = imul v2, v3
v5 = iadd v0, v1
v6 = iconst 42
v7 = imul v5, v6
분명히 어떤 합리적인 정규화 알고리즘이든 v4와 v7을 같은 것으로 보고, 둘의 사용을 하나의 정규 노드 사용으로 압축해야 할 것입니다. 하지만 이 노드들은 얕게는 같지 않습니다. 어떻게 여기서 저기로 갈 수 있을까요?
한 가지 가능한 답은 귀납입니다. 모든 피연산자가 이미 정규화(그리고 재작성)된 뒤에야 어떤 노드를 정규화한다면, 서브트리가 동일할 경우 동일한 값 번호를 갖는다는 것을 알 수 있습니다. 따라서 귀납적으로 모든 값은 깊게 정규화됩니다.
그러려면 노드의 정의를 그 사용보다 먼저 처리해야 합니다. 다행히 sea-of-nodes-with-CFG를 구성하는 출발점인 SSA CFG는, 우리가 특정 순서로 순회하면 이 성질을 이미 제공합니다. 기본 블록들을 제어 흐름 그래프 안에서 지배 트리(domtree)의 어떤 전위 순회(preorder) 순서로 방문하면 됩니다. 보통 이것은 이미 이용 가능합니다.
따라서 SSA CFG를 sea-of-nodes-with-CFG로 정규화하는 알고리즘은 대략 다음 의사코드와 같습니다:
def canonicalize(basic_block):
for inst in basic_block:
if is_pure(inst): # "순수"한 inst만 중복 제거하고 sea-of-nodes로 옮긴다;
# "스켈레톤"은 제자리에 둔다
basic_block.remove(inst)
inst.rename_values(rename_map) # value->value 맵에 따라 사용을 재작성
if inst in hashcons_map: # 동치는 얕은 내용으로 정의됨
rename_map[inst.value] = hashcons_map[inst]
else:
nodes.push(inst) # sea-of-nodes에 추가
hashcons_map[inst] = inst.value
else:
# 여전히 CFG 스켈레톤의 사용은 sea-of-nodes를 가리키도록 이름 변경해야 한다
inst.rename_values(rename_map)
# 재귀적 domtree 전위 순회.
for child in domtree.children(basic_block):
canonicalize(child)
이것은 위 예제처럼 “깊은 동치”가 있는 경우를 처리할 뿐 아니라(예를 들어 v5의 사용을 방문하기 전에 v5를 v2로 정규화하고 이름 변경하기 때문입니다), 중복이 여러 기본 블록에 걸쳐 흩어져 있는 더 복잡한 예제도 처리합니다.
마지막으로, 이 모든 것에서 “-with-CFG” 측면은 어떻게 작동할까요? 지금까지 우리는 위에서 암시했듯 CFG 스켈레톤에서 정의되는 값들에 대해서는 거의 설명을 생략했습니다. 오직 그것들이 절대 이름 변경되지 않는다는 점만 암시했죠(is_pure 분기로 들어가지 않기 때문입니다). 그런데 이것이 괜찮을까요?
어떤 의미에서는, 구성 자체로 괜찮습니다. 우리는 모든 비순수 값을, 구문적으로 얕게 같더라도 다른 어떤 값과도 구별되는 고유한 “정체성”을 가진 것으로 정의했습니다. 이는 비순수 계산이 암묵적 입력을 가진다는 개념과 맞아떨어집니다. 예를 들어 프로그램에서 두 번 나타나는 load v0은 그 두 시점에서 서로 다른 값을 만들 수 있으므로 중복 제거할 수 없습니다. 물론 암묵적 의존성을 추론할 수 있는 전용 분석이 있다면 완화할 수 있고, 실제로 로드에 대해서는 그런 것이 있습니다(alias analysis가 중복 로드 제거와 store-to-load forwarding으로 이어집니다). 하지만 일반적으로는 이런 “루트”들에 대해 할 수 있는 일이 없습니다. 이들은 스켈레톤에 남아 노드의 바다에 값을 공급하고, 다시 그 바다에서 값을 소비합니다.
프로그램의 sea-of-nodes + 스켈레톤 표현이 주어졌을 때, 이를 어떻게 다시 각 연산자가 구체적인 프로그램 지점에서 계산되는 완전히 선형화된 전통적인 CFG로 되돌려서 백엔드에 넘기고 기계어로 내릴 수 있을까요?
기본 작업은 각 연산자를 어디에 둘지 위치를 정하는 것입니다. Sea-of-nodes 안의 노드들은 CFG 스켈레톤의 부작용 있는 연산자들에 의해 “뿌리내려져”(참조되고 최종적으로 계산/사용되고) 있으므로, 가장 먼저 떠오르는 생각은 순수 노드들을 참조되는 곳의 CFG로 다시 복사하는 것입니다. 이를 재귀적으로 할 수 있습니다. 예를 들어 store v1, v2 같은 부작용 명령어가 있다면, v1과 v2의 정의(순수 연산자)를 그 명령어 바로 앞에 놓을 수 있습니다. 그 정의에 다른 값이 필요하다면, 마찬가지로 먼저 그것들을 계산합니다. 이를 “elaboration”이라고 부를 수 있습니다.
먼저 단일 기본 블록의 경우를 생각해보고 다음과 같은 의사코드를 정의해봅시다:
def demand_based_elaboration(bb):
for inst in bb:
elaborate_inst(inst, bb, before=inst)
def elaborate_inst(inst, bb, before):
for value in inst.args:
inst.rewrite_arg(value, elaborate_value(value, bb, before=inst))
if is_pure(inst):
bb.insert_before(before, inst)
return inst.def
def elaborate_value(value, bb, before):
if defined_by_inst(value): # 일부 값은 inst 정의가 아니라 blockparam 루트다
return elaborate_inst(value.inst, bb, before)
else:
return value
이것은 분명 동작하겠지만, 너무 단순합니다. 어떤 값이 사용될 때마다 계산을 _복제_하며, 결과적으로 (blockparam 루트를 제외하면) 어떤 값도 한 번 이상 사용되지 않습니다. 이는 거의 확실하게 프로그램 크기의 극단적인 폭증으로 이어질 것입니다!
따라서 어떤 값을 여러 번 사용한다면, 프로그램 안의 어느 한 곳에서 그 값을 한 번만 계산하고 모든 사용 이전에 배치해야 할 것 같습니다. 예를 들어, 위 알고리즘에 어떤 노드를 처음 elaboration했을 때의 결과 값 번호를 기록해두고 재사용하는 맵을 추가할 수 있겠습니다(즉, elaboration을 메모이제이션합니다):
# ...
def elaborate_value(value, bb, before):
if value in elaborated:
return already_elaborated[value]
else if defined_by_inst(inst):
result = elaborate_inst(value.inst, bb, before)
elaborated[value] = result
return result
else:
return value
이 수정된 알고리즘은 단일 블록에서 재사용이 있는 경우를 효율적으로 처리하여, 예상대로 값을 처음 사용될 때(“수요 기반으로”) 계산합니다.
이제 여러 기본 블록을 생각해봅시다. Sea-of-nodes로의 변환 때처럼, 위 알고리즘을 순회로 감싸고 싶을 수 있습니다:
def elaborate_domtree(bb):
demand_based_elaboration(bb)
for child in domtree.children(bb):
elaborate_domtree(child)
def elaborate(func):
elaborate_domtree(func.entry)
하지만 이것도 문제가 있습니다. 많은 경로를 가진 CFG에서 그중 두 경로가 같은 값을 계산하는 프로그램을 생각해봅시다:
위와 같은 elaboration을 수행하기 위해 전체 기본 블록을 순회하면서 하나의 elaborated 맵을 사용하면, 우리는 다음과 같이 됩니다.
bb2에서 v2 계산을 elaboration하고 거기서 사용한다.bb3에서도 그것이 이미 계산되어 메모이즈되었으므로 v3 대신 그것을 사용한다.어쩌면 계산을 모든 사용의 “공통 조상”으로 끌어올릴 수도 있을 겁니다. 여기서는 bb1이 되겠죠. 하지만 그러면 또 다른 문제가 생깁니다. 제어 흐름이 bb1에서 bb4로 가면, 그 값은 계산만 되고 전혀 사용되지 않게 됩니다—최적화되었다고 하는 코드에서 말이죠! 이것은 때때로 “부분 중복성(partial redundancy)”이라고 불립니다. 제어 흐름에 따라 때로는 사용되지 않는 계산입니다. 가능하다면 이것을 피하고 싶습니다.
알고 보니 이 문제는 정확히 공통 부분식 제거 (CSE)에 대응합니다. CSE는 여러 번 사용될 수 있는 값을 한 곳에서 계산할 위치를 찾으려는 것입니다. SSA 코드에서 흔히 쓰는 접근인 global value numbering (GVN)은 값이 이미 계산된 영역인 _범위(scope)_를 추론함으로써 문제를 해결합니다. 직관적으로는, 어떤 사용 지점에서든 아래쪽으로 “그림자”를 드리워서 그 그림자 안에서만 중복 사용을 제거할 수 있습니다. 따라서 예제 프로그램에서 bb1이 v2를 계산했다면 bb2와 bb3에서 그것을 재사용할 수 있습니다. 하지만 공통 조상이 없는 두 서브트리에서 독립적으로 발생한다면, 아무것도 하지 않습니다. 우리는 그것을 _복제_합니다(다시 elaboration합니다).
SSA의 “범위”—어떤 값을 사용할 수 있는 영역—는 지배 관계로 정의되므로, 필요한 동작을 구현하기 위해 domtree 순회를 사용할 수 있습니다. 구체적으로는 domtree 전위 순회를 하고, elaborated 맵을 유지하되 그것을 범위 “오버레이”들로 나누고, 각 서브트리마다 새 오버레이를 푸시할 수 있습니다. 이것이 위의 “그림자” 직관을 형식화한 것입니다. 이를 _범위화된 elaboration_이라고 부릅니다. 의사코드는 다음과 같습니다:
def find_in_scope(value, scope):
if value in scope.map:
return scope.map[value]
elif scope.parent:
return find_in_scope(value, scope.parent)
else:
return None
def elaborate_value(value, bb, before, scope):
if find_in_scope(value, scope):
# ...
# ...
def elaborate_domtree(bb, scope):
demand_based_elaboration(bb, scope)
for child in domtree.children(bb):
subscope = { map = {}, parent = scope }
elaborate_domtree(child, subscope)
def elaborate(func):
root_scope = { map = {}, parent = None }
elaborate_domtree(func.entry, root_scope)
우리의 실제 구현은 오버레이 레이어 사이에서 키가 겹치지 않는다는 사실(한 번 정의된 값은 아래 레이어에서 다시 정의되지 않기 때문입니다)을 활용하고, layer 번호와 레이어별 generation을 이용한 몇 가지 기법으로 조회를 O(depth)가 아니라 진정한 O(1)로 만듭니다(자세한 것은 구현을 보세요!). 그래도 의미론은 위와 같습니다.
위에서 미리 암시했듯, 이 문제가 CSE와 GVN과 밀접하게 관련되어 있는 것처럼, 범위화된 elaboration도 마찬가지입니다. 사실 domtree 전위 순회가 주어졌을 때, domtree의 서브트리에 대응하는 범위 안에서 “범위 내 정의”를 추적하는 접근은 Cranelift의 이전 구현도 정확히 그렇게 동작합니다. 우리는 범위화된 해시맵 구현도 거기서 가져왔습니다!
조금 더 관찰할 점이 있습니다. 첫째, 어떤 노드를 여러 dom 서브트리 안으로 _다시 elaboration_하는 경우가 있다는 점은 꽤 흥미롭습니다. 왜 그럴까요? 이것이 비효율성(예: 코드 크기 측면)을 도입하는 걸까요, 아니면 최선일까요?
제 생각에 이런 복제는 정규화의 _쌍대_로 보는 것이 가장 좋습니다. 원래 코드에는 어떤 순수 계산이 여러 경로에 여러 복사본으로 존재할 수 있는데, 그 값을 계산하는 공통 조상이 없을 수 있습니다. Sea-of-nodes로 번역할 때는 그 계산을 정규화해서 한 번만 최적화할 수 있습니다. 하지만 원래의 선형화된 IR로 돌아갈 때는, 정말로 (중복성을 만들지 않는) 최적화 기회가 없었다면 원래의 복제를 복원해야 할 수도 있습니다.
이 말은, 어떤 값이 원래 프로그램에 한 번만 나타났더라도 때로는 그것을 둘 이상의 장소에 elaboration하게 된다는 뜻입니다. 예를 들어 if/else 분기 위에 있던 순수 계산이 실제로는 if/else 가지 내부에서만 사용된다면, 그것은 그 분기 경로 안으로 “가라앉을” 수 있습니다. 어떤 후속 경로에서 항상 사용되는 것이 아니라면 이것을 최적화로 볼 수도 있겠지만, 어쨌든 값이 모든 후속 경로에서 반드시 사용되는지 아닌지를 증명할 분석은 아직 없습니다. 따라서 이런 경우 프로그램 크기가 원본보다 커질 수 있습니다. (이전의 잘못된 버전 글에서 이것을 지적해 준 Jamey Sharp에게 깊이 감사드립니다!)
또 다른 흥미로운 관찰은, 부작용 있는 CFG 스켈레톤의 루트들에서부터 수요 기반으로 elaboration을 구동함으로써 순수 연산의 죽은 코드 제거(DCE)를 공짜로 한다는 점입니다. 그 노드들이 sea-of-nodes에 존재하는 사실 자체는, 우리가 그것들을 최적화하느라 노력을 들였다가 나중에 버리게 된다면 컴파일 시간을 좀 먹을 수 있습니다. 하지만 sea-of-nodes 안의 재작성 때문에 죽게 된 것은 최종 결과에서 자연스럽게 사라집니다.
세 번째 관찰은, elaboration이 최종 프로그램에서 코드가 언제 어디에 놓이는지를 제어하는 중심 위치를 제공한다는 점입니다. 다시 말해, 위에서 설명한 가장 단순한 알고리즘 버전 너머로 _휴리스틱_을 추가할 여지가 있습니다. 예를 들어, 우리는 부분 중복성을 도입하고 싶지 않다고 말했습니다. 하지만 정당성 관점에서는 꼭 그 제약을 지킬 필요는 없습니다. 우리의 진짜 제약은 오직 순수 계산이 그 인자들이 계산되기 전에 일어날 수 없다는 것뿐입니다(즉 데이터 흐름 의존성을 지켜야 합니다). 따라서 예를 들어 프로그램의 _루프 중첩 구조_를 알고 있다면, 루프 안의 순수 계산이 그 루프 안에서 계산되는 어떤 값도 사용하지 않는 경우, 그것이 _루프 불변_임을 알 수 있고, 루프가 시작되기 전(“preheader”)에 elaboration하도록 선택할 수 있습니다. 이것이 바로 loop-invariant code motion (LICM)입니다. 루프가 0회 반복되면 중복 계산이 되지만, 대부분의 루프는 적어도 한 번은 실행됩니다. 그리고 루프 불변 계산을 한 번만 수행하는 것은 큰 효율 향상이 될 수 있습니다.
반대로—계산을 위로 끌어올리는 대신 아래로 미는 방향에서는—이미 elaboration된 범위에서 어떤 값을 전략적으로 잊어버리고, 새로운 사용 시점에서 다시 계산함으로써 _재물질화_를 구현할 수 있습니다. 왜 이런 일을 할까요? 어쩌면 원래 값을 프로그램 전체에 _꿰어 전달하는 것_보다 다시 계산하는 것이 더 쌀 수 있기 때문입니다. 예를 들어 상수 값은 “계산” 비용이 매우 작습니다(보통 1개 또는 2개의 명령어). 하지만 긴 함수 전체에 걸쳐 상수를 유지하기 위해 기계 레지스터를 태우는 것은 비쌀 수 있습니다.
또한 elaboration 내부에서의 휴리스틱 _코드 스케줄링_에도 많은 여지가 있습니다(LICM과 재물질화도 스케줄링으로 볼 수 있지만, 여기서 말하는 것은 그 외에 블록 내부에서 연산들을 어떤 순서로 선형화할지입니다). 현대의 out-of-order CPU에게는 이것이 하드웨어 측면에서 크게 중요하지 않을 수도 있습니다. 하지만 레지스터 할당기에는 중요할 수도 있습니다. 명령어 재배치는 “간섭 그래프”, 즉 서로 다른 live 레지스터 값들이 제한된 자원(하드웨어 레지스터)을 두고 경쟁하는 방식을 바꾸기 때문입니다. 예를 들어, 많은 값을 마지막으로 사용하는 명령어를 더 “이르게” 당겨서(그 값들을 저장할 필요를 없애기 위해) 배치하는 것은 좋습니다. 하지만 이런 최소화가 항상 간단하지는 않습니다. 사실 정의와 사용을 갖는 명령어의 순서를 정해 결과적인 live-range 간섭 그래프의 coloring 수를 최소화하는 문제는 NP-완전입니다. 컴파일러 엔지니어링에서는 너무 자주 그렇듯이 말입니다!
많은 휴리스틱을 결합할 때 생길 수 있는 복잡성에도 불구하고, 이 세 가지 차원—LICM, 재물질화, 그리고 레지스터 압박을 위한 코드 스케줄링—은 흥미로운 고차원 비용 최적화 문제이며, 우리는 여전히 이를 완전히 해결하지 못했습니다(#6159, #6260, #8959 참조).
이제 sea-of-nodes-with-CFG 프로그램 표현으로 들어가는 전환과 나오는 전환을 살펴봤습니다. 이 번역만으로도 GVN(중복 제거), DCE, LICM, 재물질화가 “공짜로” 생긴다는 것을 봤습니다(진짜 공짜는 아니지만, 알고리즘의 자연스러운 귀결로 나온다는 뜻입니다). 하지만 아직도 가장 고전적인 최적화 집합 중 하나, 즉 한 표현식을 다른 동치 표현식으로 바꾸는 대수적(및 기타) 재작성(x+0을 x로 바꾸는 것 등)은 다루지 않았습니다. 이것을 sea-of-nodes에서 어떻게 할 수 있을까요?
원칙적으로 답은 “단순하게” 이렇습니다. 재작성의 “왼쪽 항” 패턴(우리가 더 “나은” 동치 표현식을 아는 부분)에 매칭하는 로직을 만들고, 그것을 “오른쪽 항”으로 대체하면 됩니다. 즉 x + 0 -> x에서 왼쪽 항은 x + 0, 오른쪽 항은 x입니다. 이런 프레임워크는 재작성을 표현하기 위한 _도메인 특화 언어_와 매우 잘 맞습니다. 이상적으로는 이런 패턴을 찾기 위해 노드를 직접 순회하는 코드를 쓰고 싶지 않을 테니까요. 다행히 Cranelift 프로젝트에는 ISLE (instruction-selection and lowering-expressions) DSL이 있습니다(RFC, 언어 레퍼런스, 블로그 글). 저는 원래 이름이 암시하듯 명령어 lowering 맥락에서 ISLE를 설계했지만, 핵심 언어와 특정 환경에 바인딩하는 “prelude”는 분리되도록 신경 썼습니다. 덕분에 Cranelift IR 연산자 그래프를 재작성하는 쪽으로도 꽤 쉽게 적응시킬 수 있었습니다. 아이디어는 명령어 lowering에서와 마찬가지로, 미드엔드 최적화에서는 특정 노드에 대해 ISLE 생성자(진입점)를 호출하면 규칙 집합이 더 나은 노드를 반환할 수 있다는 것입니다.
이것은 하나의 표현식에 대한 로직은 제공하지만, 여전히 재작성을 어떻게 적용할지는 열린 질문으로 남습니다. 어떤 노드들에, 어떤 순서로 적용할지, 그리고 노드가 재작성되었을 때 그 노드의 사용을 어떻게 관리하거나 갱신할지 말입니다.
일반적으로 고려할 수 있는 두 가지 설계 축이 있습니다:
즉시 적용(eager)인가 지연(deferred)인가: 노드가 생기자마자 재작성을 적용할 것인가, 아니면 나중에(일괄 재작성 같은 형태로) 적용할 것인가?
단일 재작성인가 고정점 루프인가: 노드를 한 번만 재작성할 것인가, 아니면 재작성 결과에 다시 규칙을 적용할 것인가? 또한 노드의 피연산자가 재작성되면, 새 서브트리에 더 많은 트리 매칭 패턴이 적용될 수 있으므로 그 노드의 사용자들도 재작성해야 하는가, 한다면 어떻게 할 것인가?
이 질문들에 대한 선택이 효율성과 품질 간의 서로 다른 절충으로 이어질 수 있다는 것은 분명합니다. 가장 분명하게는, 고정점까지 재작성을 적용하면 컴파일 시간이 더 길어지는 대가로 더 좋은 코드를 생성할 것입니다. 하지만 그뿐 아니라, 작업 부하와 구체적인 규칙에 따라 즉시 처리와 지연 처리 중 어느 쪽이 더 유리할지도 달라질 수 있어 보입니다. 일괄 처리(즉, 한꺼번에 한 번의 패스에서 지연 적용)는 종종 효율상의 장점을 가집니다(egg 논문과 아래 논의 참조!). 하지만 지연은 반대로, 곧 낡아질 원래 값을 사용하기 전에 즉시 재작성하는 것보다 더 많은 bookkeeping을 필요로 할 수 있습니다.
지금까지 설명한 전체 설계에 대해서는 놀랍게도 상당히 분명한 최적의 답이 있습니다. 비순환적인 sea-of-nodes를 만든다는 점 때문에, 재작성 동안에도 그것을 비순환적으로 유지하기만 하면 고정점 대신 한 번의 재작성 패스로 충분해야 합니다. 그리고 그 한 번의 패스가 동작하게 하려면, 노드를 만들자마자 즉시 재작성하고, 원래 값의 모든 사용에는 그 노드의 최종 재작성 버전을 사용합니다. 정의를 사용보다 먼저 방문하고, 정의 지점에서 즉시 재작성을 수행하기 때문에, 노드가 생성된 뒤에 그것을 갱신하고(그리고 다시 정규화하고!) 할 필요가 없습니다.
여기서 잠깐 곁길 설명이 필요합니다. Sea-of-nodes-with-CFG가 처음에는 비순환이라는 것이 왜 분명한지는 비교적 명확합니다. SSA에서는 데이터 흐름 사이클이 block-parameter / phi-node를 통해서만 허용되며, 그것들은 CFG에 남아 있고 재작성을 적용할 때 우리는 그것들을 “들여다보지” 않기 때문입니다. 하지만 재작성이 왜 _비순환성을 유지하는지_는 덜 명확합니다. 특히 hash-consing이 부주의할 경우 사이클의 “매듭을 묶어” 버릴 수 있기 때문입니다. 답은 앞 단락에 있습니다. 노드를 한 번 만들면, 절대 갱신하지 않습니다. 그게 전부입니다! 이렇게 해서 우리는 구성에 의해 비순환성을 유지합니다.
놀랍게도 이 재작성 과정은 sea-of-nodes 자체로의 변환 패스와 _융합_될 수 있습니다. 따라서 위의 canonicalize를 다음과 같이 바꿀 수 있습니다:
def canonicalize(basic_block):
for inst in basic_block:
if is_pure(inst):
# ...
if inst in hashcons_map:
# ...
else:
inst = rewrite(inst) # NEW
nodes.push(inst) # sea-of-nodes에 추가
hashcons_map[inst] = inst.value
else:
# ...
즉, 단순히 노드를 생성하는 곳에서 재작성 규칙 적용을 추가하고, 명령어의 최종 버전을 기준으로 hash-cons를 하면 됩니다.
물론 이것만으로는 아직 완전하지 않습니다. inst = rewrite(inst)가 많은 일을 암시하고 있는데, 사실 조금 지나치게 단순합니다. 왜냐하면 이것은 재작성 규칙이 오른쪽 항에서 항상 하나의 명령어로만 재작성된다는 뜻이 되기 때문입니다. 하지만 실제로는 그렇지 않습니다. 예를 들어 DeMorgan 재작성 규칙 ~(x & y) -> ~x | ~y를 원할 수 있습니다. 오른쪽 항에는 세 개의 연산자 노드(명령어)가 있습니다. 두 개의 비트 NOT과 그것들을 사용하는 OR입니다. 그리고 이 패턴의 x나 y가 어떤 논리 규칙으로 단순화될 수 있는 부분식을 매칭하는 경우라면 어떨까요?
여기에는 두 가지 일반적인 답이 있는 것 같습니다. 오른쪽 항의 원래 노드들을 재작성하지 않은 채 만들고 나중에 재작성을 적용하거나, 즉시 그리고 재귀적으로 재작성하는 것입니다. 위에서 관찰했듯 지연은 노드 입력이 바뀔 때 추가 bookkeeping과 재정규화를 요구하므로, 우리는 재귀적 접근을 선택합니다. 따라서 구체적으로 ~((a & b) & (c & d))와 위의 한 가지 재작성 규칙이 주어졌을 때, 우리는 다음과 같이 합니다:
~를 만나고, 재작성 규칙의 왼쪽 항과 매칭을 시도합니다. 그러면 바인딩 x = (a & b)와 y = (c & d)로 매칭됩니다.~x | ~y를 아래에서 위로 적용하며, 가는 길에 노드를 만들고 재작성합니다:
~x. 이것은 ~(a & b)를 만들고, 이것이 재귀적으로 규칙을 다시 발동시켜 (~a | ~b)가 됩니다.~y. 이것은 ~(c & d)를 만들고, 다시 재귀적으로 규칙을 발동시켜 (~c | ~d)가 됩니다.(~a | ~b) | (~c | ~d)를 얻습니다.규칙 체인의 깊이가 정적으로 제한되지 않거나 분석하기 어렵다면 재귀를 제한할 필요가 있지만, 그렇지 않다면 이 방법은 노드의 사용자를 추적해서 나중에 재작성하고 재정규화할 필요 없이 한 번의 패스로 올바른 답을 제공합니다.
이것이 전체 파이프라인입니다. 이제 우리는 sea-of-nodes-with-CFG로 번역하고, 그 과정에서 재작성을 적용하며, 다시 고전적인 SSA CFG로 번역함으로써 코드를 최적화할 수 있습니다. 그리고 그 과정에서 우리가 목표로 했던 모든 것—GVN, LICM, DCE, 재물질화, 대수적 재작성—을 달성했습니다.
지금까지 우리는 어떤 주어진 노드에 대해 _0개 또는 1개_의 결정적 재작성만 있는 시스템을 설명했습니다. 이것은 고전적인 컴파일러 파이프라인이 명령어나 연산자를 파괴적으로 갱신하는 방식과 유사합니다. 이는 x+0 -> x 같은 재작성 규칙에는 아주 좋습니다. 오른쪽 항이 “더 작아서” (표현식 전체를 그 일부 하나로 바꾸므로) 모호함 없이 더 낫기 때문입니다. 또한 정수 나눗셈(현대 CPU에서도 보통 수십 사이클 이상)이 상수에 대해 마법의 wrapping multiply로 변환되는 것처럼, 명령어들의 비용 차이가 분명하고 큰 경우에도 괜찮습니다.
하지만 어떤 재작성의 이점이 덜 분명하거나, 문맥에 의존하거나, 주어진 프로그램 안에서 다른 재작성을 조합하거나 활성화할 수 있는지 여부에 따라 달라지는 경우는 어떨까요?
예를 들어 egg라는 e-그래프 프레임워크에 대한 2021년 논문의 고전적 예를 생각해봅시다. 프로그램 안에 (x * 2) / 2라는 표현식이 있다면, 우리는 이것이 x로 단순화되기를 기대합니다1. 이 단순화를 구현하기 위해 일반적인 재작성 규칙 (x * k) / k -> x를 둘 수 있습니다. 하지만 별도로 (x * 2^k) -> (x << k)라는 재작성 규칙도 둘 수 있습니다. 즉 곱셈을 왼쪽 시프트로 바꾸는 규칙입니다. 후자의 재작성을 즉시 수행해버리면, 전자의 재작성은 영영 매칭되지 않을 수도 있습니다.
(물론 여기서 “그렇다면 나눗셈도 오른쪽 시프트로 바꾸고, (x << k) >> k -> x라는 재작성 규칙을 두면 되지 않느냐”고 말할 수도 있습니다. 이 특정 예에서는 그럴 수 있습니다. 하지만 (i) 그러려면 2의 거듭제곱에 대한 곱셈/나눗셈이 항상 시프트로 정규화된다는 정규형에 대해 세심한 생각이 필요했고, (ii) 이런 운 좋은 행동이 모든 규칙 집합에 대해 존재하는 것은 아닐 수 있습니다.)
일반적으로 규칙 적용 수준에서도 질문이 있습니다. 여러 규칙이 적용되면 무엇을 선택할까요? 위 예에서는 예를 들어 strength-reduction 규칙을 먼저 적용해 시프트로 바꾸고, 그다음 곱셈의 나눗셈을 살펴보는 식의 우선순위 체계가 필요했을 겁니다. 이것은 최적화기를 설계할 때 고려해야 할 또 하나의 휴리스틱 엔지니어링 층입니다.
이제 새로운 자료구조인 e-그래프 또는 _동치 그래프_가 등장합니다. 이것은 일종의 sea-of-nodes 프로그램/표현식 표현으로, 프로그램의 서로 다른 많은 동치 형태를 한꺼번에 표현할 수 있습니다. 핵심 아이디어는, 어떤 값에 대해 하나의 표현식 노드만을 참조 대상으로 갖는 대신, 여러 e-node를 담는 e-class(동치 클래스)를 두고, 이 e-node들 중 어느 것이든 그 값을 계산하는 데 선택할 수 있다는 것입니다.
이 아이디어는 최적화 문제에 대한 일종의 원칙적인 접근입니다. 상태 공간을 명시적으로 모델링하고, 그다음 객관적으로 가장 좋은 결과를 선택하자는 것입니다. 보통 e-그래프는 비용 메트릭에 따라 프로그램의 한 가능한 표현을 “추출(extract)”하는 방식으로 사용됩니다. (이에 대해서는 아래에서 더 다루겠지만, 단순한 비용 메트릭은 연산자 종류당 정적인 수치에 입력 비용을 더하는 것일 수 있습니다.)
E-그래프의 마법은 동치인 프로그램들의 매우 큰 조합적 공간을 작은 자료구조로 _압축_할 수 있다는 점입니다. 이것이 어떻게 가능한지에 대한 자세한 설명은 이 글의 범위를 벗어나니, egg 논문을 꼭 읽어보시길 권합니다. 아주 훌륭합니다! 다만 아주 짧고 직관적인 요약을 하자면 대략 이렇습니다:
모든 값 사용이 특정 노드가 아니라 _e-class_를 가리키도록 하면, 동치에 대한 지식이 가능한 최대한 많은 곳으로 전파됩니다. 즉 op1 v1, v2가 op2 v3, v4와 동치라는 것을 알게 되면, op1 v1, v2 표현식을 사용하는 모든 사용자도 자동으로 어떤 형태든 사용할 수 있다는 지식을 얻게 되어야 합니다. 이런 지식 전파가 바로 e-그래프가 가능하게 하는 “equality saturation”의 본질입니다.
강력한 정규화와 “재-interning”(재-hashconsing) 체계—egg 논문에서는 이를 “rebuilding”이라고 부릅니다—는 그러한 정보가 최대한 전파되도록 보장합니다. 기본적으로 위의 op1과 op2 표현식이 동치라는 사실을 발견하면, 그 둘의 모든 사용자를 다시 처리하여 더 많은 후속 결과를 찾습니다. 그 둘을 병합하면 다른 표현식들도 동치가 되거나 다른 재작성 규칙이 발동할 수 있습니다.
“고전적 e-그래프”(여기에는 2021년 egg 논문의 일괄 rebuilding 방식도 포함합니다)에서 발생하는 두 가지 문제는 폭증(blowup)—즉 너무 많은 재작성 규칙이 적용되어 e-그래프가 너무 커지는 것—과 _자료구조 비효율성_입니다.
폭증 문제는 이해하기 쉽습니다. 프로그램의 서로 다른 많은 형태를 표현하도록 허용하면, 너무 많은 형태를 표현하게 되어 메모리와 처리 시간이 바닥날지도 모릅니다. 규칙들이 서로 조합되어 폭증으로 이어지는 방식을 제어하기도 종종 어렵습니다. 각 재작성 규칙은 개별적으로는 합리적으로 보일 수 있지만, 잘 발달한 동치 집합 아래 가능한 모든 프로그램의 추이적 폐쇄는 엄청날 수 있습니다. 그래서 e-그래프의 실용적 응용은 보통 노력을 제한하기 위한 “fuel” 같은 메타/전략 드라이버 층이 필요하고, 또는 더 나은 결과로 이어질 가능성이 높은 곳에서만 선택적으로 재작성을 적용해야 합니다. 그래도 이런 운용 방식은 종종 컴파일 시간이 몇 초 이상으로 측정됩니다. 이는 컴파일이 한 번 또는 드물게 일어나고 결과 품질이 극도로 중요한 최적화 문제(예: 하드웨어 설계)에는 적합할 수 있지만, Cranelift 같은 빠른 컴파일러에는 맞지 않습니다.
물론 세심한 휴리스틱으로 그런 결과를 막을 수는 있습니다. 그리고 가능한 최적 표현을 객관적으로 선택할 수 있다는 가능성은 여전히 매우 매력적입니다. 그래서 초기 실험에서 저는 egg crate를 문제에 적용했고, 결국 맞춤형 수정까지 더해 e-그래프 왕복(roundtripping) 자체를 23% 오버헤드까지 낮출 수 있었습니다—재작성은 하나도 적용하지 않은 상태에서요. 얼핏 보면 나쁘지 않지만, 이것은 전체 컴파일 시간의 10% 정도만 차지하는 기존 최적화 파이프라인을 대체하겠다는 이야기입니다. 게다가 아직 그 23% 위에 재작성을 추가하지도 않았습니다. (그리고 이 23%도 저장 공간을 줄이기 위한 상당한 자료구조 엔지니어링 끝에 나온 결과입니다. 초기 오버헤드는 2배를 넘었습니다.)
최적화기의 실행을 프로파일링해보면, 오버헤드는 대체로 _e-그래프를 구축하는 과정 자체_에서 발생하고 있었습니다(즉 IR을 e-그래프로 전사하는 코드 전반에서 캐시 미스가 발생하고 있었습니다). 그런데 e-그래프 안에는 무엇이 들어 있을까요? e-class마다 “부모 포인터” 목록이 들어 있습니다. e-class들이 병합될 때(새로운 동치를 발견할 때) “rebuild” 단계에서 사용자들을 다시 정규화해야 하므로, 모든 e-class의 사용자를 추적해야 합니다. 그리고 더 근본적으로는 e-node를 e-class와 별도로 저장합니다. 이것은 아이디어의 핵심 요소이긴 하지만, 대부분의 e-class가 e-node를 하나만 가질 때조차 값 하나당 (적어도) 두 종류의 다른 엔티티를 가지게 된다는 뜻입니다.
한 값에 대해 그렇게 많은 조각을 저장하지 않아도 되도록 자료구조를 단순화할 방법은 없을까요?
Cranelift에서 효율적인 e-그래프 구현을 가능하게 한 첫 번째 큰 통찰은, 함수 본문 전체를 e-그래프로 복사했다가 다시 되돌리지 않고도 기존 IR 자체를 _암묵적 e-그래프_로 재정의할 수 있다는 점이었습니다. 이렇게 하면 이런 데이터 이동에 따른 컴파일 시간 패널티를 피할 수 있습니다. (프로그램의 핵심 루프들이 이미 꽤 최적화되어 있을 때는 데이터 이동이 매우 비쌀 수 있습니다! 가능하면 데이터를 제자리에서 유지하고 그 위에서 바로 연산하는 것이 최선입니다.)
우리는 기본 블록에 배치되지 않은 SSA 값을 가진 sea-of-nodes-with-CFG에서 시작합니다. Cranelift의 IR인 CLIF에서는 기존 SSA 정의를 CFG에서 제거하되, 그 데이터는 data-flow graph(DFG) 자료구조 안에 남겨두는 방식으로 이것을 이미 제자리에서 구성할 수 있습니다.
그다음 e-그래프에서 다중 표현을 허용하기 위해, e-class와 e-node의 분리를 버리고, 대신 union 노드라는 새로운 종류의 IR 노드를 정의하는 것이 아이디어입니다. e-node와 e-class를 위한 두 개의 인덱스 공간 대신, 하나의 인덱스 공간, 즉 SSA 값 공간만을 갖습니다. SSA 값은 기존처럼 일반 연산자 결과이거나 블록 매개변수이거나, 또는 두 다른 SSA 값의 _union_입니다. 그러면 임의의 e-class는 union 노드의 이진 트리로 표현할 수 있습니다. 이 표현을 사용하기 위해 연산자 인자에 대해 바꿔야 할 것은 아무것도 없습니다. 연산자는 이미 값 번호를 참조하고 있으며, 여러 e-node를 가진 e-class(그 union 트리의 “맨 위” union 노드로 정의되는)는 이미 값 번호를 가지고 있기 때문입니다.
이 표현의 가장 멋진 점은, sea-of-nodes가 일단 있으면 그것이 _이미 암묵적으로 e-그래프_라는 것입니다. 각 e-node마다 “자명한” (원소가 하나뿐인) e-class가 있는 셈이죠. 따라서 sea-of-nodes에서 e-그래프로의 승격은 아무 일도 하지 않는 no-op입니다—컴파일 시간 패스 중에서 가장 좋고(그리고 가장 싼) 종류죠. 다중 표현을 실제로 사용할 때만, 필요에 따라 union 노드를 만들면서 비용을 지불합니다.
고전적 e-그래프 자료구조 비용의 또 다른 측면은 _rebuild_가 필요하다는 점, 그리고 그를 위해 e-class의 모든 사용(egg 용어로는 “부모”)을 추적해야 한다는 점과 관련이 있습니다. Cranelift는 양방향 use-def 링크를 유지하지 않으며, union 노드의 이진 트리는 이를 추적하는 일을 더욱 복잡하게 만듭니다.
이 비용을 해결하려고 하면서, 저는 다소 급진적인 질문에서 시작했습니다. 동치 전파를 위해 절대 rebuild를 하지 않는다면 어떻게 될까? 그렇게 해도 얼마나 많은 “최적화의 이익”을 얻을 수 있을까?
만약 (i) e-그래프를 구축한 다음 (ii) 재작성 규칙을 적용해 더 나은 버전의 노드를 찾아 e-class에 추가한다면, 답은 거의 동작하지 않는다는 것입니다. 왜냐하면 그러면 어떤 값의 모든 사용자는 그 값의 초기 형태만 보고, 그 재작성 형태는 결코 보지 못하기 때문입니다. 재작성된 형태들은 sea-of-nodes 안에 떠다니고, 그것들을 원래 형태와 잇는 union 노드는 존재하겠지만, 실제로 어떤 사용자도 그 union 노드를 참조하지 않을 것입니다.
대신 필요한 것은 재작성을 즉시 적용하는 것입니다. Sea-of-nodes에서 새 노드를 만들 때, 즉시 모든 재작성을 적용하고, 그 재작성 결과들을 원래 형태와 union 노드로 연결합니다. 그러면 그 union 트리의 “맨 위”가 원래 값의 “최적화된 형태”로 사용되는 값 번호가 되고, 이후의 모든 사용이 그것을 참조합니다.
Union 노드 표현은 이 이야기의 핵심 역할을 합니다. 이것은 일종의 _불변 자료구조_처럼 동작합니다. 우리는 항상 새 지식을 덧붙이고 기존 값들과 union하여 e-class의 “더 새로운 버전”을 참조하지만, 기존 참조를 돌아가서 갱신하지는 않습니다.
이것은 노드의 바다의 그래프 구조에도 아주 좋은 함의를 갖습니다. 바로 비순환성을 보존한다는 것입니다! 고전적인 e-그래프는 rebuild 단계에서 노드를 임의로 압축할 수 있기 때문에 입력이 비순환이어도 사이클을 만들 수 있습니다. 하지만 즉시 재작성한 뒤 얼려버리는 방식에서는, 절대로 “매듭을 묶어” 사이클을 만들 수 없습니다.
이 비순환성은 중요합니다. 왜냐하면 재작성을 _한 번의 패스_로 가능하게 해주기 때문입니다. 사실 위의 sea-of-nodes 구축 알고리즘을 기준선으로 삼으면, 즉시 재작성은 아주 작은 변경만으로 추가할 수 있습니다. 재작성을 적용할 때, 재작성된 형태만 파괴적으로 취하는 대신 모든 재작성된 형태를 연결하는 “union-node spine”을 만드는 것입니다.
def canonicalize_and_rewrite(basic_block):
for inst in basic_block:
if is_pure(inst):
# ...
if inst in hashcons_map:
# ...
else:
optimized = rewrites(inst) # NEW
union = join_with_union_nodes(inst, optimized) # NEW
optimized_form[inst.def] = union
else:
# ...
이 모든 측면은 함께 작동하며, 사실상 분리할 수 없습니다:
여기서 우리는 재귀적 재작성을 생략하고 있다는 점에 유의하세요. 분량상 문제와 해법을 간단히만 개요하겠습니다. 재작성 규칙 적용의 오른쪽 항(rewrites 위 의사코드)은 그 자체로 추가 재작성을 유발할 수 있는 노드들을 만들어낼 수 있습니다. 고전적 e-그래프 드라이버처럼 이것을 또 다른 재작성 루프 반복으로 미루는 대신, 우리는 사용이 생기기 전에 이 오른쪽 항도 즉시 재작성하고 싶습니다. 그래서 rewrites를 재귀적으로 다시 호출합니다. 그리고 이것은 규칙 오른쪽 항의 일부 조각들이 만들어질 때마다 조각 단위로 발생합니다. 이 재귀는 폭증을 막기 위해 (깊이와 최상위 루프 반복당 총 재작성 호출 수 모두에서) 엄격히 제한됩니다.
마지막으로, 이제 여러 재작성이 허용될 때 패턴 매칭/재작성 DSL인 ISLE를 재작성 문제에 어떻게 적용하는지에 대한 세부사항도 여기서는 생략하고 있습니다. 간단히 말하면, 우리는 언어를 확장해 “multi-extractor”와 “multi-constructor”를 허용했습니다. 우선순위로 하나의 규칙만 선택하고 모호성을 해소하는 대신, 적용 가능한 모든 규칙을 취합니다. 자세한 내용은 RFC에 있습니다.
이제 같은 값을 계산하는 여러 표현식을 대안으로 나타낼 수 있게 되었습니다. 그렇다면 이 프로그램을 어떻게 컴파일할까요? 이 표현식들을 모두 컴파일하는 것은 분명 말이 되지 않습니다. 모두 같은 비트를 만들기 때문에 하나만 있으면 됩니다. 그럼 무엇을 고를까요?
이것이 바로 _추출 문제_이며, 말로 하기는 쉽지만 의외로 어렵습니다(사실 NP-난해합니다). 어떤 주어진 값을 계산하는 데 가장 쉬운 (가장 싼) 표현식을 고르는 문제입니다.
왜 이것이 어려울까요? 먼저 쉬운 경우를 만들어봅시다. 함수의 반환값 같은 하나의 루트 표현식이 있고, 모든 순수 연산자로 이루어져 있다고 합시다. 그러면 이것은 선택의 트리를 형성합니다. 각 eclass는 그것을 계산할 enode 하나를 선택하게 하고, 그 enode의 인자들은 다시 선택을 가진 eclass들을 가리킵니다.
이 트리 형태의 선택에서는 모든 선택이 독립적입니다. 따라서 각 서브트리에 대해 최선의 선택을 고를 수 있고, 어떤 표현식 노드의 비용은 그 인자들의 최적 비용에 해당 노드 자체의 계산 비용을 더한 것으로 계산할 수 있습니다. 좀 더 형식적인 알고리즘 용어로 말하면, 이것은 최적 부분 구조입니다.
불행히도 공유 노드에 대한 참조 (즉 트리가 아니라 DAG)를 허용하는 순간, 이 좋은 구조는 사라집니다. 왜 그런지 보이기 위해, 우리가 계산하고 싶은 두 eclass가 있다고 합시다:
v0 = union v10, v11
v1 = union v10, v12
그리고 (표시는 생략했지만) v10은 계산 비용이 10이고, v11과 v12는 각각 7이라고 합시다. 각 하위 문제 수준에서의 최적 선택은 더 싼 계산(v11 또는 v12)을 고르는 것입니다. 하지만 프로그램 전체로는 v10만 한 번 계산하는 편이 더 최적입니다(총비용 10). 이것을 인식하려는 해법은 각 루트(v0와 v1)를 하나씩 처리하다가 추가 사용을 보고 어느 시점에서 “되돌아가야” 하거나, 아니면 더 이상 하위 문제 해법이 자연스럽게 조합되지 않는 형태의 공유 표현으로 문제를 구성해야 합니다.
실제로 추출 문제는 _NP-난해_합니다. 왜 그런지 보이기 위해, 알려진 NP-난해 문제인 weighted set-cover에서 eclass 추출로 가는 단순한 선형 시간 환원(매핑)을 보이겠습니다.
가중치 w를 가진 각 집합 S와 그 원소들 S = { x_1, x_2, ... }를 취합시다. 자기 비용(인자 비용 제외)이 w이고 인자가 없는 enode(연산자) N을 추가합니다. 그런 다음 우주(모든 집합의 원소들의 합집합)의 각 원소 x_n에 대해 eclass를 정의합니다. 즉 x_i가 있으면 eclass C_i를 정의합니다. 그리고 각 집합-원소 간선에 대해(각 i, j에 대해 x_i ∈ S_j이면), C_i에 enode를 추가하는데, 0 비용의 불투명 연산자 SetElt_ij(y)를 사용하고 y는 x_i의 eclass입니다.
이제 모든 eclass C_i를 루트로 하여 최적(최저 비용) 추출을 수행하면, 최저 가중치 set cover를 계산하게 됩니다. 각 eclass C_i에서 enode를 고르는 선택이 원소 x_i를 덮기 위해 어떤 집합을 선택했는지를 부호화하기 때문입니다. 즉 공유 구조가 있는 egraph 추출이 NP-난해 문제(weighted set cover)의 해를 계산할 수 있으므로, 공유 구조가 있는 egraph 추출은 NP-난해합니다.
좋습니다. 하지만 우리는 빠른 컴파일러를 원합니다. 그럼 어떻게 해야 할까요?
컴파일러 문헌에서 고전적으로 반복해서 등장하는 답은 “더 단순한 근사 문제를 푼다”입니다. 예를 들어 레지스터 할당은 결정 공간을 줄여 더 간단한 알고리즘을 가능하게 하는 단순화된 문제 모델(선형 스캔, live-range splitting 없음, …)로 가득합니다.
우리의 경우, 추출 문제를 다음과 같은 단순화 선택으로 해결합니다. 공유 서브구조와 그것이 비용 계산을 복잡하게 만드는 방식을 _고려하지 않겠다_는 것입니다. 다시 말해, 공유 서브구조를 무시하고, 서브트리를 사용할 때마다 그 서브트리의 비용이 새로 든다고 가정합니다. 각 enode에 대해 그 인자들의 비용을 이미 계산했다면, 그 노드의 비용은 인자 비용의 합에 그 노드 자체의 계산 비용을 더해 쉽게 구할 수 있습니다. 그리고 각 eclass에 대해서는 최소 비용 enode를 고르면 됩니다. 끝입니다!
우리는 이것을 동적 계획법 알고리즘으로 구현합니다. Aegraph를 위상 정렬(toposort)하고(비순환이므로 항상 가능합니다), 그다음 리프에서 위로 노드를 처리하면서 비용을 누적하고 각 하위 문제에서 최소값을 선택합니다. 이것은 단일 패스이며, 비교적 빠르고 직관적인 알고리즘입니다.
1월 Dagstuhl 세미나 이후, 이 부분에서 더 나은 방법이 있을지에 대해 협업자 Alexa VanHattum, Nick Fitzgerald와 지속적으로 논의했습니다. Alexa와 Nick은 여러 흥미로운 대안을 프로토타이핑했습니다. 서브트리가 사용되면 비용을 동적으로 갱신(0으로 shortcutting)하는 방식의 “sunk-cost” 계산, 아래에서 위로의 동적 계획 대신 완전한 위에서 아래로 순회를 통해 비용을 계산하고 거기에 메모이제이션을 섞는 방식, 공유를 고려하기 위해 DP를 하되 덮인 리프들의 전체 집합을 추적하는 방식, 그리고 그 외 몇 가지입니다. 흥미로운 탐색이었지만, 결국 컴파일 시간 / 실행 시간 절충 공간에서 더 나아 보이는 것을 찾지는 못했습니다. 이에 대한 추적 이슈가 있고, 물론 더 많은 아이디어는 언제나 환영입니다.
우리 aegraph 구현에는 이 글에서 다루지 못하는 두 가지 측면이 더 있습니다:
0을 만든다는 것을 알 수 있습니다. 그러면 iconst 0을 포함한 union 노드를 가질 수 있습니다. 로드는 현재 위치에서만 일어날 수 있지만, iconst 0은 어디서든 계산할 수 있습니다. 이 eclass의 사용자는 두 값 중 어느 것이든 선택할 수 있어야 합니다(다르게 말하면, 정당성을 위해 추출이 반드시 특정 선택을 하도록 부담을 져서는 안 됩니다). 사용자가 로드 아래의 지배 서브트리 안에 있다면 아무 문제가 없습니다. 하지만 그렇지 않고, 예를 들어 함수의 다른 곳에 있는 iconst 0의 다른 사용자가 우연히 eclass 이웃인 load 명령어를 집어들면, 잘못된 프로그램이 될 수 있습니다.여기에 대해서는 여러 해결책을 떠올릴 수 있겠지만, 결국 우리는 노드를 만들면서 함께 수행되는 “available block” 분석에 도달했습니다. 모든 노드에 대해, 그것이 계산될 수 있는 domtree 상에서 가장 “높은” 블록이 무엇인지 기록합니다. 순수한 0-인자 노드라면 함수 진입점, 비순수 노드라면 현재 블록, 그 외의 경우는 모든 인자의 available block들 중 domtree에서 가장 낮은 노드입니다. (주장: 어떤 노드의 모든 인자에 대한 available-node들은 domtree에서 조상 경로를 이룬다. 따라서 항상 나머지 모두에 의해 지배되는 하나가 존재한다. 이것은 SSA의 성질에서 따릅니다.) 그다음 hashcons 맵에 넣을 때는 최종 union이 사용 가능한 수준에 넣습니다.
subsume입니다. 이것은 재작성 규칙이 반환한 값을 감싸는 항등 연산자입니다. 정당성에 필수는 아니지만, 의미는 이렇습니다. 어떤 값이 “subsume”으로 표시되면, 그 “subsume하는” 값들은 eclass의 기존 구성원들을 지워버립니다. 보통은 하나의 subsuming 규칙만 매칭되지만(그렇다고 해서 이것도 정당성에 필수는 아닙니다).전형적인 사용 사례는 분명한 “방향성”을 가진 규칙입니다. 예를 들어 (iadd 1 1)보다 2라고 쓰는 편이 항상 더 좋습니다. 그렇다면 eclass를 더 작게 줄여서 이후의 모든 매칭과 최종 추출이 더 효율적이 되게 하자는 것입니다.
그렇다면 이 모든 것이 실제로는 어떻게 동작할까요? Aegraph는 Cranelift의 강점—코드를 최적화하는 능력, 그것을 빠르게 하는 효율성, 또는 둘 다—에 도움이 될까요?
여기서 제가 다소 놀라운 결론을 제시하게 됩니다. 이 글의 tl;dr은, 이 미드엔드의 sea-of-nodes-with-CFG 측면은 매우 잘 작동한다고 믿지만, aegraph 자체—즉 하나의 값에 대해 여러 선택지를 표현하는 능력—은 아직(?) 제 몫을 충분히 하고 있지 않을 수도 있다는 것입니다. 그렇다고 해서 크게 해를 끼치는 것도 아니니, 유지할 만한 기능일지도 모릅니다. 어쨌든 흥미로운 결론이니 아래에서 더 파고들어 보겠습니다.
가장 흥미로운 평가는 두 차원의 비교입니다. X축에는 컴파일 시간—즉 Cranelift가 코드를 컴파일하는 데 걸리는 시간—이 있고, Y축에는 실행 시간—즉 결과 코드가 실행되는 데 걸리는 시간—이 있습니다. 이것은 절충 공간을 이룹니다. 예를 들어 결과 코드가 더 빨라진다면 컴파일에 약간 더 시간을 써도 좋을 수 있고, 반대도 마찬가지입니다. 물론 둘 다 줄이는 것이 최선입니다. 어떤 점이 다른 점보다 둘 다 줄인다면, 그 점은 “엄격히 더 낫다”고 할 수 있습니다. 그러면 절충이 없고, 더 빨리 컴파일되고 더 좋은 코드를 내는 구성을 항상 고르게 됩니다. (이렇게 해서 서로 누구도 엄격히 우월하지 않은 점들의 집합인 Pareto frontier를 찾을 수 있습니다. 이는 목표에 따라 합리적으로 선택할 수 있는 “유효한 구성 지점”들입니다.)
아래는 Sightglass 벤치마크 스위트를 컴파일하고 실행했을 때의 여러 Cranelift 구성에 대한 컴파일 시간 대 실행 시간 그래프입니다:
주요 결과는 다음과 같습니다:
여기서 몇 가지 결론을 내릴 수 있습니다. 첫째, aegraph 파이프라인은 고전적 파이프라인보다 더 좋은 코드를 생성합니다. 이는 aegraph 노력의 원래 동기에 대해 “임무 완수”라고 할 수 있는 객관적 결과입니다. 우리는 최적화 패스들이 더 세밀하게 상호작용하고 더 완전하게 최적화되기를 원했습니다. 특히 고전적 파이프라인을 여러 번 반복해도 같은 결과에 도달하지 못한다는 점에 주목하세요. 새로운 최적화 프레임워크를 구축하지 않고서는 약 2%의 속도 향상을 얻을 수 없었습니다.
둘째, 하지만 “최적화 없음”, “고전적 파이프라인”, 그리고 aegraph 변형들을 모두 포함하는 Pareto frontier가 분명히 존재합니다. 각각 이전 것보다 더 많은 컴파일 시간을 필요로 합니다. 다시 말해, 고전적 컴파일러 파이프라인에서 여기 설명한 설계로 이동하면서, 우리는 컴파일 시간 약 7~8%를 더 씁니다. 흥미로운 점은, 이것이 우리가 2023년에 aegraph 구현을 처음 만들고 전환했을 때의 결과는 아니라는 것입니다. 당시에는 거의 대등한 수준이었습니다. 이는 아마 그 후 3년 동안 재작성 규칙 본문이 성장한 결과일 가능성이 큽니다.
Aegraph의 다양한 설계 선택이 어떻게 영향을 미치는지 더 잘 보기 위해, 위 그래프의 빨간 타원 안 영역을 확대해봅시다. 여기에는 aegraph 파이프라인의 여러 _변형_이 들어 있습니다:
그래프는 다음과 같습니다:
분명한 절충이 일부 보이긴 하지만, 축 스케일을 자세히 보면 이 효과들은 매우 매우 작습니다. 특히 sea-of-nodes-with-CFG에서 진정한 aegraph(모든 재작성 값을 취하고, 비용 기반 추출로 원칙적으로 최선을 고르는 것)로 가면, 실행 시간 약 0.1% 개선을 얻는 대신 컴파일 시간 약 0.005% 비용이 듭니다. 거의 잡음 수준입니다.
이 결론을 뒷받침하는 통계도 있습니다. 재작성 후 평균 eclass 크기가 1.13 enode라는 것입니다. 다시 말해, 우리의 규칙 집합과 벤치마크 코퍼스에서는 실제로 하나 이상의 선택지가 생기는 경우가 매우 적습니다.
마지막으로, 제 관점에서 가장 흥미로운 질문입니다. Aegraph의 즉시(eager) 측면—재작성 규칙을 바로 적용하고, 결코 돌아가서 다른 동치를 “채워 넣지” 않는 것—이 실제로 중요할까요? 다시 말해, equality saturation을 건너뛰면 egraph(유사체)에서 egraph다움이 빠지는 걸까요?
이 역시 측정할 수 있습니다. 저는 구현에 계측을 추가해서, 어떤 eclass의 서브트리가 추출에서 선택되지 않았는데, 그 서브트리의 어떤 노드가 나중에 실제로 elaboration되는 경우를 추적했습니다. 다시 말해, “잘못된 방향”의 동치를 볼 수 없어서 차선의 선택을 사용하는 경우입니다. 이것은 이론상 규칙이 f를 g로 재작성하는데 cost(g) > cost(f)이고, g를 f로 되돌리는 재작성이 없을 때만 일어나야 합니다. 그러면 g의 사용자는 즉시 방식으로 f의 재작성을 직접 얻지 못하지만, 나중에 우연히 생긴 f가 g로 재작성될 수는 있습니다(하지만 우리는 그 동치를 원래 g 사용자들에게 전파하지는 않습니다).
결과적으로, 전체 벤치마크에서 생성된 약 400만 개의 값 노드 중 이런 일이 일어난 것은 단 두(2) 번이었습니다. 두 사례 모두 spidermonkey.wasm에서 발생했습니다(SpiderMonkey JS 엔진을 WebAssembly로 컴파일한 뒤 Wasmtime+Cranelift로 실행하는 큰 벤치마크입니다). 그리고 둘 다 비용이 더 낮은 방향으로만 이동한다는 원칙을 위반하는 ireduce-of-iadd 재작성 규칙 때문이었습니다(명시적으로 단순성을 위해 그렇게 했습니다). 전반적으로 우리는 규칙 집합이 모든 동치 표현식을 탐색하는 것보다는 _최적화_를 염두에 두고 설계되어 있다면, 즉시 재작성이 효과적이라는 결론에 도달합니다.
모든 데이터 가운데 가장 놀라운 결론은, 적어도 저에게는, aegraph(그 자체) — 다중 값 표현 — 이 별로 중요하지 않아 보인다는 점이었습니다. 뭐라고요?! 그게 프로젝트의 핵심이었고, 제대로 된 e-그래프는 다른 응용 영역에서 큰 가능성을 보여주었는데 말이죠.
제 생각에 주된 이유는 우리의 작업 부하가 조합적 가능성 공간이라는 관점에서 다소 “작기” 때문입니다. 우리는 (i) Cranelift 컴파일 파이프라인에 들어오기 전에 이미 최적화된 경우가 많은(Wasmtime 모듈인) 작업 부하를 컴파일하고 있고, (ii) 규칙 집합이 크고 계속 늘어나고는 있지만(수백 개의 규칙), 결합법칙이나 교환법칙 같은 항등식, 또는 어떤 의미에서든 “단순화”되지 않는 임의의 대수적 항등식은 명시적으로 포함하지 않습니다. 다시 말해, 우리가 일반적으로 적용하는 재작성이 단순하고 자명한 “정리”에 가까운 것이라면, 아주 자주 여러 좋은 표현식 선택지의 “중첩 상태”를 들고 있을 것이라고 기대하기는 어렵습니다.
그럼에도 aegraph를 유지하는 데 컴파일 시간이 그리 많이 들지 않는다면, 이것은… 괜찮은 걸지도 모릅니다. 비용 기반 추출을 원칙적으로 할 수 있는 _능력_을 가지고 있다는 것은, 어떤 재작성 규칙이 존재해야 하는지 일일이 고민하는 것보다 훌륭합니다. 물론 우리는 여전히 절대 생산적이지 않은 규칙을 도입하지 않으려 조심합니다.
그리고 더 먼 미래를 생각하면, 최적화 여지가 더 많은 작업 부하에서는 aegraph 내부에서 더 흥미로운 상황이 생겨, 재작성들 사이의 더 많은 창발적 조합으로 이어질 수도 있습니다.
앞으로 이 일을 진전시킬 수 있고, 또 그래야 하는 방향은 많이 있습니다. 평가 측면에서는, aegraph가 진정으로 빛나는 “사용 사례 도메인의 모서리”를 찾는 것이 여전히 열린 질문입니다. 좀 더 구체적으로는, 새로운 다른 작업 부하로 Cranelift를 평가하고, 또는 재작성 규칙을 더 많이 쌓으면, 고전적인 “비용 기반 추출을 가진 다중 표현”의 이점이 전통적인 컴파일러에서 실제로 보상되는 지점에 도달할까요? 저도 모르겠습니다!
핵심 알고리즘 자체를 개선할 여지도 아직 많습니다:
위에서 언급한 더 나은 추출: 공유 서브구조를 고려할 수 있는 무언가가 있으면 좋겠습니다. 다만 그 때문에 NP-난해한 비용을 지불하지 않아야겠죠. 현재 동적 계획 접근보다 더 나은 근사 알고리즘이 있을지도 모릅니다.
CFG 스켈레톤 자체를 바꾸는 더 많은 재작성도 다룰 수 있으면 좋겠습니다. 지금은 스켈레톤 명령어의 파괴적 재작성을 허용하는 별도의 ISLE 진입점이 있습니다(이것을 만든 동료 Nick Fitzgerald에게 감사드립니다!). 하지만 예를 들어 중복 블록 매개변수(phi node)를 제거할 수도 있지 않을까요? 그리고/또는 분기를 접을 수도 있지 않을까요? 그리고/또는 특정 제어 흐름 문맥에서 사용되는 값에 경로 민감(path-sensitive) 지식을 적용할 수도 있지 않을까요? (if x==1, goto ...의 “true” 가지 아래 지배 서브트리에서는 x=1 같은 식으로요.) 제 예전 동료 Jamey Sharp가 이 주제들에 대해 트래커에 몇 가지 훌륭하고 깊이 있는 이슈를 남겼고(#5623, #6109, #6129), 저는 여기 큰 잠재력이 있다고 생각합니다.
(이것의 완전한 버전은 다시 말해, 모든 유용한 제어 흐름 재작성 형태를 표현하기 위해 노드 언어 안에 RVSDG 같은 것이 들어가는 것이 가장 원칙적인 선택처럼 보입니다. Jamey는 이를 위한 optir라는 프로토타입도 가지고 있습니다.)
이 아이디어의 단순한 버전은 lowering 규칙을 재작성으로 통합하고, egraph의 노드 언어를 CLIF와 기계 명령어 집합의 합집합으로 만드는 것입니다. 하지만 아마 더 나은 방법이 있을지도 모릅니다. Multi-extractor가 aegraph eclass를 직접 보고 다양한 VCode 시퀀스를 유지하도록 하는 식으로요. 언젠가 이 주제에 대한 제 아이디어를 더 정리해서 써야겠습니다. Jamey도 #8529에서 이에 대해 더 많은 생각을 남겼습니다.
분명 여기서 할 수 있는 다른 일들도 많을 겁니다!
저는 EGRAPHS 2023에서 aegraph에 대해 발표했습니다: 슬라이드, 다시 녹화한 비디오 (원래 발표는 녹화되지 않았습니다).
2026년 1월 Dagstuhl e-graphs 세미나에서도 aegraph에 대해 발표했습니다. 슬라이드는 2023년 발표를 크게 업데이트하고 수정한 버전으로, 여기서 제시한 실험/데이터를 포함합니다.
Aegraph에 대한 Cranelift RFC는 여기에 있고, aegraph에서 재작성을 구동하는 데 사용하는 재작성 DSL인 ISLE에 대한 RFC는 여기에 있습니다.
현재 형태의 aegraph를 구현한 주요 PR은 여기에 있습니다. 제 전 동료 Jamey Sharp와 공동 작성했으며(이 프로덕션 구현은 정말 즐겁고 생산적인 페어 프로그래밍 프로젝트였습니다!).
수년에 걸쳐 aegraph 관련 아이디어를 논의해 준 많은 분들께 감사드립니다. Nick Fitzgerald, Jamey Sharp, Trevor Elliott, Max Willsey, Alexa VanHattum, Max Bernstein, 그리고 Dagstuhl e-graphs 세미나의 많은 분들까지. 이 글은 그 누구도 검토하지 않았습니다(이미 너무 오래 묵혀 두었고, 저는 그냥 세상에 내놓고 싶었습니다). 따라서 여기의 어떤 오류든 전적으로 제 책임입니다!
1
우리 IR 의미론이 정의된 wrapping/truncation 동작을 가진다면, 최상위 비트 마스킹이 필요할 수도 있습니다: x & 0x7fff..ffff.
