V8의 최적화 컴파일러 Turbofan이 Sea of Nodes에서 벗어나 CFG 기반 IR인 Turboshaft로 전환한 배경과 이유를 사례와 함께 설명합니다.
V8의 최상위 단계 최적화 컴파일러 Turbofan은 대규모 프로덕션 컴파일러 중 드물게 Sea of Nodes (SoN)를 사용하는 것으로 잘 알려져 있습니다. 하지만 약 3년 전부터 우리는 Sea of Nodes를 걷어내고, 보다 전통적인 Control-Flow Graph (CFG) Intermediate Representation (IR)로 되돌아가기 시작했고, 그 IR을 Turboshaft라고 명명했습니다. 지금은 Turbofan의 JavaScript 백엔드 전체가 Turboshaft를 사용하고 있으며, WebAssembly는 파이프라인 전 구간에서 Turboshaft를 사용합니다. Turbofan의 일부는 아직 SoN을 사용합니다. 내장(builtin) 파이프라인은 Turboshaft로 천천히 대체 중이고, JavaScript 파이프라인의 프런트엔드는 또 다른 CFG 기반 IR인 Maglev로 바꾸고 있습니다. 이 글은 우리가 Sea of Nodes에서 벗어나기로 한 이유를 설명합니다.
12년 전인 2013년에 V8에는 Crankshaft라는 단 하나의 최적화 컴파일러가 있었습니다. 이는 Control-Flow Graph 기반 IR을 사용했습니다. 초기 버전의 Crankshaft는 아직 지원 범위가 제한적이었음에도 상당한 성능 향상을 제공했습니다. 이후 몇 년간 팀은 더 많은 상황에서 더 빠른 코드를 생성하도록 이를 개선했습니다. 그러나 기술 부채가 쌓이기 시작했고, 몇 가지 문제가 발생했습니다.
JSAdd(x,y)를 나중에 if (x is String and y is String) { StringAdd(x, y) } else { … } 같은 것으로 낮추는 것이 타당할 수 있는데, Crankshaft에서는 불가능했습니다.각 문제를 개별적으로 보면 해결할 수 있었겠지만, 모두 합쳐지니 과도했습니다. 그래서 Crankshaft를 새로 작성한 컴파일러로 교체하기로 결정했습니다: Turbofan. 그리고 전통적인 CFG IR 대신 더 강력하다고 여겨지던 Sea of Nodes IR을 사용하기로 했습니다. 당시 이 IR은 이미 Java HotSpot VM의 JIT 컴파일러 C2에서 10년 이상 사용되고 있었습니다.
먼저 Control-Flow Graph(CFG)를 간단히 상기해 보겠습니다. CFG는 프로그램을 그래프로 나타내는 방식으로, 그래프의 노드는 프로그램의 기본 블록 (들어오거나 나가는 분기/점프가 없는 명령열)을 나타내고, 간선은 프로그램의 제어 흐름을 나타냅니다. 간단한 예시는 다음과 같습니다.
간단한 CFG 그래프
기본 블록 내의 명령은 암묵적으로 순서가 있습니다. 첫 번째 명령이 두 번째 명령보다 먼저, 두 번째가 세 번째보다 먼저 실행되어야 합니다. 위의 작은 예시에서는 매우 자연스럽습니다. 어차피 x % 2가 계산되기 전에 v1 == 0을 계산할 수는 없습니다. 하지만 다음을 생각해 보죠.
재배치될 수 있는 산술 연산이 있는 CFG 그래프
여기서 CFG는 겉보기에는 a * 2가 b * 2보다 먼저 계산되어야 한다고 강제합니다. 반대 순서로 계산해도 문제가 없는데도 말이죠.
이때 Sea of Nodes가 등장합니다. Sea of Nodes는 기본 블록을 표현하지 않고, 대신 명령들 사이의 실제 의존성만을 표현합니다. Sea of Nodes의 노드는 단일 명령(기본 블록이 아니라)이고, 간선은 값 사용 관계를 나타냅니다(의미: a에서 b로의 간선은 a가 b를 사용함을 뜻함). 따라서 마지막 예시는 Sea of Nodes에서는 다음과 같이 표현됩니다.
산술 연산이 있는 간단한 Sea of Nodes 그래프
결국 컴파일러는 어셈블리를 생성해야 하므로 이 두 곱셈을 순차적으로 스케줄해야 하지만, 그전까지는 이들 사이에 더 이상 의존성이 없습니다.
이제 제어 흐름을 추가해 봅시다. 제어 노드(예: branch, goto, return)는 보통 서로 간에 특정 스케줄을 강제할 값 의존성이 없습니다. 하지만 반드시 특정 순서로 스케줄되어야 합니다. 따라서 제어 흐름을 표현하기 위해 값 의존성이 없는 노드들에 순서를 부여하는 새로운 종류의 간선, _제어 간선(control edges)_이 필요합니다.
제어 흐름이 있는 Sea of Nodes 그래프
이 예시에서 제어 간선이 없다면 branch보다 먼저 return들이 실행되는 것을 막을 수 없는데, 이는 명백히 잘못입니다.
여기서 중요한 점은 제어 간선은 그러한 간선의 입출력을 가진 연산들의 순서만 강제할 뿐, 산술 연산과 같은 다른 연산들의 순서는 강제하지 않는다는 것입니다. 이것이 Sea of Nodes와 Control-Flow Graph의 주된 차이점입니다.
이제 부수 효과가 있는 연산(예: 메모리에서의 load/store)을 추가해 봅시다. 제어 노드와 마찬가지로, 효과가 있는 연산은 종종 값 의존성이 없지만 임의의 순서로 실행될 수는 없습니다. 예를 들어 a[0] += 42; x = a[0]과 x = a[0]; a[0] += 42는 동등하지 않습니다. 따라서 효과가 있는 연산들에 순서를 부여(= 스케줄)할 방법이 필요합니다. 이를 위해 제어 체인을 재활용할 수도 있겠지만, 그러면 필요 이상으로 엄격해집니다. 다음의 작은 코드 조각을 보세요.
let v = a[2];if (c) { return v;}
a[2](메모리 읽기)를 제어 체인에 올려두면, 이 로드가 반드시 c에 대한 분기 이전에 발생하도록 강제하게 됩니다. 하지만 실제로 이 로드의 결과가 then-브랜치 본문 안에서만 사용된다면 분기 이후에 로드해도 됩니다. 프로그램의 많은 노드를 제어 체인에 올려두면 Sea of Nodes의 목적이 무색해집니다. 사실상 순수 연산만 떠다니는 CFG 유사 IR이 되어버리기 때문이죠.
그래서 Sea of Nodes의 장점을 더 누리기 위해 Turbofan은 또 다른 종류의 간선인 _효과 간선(effect edges)_을 도입했습니다. 이는 부수 효과가 있는 노드들 사이에 순서를 부여합니다. 잠시 제어 흐름은 무시하고 작은 예시를 보겠습니다.
부수 효과가 있는 연산을 포함한 Sea of Nodes 그래프
이 예시에서 arr[0] = 42와 let x = arr[a]는 값 의존성이 없습니다(즉, 전자가 후자의 입력도 아니고, 그 반대도 아님). 하지만 a가 0일 수 있기 때문에, x = arr[a]가 항상 올바른 값을 배열에서 읽도록 하려면 arr[0] = 42가 그보다 먼저 실행되어야 합니다.
참고: Turbofan에는 모든 부수 효과 연산에 사용되는 단일 효과 체인이 있습니다(분기에서 분기되고, 제어 흐름이 합쳐질 때 다시 합쳐짐). 하지만 다중 효과 체인을 둘 수도 있습니다. 의존성이 없는 연산들이 서로 다른 효과 체인에 놓일 수 있어 스케줄 제약이 느슨해집니다(자세한 내용은 SeaOfNodes/Simple 10장 참조). 다만, 뒤에서 설명하겠지만 단일 효과 체인만 유지하는 것도 이미 상당히 오류를 유발하기 쉬워서, Turbofan에서는 다중 효과 체인을 시도하지 않았습니다.
물론 실제 프로그램 대부분은 제어 흐름과 부수 효과 연산을 모두 포함합니다.
제어 흐름과 부수 효과 연산이 있는 Sea of Nodes 그래프
store와 load는 각종 검사(타입 검사나 경계 검사 등)에 의해 보호될 수 있으므로 제어 입력이 필요합니다.
이 예시는 CFG에 비해 Sea of Nodes의 강점을 잘 보여줍니다. y = x * c는 else 브랜치에서만 사용되므로, 원래 JavaScript 코드에서 분기 이전에 계산되었다 하더라도 자유롭게 branch 이후로 떠내려갈 수 있습니다. arr[0]도 마찬가지로 else 브랜치에서만 사용되므로 이론적으로는 branch 이후로 이동할 수 있습니다(다만 실제 Turbofan은 뒤에 설명할 이유로 arr[0]을 아래로 내리지 않습니다).
비교를 위해 동일한 CFG는 다음과 같습니다.
제어 흐름과 부수 효과 연산이 있는 CFG 그래프
벌써부터 SoN의 주요 문제가 보입니다. SoN은 CFG에 비해 컴파일러의 입력(소스 코드)과 출력(어셈블리) 모두로부터 더 멀리 떨어져 있어 직관적으로 이해하기 어렵습니다. 또한 효과 및 제어 의존성이 항상 명시적이기 때문에 그래프를 빠르게 추론하기도 어려우며, 로워링을 작성할 때도 제어/효과 체인을 항상 명시적으로 유지해야 해서(반면 CFG에서는 암묵적) 힘듭니다.
Sea of Nodes를 10년 넘게 다뤄본 결과, 적어도 JavaScript와 WebAssembly에 한해서는 장점보다 단점이 더 많다고 판단했습니다. 아래에서는 그중 몇 가지 문제를 자세히 설명합니다.
작은 프로그램에서는 CFG가 더 읽기 쉽다는 것을 이미 봤습니다. 이는 우리가(컴파일러 엔지니어 포함) 익숙하게 작성하는 원본 소스 코드에 더 가깝기 때문입니다. 그래도 확신이 서지 않는 독자를 위해 문제를 더 잘 이해할 수 있도록 약간 더 큰 예시를 보겠습니다. 다음은 문자열 배열을 이어붙이는 JavaScript 함수입니다.
function concat(arr) { let res = ""; for (let i = 0; i < arr.length; i++) { res += arr[i]; } return res;}
다음은 Turbofan 컴파일 파이프라인 중간 단계(즉, 일부 로워링이 이미 진행된 상태)의 해당 Sea of Nodes 그래프입니다.
간단한 배열 연결 함수의 Sea of Nodes 그래프
이미 여기서부터 노드의 지저분한 수프처럼 보이기 시작합니다. 그리고 컴파일러 엔지니어로서 제 업무의 큰 부분은 Turbofan 그래프를 보고 버그를 이해하거나 최적화 기회를 찾는 것입니다. 그래프가 이렇게 보이면 쉽지 않습니다. 컴파일러의 입력은 CFG 같은 구조(각 블록에서 명령이 고정된 위치를 가짐)의 소스 코드이고, 출력은 역시 CFG 같은 구조의 어셈블리입니다(각 블록에서 명령이 고정된 위치를 가짐). 따라서 CFG 같은 IR을 사용하면 컴파일러 엔지니어가 IR의 요소를 소스나 생성된 어셈블리와 쉽게 대응시킬 수 있습니다.
비교를 위해(이미 SoN을 CFG로 대체하기 시작했기 때문에 가능) 해당 CFG 그래프는 다음과 같습니다.
동일한 간단한 배열 연결 함수의 CFG 그래프
CFG에서는 루프가 어디인지, 루프의 종료 조건이 무엇인지가 명확합니다. 또한 우리가 예상하는 위치를 바탕으로 CFG에서 특정 명령을 쉽게 찾을 수 있습니다. 예를 들어 arr.length는 루프 헤더에 있습니다(이는 v22 = [v0 + 12]). 문자열 연결은 루프 끝부분에서 찾을 수 있습니다(v47 StringConcat(...)).
가치(use) 체인을 따라가는 것은 CFG 버전이 더 어렵다고 주장할 수 있겠지만, 대체로 그래프의 제어 흐름 구조를 명확히 보는 편이 값 노드의 수프를 보는 것보다 낫다고 생각합니다.
Sea of Nodes의 이점을 누리려면 그래프의 대부분 노드가 제어/효과 체인 없이 자유롭게 떠다녀야 합니다. 불행히도 일반적인 JavaScript 그래프에서는 거의 모든 일반 JS 연산이 임의의 부수 효과를 일으킬 수 있기 때문에 그렇지 않습니다. Turbofan에서는 피드백을 통해 일반 연산을 더 구체적인 연산으로 로워링할 수 있어 이런 경우가 드물어야 하긴 합니다.
그럼에도 모든 메모리 연산은 효과 입력(Load가 Store를 앞지르거나 그 반대가 되면 안 되기 때문)과 제어 입력(연산 전에 타입 검사나 경계 검사가 있을 수 있기 때문)이 필요합니다. 심지어 나눗셈과 같은 일부 순수 연산도 특수 케이스를 검사로 보호하기 때문에 제어 입력이 필요합니다.
구체적인 예시를 보겠습니다. 다음 JavaScript 함수에서 시작합니다.
function foo(a, b) { // 여기서 \\a.str\과 \\b.str\이 문자열이라고 가정 return a.str + b.str;}
다음은 해당 Turbofan 그래프입니다. 보기 쉽게 하려고 빨간 점선으로 효과 체인의 일부를 강조 표시했고, 아래에서 논의할 수 있도록 몇몇 노드에 번호를 달았습니다.
간단한 문자열 연결 함수의 Sea of Nodes 그래프
첫 번째 관찰은 거의 모든 노드가 효과 체인에 올라가 있다는 점입니다. 몇 가지를 살펴보며 정말 필요한지 보겠습니다.
1(CheckedTaggedToTaggedPointer): 함수의 첫 번째 입력이 "스몰 정수"가 아니라 포인터인지 검사합니다(V8의 포인터 압축 참고). 이 노드 자체만 보면 효과 입력이 꼭 필요하지는 않지만, 실제로는 다음 노드들을 가드하기 때문에 효과 체인 위에 있어야 합니다.2(CheckMaps): 이제 첫 번째 입력이 포인터임을 알았으니, 해당 객체의 "맵"을 로드하고(V8의 맵(숨은 클래스) 참고), 피드백이 기록한 맵과 일치하는지 검사합니다.3(LoadField): 첫 번째 객체가 올바른 맵을 가진 포인터임을 알았으니, 그 .str 필드를 로드합니다.4, 5, 6: 두 번째 입력에 대해서도 같은 과정을 반복합니다.7(CheckString): 이제 a.str을 로드했으므로 그것이 실제 문자열인지 검사합니다.8: 두 번째 입력에 대해 반복합니다.9: a.str과 b.str의 합친 길이가 V8에서 허용하는 문자열의 최대 크기보다 작은지 검사합니다.10(StringConcat): 마지막으로 두 문자열을 연결합니다.이 그래프는 JavaScript 프로그램에 대한 Turbofan 그래프에서 매우 전형적입니다. 맵을 검사하고, 값을 로드하고, 로드한 값의 맵을 검사하고, … 그런 다음 결국 그 값들로 몇 가지 계산을 수행합니다. 그리고 이 예시처럼 많은 경우 대부분의 명령이 효과나 제어 체인 위에 놓이게 됩니다. 이는 연산의 엄격한 순서를 강제하여 Sea of Nodes의 목적을 완전히 무색하게 만듭니다.
다음 JavaScript 프로그램을 보겠습니다.
let x = arr[0];let y = arr[1];if (c) { return x;} else { return y;}
x와 y가 각각 if-else의 한쪽에서만 사용되므로, SoN이 이들을 자유롭게 아래로 떠내려가서 "then"과 "else" 브랜치 내부로 이동하게 해주길 기대할 수 있습니다. 하지만 실제로 SoN에서 이를 성사시키는 것이 CFG보다 쉽지는 않습니다. 그 이유를 이해하기 위해 SoN 그래프를 살펴보겠습니다.
효과 체인이 제어 체인을 거울처럼 따라가면서, 부수 효과 연산이 기대만큼 자유롭게 떠다니지 못하는 Sea of Nodes 그래프
SoN 그래프를 만들 때 우리는 진행 순서대로 효과 체인을 생성합니다. 그래서 두 번째 Load는 첫 번째 바로 뒤에 오게 되고, 이후 효과 체인은 두 개의 return에 도달하기 위해 분기되어야 합니다(왜 return이 효과 체인 위에 있는지 궁금하다면, 앞에 Store 같은 부수 효과 연산이 있을 수 있고, 그것들은 함수 반환 전에 반드시 실행되어야 하기 때문입니다). 두 번째 Load가 두 return 모두의 선행 노드이므로, 이는 branch 이전에 스케줄되어야 합니다. 따라서 SoN은 두 Load 중 어느 것도 자유롭게 아래로 떠내려갈 수 있게 허용하지 않습니다.
Load들을 "then"과 "else" 브랜치로 내리려면, 그 사이에 부수 효과가 없다는 점, 그리고 두 번째 Load와 return 사이에도 부수 효과가 없다는 점을 분석해낸 뒤, 두 번째 Load 이후가 아니라 시작 지점에서 효과 체인을 분기해야 합니다. 이 분석은 SoN 그래프에서 하든 CFG에서 하든 거의 동일합니다.
많은 노드가 효과 체인에 올라가고, 효과가 있는 노드들이 멀리 떠내려가지 못한다는 점을 이제 언급했으니, 한 가지 사실을 인지할 때입니다. 실제로 SoN은 순수 노드만 떠다니는 CFG에 가깝습니다. 실제로 제어 노드와 제어 체인은 항상 해당 CFG의 구조를 그대로 반영합니다. 그리고 분기의 두 대상이 모두 부수 효과를 가진 경우(자바스크립트에서는 흔함), 효과 체인은 제어 체인이 분기되는 지점과 동일하게 분기되고, 제어 흐름이 합쳐질 때 동일 지점에서 다시 합쳐집니다(위 예시처럼: 제어 체인은 branch에서 분기되고, 효과 체인은 Load에서 이를 거울처럼 분기합니다. 그리고 만약 프로그램이 if-else 뒤에서 이어진다면 두 체인은 비슷한 지점에서 합쳐질 것입니다). 따라서 효과가 있는 노드들은 보통 두 제어 노드 사이, 즉 기본 블록 안에서만 스케줄되도록 제약됩니다. 그리고 이 기본 블록 안에서는 효과 체인이 소스 코드에 나타난 순서 그대로 효과가 있는 노드들의 순서를 제약합니다. 결국 실제로 자유롭게 떠다니는 것은 순수 노드뿐입니다.
떠다니는 노드를 더 늘리는 방법 중 하나는 앞서 언급했듯 다중 효과 체인을 사용하는 것입니다. 하지만 대가가 따릅니다. 첫째, 단일 효과 체인을 관리하는 것만으로도 이미 어렵고, 여러 개를 관리하는 것은 훨씬 더 어렵습니다. 둘째, JavaScript처럼 동적 언어에서는 서로 앨리어싱할 수 있는 메모리 접근이 매우 많기 때문에, 다중 효과 체인은 자주 서로 합쳐져야 하며, 이는 다중 효과 체인의 장점 일부를 상쇄합니다.
앞 절에서 말했듯, 효과 체인과 제어 체인은 구분되지만, 실제로 효과 체인은 보통 제어 체인과 같은 "형상"을 가집니다. 분기 대상에 부수 효과 연산이 포함되어 있으면(흔함) 효과 체인은 분기 지점에서 분기되고 제어 흐름이 합쳐질 때 다시 합쳐집니다.
JavaScript를 다루기 때문에 많은 노드가 부수 효과를 가지며, 분기도 많습니다(보통 어떤 객체의 타입에 따라 분기). 그 결과, CFG였다면 제어 체인만 추적하면 될 일인데, SoN에서는 효과 체인과 제어 체인을 나란히 모두 추적해야 합니다.
역사가 보여주듯, 효과/제어 체인을 수동으로 관리하는 것은 오류가 발생하기 쉽고, 읽기도 유지보수도 어렵습니다. JSNativeContextSpecialization 단계의 코드 샘플을 보세요.
JSNativeContextSpecialization::ReduceNamedAccess(...) { Effect effect{...}; [...] Node* receiverissmi_effect = effect; [...] Effect this_effect = effect; [...] this_effect = graph()->NewNode(common()->EffectPhi(2), this_effect, receiverissmi_effect, this_control); receiverissmi_effect = receiverissmi_control = nullptr; [...] effect = graph()->NewNode(common()->EffectPhi(control_count), ...); [...]}
여기서는 다양한 분기와 경우를 처리해야 해서 결과적으로 서로 다른 효과 체인 3개를 관리하게 됩니다. 어느 효과 체인을 써야 하는지 헷갈리기 쉽습니다. 실제로 우리는 처음에 틀렸고, 몇 달이 지나서야 실수를 알아차렸습니다.
이 문제는 Turbofan과 Sea of Nodes 모두의 탓이라고 보겠습니다. Turbofan에 더 나은 헬퍼가 있었다면 효과/제어 체인 관리를 단순화할 수 있었겠지만, CFG였다면 애초에 문제가 되지 않았을 것입니다.
결국 모든 명령은 어셈블리를 생성하기 위해 스케줄되어야 합니다. 이론은 꽤 간단합니다. 각 명령은(루프는 무시하고) 자신의 값/제어/효과 입력 뒤에 스케줄되어야 합니다.
흥미로운 예시를 보겠습니다.
간단한 switch-case에 대한 Sea of Nodes 그래프
소스 JavaScript 프로그램에는 동일한 나눗셈이 두 번 있지만, Sea of Nodes 그래프에는 하나만 있는 것을 볼 수 있습니다. 실제로는 두 번의 나눗셈으로 시작하지만, 이는 순수 연산(입력이 더블이라고 가정)이므로 중복 제거가 쉽게 둘을 하나로 합칩니다.
그 다음 스케줄링 단계에 이르면 이 나눗셈을 어디에 배치할지 찾아야 합니다. 분명 case 1이나 case 2 뒤에 놓을 수는 없는데, 서로의 경로에서 사용되기 때문입니다. 대신 switch 이전에 스케줄해야 합니다. 단점은 이제 c가 3일 때도 a / b가 계산된다는 것입니다. 실제로 필요 없는데도 말이죠. 이는 중복 제거된 많은 명령이 사용자들의 공통 도미네이터로 떠올라, 필요 없는 경로까지 느려지게 만드는 실제 문제입니다.
해법이 있긴 합니다. Turbofan의 스케줄러는 이런 경우를 식별해, 필요한 경로에서만 계산되도록 명령을 복제하려 시도합니다. 하지만 이는 스케줄러를 더 복잡하게 만듭니다. 어떤 노드를 복제할 수 있고 복제해야 하는지, 그리고 어떻게 복제할지를 판단하는 추가 로직이 필요하기 때문입니다.
결국 우리는 2개의 나눗셈으로 시작해, "최적화"를 통해 1개로 만들었다가, 다시 2개로 최적화하는 셈이 되었습니다. 이는 나눗셈뿐 아니라 다른 많은 연산에서도 비슷하게 일어납니다.
컴파일러의 모든 패스는 그래프를 방문해야 합니다. 노드를 로워링하든, 국소 최적화를 적용하든, 전체 그래프에 대한 분석을 하든 말이죠. CFG에서는 노드를 방문하는 순서가 보통 명확합니다. 첫 블록(단일 진입 함수라고 가정)에서 시작해 블록의 각 노드를 순회한 다음, 후속 블록으로 넘어가는 식입니다. 피프홀 최적화 단계(예: strength reduction)에서, 이 순서의 좋은 점은 입력이 항상 노드보다 먼저 최적화된다는 것입니다. 따라서 각 노드를 정확히 한 번씩 방문하는 것만으로도 대부분의 피프홀 최적화를 적용하기 충분합니다. 다음과 같은 축약 시퀀스를 생각해 봅시다.
전체를 최적화하는 데 세 단계가 걸렸고, 각 단계는 유효한 작업을 했습니다. 그 다음 데드 코드 제거가 v1과 v2를 제거하여, 초기 시퀀스보다 명령이 하나 줄었습니다.
Sea of Nodes에서는 순수 명령을 시작부터 끝까지 처리하는 것이 불가능합니다. 이들은 어떤 제어/효과 체인에도 속하지 않아서, 순수 루트에 접근할 포인터 같은 게 없기 때문입니다. 대신 SoN 그래프에서 피프홀 최적화를 위해 보통 사용하는 방법은 끝에서 시작하는 것입니다(예: return 명령에서 시작하여, 값/효과/제어 입력을 거슬러 올라감). 이 방법은 사용되지 않는 명령을 방문하지 않는다는 장점이 있지만, 장점은 거기까지입니다. 피프홀 최적화 관점에서는 최악의 방문 순서이기 때문입니다. 위 예시에서 우리가 밟게 될 단계를 보겠습니다.
v3를 방문하지만 이 시점에서는 낮출 수 없으니 입력으로 넘어갑니다.
v1을 방문해 a << 3으로 로워링한 뒤, 이 로워링이 사용자를 최적화할 수 있도록 사용자로 이동합니다.
v3를 방문하지만 아직 낮출 수 없습니다(이번에는 입력들을 다시 방문하지는 않습니다).v2를 방문해 b << 3으로 로워링한 뒤, 이 로워링이 사용자 최적화를 가능하게 할지 확인하려 사용자로 이동합니다.
v3를 방문해 이번에는 (a & b) << 3으로 로워링합니다.결국 v3는 세 번 방문되었지만 한 번만 로워링되었습니다.
우리는 한동안 전형적인 JavaScript 프로그램에서 이 효과를 측정했는데, 평균적으로 노드가 20번 방문될 때 겨우 한 번만 바뀐다는 사실을 알게 됐습니다!
또 다른 결과로, 상태 추적이 어렵고 비용이 크다는 문제가 있습니다. 많은 최적화는 로드 제거(Load Elimination)나 이스케이프 분석(Escape Analysis)처럼 그래프를 따라 어떤 상태를 추적해야 합니다. 하지만 SoN에서는 특정 시점에 어떤 상태를 유지해야 하는지 판단하기가 어렵습니다. 아직 처리되지 않은 노드가 그 상태를 필요로 하는지 파악하기 어렵기 때문입니다.
결과적으로 Turbofan의 Load Elimination 단계는 너무 오래 걸리거나 메모리를 너무 많이 쓰는 것을 피하기 위해 큰 그래프에서는 bailout을 합니다. 비교를 위해, 우리는 새 CFG 컴파일러를 위한 새로운 로드 제거 단계를 작성했는데, 벤치마크 결과 최대 190배 더 빨랐습니다(최악의 경우 복잡도가 더 좋아서 큰 그래프에서는 이런 속도 향상이 쉽게 나옵니다). 메모리 사용량도 훨씬 적었습니다.
Turbofan의 거의 모든 단계는 그래프를 제자리에서(mutating in-place) 변형합니다. 노드는 메모리에서 꽤 큰 편입니다(각 노드가 자신의 입력과 사용자를 모두 가리키는 포인터를 갖기 때문). 그래서 가능한 한 노드를 재사용하려고 합니다. 하지만 노드를 여러 개의 노드 시퀀스로 로워링할 때는 새 노드를 도입할 수밖에 없는데, 이들은 원래 노드와 메모리에서 가깝게 할당되지 않습니다. 그 결과, Turbofan 파이프라인을 더 깊이 진행하고 더 많은 단계를 돌릴수록 그래프는 캐시 친화적이지 않게 됩니다. 아래 그림은 이 현상을 보여줍니다.
정확한 영향도를 추정하기는 어렵습니다. 그래도 이제 새로운 CFG 컴파일러가 있으니 둘 사이의 캐시 미스를 비교해볼 수 있습니다. Sea of Nodes는 새로운 CFG IR에 비해 평균 약 3배 더 많은 L1 데이터 캐시 미스를 겪고, 어떤 단계에서는 최대 7배까지 증가합니다. 우리는 이것이 컴파일 시간의 최대 5% 정도를 차지한다고 추정합니다(다소 러프한 수치입니다). 그래도 JIT 컴파일러에서는 빠른 컴파일이 필수라는 점을 기억해야 합니다.
다음 JavaScript 함수를 보겠습니다.
function foo(x) { if (x < 42) { return x + 1; } return x;}
지금까지 x와 x+1의 결과에 대해 "스몰 정수"(31비트 정수, V8의 값 태깅 참고)만 보았다면, 우리는 앞으로도 그럴 것이라고 추측합니다. 만약 언젠가 x가 31비트를 넘는 값을 갖게 되면 디옵트합니다. 마찬가지로, x+1의 결과가 31비트를 넘으면 디옵트합니다. 이는 x+1이 31비트에 들어맞는지 검사해야 함을 의미합니다. 이에 해당하는 CFG와 SoN 그래프를 보겠습니다.
(결과가 31비트를 넘치면 디옵트하는 CheckedAdd 연산이 있다고 가정)
CFG에서는 CheckedAdd(v1, 1)이 실행될 때 v1은 42보다 작음이 보장된다는 사실을 쉽게 알 수 있습니다. 따라서 31비트 오버플로 검사가 필요 없습니다. 우리는 CheckedAdd를 일반 Add로 쉽게 대체하여 더 빠르게 실행되고, 디옵트 상태(디옵트 후 실행을 재개하는 방법을 알기 위해 필요한 상태)도 필요 없게 만들 수 있습니다.
하지만 SoN 그래프에서는 CheckedAdd가 순수 연산이므로 그래프에서 자유롭게 떠다닙니다. 따라서 분기 이후에 계산하겠다는 스케줄을 만들 때까지 검사를 제거할 방법이 없습니다(이 시점에서는 CFG로 돌아온 것이므로 더 이상 SoN 최적화가 아닙니다).
이런 체크드 연산은 31비트 스몰 정수 최적화 때문에 V8에서 자주 등장하며, 체크드 연산을 언체크드 연산으로 대체하는 능력은 Turbofan이 생성하는 코드의 품질에 큰 영향을 줄 수 있습니다. 그래서 Turbofan의 SoN은 CheckedAdd에 제어 입력을 둡니다. 이는 이 최적화를 가능하게 하지만, 동시에 순수 노드에 스케줄 제약을 도입하는 것이기도 합니다. 즉, CFG로 돌아가는 셈입니다.
죽음(deadness) 전파가 어렵습니다. 로워링 중에 현재 노드가 실제로 도달 불가능함을 자주 알게 됩니다. CFG에서는 현재 기본 블록을 여기서 잘라버리면, 뒤따르는 블록은 더 이상 전임자가 없어 자동으로 도달 불가능해집니다. Sea of Nodes에서는 더 어렵습니다. 제어 체인과 효과 체인을 모두 수정해야 하기 때문입니다. 효과 체인상의 노드가 죽었다면 다음 merge까지 효과 체인을 앞으로 따라가면서 그 사이를 모두 제거하고, 제어 체인에 있는 노드들은 주의 깊게 처리해야 합니다.
새로운 제어 흐름을 도입하기 어렵습니다. 제어 흐름 노드는 제어 체인 위에 있어야 하므로, 일반 로워링 중에 새로운 제어 흐름을 도입할 수 없습니다. 예를 들어 Int32Max 같은 순수 노드가 있어 두 정수의 최댓값을 반환하고, 궁극적으로 이를 if (x > y) { x } else { y }로 로워링하고 싶다고 합시다. Sea of Nodes에서는 이 서브그래프를 제어 체인 어디에 연결해야 할지 알 방법이 없어 쉽지 않습니다. 이를 구현하는 한 가지 방법은 시작부터 Int32Max를 제어 체인 위에 두는 것입니다. 그러나 이 노드는 순수하므로 자유롭게 이동할 수 있어야 하기에 낭비로 보입니다. 그래서 Turbofan과 SoN의 창시자 Cliff Click 모두(이 Coffee Compiler Club 대화에서 언급) 사용하는 전형적인 SoN 해법은, 이런 로워링을 스케줄(즉 CFG)이 준비될 때까지 지연하는 것입니다. 그 결과 파이프라인 중간 즈음에 스케줄을 계산하고 그래프를 로워링하는 단계가 있으며, 스케줄이 필요하다는 이유로 여러 잡다한 최적화가 함께 묶여 있습니다. CFG라면 이런 최적화를 파이프라인의 더 이르거나 늦은 시점에 자유롭게 수행할 수 있습니다.
또한 서론에서 언급했듯 Crankshaft(= Turbofan의 전임자)의 문제 중 하나는 그래프를 만든 뒤에는 사실상 제어 흐름을 도입할 수 없었다는 점입니다. Turbofan은 제어 체인 위의 노드 로워링이 새로운 제어 흐름을 도입할 수 있다는 점에서 약간 개선되었지만, 여전히 제한적입니다.
루프 내부에 무엇이 있는지 파악하기 어렵습니다. 많은 노드가 제어 체인 밖에서 떠돌기 때문에, 각 루프 안에 무엇이 있는지 파악하기 어렵습니다. 그 결과 루프 필링/언롤링 같은 기본 최적화조차 구현이 어렵습니다.
컴파일이 느립니다. 앞서 언급한 여러 문제의 직접적 결과입니다. 노드를 방문할 좋은 순서를 찾기 어렵고, 이로 인해 쓸모없는 재방문이 많아집니다. 상태 추적은 비용이 크고, 메모리 사용과 캐시 지역성도 나쁩니다. 축약(리덕션) 단계에서 고정점에 도달하는 데도 시간이 오래 걸립니다. AOT 컴파일러에서는 큰 문제가 아닐 수 있지만, JIT 컴파일러에서 컴파일이 느리면 최적화된 코드가 준비될 때까지 느린 비최적화 코드를 계속 실행해야 하며, 다른 작업(예: 다른 컴파일 작업이나 가비지 컬렉터)에서 리소스를 빼앗습니다. 그 결과 우리는 새로운 최적화의 컴파일 시간 대비 속도 향상 트레이드오프를 매우 신중히 고민해야 하며, 대개는 빠른 최적화를 위해 최적화 강도를 낮추는 쪽으로 기울게 됩니다.
Sea of Nodes는 설계상 기존 스케줄을 파괴합니다. JavaScript 소스 코드는 보통 CPU 마이크로아키텍처를 고려해 수동 최적화되지 않습니다. 하지만 WebAssembly 코드는 소스 수준(C++ 등)이나 사전(AOT) 컴파일 도구체인(Binaryen/Emscripten)에 의해 그렇게 될 수 있습니다. 그 결과 WebAssembly 코드는 대부분의 아키텍처에서 좋은 방식(예: 레지스터가 16개라고 가정할 때 스필링을 줄이는)으로 스케줄되어 있을 수 있습니다. 그러나 SoN은 항상 초기 스케줄을 버리고 자체 스케줄러에만 의존해야 합니다. JIT 컴파일의 시간 제약 때문에, 이는 AOT 컴파일러(혹은 코드 스케줄링을 신중하게 고려한 C++ 개발자)가 할 수 있는 것보다 쉽게 나빠질 수 있습니다. 우리는 WebAssembly가 이로 인해 손해를 보는 사례를 보았습니다. 또한 Turbofan에서 WebAssembly에는 CFG 컴파일러, JavaScript에는 SoN 컴파일러를 쓰는 방식도 불가능했습니다. 두 언어 간 인라이닝을 위해 동일한 컴파일러를 사용하는 것이 필요하기 때문입니다.
요약하면, Sea of Nodes와 Turbofan에서 우리가 겪는 주요 문제는 다음과 같습니다.
그래서 Turbofan과 Sea of Nodes와 씨름한 지 10년 끝에, 우리는 이를 버리고 보다 전통적인 CFG IR로 돌아가기로 했습니다. 새로운 IR과 함께한 우리의 경험은 지금까지 매우 긍정적이었고, CFG로 돌아오길 정말 잘했다고 생각합니다. SoN과 비교해 컴파일 시간은 절반으로 줄었고, 컴파일러 코드는 훨씬 단순하고 짧아졌으며, 버그 조사도 보통 훨씬 쉬워졌습니다.
이 글이 이미 상당히 길어졌으니 여기까지 하겠습니다. 새로운 CFG IR, Turboshaft의 설계를 설명하는 후속 글을 기대해 주세요.