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의 두 부분은 여전히 Sea of Nodes를 일부 사용하는데, 하나는 내장 파이프라인이며, 이를 천천히 Turboshaft로 교체하고 있으며, 다른 하나는 JavaScript 파이프라인의 프론트엔드로 이는 또 다른 CFG 기반 IR인 Maglev로 교체 중입니다. 이 블로그 글에서는 우리가 Sea of Nodes를 벗어나기로 한 이유를 설명합니다.

12년 전인 2013년에 V8에는 단 하나의 최적화 컴파일러인 Crankshaft가 있었습니다. Crankshaft는 Control-Flow Graph 기반 Intermediate Representation(IR)을 사용하고 있었습니다. Crankshaft의 초기 버전은 지원 범위는 제한적이었지만 상당한 성능 향상을 제공했습니다. 이후 몇 년간 팀은 이를 개선하여 더 많은 상황에서 더 빠른 코드를 생성할 수 있도록 했습니다. 그러나 기술적 부채가 쌓이기 시작했고 Crankshaft와 관련된 여러 문제가 발생하기 시작했습니다:

1. 너무 많은 수작업으로 작성된 어셈블리 코드가 포함되어 있었습니다. IR에 새로운 연산자가 추가될 때마다 이를 어셈블리로 변환하기 위한 코드가 V8이 공식적으로 지원하는 네 가지 아키텍처(x64, ia32, arm, arm64)에 대해 수동으로 작성되어야 했습니다.

2. asm.js를 최적화하는 데 어려움을 겪었습니다. 이는 당시 고성능 JavaScript를 향한 중요한 단계로 간주되었습니다.

3. 로어링에서 제어 흐름을 도입할 수 없었습니다. 즉, 제어 흐름은 그래프 빌드 시점에 생성되며 이후에는 변경할 수 없었습니다. 이는 컴파일러를 작성할 때 고수준의 연산으로 시작하여 낮은 수준의 연산으로 낮추는 작업을 하면서 추가적인 제어 흐름을 도입하는 것이 흔한 일이기 때문에 큰 제한이었습니다. 예를 들어 고수준 연산 JSAdd(x,y)를 다음처럼 낮추는 것이 합리적일 수 있습니다: if (x is String and y is String) { StringAdd(x, y) } else { … }. 그러나 Crankshaft에서는 이것이 불가능했습니다.

4. 'try-catch'를 지원하지 않았고 이를 지원하는 것은 매우 도전적이었습니다. 여러 엔지니어들이 이를 지원하려는 작업을 몇 달 동안 수행했지만 성공하지 못했습니다.

5. 많은 성능 급락 및 포기 현상이 있었습니다. 특정 기능이나 명령어를 사용하거나 특정 에지 케이스를 만날 때 성능이 100배로 떨어지는 문제가 있었습니다. 이는 JavaScript 개발자들이 효율적인 코드를 작성하거나 애플리케이션의 성능을 예측하는 데 어려움을 겪게 만들었습니다.

6. 많은 재최적화 루프가 포함되어 있었습니다. Crankshaft는 일부 추측적 가정을 기반으로 기능을 최적화했지만 이러한 가정이 맞지 않을 경우 기능이 비최적화되었습니다. 그러나 너무 자주 Crankshaft는 같은 가정을 사용하여 기능을 다시 최적화해 끝없는 최적화-비최적화 루프에 빠지곤 했습니다.

각각의 문제는 단독으로 극복할 수 있었을지도 모릅니다. 하지만 모든 문제가 합쳐졌을 때는 너무 많은 어려움이 있었습니다. 그래서 Crankshaft를 대체하고 처음부터 새로 작성된 컴파일러인 Turbofan으로 교체하기로 결정했습니다. 그리고 전통적인 CFG IR 대신 Turbofan은 더 강력하다고 여겨지는 IR인 Sea of Nodes를 사용하기로 했습니다. 당시 이 IR은 Java HotSpot Virtual Machine의 JIT 컴파일러인 C2에서 10년 이상 사용되었습니다.

Sea of Nodes란 무엇인가?

먼저 Control-Flow Graph (CFG)에 대한 간단한 설명입니다: CFG는 프로그램을 그래프로 나타낸 것으로, 그래프의 노드는 프로그램의 기본 블록을 나타내며(즉, 들어오는 또는 나가는 분기나 점프가 없는 명령어의 순서), 엣지가 프로그램의 제어 흐름을 나타냅니다. 다음은 간단한 예입니다:

기본 블록 내의 명령문은 암묵적으로 순서가 지정됩니다: 첫 번째 명령문은 두 번째 명령문보다 먼저 실행되어야 하고, 두 번째 명령문은 세 번째 명령문보다 먼저 실행되어야 합니다. 위의 간단한 예에서 이는 매우 자연스러워 보입니다: v1 == 0은 어쨌든 x % 2가 계산되기 전에 계산될 수 없습니다. 하지만 다음을 고려해 보세요.

여기서 CFG는 a * 2를 b * 2보다 먼저 계산해야 한다고 부과하는 것처럼 보이지만, 이를 반대로 계산해도 문제가 없습니다. 바로 여기에서 Sea of Nodes가 등장합니다: Sea of Nodes는 기본 블록을 나타내지 않고 명령문 사이의 실제 의존성만을 나타냅니다. Sea of Nodes의 노드는 단일 명령문이며(기본 블록이 아닌), 간선은 값 사용을 나타냅니다(즉, a에서 b로의 간선은 a가 b를 사용한다는 사실을 나타냅니다). 따라서, 마지막 예제를 Sea of Nodes로 표현하면 다음과 같습니다:

최종적으로 컴파일러는 어셈블리를 생성해야 하므로 이 두 곱셈을 순차적으로 스케줄해야 하지만, 그 전까지는 이들 간에 더 이상 의존성이 없습니다.

이제 제어 흐름을 추가해 보겠습니다. 제어 노드(예: branch, goto, return)는 일반적으로 특정 스케줄을 강제할 수 있는 값 의존성이 없지만, 특정 순서로 스케줄되어야 합니다. 그러므로 제어 흐름을 나타내기 위해 값을 의존하지 않는 노드에 대해 일부 순서를 부과하는 새로운 종류의 간선, 제어 간선이 필요합니다:

이 예제에서, 제어 간선 없이 return이 branch보다 먼저 실행되는 것을 막을 수 없으며, 이는 명백히 잘못입니다. 여기서 중요한 점은 제어 간선이 그러한 입출력 간선을 가진 연산의 순서만 규정하고, 산술 연산과 같은 다른 연산에는 영향을 주지 않는다는 점입니다. 이는 Sea of Nodes와 제어 흐름 그래프의 주요 차이점입니다.

이제 부작용이 있는 연산(예: 메모리에서의 로드와 저장)을 추가해 보겠습니다. 제어 노드와 마찬가지로, 부작용 연산은 값 의존성이 없는 경우가 많지만 무작위 순서로 실행될 수는 없습니다. 예를 들어, 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은 또 다른 종류의 간선, 효과 간선을 가지고 있으며, 이는 부작용이 있는 노드에 일부 순서를 부과합니다. 제어 흐름은 무시하고 간단한 예제를 살펴보겠습니다:

이 예제에서 arr[0] = 42와 let x = arr[a]는 값 의존성이 없습니다(즉, 전자는 후자의 입력이 아니며 반대도 마찬가지입니다). 그러나 a가 0일 수 있으므로, arr[0] = 42는 항상 배열에서 올바른 값을 로드하기 위해 x = arr[a]보다 먼저 실행되어야 합니다. 참고로, Turbofan은 모든 부작용 연산에 대해 사용되는 단일 효과 체인(분기에서 분리되고 제어 흐름이 병합될 때 다시 병합됨)을 가지고 있지만, 의존성이 없는 연산이 다른 효과 체인에 있을 수 있는 경우, 여러 효과 체인을 가지는 것도 가능합니다. 이렇게 하면 스케줄링 방법이 완화됩니다(자세한 내용은 SeaOfNodes/Simple의 10장을 참조하세요). 하지만 나중에 설명할 것처럼, 단일 효과 체인을 유지하는 것만으로도 매우 오류가 발생하기 쉬운 작업이므로, Turbofan에서 여러 개의 체인을 가지려고 시도하지 않았습니다.

물론 대부분의 실제 프로그램은 제어 흐름과 부작용 연산을 모두 포함합니다.

store와 load는 다양한 검사(유형 검사 또는 경계 검사 등)에 의해 보호될 수 있으므로 제어 입력이 필요하다는 점에 유의하세요. 이 예제는 CFG와 비교했을 때 Sea of Nodes의 강력함을 잘 보여줍니다: y = x * c는 else 분기에서만 사용되므로 원래의 JavaScript 코드에서 작성된 것처럼 분기 전에 계산되지 않고 branch 이후로 자유롭게 이동합니다. 이는 arr[0]에도 해당하며, 이는 else 분기에서만 사용되므로 branch 이후로 이동할 수 있습니다 (하지만 실제로 Turbofan은 나중에 설명할 이유로 인해 arr[0]을 아래로 이동시키지는 않습니다). 비교를 위해, 해당되는 CFG가 어떻게 보일지 확인해 보겠습니다:

벌써 우리는 SoN의 주요 문제를 보기 시작합니다: 이는 입력(소스 코드)과 출력(어셈블리) 모두에서 CFG보다 훨씬 멀어져 있어 이해하기가 덜 직관적입니다. 또한, 효과와 제어 종속성을 항상 명시적으로 표시해야 하기 때문에 그래프를 빠르게 논리적으로 이해하거나 단순화 작업을 작성하기 어려워집니다(CFG에서는 암묵적인 제어 및 효과 체인을 명시적으로 유지해야 할 필요가 없습니다).

문제가 시작됩니다…

Sea of Nodes를 10년 이상 다뤄본 결과, 적어도 JavaScript와 WebAssembly와 관련하여, 장점보다 단점이 더 많다고 생각합니다. 아래에서 몇 가지 문제에 대해 자세히 살펴보겠습니다.

수동/시각적으로 Sea of Nodes 그래프를 검사하고 이해하는 데 어려움이 있습니다

작은 프로그램에서는 CFG가 읽기 쉬운 것을 이미 보았습니다. 이는 원본 소스 코드에 더 가깝기 때문이며, 이는 개발자(컴파일러 엔지니어 포함)가 작성하던 방식입니다. 의심의 여지가 있는 독자들에게는, 이 문제를 더 잘 이해할 수 있도록 조금 더 큰 예제를 제공하겠습니다. 다음 JavaScript 함수는 문자열 배열을 연결합니다:

function concat(arr) {
  let res = "";
  for (let i = 0; i < arr.length; i++) {
    res += arr[i];
  }
  return res;
}

다음은 Turbofan 컴파일 파이프라인 중간에 해당하는 Sea of Nodes 그래프입니다(즉, 일부 단순화 작업이 이미 이루어진 상태입니다):

이미 이것은 엉킨 노드의 수프처럼 보이기 시작합니다. 그리고 컴파일러 엔지니어로서 제 작업의 큰 부분은 Turbofan 그래프를 보면서 버그를 이해하거나 최적화 기회를 찾는 것입니다. 하지만 그래프가 이렇게 보일 때는 이해하기 쉽지 않습니다. 결국 컴파일러의 입력은 소스 코드로서 CFG와 유사합니다(명령어가 특정 블록에 고정된 위치를 가짐). 컴파일러의 출력은 어셈블리이며, 역시 CFG와 유사합니다(명령어가 일정한 블록 내에 고정된 위치를 가짐). 따라서 CFG와 유사한 IR을 사용하면 컴파일러 엔지니어가 IR의 요소를 소스 코드 또는 생성된 어셈블리와 쉽게 연결할 수 있습니다.

비교를 위해, 다음은 대응되는 CFG 그래프입니다(우리는 이미 Sea of Nodes를 CFG로 대체하는 과정을 시작했기 때문에 이 데이터를 사용할 수 있습니다):

다른 점들 중에서 CFG를 통해 반복문이 어디에 있는지, 반복문의 종료 조건이 무엇인지 명확히 알 수 있으며, 예상 위치에 따라 몇 가지 명령어를 CFG에서 쉽게 찾을 수 있습니다: 예를 들어, arr.length는 반복문 헤더에서 찾을 수 있습니다(이는 v22 = [v0 + 12]입니다). 문자열 연결은 반복문의 끝 부분에서 찾을 수 있습니다(v47 StringConcat(...)). 물론 값 사용 체인은 CFG 버전에서 따라가기 더 어렵지만, 종종 그래프의 제어 흐름 구조를 명확히 보는 것이 값 노드의 수프보다는 더 나은 경우가 많다고 생각합니다.

너무 많은 노드가 효과 체인에 있거나/또는 제어 입력을 갖습니다

Sea of Nodes의 이점을 얻으려면 그래프의 대부분의 노드가 제어 또는 효과 체인 없이 자유롭게 떠다녀야 합니다. 그러나 일반적인 JavaScript 그래프에서는 거의 모든 일반 JS 연산이 임의의 부작용을 가질 수 있기 때문에 이는 실제로 잘 이루어지지 않습니다. 하지만 피드백을 통해 더 구체적인 연산으로 낮출 수 있는 경우에는 Turbofan에서 드물게 나타나야 합니다.

그래도 모든 메모리 연산은 효과 입력(로드가 스토어를 넘어가거나 그 반대가 되지 않도록 하기 위해)과 제어 입력(연산 전에 타입 체크나 경계 체크가 있을 수 있으므로)이 모두 필요합니다. 그리고 나눗셈과 같은 몇몇 순수 연산조차도 제어 입력이 필요합니다. 왜냐하면 특별한 경우가 체크를 통해 보호될 수 있기 때문입니다.

다음 JavaScript 함수를 예로 들어 살펴봅시다:

function foo(a, b) {
  // `a.str` 및 `b.str`이 문자열이라고 가정
  return a.str + b.str;
}

다음은 해당 Turbofan 그래프입니다. 더 명확하게 하기 위해, 효과 체인의 일부를 빨간색 점선으로 강조했고, 아래에서 설명하기 위한 숫자로 몇 개의 노드를 주석 처리했습니다.

첫 번째 관찰은 거의 모든 노드가 효과 체인에 있다는 것입니다. 몇 가지를 살펴보고 정말 필요한지 확인해 보겠습니다:

• 1 (CheckedTaggedToTaggedPointer): 이 노드는 함수의 첫 번째 입력이 포인터인지 아니면 '소정수(small integer)'인지 확인합니다(참조: V8의 포인터 압축(Pointer Compression in V8)). 독립적으로는 효과 입력이 필요하지 않지만, 실제로는 다음 노드를 보호하기 때문에 효과 체인에 연결되어야 합니다.
• 2 (CheckMaps): 이제 첫 번째 입력이 포인터라는 것을 알았으므로, 이 노드는 해당 객체의 '맵(map)'(참조: V8의 맵(숨겨진 클래스)(Maps (Hidden Classes))을 로드하고 피드백에 기록된 대상과 일치하는지 확인합니다.
• 3 (LoadField): 이제 첫 번째 객체가 올바른 맵을 갖춘 포인터라는 것을 알았으므로, .str 필드를 로드할 수 있습니다.
• 4, 5 및 6: 두 번째 입력에 대해 반복합니다.
• 7 (CheckString): a.str을 로드한 후, 이 노드는 그것이 문자열인지 확인합니다.
• 8: 두 번째 입력에 대해 반복합니다.
• 9: a.str과 b.str의 결합된 길이가 V8에서 문자열의 최대 크기보다 작은지 확인합니다.
• 10 (StringConcat): 마지막으로 두 문자열을 연결합니다.

이 그래프는 자바스크립트 프로그램에 대한 Turbofan 그래프에서 매우 일반적입니다: 맵을 확인하고 값을 로드하고 로드된 값의 맵을 확인하는 등의 작업을 수행한 후, 결국 이 값들에 대해 일부 계산을 수행합니다. 이 예시처럼 많은 경우, 대부분의 명령어가 효과 또는 제어 체인에 속하게 되어 연산 간 엄격한 순서를 강요하며 Sea of Nodes의 목적을 완전히 저해합니다.

메모리 작업은 쉽게 떠다니지 않습니다

다음 자바스크립트 프로그램을 고려해 봅시다:

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 그래프를 살펴보며 그 이유를 이해해 봅시다:

SoN 그래프를 작성할 때, 진행하면서 효과 체인을 생성하므로 두 번째 Load는 첫 번째 Load 바로 뒤에 오게 됩니다. 그런 다음 효과 체인은 두 return에 도달하기 위해 분기해야 합니다(return이 효과 체인에 있는 이유가 궁금하다면, 이는 함수에서 반환하기 전에 실행되어야 하는 Store와 같은 부작용 작업이 있을 수 있기 때문입니다). 두 번째 Load가 두 return의 선행 노드이기 때문에, 이는 branch보다 먼저 스케줄되어야 하며, SoN은 두 Load를 자유롭게 아래로 떠다니지 못하게 합니다. Load를 'then'과 'else' 브랜치 아래로 이동하려면, 그 사이에 부작용이 없다는 것과 두 번째 Load와 return 사이에 부작용이 없다는 것을 계산해야 하며, 그런 다음 두 번째 Load 이후가 아닌 시작에서 효과 체인을 나눌 수 있어야 합니다. SoN 그래프나 CFG에서 이 분석을 수행하는 것은 매우 유사합니다.

많은 노드가 효과 체인에 속하게 되고, 효과 노드가 종종 멀리 떠다니지 않는다는 사실을 언급하면서, SoN은 단순히 순수 노드가 떠다니는 CFG라는 점을 인지할 때입니다. 실제로, 제어 노드와 제어 체인은 항상 동등한 CFG 구조를 반영합니다. 자바스크립트에서 branch의 두 대상이 부작용(자주 발생함)이 있을 경우, 효과 체인은 제어 체인과 동일한 위치에서 분기하고 다시 합쳐집니다(위 예에서처럼: 제어 체인은 branch에서 분기하고, 효과 체인은 Load에서 분기하여 이를 반영하며, 프로그램이 if-else 이후 계속된다면 두 체인은 거의 동일한 위치에서 다시 합쳐집니다). 따라서 효과 노드는 일반적으로 두 제어 노드 사이에, 즉 기본 블록 내부에 스케줄링되도록 제한됩니다. 이 기본 블록 내에서 효과 체인은 소스 코드에 있는 순서와 동일한 동일한 순서를 따르게 됩니다. 결과적으로 오직 순수 노드만 자유롭게 떠다닙니다.

더 많은 노드를 떠다니게 하기 위한 한 가지 방법은 앞서 언급했듯이 여러 효과 체인을 사용하는 것입니다. 그러나 이는 비용이 많이 드는 접근 방식입니다. 첫째, 단일 효과 체인을 관리하는 것만으로도 어렵습니다. 여러 개의 체인을 관리하는 것은 훨씬 더 어려울 것입니다. 둘째, 자바스크립트와 같은 동적 언어에서는 많은 메모리 접근이 중복될 가능성이 있어서 여러 효과 체인이 자주 병합되어야 하므로 여러 효과 체인을 사용하는 이점의 일부가 상쇄됩니다.

효과 및 제어 체인을 수동으로 관리하는 것은 어렵습니다

앞서 언급했듯이, 효과 체인과 제어 체인은 약간 구별되지만, 실제로 효과 체인은 일반적으로 제어 체인과 동일한 '형태'를 가집니다: 분기 대상으로 부작용 작업이 포함될 경우(자주 발생함), 효과 체인은 분기 시점에서 분기하고 제어 플로우가 다시 합쳐질 때 효과 체인도 다시 합쳐집니다. 자바스크립트를 다루고 있기 때문에 많은 노드들이 부작용을 가지고 있으며, 많은 분기(일반적으로 객체의 어떤 유형에 따라 분기)가 있습니다. 이는 효과와 제어 체인을 병행하여 추적해야 함을 의미하며, CFG를 사용하는 경우 제어 체인만 추적하면 됩니다.

역사는 효과와 제어 체인을 수동으로 관리하는 것이 오류를 유발하기 쉽고, 읽기 어렵고 유지 관리하기 어렵다는 것을 보여줍니다. 아래는 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), ...);
  [...]
}

여기에서 처리해야 하는 다양한 분기와 경우로 인해 우리는 세 가지 다른 효과 체인을 관리하게 됩니다. 다른 체인을 대신 사용하는 것이 너무 쉽기 때문에 실제로 처음에 실수를 했고 몇 달 후에야 우리의 실수를 인식했습니다:

이 문제에 대해, 나는 Turbofan과 Sea of Nodes 둘 중 하나만의 문제가 아니라 둘 다의 문제라고 생각합니다. Turbofan에서 더 나은 도우미 기능이 있었다면 효과와 제어 체인을 관리하는 것이 더 간단해졌겠지만, 이 문제는 CFG에서는 발생하지 않았을 것입니다.

일정 관리가 너무 복잡함

결국 모든 명령은 어셈블리 코드를 생성하기 위해 일정이 지정되어야 합니다. 명령을 일정 지정하는 이론은 충분히 간단합니다: 각 명령은 해당 값, 제어 및 효과 입력(루프 무시)을 처리한 후에 일정이 지정되어야 합니다.

흥미로운 예제를 살펴보겠습니다:

소스 JavaScript 프로그램에 동일한 두 분할이 있지만, Sea of Node 그래프에는 하나만 있다는 것을 알 수 있습니다. 실제로 Sea of Nodes는 두 개의 분할로 시작하지만, 이 작업이 순수 작업(더블 입력 가정)이기 때문에 중복 제거를 통해 쉽게 하나로 중복 제거됩니다. 그런 다음 일정 지정 단계에 도달하면 이 분할을 일정 지정할 위치를 찾아야 합니다. 분명히 case 1 또는 case 2 이후에는 갈 수 없습니다. 이는 다른 곳에서 사용되기 때문입니다. 대신 switch 이전에 일정이 지정되어야 합니다. 단점은 이제 a / b는 c가 3일 때에도, 실제로 계산되지 않아도 되는 곳에서도 계산될 것입니다. 이는 사용자들 사이의 공통 지배자로 많은 중복 명령이 떠돌아 다니며 필요하지 않은 많은 경로들을 느리게 만드는 실제 문제를 초래할 수 있습니다. 그러나 해결책이 있습니다: Turbofan의 일정 지정자는 이러한 경우를 식별하고 명령을 복제하여 필요한 경로에서만 계산되도록 합니다. 단점은 일정 지정자가 더 복잡해지고, 어떤 노드를 복제해야 하고 복제할 수 있을지를 알아내기 위해 추가 논리가 필요하다는 것입니다. 즉, 우리는 처음에 2개의 분할로 시작해서, 단일 분할로 "최적화"한 뒤 다시 2개의 분할로 추가 최적화했습니다. 그리고 이것은 분할에만 국한되지 않고 다른 많은 작업도 유사한 사이클을 겪을 것입니다.

그래프를 방문하는 좋은 순서를 찾는 것이 어려움

컴파일러의 모든 패스는 그래프를 방문해야 합니다. 노드를 낮추거나, 로컬 최적화나 전반적인 그래프 분석을 적용하기 위해서입니다. CFG에서 노드를 방문할 순서는 일반적으로 명확합니다: 첫 번째 블록에서 시작하고(단일 진입 함수 가정) 블록의 각 노드를 반복한 후 후속 블록으로 이동하는 식입니다. 구멍 체커 최적화 단계(예: 강도 감소)에서는 이러한 순서로 그래프를 처리함으로써 들어오는 정보가 먼저 최적화되고 그 다음에 노드가 처리되며, 각 노드를 정확히 한 번 방문하는 것으로 대부분의 구멍 체커 최적화를 적용하기 충분한 좋은 성질을 가집니다. 예를 들어 다음 축소 시퀀스를 고려하세요:

총 세 단계가 필요했으며 각 단계에서 유용한 작업을 수행했습니다. 이후 불필요한 코드 제거로 인해 v1과 v2가 제거되어 초기 시퀀스보다 명령이 하나 적게 남았습니다.

Sea of Nodes를 사용하면 순수 명령어를 처음부터 끝까지 처리할 수 없습니다. 이는 어떤 제어나 효과 체인에 속하지 않기 때문이며, 따라서 순수 루트에 대한 포인터나 이와 비슷한 것이 없습니다. 대신, Sea of Nodes 그래프에서 peephole 최적화를 처리하는 일반적인 방법은 끝부분(예: return 명령어)에서 시작하여 값, 효과 및 제어 입력으로 이동하는 것입니다. 이렇게 하면 사용되지 않는 명령어를 방문하지 않게 되는 좋은 점이 있지만, peephole 최적화를 위해서는 이것이 가능한 최악의 방문 순서입니다. 위의 예에서, 우리가 수행할 단계는 다음과 같습니다:

• v3를 방문하지만 이 시점에서는 낮출 수 없으므로 그 입력으로 이동합니다.
  • v1을 방문하여 a << 3으로 낮추고, v1의 최적화 가능성을 활성화했을 경우 사용으로 이동합니다.
    • 다시 v3를 방문하지만 아직 낮출 수 없습니다(이번에는 그 입력을 다시 방문하지 않습니다).
  • v2를 방문하여 b << 3으로 낮추고, 이 변환이 최적화를 활성화했을 경우 사용으로 이동합니다.
    • 다시 v3를 방문하여 (a & b) << 3으로 낮춥니다.

결국, v3는 총 3번 방문되었지만 한 번만 낮춰졌습니다.

우리가 일반적인 JavaScript 프로그램에서 이러한 효과를 측정했으며, 평균적으로 노드는 20번 방문할 때마다 한 번씩만 변경된다는 것을 알게 되었습니다!

그래프의 적절한 방문 순서를 찾는 어려움의 또 다른 결과는 상태 추적이 어렵고 비용이 많이 든다는 것입니다. Load Elimination나 Escape Analysis와 같은 많은 최적화는 그래프를 따라 일부 상태를 추적해야 합니다. 그러나 Sea of Nodes에서는 이는 어려운 작업입니다. 특정 상태가 활성 상태로 유지되어야 하는지 여부를 알기 어렵고, 처리되지 않은 노드가 처리되기 위해 이 상태를 필요로 하는지 판단하기도 어렵습니다. 이로 인해 Turbofan의 Load Elimination 단계는 너무 오래 걸리거나 메모리를 너무 많이 사용하지 않기 위해 큰 그래프에서 포기합니다. 비교를 위해 우리는 새 CFG 컴파일러를 위한 새로운 Load Elimination 단계를 작성했으며, 이를 최대 190배 더 빠르게 벤치마킹했습니다(더 나은 최악의 복잡성을 가지고 있으므로 이러한 속도 향상은 큰 그래프에서 쉽게 달성됩니다), 또한 훨씬 적은 메모리를 사용합니다.

캐시 친화성 부족

Turbofan의 거의 모든 단계는 그래프를 제자리에서 변형합니다. 노드가 메모리 내에서 꽤 큰 크기를 가지므로(대부분 각 노드가 자신의 입력과 사용에 대한 포인터를 가지고 있기 때문입니다), 가능한 한 노드를 재사용하려고 합니다. 그러나 불가피하게 노드를 다단계 노드 시퀀스로 낮출 경우 새로운 노드를 도입해야 하며, 이는 필연적으로 메모리에서 원래 노드와 가까운 위치에 할당되지 않습니다. 결과적으로, Turbofan 파이프라인을 깊게 탐색할수록 실행 단계가 많아질수록 그래프는 캐시 친화성이 떨어지게 됩니다. 이 현상을 다음과 같이 설명할 수 있습니다:

캐시 비친화성이 메모리에 미치는 정확한 영향을 추정하기 어렵지만, 이제 새로운 CFG 컴파일러를 사용하여 두 가지 간의 캐시 누락 횟수를 비교할 수 있습니다. Sea of Nodes는 평균적으로 새로운 CFG IR에 비해 L1 데이터 캐시 누락 횟수가 3배 더 많으며, 일부 단계에서는 최대 7배 더 많습니다. 우리는 이것이 컴파일 시간의 최대 5%까지 비용이 든다고 추정하지만, 이 숫자는 어느 정도 추상적입니다. 그래도 JIT 컴파일러에서는 빠른 컴파일이 필수적이라는 점을 명심하십시오.

제어 흐름 의존적 유형 지정이 제한적임

다음 JavaScript 함수를 고려해 봅시다:

function foo(x) {
  if (x < 42) {
    return x + 1;
  }
  return x;
}

현재까지 x와 x+1의 결과에 대해 작은 정수만 본 경우(“작은 정수”는 31비트 정수, cf. 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 최적화는 아닙니다.

V8에서는 31비트 작은 정수 최적화로 인해 체크된 연산이 자주 발생하는데, 체크된 연산을 체크되지 않은 연산으로 대체할 수 있는 기능은 Turbofan이 생성하는 코드의 품질에 큰 영향을 미칠 수 있습니다. 그래서 Turbofan의 SoN은 CheckedAdd에 컨트롤 입력을 넣어 이 최적화를 가능하게 하지만, 이로 인해 순수 노드에 스케줄링 제약을 도입하게 되며, 즉 CFG로 되돌아가게 됩니다.

그리고 많은 다른 문제들…

죽음을 전파하는 것은 어렵습니다. 종종, 일부 낮추는 과정에서 현재 노드가 실제로 도달할 수 없음을 알게 됩니다. CFG에서는 현재 기본 블록을 여기서 자르기만 하면 되고, 이후 블록은 더 이상 후속 블록이 없기 때문에 자동으로 명백히 도달할 수 없는 상태가 됩니다. 하지만 Sea of Nodes에서는 제어 체인과 영향 체인을 모두 수정해야 하기 때문에 더 어렵습니다. 따라서 영향 체인에 있는 노드가 죽었을 경우, 다음 병합까지 영향 체인을 앞으로 걸어가며 경로를 따라 모든 것을 제거하고, 제어 체인의 노드를 신중히 처리해야 합니다.

새로운 제어 흐름을 도입하는 것은 어렵습니다. 제어 흐름 노드가 제어 체인에 있어야 하기 때문에, 일반적인 낮추는 과정에서 새로운 제어 흐름을 도입할 수 없습니다. 예를 들어, 그래프 내에 Int32Max와 같은 순수 노드가 있고, 이는 두 정수 중 최대값을 반환하는데, 이를 궁극적으로 if (x > y) { x } else { y }로 낮추고 싶다면, 이것을 Sea of Nodes에서는 쉽게 할 수 없습니다. 왜냐하면 이 서브그래프를 제어 체인의 어느 부분에 연결할지를 알아내는 방법이 필요하기 때문입니다. 이를 구현하는 한 가지 방법은 처음부터 Int32Max를 제어 체인에 올려놓는 것이지만, 이는 낭비처럼 느껴질 수 있습니다. 이 노드는 순수하며 자유롭게 이동할 수 있어야 합니다. 따라서 이를 해결하기 위한 Sea of Nodes의 정식 방법, Turbofan과 Sea of Nodes의 발명가인 Cliff Click이 사용하는 방법으로, Coffee Compiler Club 대화에서 언급된 것처럼, 스케줄이 있고 CFG가 있을 때까지 이러한 낮추는 과정을 지연시키는 것입니다. 그 결과, 파이프라인 중간에 스케줄을 계산하고 그래프를 낮추는 단계가 있으며, 여기에는 많은 무작위적인 최적화가 포함됩니다. 이 최적화들은 모두 스케줄을 필요로 하기 때문입니다. CFG와 비교하면 이러한 최적화를 파이프라인 전에 하거나 나중에 할 수 있는 자유가 있습니다. 또한, 소개에서 Crankshaft(Turbofan의 전신)의 한 가지 문제는 그래프를 구축한 후에 제어 흐름을 도입하는 것이 사실상 불가능하다는 점이었습니다. Turbofan은 약간의 개선이 이루어졌으며, 제어 체인의 노드를 낮추는 과정에서 새로운 제어 흐름을 도입할 수 있지만 여전히 제한적입니다.

루프 내부에 무엇이 있는지 알아내는 것은 어렵습니다. 많은 노드가 제어 체인 밖에 떠 있기 때문에 각 루프 내부에 무엇이 있는지 알아내기가 어렵습니다. 그 결과, 루프 피링 및 루프 언롤링과 같은 기본 최적화를 구현하기도 어렵습니다.

컴파일이 느립니다. 이것은 앞서 언급한 여러 문제들의 직접적인 결과입니다. 노드의 방문 순서를 잘 찾기가 어려워 많은 쓸모 없는 재방문이 발생하고, 상태 추적 비용이 비싸며, 메모리 사용량이 나쁘고, 캐시 지역성이 나쁘고… 이 문제들은 사전 컴파일러에게는 큰 문제가 아닐 수 있지만, JIT 컴파일러에서는 느린 컴파일이 최적화된 코드가 준비될 때까지 느리고 최적화되지 않은 코드를 계속 실행한다는 의미이며, 이는 다른 작업(JIT 컴파일 작업 등) 또는 Garbage Collector로부터 자원을 가져가는 결과를 초래합니다. 이로 인해 새로운 최적화의 컴파일 시간 - 속도 향상 균형을 매우 신중히 고려해야 하며, 종종 빠른 최적화를 유지하기 위해 최적화를 덜 하는 쪽으로 치우치는 경우가 많습니다.

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: JavaScript에 대해 우아하지만 비실용적임

요약하자면, Sea of Nodes와 Turbofan과 관련한 주요 문제는 다음과 같습니다:

1. 그것은 너무 복잡합니다. 효과와 제어 체인은 이해하기 어렵고, 많은 미묘한 버그를 유발합니다. 그래프를 읽고 분석하기 어려워 새로운 최적화를 구현하고 개선하기 힘듭니다.

2. 그것은 너무 제한적입니다. 너무 많은 노드가 효과 및 제어 체인에 포함되어 있습니다(JavaScript 코드를 컴파일하기 때문), 그래서 전통적인 CFG보다 많은 이점을 제공하지 못합니다. 또한, 로워링에서 새로운 제어 흐름을 도입하기 어렵기 때문에 기본적인 최적화조차 구현하기 어렵습니다.

3. 컴파일이 너무 느립니다. 그래프를 방문하는 좋은 순서를 찾기 어려워 상태 추적이 비용이 많이 듭니다. 캐시 지역성이 좋지 않습니다. 감소 단계에서 고정점을 도달하는 데 너무 많은 시간이 걸립니다.

그래서 Turbofan과 Sea of Nodes와 싸우는 데 10년을 보낸 후 결국 이를 버리고 보다 전통적인 CFG IR로 돌아가기로 결정했습니다. 새로운 IR에 대한 경험은 지금까지 매우 긍정적이며 CFG로 돌아간 것에 대해 매우 만족합니다: SoN과 비교했을 때 컴파일 시간이 절반으로 줄었고, 컴파일러의 코드가 훨씬 간단하고 짧아졌으며, 버그를 조사하는 것도 일반적으로 훨씬 더 쉬워졌습니다. 이 포스트는 이미 상당히 길어졌으니 여기서 마치겠습니다. 새로운 CFG IR인 Turboshaft의 설계를 설명할 예정인 블로그 게시물을 기대해 주세요.