이전이야기

이전 글에서는 React Compiler가 AST를 HIR로 변환하는 과정을 살펴보았어요. HIR (High-level Intermediate Representation)는 CFG(Control Flow Graph)를 사용하여 AST를 변환한 중간 표현이었습니다.

그 다음은?

하지만, 더 디테일한 최적화를 하기 위해서는 기본적인 HIR의 형태만으로는 부족합니다.
무엇이 더 필요할까요?
최적화 과정중 하나인, 상수전파(constant propagation)과정을 가지고 살펴봅시다.

상수전파란 변수에 상수가 대입되어 있을 때, 해당 변수를 상수로 대체하는 최적화 기법입니다.
간단하게 설명해보자면, 미리 대입할 수 있는 것들을 대입해 놓는 것이죠.

예시를 들어보겠습니다.

x = 5
y = x + 2
x = 10
z = x + y

이런 코드가 있다고 가정해봅시다.(실제로는 HIR 형태로 변환된 코드겠죠?)
여기서 def-use chain이라는 개념을 사용하게 됩니다.
def-use chain은 변수의 할당(def)과 사용(use)의 관계를 의미합니다.

x의 첫 번째 할당(def) x = 5는 y = x + 2에서 사용(use) 되지만, z = x + y에는 영향을 주지 않습니다.
그리고 x의 두 번째 할당 x = 10은 z = x + y에서 사용됩니다.
y = x + 2에서 사용된 x의 값과 z = x + y에서 사용된 x의 값은 다르다는 것을 알 수 있습니다.

이런 복잡한 관계를 추적하려면 더 디테일한 데이터 흐름에 대한 분석이 필요합니다.
그래서 HIR을 SSA로 변환하는 과정이 필요한 것이죠.

변환하게 되면 아래와 같이 변환됩니다.

x1 = 5
y1 = x1 + 2
x2 = 10
z1 = x2 + y1

오! 변수에 인덱스가 붙었네요. x가 x1, x2로 나눠졌습니다

이렇게 변환하게 되면, def-use chain을 추적하기가 훨씬 쉬워집니다. 내가 사용하는 x가 어떤 x인지 알 수 있죠.
그러면 이제 좀 더 자신있게, y는 7이고, z는 17이라고 말할 수 있겠죠?
이렇게 대체할 수 있는 변수들을 대체해 놓는 것이 상수전파 최적화입니다.
그리고 SSA형태를 통해서 편하게 이런 작업을 할 수 있는 것도 빠르게 살펴볼 수 있었습니다.

이번 글에서는 HIR를 SSA로 변환하는 과정을 살펴보겠습니다.

먼저 SSA가 무엇인지 알고 넘어가야겠죠?

잠깐! 상수 전파는 SSA 변환을 하지 않아도 알 수 있습니다. 이때 도달 정의 분석 방식을 사용할 수 있습니다.
궁금하신 분만 읽어보시고, 바로 아래로 넘어가셔도 좋습니다.

SSA (정적 단일 대입, Static Single Assignment)

SSA는 정적 단일 대입이라는 뜻으로, 최적화를 위해 사용되는 중간 표현 중 하나입니다.
SSA는 변수가 한 번만 대입되도록 제한하는 특징이 있습니다.
이는 위에서 간단한 예시로 든 것처럼 def-use chain을 추적하기가 쉽도록 도와줍니다.

아까의 예시를 다시 살펴봅시다.

x = 5
y = x + 2
x = 10
z = x + y

우리는 여러번 정의되고 할당되는 이 x, y, z변수들을 아래와 같이 변환해주었습니다.

x1 = 5
y1 = x1 + 2
x2 = 10
z1 = x2 + y1

각 변수들에게 한 번에 하나의 정의를 부여하도록 변환을 하여 def-use chain을 심플하게 만들어준 것이죠. 이로써 각 변수의 짐을 덜어주고, 데이터의 흐름 파악이 조금 더 쉬워집니다.

생각보다 간단하죠? 🤓

그렇다면 이런경우는 어떻게 변환 할 수 있을까요?

if(condition){
  x = 5
} else {
  x = 10
}
y = x + 2

흠 몇 줄 안되는 코드인데, 바로 변환해보겠습니다.

if(condition){
  x1 = 5
} else {
  x2 = 10
}
// ...

새로운 x를 만날때 마다 새로운 변수로 잘 바꿔주었습니다.
여기까지는 수월하게 변환했는데요. 그 다음줄에서 난관에 부딪히게 됩니다.

y1 = x + 2 // 🤔 y는 y1로 바꾸면 되겠는데... x는 뭐로 바꾸지?

condition에 따라 x가 정해져야하는데, 어떤 x가 들어가는지 표시 하는법은 아직 모르겠습니다.

위의 케이스는 x가 if-else문의 조건에따라 다른 값을 가질 수 있는 경우입니다.
y = x + 2에서 사용된 x는 어떤 x인지 알 수 없습니다. 조건문을 만났더니 이전의 예시처럼 쉽게 x 넣을 수 없습니다.

참지 못하고 답안지를 먼저 살펴보겠습니다.
SSA로 변환하게 되면 아래와 같이 변환됩니다.

if(condition){
  x1 = 5
} else {
  x2 = 10
}
x3 = φ(x1, x2)
y1 = x3 + 2

φ(이하 ‘phi’)라는 함수가 등장했습니다.

phi는 if-else문과 같은 분기 의해 다른 값을 가질 수 있는 변수를 결합하는 함수입니다.
이로써 우리는 x3를 새로운 변수로 만들어주고, φ함수를 통해if-else문의 조건에 따라 x1과 x2중 하나를 선택하게 됩니다.
φ함수의 역할을 다른 말로 표현해보면, 분기를 합류시켜주는 함수라고도 할 수 있겠죠.

시간여행 영화에서처럼 선택에 의해 분기된 두 평행우주 속 x를 다시 하나로 합쳐주는 것 처럼 보입니다.

SSA의 주요 개념을 정리하면 아래와 같습니다.

1. 각 변수의 단일 정의:

• SSA 형태에서는 각 변수는 프로그램 내에서 단 한 번만 정의됩니다. 즉, 동일한 변수 이름이 여러 번 정의되지 않습니다. 이를 위해 변수를 정의할 때마다 새로운 이름(예: x1, x2, x3)을 부여합니다.

2. φ (phi) 함수:

• 제어 흐름이 합쳐지는 지점에서는 여러 정의를 하나로 합치는 φ(phi) 함수를 사용합니다. φ 함수는 제어 흐름의 어느 경로를 통해 도달했는지에 따라 다른 값을 선택합니다.

이제 의미적으로는 phi함수를 어디에 놓아야하는지는 쉽게 이해 할 수 있습니다.
‘적절한 분기의 합류 지점에 둔다.’ 이렇게 요약해 볼 수 있겠죠.
하지만 이걸 논리적으로 표현해야한다면, 어떻게 해야할까요?

SSA 변환 알고리즘

SSA 변환 알고리즘의 핵심은 phi함수를 어디에 놓을지를 결정하는 것입니다.
React Compiler의 경우 커밋을 살펴보면 아래의 논문(Simple and Efficient Construction of Static Single Assignment Form)의 알고리즘을 사용하고 있습니다.

Add SSA-ify pass · facebook/react@379251c · GitHub

The library for web and native user interfaces. Contribute to facebook/react development by creating an account on GitHub.

https://github.com/facebook/react/commit/379251c65f39039ace1d2e5a80bdb5938cf3427c

// commit message
The algorithm is described in detail here: 

https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf 
// 링크가 잘못되어있어서 교체했습니다.

Note that the SSA form generated is not minimal. A follow on 
RedundantPhiElimination pass 

is required to prune the graph.

이 논문에서는 Cytron et al.의 알고리즘에 대한 개선된 버전을 제안하고 있습니다.
기존 알고리즘에 비해서 더 단순하고, 효율적이라고 합니다.
그렇다면 이 장점을 느껴보기 위해서는 Cytron의 알고리즘을 먼저 살펴보는 것이 좋겠죠? (바로 다음 챕터로 넘어가셔도 좋습니다.)

Cytron의 알고리즘

이 논문은 1991년 IBM Research에서 발표된 논문으로, SSA를 생성하는 알고리즘 중 하나입니다.

주요 개념은 Dominator Tree와 Dominator Frontier입니다.

1. 지배자 트리(Dominator Tree) 구성: 프로그램의 제어 흐름 그래프(CFG)에서 각 노드 간의 지배 관계를 표현하는 트리를 구성합니다.
2. 지배 경계(Dominance Frontier) 계산: 각 노드에 대해 지배 경계를 계산합니다. 지배 경계는 노드가 직접 지배하지 않는 가장 가까운 후손 노드들의 집합입니다.

우리가 궁금했던 것은 phi함수를 어디에 놓아야할지에 대한 것이니깐. 그것을 목적으로 논문을 탐구해봅시다.
이 알고리즘에서는 우선적으로 전체 트리에 대한 분석이 이뤄집니다. 이것을 통해 지베자 트리를 구성하고 지배 경계를 계산하게 됩니다.
그리고 이를 통해 phi함수를 어디에 놓아야할지를 결정하게 됩니다.

지배자 트리(Dominator Tree)

우선 지배자 트리 Dominator Tree란 무엇일까요?
여기서 지배(Dominance), 노드 A가 노드 B를 지배한다는 것은, B로 가는 모든 경로가 A를 통과해야 한다는 것을 의미합니다.
또한 모든 노드는 자기 자신을 지배한다고 가정합니다.

이런 CFG(우리의 경우 HIR이 되겠죠?)가 있다고 가정하고 지배관계를 살펴봅시다.

• 2번과 5번은 반드시 1번을 지나야합니다. 그러므로 1번이 2번과 5번을 지배합니다.
• 3번과 4번은 반드시 1, 2번을 지나야합니다. 그러나 지배 관계에선 제일 가까운 지배자만 고려하기로 합니다. 그러므로 2번이 3번을 지배합니다.
• 6번의 경우는 3번, 4번이 부모지만, 반드시 지나가야하는 것은 아닙니다. 그럼 한단계 위로 올라가서 보면 2번은 반드시 지나가야합니다. 그러므로 2번이 6번을 지배합니다.
• 7번의 경우도 똑같이 6번과 5번을 통해 올 수 있습니다. 그러므로 각 루트를 쭉 따라 올라가다보면 1번을 반드시 지나야하는 것을 알 수 있습니다. 그러므로 1번이 7번을 지배합니다.

이 관계를 다시 트리(지배자 트리)로 표현하면 아래와 같습니다.

위에서 살펴봤던 지배 관계대로 표현이 되어있죠?
기존의 CFG와 언듯 비슷해보이지만, 조금은 다른 모습을 보이고 있습니다.
반드시 지나야 하다보니깐, 큰 분기를 두고 있는 것들은 분기 이전 노드가 지배하게 되는 것을 볼 수 있습니다. (7이 대표적이죠)

지배 경계(Dominance Frontier)

그 다음으로 지배 경계(Dominance Frontier)를 계산합니다.
노드 N의 지배 경계(DF)는 다음과 같이 정의됩니다:

• N이 직접 지배하지 않지만, N이 직접 지배하는 노드가 지배하는 CFG의 노드들의 집합
  직관적으로는, DF(N)은 N의 지배력이 끝나는 지점이라고 생각할 수 있습니다.

이게 무슨말인가? 😥 이해가 단번에 되지 않습니다.
그림으로 2와 5의 지배 경계 DF를 구하는 과정을 같이 살펴보도록 하죠.

2의 경우 3,4,6 그리고 2(본인) 을 지배합니다.
그러면 지배하고 있는 2, 3, 4, 6의 자식중에 2가 지배하지 않는 노드들을 찾아보면 6의 자식인 7을 찾을 수 있습니다.
그러므로 DF(2)는 7이 됩니다.

5의 경우 지배트리를 보면 본인 밖에 없습니다.
CFG에서 5가 지배하지 않는 노드는 자식인 7이 됩니다.
그러므로 DF(5)는 7이 됩니다.

이런식으로 지배 경계를 계산하게 됩니다. 그럼 각 경우를 다 살펴보면 아래와 같습니다.

DF(1) = {} // 1은 모든 노드를 지배하므로 DF가 없음
DF(2) = {7}
DF(3) = {6}
DF(4) = {6}
DF(5) = {7}
DF(6) = {7}
DF(7) = {} 

이제 완전히 이해 가지 않아도 대략적으로 어떤 식으로 DF를 찾을 수 있는지 알 수 있게 되었습니다.
DF에 있는 노드들에 phi함수를 놓게 됩니다.

흠 뭔가 아직 명쾌하게 풀리진 않을 수 있습니다. 그래프를 가지고 장난을 치는 것 같이 보이죠.

그렇다면 지배 경계의 정의로 부터 의미를 분석해봅시다.
DF(X) = Y, X의 지배 경계는 Y라는 의미를 살펴봅시다. Y는 X의 지배력이 끝나는 지점이라고 볼 수 있겠죠.

1. DF의 정의에 따라 Y는 X가 지배하는 노드의 자식 노드입니다.
   이말은 X를 통해서 Y로 가는 경로가 있다는 것을 의미합니다.
2. DF의 정의에 따라 Y는 X의 직접 지배 관계가 아니다.
   이 말은 Y로 가는 경로가 반드시 X를 지나지 않는다는 것을 의미합니다.

종합해 보면 Y는 X를 통해서도 갈 수 있지만, 다른 경로로도 갈 수 있는 노드입니다.
그럼 적어도 두개의 경로를 통해 Y로 향할 수 있다는 의미가 되겠죠.
그 말은 즉 분기가 합류되는 지점이라는 것을 의미합니다.

그러므로 phi함수를 분기가 합류되는 지점, 즉 지배 경계 DF에 놓게 됩니다.
이제 대략 이해가 되었으니 코드로 살펴봅시다.

아까 예시 코드도 그래프로 표현해볼까요?

if(condition){
  x = 5
} else {
  x = 10
}
y = x + 2

우선 HIR 형태로 간단하게 표현해봅시다

bb0:
  if (condition) goto bb2 else goto bb3
bb2:
  x = 5
  goto bb1
bb3:
  x = 10
  goto bb1
bb1:
  y = x + 2

bb0, bb1, bb2, bb3, 4개의 블럭으로 나눠지고 CFG와 DT그래프를 그려보면 아래와 같이 그려지게 됩니다.

그럼 각각의 DF를 구해봅시다.

DF(bb0) = {} 
DF(bb2) = {bb1} 
DF(bb3) = {bb1}
DF(bb1) = {} 

DF들을 살펴보면 bb1하나만 존재하는 군요! 🥳
그러면 phi함수는 bb1에 놓게 됩니다.
위에서 변환해봤던 것처럼 y = x + 2가 있는 블럭에 phi함수가 놓이게 되는 것이죠.

참 간단하죠? 😊

Cytron 알고리즘은 이런 방법으로 지배트리와 지배 경계를 통해 phi함수를 놓게 됩니다.
하지만, 이 알고리즘을 실행하기 위해서는 지배트리를 먼저 만들어야하고, DF를 계산해야하는 이런 과정들이 필요합니다.
리소스가 많이 든다고 느껴지시나요?

시간이 흘러 2013년, Braun은 이 알고리즘을 개선한 논문을 발표하게 됩니다.

Braun의 알고리즘

이 논문은 2013년 Karlsruhe Institute of Technology에서 Matthias Braun 등이 발표한 논문입니다.
아까 커밋에서 살펴본 것 처럼 React Compiler에서 사용하고 있는 알고리즘이죠.

Add SSA-ify pass · facebook/react@379251c · GitHub

The library for web and native user interfaces. Contribute to facebook/react development by creating an account on GitHub.

https://github.com/facebook/react/commit/379251c65f39039ace1d2e5a80bdb5938cf3427c

React Conf 2024에서 Q&A 시간에 컴파일러 개발을 위해 Meta에서 컴파일러 전문가들을 많이 영입했다는 이야기가 나왔었는데요.
이 논문의 저자 Braun도 현재 Meta에서 2018년부터 Compiler Engineer로 일하고 있하고 있는 것을 링크드인에서 찾아 볼 수 있습니다.

Braun의 알고리즘은 Cytron의 알고리즘과 비교하여 몇 가지 중요한 개선점을 가지고 있습니다:

1. Cytron의 알고리즘과 달리 지배자 트리나 지배 경계를 미리 계산할 필요가 없습니다.
2. 추상 구문 트리(AST)나 바이트코드에서 직접 SSA 형식으로 변환할 수 있습니다.
3. 코드를 수정할 때마다 SSA 형식을 다시 계산할 필요가 없습니다.

Braun의 알고리즘의 주요 단계는 다음과 같습니다:

1. 지역 값 번호 매기기 Local Variable Numbering: 단일 기본 블록 내에서 변수의 정의와 사용을 추적하는 과정입니다. 주요 목적은 중복 계산을 제거하고 지역적 최적화를 수행
2. 전역 값 번호 매기기 Global Variable Numbering: 단일 기본 블럭을 넘어 전체 제어 흐름 그래프(CFG) 내에서 변수의 정의와 사용을 추적하는 과정입니다.

지역 값 번호 매기기(Local Variable Numbering)

function foo() {
  let x = 0;
  if (x > 3) {
    x = 5;
  } else {
    x = 10;
  }
  let y = x + 2;
}

이 예제 코드를 가지고 진행 과정을 살펴봅시다.
중간에 조건문이 있음으로 이 코드는 중간이 두개의 블럭으로 나눠질 것입니다.
그래서 HIR로 변환하면 아래와 같이 변환됩니다. (이번에는 컴파일러의 중간 결과물 HIR로 살펴봅시다)

function foo
bb0 (block):
  [1] $0 = 0
  [2] $2 = StoreLocal Let x$1 = $0
  [3] $7 = LoadLocal x$1
  [4] $8 = 3
  [5] $9 = Binary $7 > $8
  [6] If ($9) then:bb2 else:bb3 fallthrough=bb1
bb2 (block):
  predecessor blocks: bb0
  [7] $3 = 5
  [8] $4 = StoreLocal Reassign x$1 = $3
  [9] Goto bb1
bb3 (block):
  predecessor blocks: bb0
  [10] $5 = 10
  [11] $6 = StoreLocal Reassign x$1 = $5
  [12] Goto bb1
bb1 (block):
  predecessor blocks: bb2 bb3
  [13] $10 = LoadLocal x$1
  [14] $11 = 2
  [15] $12 = Binary $10 + $11
  [16] $14 = StoreLocal Let y$13 = $12
  [17] $15 = <undefined>
  [18] Return $15

분기 이전의 bb0, if의 then블럭인 bb2, else블럭인 bb3 그리고 분기 이후의 bb1로 나눠진 것을 볼 수 있습니다.
먼저 각 블럭에 대해서 지역 값 번호 매기기를 수행합니다.

기존 HIR에서는 공통적으로 x$1이라는 변수를 사용하고 있습니다.
이걸 이제 각 블럭에 대해서 새로운 변수로 변환해야합니다. 이때 각 변수의 정의def와 사용use을 추적합니다.
정의와 사용이 같은 블럭에 있을 때, 새로운 지역 값를 매기게 됩니다.

bb0에서는 정의인 StoreLocal과 사용인 LoadLocal이 같은 블럭에 있으므로 새로운 지역 값x_1를 매기게 됩니다.
bb2에서는 StoreLocal과 Reassign이 같은 블럭에 있으므로 지역 값x_2를 매기게 됩니다.
bb3에서도 마찬가지로 지역 값x_3를 매기게 됩니다.

bb0의 x는 x_1, bb2의 x는 x_2, bb3의 x는 x_3으로 변환됩니다.

function foo
bb0 (block):
  [1] $0 = 0
  [2] $2 = StoreLocal Let x$1 = $0 // x$1 -> x$1 
  [3] $7 = LoadLocal x$1
  [4] $8 = 3
  [5] $9 = Binary $7 > $8
  [6] If ($9) then:bb2 else:bb3 fallthrough=bb1
bb2 (block):
  predecessor blocks: bb0
  [7] $3 = 5
  [8] $4 = StoreLocal Reassign x$2 = $3 // x$1 -> x$2
  [9] Goto bb1
bb3 (block):
  predecessor blocks: bb0
  [10] $5 = 10
  [11] $6 = StoreLocal Reassign x$3 = $5 // x$1 -> x$3
  [12] Goto bb1
bb1 (block):
  predecessor blocks: bb2 bb3
  [13] $10 = LoadLocal x$1 // x$1 -> ??
  [14] $11 = 2
  [15] $12 = Binary $10 + $11
  [16] $14 = StoreLocal Let y$13 = $12
  [17] $15 = <undefined>
  [18] Return $15

그런데 bb1에서는 정의와 사용이 같은 블럭에 있지 않습니다.
정의(def)부분은 찾아볼 수 없고 바로 LoadLocal(use)이 있습니다.
그러면 이 경우는 지역 값을 매길 수 없습니다. 그렇게 다음단계인 전역 값 번호 매기기로 넘어가게 됩니다.

전역 값 번호 매기기(Global Variable Numbering)

전역 값 번호 매기기는 지역 값 번호 매기기에서 지역적인 것을 넘어 전체 제어 흐름 그래프(CFG) 내에서 변수의 정의와 사용을 추적하는 과정입니다.
이 과정을 통해 phi함수를 놓을 위치를 찾게 됩니다.

bb1에서의 y = x + 2를 처리하려면, x의 값을 찾아야합니다. 하지만 bb1에서는 정의 부분을 찾아 볼 수 없음으로 우리는 이전으로 돌아가서 x의 값을 찾아야합니다.
여기서부턴 재귀적으로 x의 정의를 찾아 올라가게 됩니다.
블럭 상단에 보면

bb1 (block):
  predecessor blocks: bb2 bb3

이런 것들이 보이는데요.
이 predecessor(전임자)를 통해 이전 블럭으로 올라가게 됩니다.

predecessor는 어떻게 찾을 수 있을까요?

위의 그래프에서 볼 수 있듯이 이전 블럭이 predecessor 됩니다.

predecessor가 하나였다면 x의 정의를 이전 블럭에서 쉽게 찾았을 겁니다.

하지만 bb1의 경우는 bb2와 bb3 두개의 predecessor를 가지고 있습니다. 이 두 블럭에서 x의 정의를 찾아야합니다.
그럼 각 블럭을 찾아볼까요?
bb2에는 x_2의 정의가 있고, bb3에는 x_3의 정의가 있습니다.
이 의미는 bb1은 분기가 합류되는 지점이라고도 볼 수 있겠죠!

그렇다면 자신있게 phi함수를 bb1에 놓아 봅시다.

bb1 (block):
  predecessor blocks: bb2 bb3
  x$4: phi(bb2: x$2, bb3: x$3) // phi 함수 추가
  [14] $10 = LoadLocal x$4 // x$1 -> x$4
  [15] $11 = 2
  [16] $12 = Binary $10 + $11
  [17] $14 = StoreLocal Let y$13 = $12
  [18] $15 = <undefined>
  [19] Return $15

이렇게 phi함수를 추가함으로써, SSA 변환의 고비중 하나였던, 분기가 합류되는 지점에 phi함수를 놓는 것을 성공적으로 해냈습니다.
생각보다 간단하죠? 🤓

이 과정말고도 phi함수들의 최적화를 위한 과정들이 더 있지만, 이정도만 알아도 Braun의 알고리즘의 SSA 변환의 핵심을 이해할 수 있습니다.

두개의 논문을 살펴보면서 사실상 SSA변환의 핵심은 다 파악하게 되었습니다.
그렇다면 이제 React Compiler의 SSA 변환을 살펴보러 가봅시다!

React Compiler의 SSA 변환

이전 글에서 살펴보기 시작했던 Pipeline.ts의 runWithEnvirionment함수를 다시 꺼내봅시다.

// packages/babel-plugin-react-compiler/src/Entrypoint/Pipline.ts
function* runWithEnvironment(
  func: NodePath<
    t.FunctionDeclaration | t.ArrowFunctionExpression | t.FunctionExpression
  >,
  env: Environment
): Generator<CompilerPipelineValue, CodegenFunction> {
  const hir = lower(func, env).unwrap();
  // ...
  enterSSA(hir);
  // ...
}

lower 이후 몇가지 최적화 과정을 거친뒤 enterSSA함수를 통해 HIR을 SSA로 변환을 시작해주게 됩니다.

그럼 enterSSA함수를 통해 SSA 변환 과정을 살펴보도록 하죠!

export default function enterSSA(func: HIRFunction): void {
  const builder = new SSABuilder(func.env, func.body.blocks);
  enterSSAImpl(func, builder, func.body.entry);
}

이전 과정에서 만들어진 HIRFunction을 가지고 SSABuilder를 만들어주고, enterSSAImpl함수를 통해 SSA 변환을 시작합니다.
SSABuilder는 여러가지 SSA 변환을 도와주는 메서드들을 가지고 있습니다.
자세한 메서드들은 변환 과정을 통해 소개해 보기로 합시다.

function enterSSAImpl(
  func: HIRFunction,
  builder: SSABuilder,
  rootEntry: BlockId
): void {
  const visitedBlocks: Set<BasicBlock> = new Set();
  for (const [blockId, block] of func.body.blocks) {
    // ... SSA 변환 과정
  }
}

enterSSAImpl함수는 rootEntry를 시작으로 모든 블럭을 방문하게 됩니다.
for문을 통해 블럭을 하나씩 방문하게 되는데, 이때 SSA 변환이 이뤄지게 됩니다.
visitedBlocks Set을 가지고 시작하는 것을 보니, 재방문에 대한 검증이 필요한 부분이 있을 것 같습니다.

for (const [blockId, block] of func.body.blocks) {
  CompilerError.invariant(!visitedBlocks.has(block), {
    reason: `found a cycle! visiting bb${block.id} again`,
    description: null,
    loc: null,
    suggestions: null,
  });

  visitedBlocks.add(block);
  // ...
}

이미 방문한 블럭을 다시 방문하는 경우는 루프가 있는 경우이므로 에러와 함께 종료하게 됩니다.
그렇지 않다면, visitedBlocks에 추가하고 SSA 변환을 시작하게 됩니다.

초기화

for (const [blockId, block] of func.body.blocks) {
  // ...
  builder.startBlock(block);
}

// SSABuilder
class SSABuilder {
  #states: Map<BasicBlock, State> = new Map();
  #current: BasicBlock | null = null;
  // ...

  startBlock(block: BasicBlock): void {
    this.#current = block;
    this.#states.set(block, {
      defs: new Map(),
      incompletePhis: [],
    });
  }
}

startBlock 메서드를 통해 현재 블럭과 블럭에 대한 상태를 builder를 통해 초기화해주게 됩니다.

파라미터 처리

컴파일러의 컴파일 단위는 이전에 살펴봤던 것 처럼 함수단위로 이뤄지게 됩니다.
그렇다면 함수의 시작부분인 파라미터에 대한 처리가 필요하겠죠?

for (const [blockId, block] of func.body.blocks) {
  // ...
  if (blockId === rootEntry) { // rootEntry인 경우
    func.params = func.params.map((param) => {
      // 일반적인 파라미터인 경우, foo(a, b, c)에서 a, b, c
      if (param.kind === "Identifier") {
        return builder.definePlace(param);
      } else {
        // Spread 파라미터인 경우, foo(...rest)에서 ...rest
        return {
          kind: "Spread",
          place: builder.definePlace(param.place),
        };
      }
    });
  }
  // ...
}

먼저 rootEntry인 경우에는 함수 파라미터를 builder의 definePlace를 통해 다시 정의해주게 됩니다.

class SSABuilder {
  // ...
  definePlace(oldPlace: Place): Place {
    const oldId = oldPlace.identifier;
    const newId = this.makeId(oldId);
    this.state().defs.set(oldId, newId);
    return {
      ...oldPlace,
      identifier: newId,
    };
  }
  // ...
  makeId(oldId: Identifier): Identifier {
    return {
      id: this.nextSsaId,
      name: oldId.name,
      mutableRange: {
        start: makeInstructionId(0),
        end: makeInstructionId(0),
      },
      scope: null, // reset along w the mutable range
      type: makeType(),
      loc: oldId.loc,
    };
  }
  get nextSsaId(): IdentifierId {
    return this.#env.nextIdentifierId;
  }
}

이때, 기존의 identifier를 makeId메서드를 통해 새로운 identifier로 만들어주게 됩니다.
id의 경우는 next.SsaId라는 getter를 통해 새로 가져오게 되는데요.
전역 단위로 관리되는 Environment의 nextIdentifierId를 통해 새로운 id를 가져오게 됩니다.
즉 SSA 단위의 새로운 id를 지정하는 것이 아니고, 전역적으로 새로운 id가 할당 될 것 입니다.
이전까지 (lowering과정) 에서 10까지 사용했다면, SSA 변환을 통해 11부터 새로운 id가 할당될 것입니다.

// Environment.ts
makeIdentifierId(id: number): IdentifierId {
  return id as IdentifierId;
}

class Environment {
  get nextIdentifierId(): IdentifierId {
    return makeIdentifierId(this.#nextIdentifer++);
  }
}

개인적으로는 흥미로운 스킬이 있었는데요. 새 id를 getter를 통해 return하고 후위증감연산자를 통해 id를 하나 올려주는 방식이었습니다.

이런식의 id관리 방법은 모달 관리 할때도 사용해보면 좋을 것 같습니다.

인스트럭션 변환

이 다음 과정으로는 인스트럭션에 대한 변환을 진행하게 됩니다.
여기서는 예제코드와 함께 변환 과정을 살펴보도록 합시다.

function foo() {
  let y = 333;

  if (y > 1) {
    y = 111;
  } else {
    y = 222;
  }

  let x = y;
}

이 코드를 HIR형태로 변환하면 아래와 같이 변환됩니다.

function foo
bb0 (block):
  [1] $0 = 333
  [2] $2 = StoreLocal Let y$1 = $0
  [3] $7 = LoadLocal y$1
  [4] $8 = 1
  [5] $9 = Binary $7 > $8
  [6] If  $9) then:bb2 else:bb3 fallthrough=bb1
bb2 (block):
  predecessor blocks: bb0
  [7] $3 = 111
  [8] $4 = StoreLocal Reassign y$1 = $3
  [9] Goto bb1
bb3 (block):
  predecessor blocks: bb0
  [10] $5 = 222
  [11] $6 = StoreLocal Reassign y$1 = $5
  [12] Goto bb1
bb1 (block):
  predecessor blocks: bb2 bb3
  [13] $10 = LoadLocal y$1
  [14] $12 = StoreLocal Let x$11 = $10
  [15] $13 = <undefined>
  [16] Return $13

bb0~3의 block이란 단위로 나눠지게 되고, 각 블럭은 instruction과 terminal로 이뤄지게 됩니다.
bb0의 경우는 아래와 같이 총 5채의 Instruction과 1개의 Terminal로 이뤄지게 됩니다.

// Instruction
[1] $0 = 333
[2] $2 = StoreLocal Let y$1 = $0
[3] $7 = LoadLocal y$1
[4] $8 = 1
[5] $9 = Binary $7 > $8

// Terminal
[6] If  $9) then:bb2 else:bb3 fallthrough=bb1

타입으로도 살펴보면 이렇게 표현하고 있습니다

// HIR.ts
export type BasicBlock = {
  kind: BlockKind;
  id: BlockId;
  instructions: Array<Instruction>; // 명령어들
  terminal: Terminal;  // 종결
  preds: Set<BlockId>;
  phis: Set<Phi>;
};

각 명령어들은 아래와 같은 타입을 가지고 있습니다.
명령어는 좌변값(lvalue) = 우변값(value) 꼴로 이뤄져 있습니다.

export type Instruction = {
  id: InstructionId;    // 명령어의 고유 식별자
  lvalue: Place;        // 결과값이 저장될 위치
  value: InstructionValue; // 명령어의 실제 값/연산
  loc: SourceLocation;  // 원본 소스 코드에서의 위치
};

몇개의 명령어로 확인해보면 아래와 같습니다.

// [1] $0 = 333
{
  id: 1,
  lvalue: { 
    kind: "Identifier", 
    identifier: { id: 0, ... }, ... 
  },
  value: { kind: "Primitive", value: 333, ... },
  loc,
}
// [2] $2 = StoreLocal Let y$1 = $0
{
  id: 2,
  lvalue: { 
    kind: "Identifier", 
    identifier: { id: 2, ... }, ... 
  },
  value: {
    kind: "StoreLocal",
    lvalue: {
      kind: "Let",
      place: { 
        kind: "Identifier", 
        identifier: { id: 1, name: { value: "y"}, ... }, ...
      },
    },
    value: { 
      kind: "Identifier", 
      identifier: { id: 0, ... }, ...
    },
  },
}

**[1]**번 명령어의 경우는 제일 단순한 형태로 좌변에는 identifier가, 우변에는 Primitive가 들어가게 됩니다.
**[2]**번의 경우는 조금 복잡한데요. 좌변에는 identifier가, 우변에는 StoreLocal이 들어가게 됩니다.
이때, StoreLocal또한 좌변과 우변으로 이뤄져 있습니다.
좌변에는 Let y$1이 들어가고, 우변에는 identifier가 들어가게 됩니다.

자 그럼 이제 변환과정을 살펴보도록 하죠!

block의 instruction들을 하나씩 방문하게 됩니다.

for (const instr of block.instructions) {
  mapInstructionOperands(instr, (place) => builder.getPlace(place));
  mapInstructionLValues(instr, (lvalue) => builder.definePlace(lvalue));
  // ...
}

각 instruction에 대해서 mapInstructionOperands와 mapInstructionLValues를 통해 operand와 lvalue를 변환해주게 됩니다.
operand는 instruction의 우변에 해당하고, lvalue는 instruction의 좌변에 해당합니다. 좌변(LValue)의 경우는 값이 쓰이는 위치이기 때문에, 위에서 살펴봤던 새로운 id를 할당해주는 definePlace를 통해 변환해주게 됩니다.
우변(OPerands)의 경우는 값을 참조하는 위치이기 때문에, getPlace를 통해 변환해주게 됩니다.

어떤 과정을 통해서 값을 가져오는지 getPlace를 살펴봅시다.
getIdAt를 통해서 id를 가져오고 있군요. 그럼 getIdAt을 살펴보도록 하죠.

class SSABuilder {
  getPlace(oldPlace: Place): Place {
    const newId = this.getIdAt(oldPlace.identifier, this.#current!.id);
    return {
      ...oldPlace,
      identifier: newId,
    };
  }
  getIdAt(oldId: Identifier, blockId: BlockId): Identifier {
    // check if Place is defined locally
    const block = this.#blocks.get(blockId)!;
    const state = this.#states.get(block)!;

    if (state.defs.has(oldId)) {
      return state.defs.get(oldId)!;
    }

    if (block.preds.size == 0) {
      /*
       * We're at the entry block and haven't found our defintion yet.
       * console.log(
       *   `Unable to find "${printIdentifier(
       *     oldId
       *   )}" in bb${blockId}, assuming it's a global`
       * );
       */
      this.#unknown.add(oldId);
      return oldId;
    }

    if (this.unsealedPreds.get(block)! > 0) {
      /*
       * We haven't visited all our predecessors, let's place an incomplete phi
       * for now.
       */
      const newId = this.makeId(oldId);
      state.incompletePhis.push({ oldId, newId });
      state.defs.set(oldId, newId);
      return newId;
    }

    // Only one predecessor, let's check there
    if (block.preds.size == 1) {
      const [pred] = block.preds;
      const newId = this.getIdAt(oldId, pred);
      state.defs.set(oldId, newId);
      return newId;
    }
    // There are multiple predecessors, we may need a phi.
    const newId = this.makeId(oldId);
    /*
     * Adding a phi may loop back to our block if there is a loop in the CFG.  We
     * update our defs before adding the phi to terminate the recursion rather than
     * looping infinitely.
     */
    state.defs.set(oldId, newId);
    return this.addPhi(block, oldId, newId);
  }
}

getIdAt는 여러 경우에 대해서 id를 가져오는데요.
하나씩 살펴보도록 하죠.

1. 현재 블럭에서 oldId가 정의되어 있는 경우, 해당 id를 반환합니다.

if (state.defs.has(oldId)) {
  return state.defs.get(oldId)!;
}

이전에 definePlcae에서 새로운 id를 발급하고 나면 state의 defs id쌍을 저장해두었었습니다.
이때 oldId가 정의되어 있는 경우, 해당 id를 반환하게 됩니다.

definePlace(oldPlace: Place): Place {
  const oldId = oldPlace.identifier;
  const newId = this.makeId(oldId);
  this.state().defs.set(oldId, newId); // 새로운 id와 함께 저장
  return {
    ...oldPlace,
    identifier: newId,
  };
}

2. entry block인 경우, id를 찾지 못한 경우는 global로 간주하고 반환합니다.

if (block.preds.size == 0) {
  this.#unknown.add(oldId);
  return oldId;
}

entry block인 경우는 preds가 없기 때문에 global로 간주하고 반환하게 됩니다.

preds는 predecessor(선행자)를 의미합니다. 어디서 들어본 적 있지 않나요?
앞에서 Braun의 알고리즘에서 predecessor를 통해 이전 블럭으로 올라가는 것을 살펴봤었죠.

3. predecessor가 남아있는 경우, incomplete phi를 추가하게 됩니다.

if (this.unsealedPreds.get(block)! > 0) {
  const newId = this.makeId(oldId);
  state.incompletePhis.push({ oldId, newId });
  state.defs.set(oldId, newId);
  return newId;
}

아직 unsealed 개념에 대해 살펴보지 않았음으로 일단 넘어가주도록 합니다.

4. predecessor가 하나인 경우, predecessor로 이동하여 id를 찾아 반환하게 됩니다.

if (block.preds.size == 1) {
  const [pred] = block.preds;
  const newId = this.getIdAt(oldId, pred);
  state.defs.set(oldId, newId);
  return newId;
}

predecessor가 하나라면 고민할 필요 없이 이전 블럭을 탐색해야합니다, 이때 재귀적으로 탐색하게 됩니다.

5. predecessor가 여러개인 경우, phi함수를 추가하게 됩니다.

const newId = this.makeId(oldId);
state.defs.set(oldId, newId);
return this.addPhi(block, oldId, newId);

이전에 살펴봤던 Braun의 알고리즘에서 predecessor가 여러개인 경우, 그 블럭에서 phi함수를 추가하는 것을 볼 수 있었습니다.
이 경우가 바로 그 구현 부분입니다! 🤓
논문에서 봐왔던대로 구현이 되어있군요.

그럼 이어서 addPhi함수가 어떻게 phi함수를 추가하는지 살펴보도록 하죠.

addPhi(block: BasicBlock, oldId: Identifier, newId: Identifier): Identifier {
  const predDefs: Map<BlockId, Identifier> = new Map();
  for (const predBlockId of block.preds) {
    const predId = this.getIdAt(oldId, predBlockId);
    predDefs.set(predBlockId, predId);
  }

  const phi: Phi = {
    kind: "Phi",
    id: newId,
    operands: predDefs,
    type: makeType(),
  };

  block.phis.add(phi);
  return newId;
}

이전에 정의된 것들을 담을 predDefs를 blockId와, identifier로 구성된 Map으로 만들어줍니다.

현재 블럭의 선행자들 block.preds를 순회하며 재귀적으로 getIdAt을 통해 id를 찾아 predDefs에 저장해줍니다.
그렇게 얻어진 predDefs를 통해 phi를 만들어주고, block.phis에 추가해줍니다.

함수표현식, 객체 메서드 처리

if (
  instr.value.kind === "FunctionExpression" ||
  instr.value.kind === "ObjectMethod"
) {
  const loweredFunc = instr.value.loweredFunc.func;
  const entry = loweredFunc.body.blocks.get(loweredFunc.body.entry)!;
  builder.defineFunction(loweredFunc);
  builder.enter(() => {
    loweredFunc.context = loweredFunc.context.map((p) =>
      builder.getPlace(p)
    );
    loweredFunc.params = loweredFunc.params.map((param) => {
      if (param.kind === "Identifier") {
        return builder.definePlace(param);
      } else {
        return {
          kind: "Spread",
          place: builder.definePlace(param.place),
        };
      }
    });
    enterSSAImpl(loweredFunc, builder, rootEntry);
  });
}

FunctionExpression과 ObjectMethod의 경우는 nested된 함수이기 때문에, 재귀적으로 enterSSAImpl을 통해 다시 SSA 변환을 진행해주게 됩니다.

종결 처리

mapTerminalOperands(block.terminal, (place) => builder.getPlace(place));

terminal의 경우 아래와 같은 케이스 입니다.

[6] If  $9) then:bb2 else:bb3 fallthrough=bb1 // $9
[9] Goto bb1
[12] Goto bb1
[16] Return $13  // $13

이 경우에서 다른 요소들($9,$13)을 참조하는 경우가 있음으로 id를 찾아서 변환해주게 됩니다.

최종 비교

여기까지 하면 HIR을 이루는 모든 요소들에 대해서 정적 단일 대입(SSA)를 해주게 됩니다. 아까의 예제 코드는 이런 형태로 변환될 것입니다.

https://playground.react.dev/#N4Igzg9grgTgxgUxALhAMygOzgFwJYSYAEaEEAFAJRHAA6xRANgjkQJ5EC8RAzHwNz16RInjRFyHAHxEAjNToMRHbrLWCGAXyIJGYBDWEj2XIgCYLGkZqENmrAB6m2GzSE1A

function foo
bb0 (block):
  [1] $14 = 333
  [2] $16 = StoreLocal Let y$15 = $14
  [3] $17 = LoadLocal y$15
  [4] $18 = 1
  [5] $19 = Binary $17 > $18
  [6] If  $19) then:bb2 else:bb3 fallthrough=bb1
bb2 (block):
  predecessor blocks: bb0
  [7] $20 = 111
  [8] $22 = StoreLocal Reassign y$21 = $20
  [9] Goto bb1
bb3 (block):
  predecessor blocks: bb0
  [10] $23 = 222
  [11] $25 = StoreLocal Reassign y$24 = $23
  [12] Goto bb1
bb1 (block):
  predecessor blocks: bb2 bb3
  y$26: phi(bb2: y$21, bb3: y$24)
  [13] $27 = LoadLocal y$26
  [14] $29 = StoreLocal Let x$28 = $27
  [15] $30 = <undefined>
  [16] Return $30

눈으로는 비교가 어려우니 diff를 통해 비교해보도록 하죠!

y의 값들을 살펴보면 모두 개별의 값으로 변환 되었고, phi함수가 추가된 것을 볼 수 있습니다.

루프 처리 (심화과정)

위의 과정까지만 살펴봐도 SSA 변환과정이 어떤 과정인지 충분히 이해 할 수 있으니 넘어가도 괜찮습니다.
하지만 더 깊게 들어가보자면 루프에 대한 처리가 필요하게 됩니다.

function foo() {
  let x = 1;
  for (let i = 0; i < 10; i++) {
    x += 1;
  }
  return x;
}

https://playground.react.dev/#N4Igzg9grgTgxgUxALhAMygOzgFwJYSYAEaEEAFAJRHAA6xRANgjkQB5EC8RAjANz0iJCDCLlmrPFyIAGPkSkAeXnIUBqNdToMhHNd36CiAXyMwWsYmwGZjIY0A

이런 for문이 있는 코드를 살펴봅시다.
우리가 여태 살펴봤던 조건문 같은 경우는 비교적 직관적으로 위에서 아래로의 흐름 이였습니다.
위쪽 블럭의 분기로 부터 아래에서 합류되는 경우가 대부분이었죠.

하지만 루프의 경우는 다시 위로 올라가는 경우(back edge)가 생기게 됩니다.
이런 경우는 어떻게 처리해야할까요?

우선 HIR로 변환먼저 해봅시다.

function foo
bb0 (block):
  [1] $0 = 1
  [2] $2 = StoreLocal Let x$1 = $0
  [3] For init=bb3 test=bb1 loop=bb5 update=bb4 fallthrough=bb2
bb3 (loop):
  predecessor blocks: bb0
  [4] $3 = 0
  [5] $5 = StoreLocal Let i$4 = $3
  [6] Goto bb1
bb1 (loop):
  predecessor blocks: bb3 bb4
  [7] $12 = LoadLocal i$4
  [8] $13 = 10
  [9] $14 = Binary $12 < $13
  [10] Branch (<unknown> $14) then:bb5 else:bb2
bb5 (block):
  predecessor blocks: bb1
  [11] $7 = LoadLocal x$1
  [12] $8 = 1
  [13] $9 = Binary $7 + $8
  [14] $10 = StoreLocal Reassign x$1 = $9
  [15] $11 = LoadLocal x$1
  [16] Goto(Continue) bb4
bb4 (loop):
  predecessor blocks: bb5
  [17] $6 = PostfixUpdate i$4 = i$4 ++
  [18] Goto bb1
bb2 (block):
  predecessor blocks: bb1
  [19] $15 = LoadLocal x$1
  [20] Return $15

이해가 쉽도록 CFG를 그려보도록 하겠습니다.

phi함수는 분기가 합류하는지점에 놓아주면 되었었죠.
그렇다면 bb3, bb4로 부터 합류하는 bb1에 phi함수를 놓아주면 될 것 같습니다.

마침 bb1 블럭을 살펴보면 predecessor도 주어져 있네요. 그럼 이전에 살펴봤던 재귀적인 방법으로 이전블럭을 타고 올라가면 되는걸까요?
하지만 이경우는 다릅니다.

우리가 terminal의 처리 이후에 넘어간 과정이 하나 있습니다.
terminal successor에 대한 처리가 있습니다. 터미널 후속 블럭에 대한 처리입니다.
터미널 후속 블럭이란, terminal의 경우에 If, Goto, for와 같은 명령어가 있을 경우, 그 명령어에 대한 후속 블럭을 의미합니다.
if 문의 경우는 then(consequent), else(alternate)로 나뉘게 되고, for문의 경우는 init, test, loop, update로 이런식으로 정의된 후속 블럭이 있습니다.

mapTerminalOperands(block.terminal, (place) => builder.getPlace(place));
for (const outputId of eachTerminalSuccessor(block.terminal)) {
    const output = func.body.blocks.get(outputId)!;

    let count;
    if (builder.unsealedPreds.has(output)) {
      count = builder.unsealedPreds.get(output)! - 1;
    } else {
      count = output.preds.size - 1;
    }
    builder.unsealedPreds.set(output, count);

    if (count === 0 && visitedBlocks.has(output)) {
      builder.fixIncompletePhis(output);
    }
  }

후속 블럭에 대해서 해당 블럭의 선행자(preds) 개수를 카운트 하게 됩니다. 처음 훑어보는 블럭이라면 선행자 개수를 count에 넣어서 unsealedPreds에 저장하게 됩니다.

count = output.preds.size - 1;
builder.unsealedPreds.set(output, count);

이미 훑었던 후속 블럭이라면, 아까 set해뒀던, count에서 카운트를 하나 빼주게 됩니다.

count = builder.unsealedPreds.get(output)! - 1;

그 count가 0이 되었고, 이미 방문한 블럭이라면, 모든 선행자를 방문 했음을 의미하게 됩니다.
이때, fixIncompletePhis를 통해 phi함수를 추가해주게 됩니다.

이해를 돕기위해 위의 예제를 통해서 블럭의 순서대로 어떻게 처리되는지 살펴보도록 하죠.

1. bb0

[3] For init=bb3 test=bb1 loop=bb5 update=bb4 fallthrough=bb2

bb0의 경우 For문의 후속 블럭은 init인 bb3이 됩니다.
최초 for문이 시작되는 부분이기 때문에 init 블럭이 됩니다.

export function* eachTerminalSuccessor(terminal: Terminal): Iterable<BlockId> {
  switch(terminal.kind){
    case "for": {
      yield terminal.init;
      break;
    }
    // ...
  }
}

이때 output, 후속 블럭인 bb3이 되고, bb3의 preds는 bb0 1개이기 때문에 count는 0이 됩니다.
unsealedPreds에 {bb3: 0}이 저장되게 됩니다.
이때 visitedBlocks에는 bb3이 없기 때문에 fixIncompletePhis는 실행되지 않습니다.

2. bb3

[6] Goto bb1

bb3의 경우 Goto문의 후속 블럭은 bb1이 됩니다.
bb1의 preds는 bb3, bb4이기 때문에 count는 1이 됩니다.
unsealedPreds를 {bb3: 0, bb1: 1}로 업데이트 해줍시다.

3. bb1

bb1의 종결문을 처리하기 전에 instruction 처리 과정에서 분기를 만나게 됩니다.
위에서 살펴봤던 getIdAt을 통해 id를 처리하는 과정에서 아까 우리가 스킵했던 이 조건문을 만나게 됩니다.

getIdAt(oldId: Identifier, blockId: BlockId): Identifier {
  // ...
  if (this.unsealedPreds.get(block)! > 0) {
    /*
      * We haven't visited all our predecessors, let's place an incomplete phi
      * for now.
      */
    const newId = this.makeId(oldId);
    state.incompletePhis.push({ oldId, newId });
    state.defs.set(oldId, newId);
    return newId;
  }
  // ...
}

이때 unsealedPreds에서 bb1의 count는 1이기 때문에 이 조건문이 참이 되게 됩니다.
unsealed된 선행블럭이 남아있다는 의미이므로, 바로 phi 함수를 추가하지 않고, incompletePhis에 필요한 정보를 추가해줍니다.

다시 이어서 종결문을 처리해봅시다

[10] Branch (<unknown> $14) then:bb5 else:bb2

bb1의 경우 Branch문의 후속 블럭은 then(consequent):bb5, else(alternate):bb2가 됩니다.

case "branch": {
  yield terminal.consequent;
  yield terminal.alternate;
  break;
}

차례대로 처리하고 나면 unsealedPreds는 {bb3: 0, bb1: 1, bb5: 0, bb2: 0}이 됩니다.
둘다 0이 되었고, visitedBlocks에는 bb5, bb2가 없기 때문에 fixIncompletePhis는 실행되지 않습니다.

4. bb5

[16] Goto(Continue) bb4

bb5의 경우 Goto문의 후속 블럭은 bb4가 됩니다.
unsealedPreds는 {bb3: 0, bb1: 1, bb5: 0, bb2: 0, bb4: 0}이 됩니다.

5. bb4

[18] Goto bb1

bb4의 경우 Goto문의 후속 블럭은 bb1이 됩니다.
bb1은 이미 unsealedPreds에 있기 때문에 이전 count를 가져와 1을 빼줍니다.
unsealedPreds는 {bb3: 0, bb1: 0, bb5: 0, bb2: 0, bb4: 0}이 됩니다.

이때는 visitedBlocks에 bb1이 있기 때문에 fixIncompletePhis가 실행되게 됩니다.

fixIncompletePhis(block: BasicBlock): void {
  const state = this.#states.get(block)!;
  for (const phi of state.incompletePhis) {
    this.addPhi(block, phi.oldId, phi.newId);
  }
}

아까 bb1에서 incompletePhis에 추가해둔 phi함수를 추가해주게 됩니다.
이로써 루프에 대한 phi함수 처리까지 완료 할 수 있게 됩니다.

마지막으로 결과를 확인해볼까요?

function foo
bb0 (block):
  [1] $17 = 1
  [2] $19 = StoreLocal Let x$18 = $17
  [3] For init=bb3 test=bb1 loop=bb5 update=bb4 fallthrough=bb2
bb3 (loop):
  predecessor blocks: bb0
  [4] $20 = 0
  [5] $22 = StoreLocal Let i$21 = $20
  [6] Goto bb1
bb1 (loop):
  predecessor blocks: bb3 bb4
  i$23: phi(bb3: i$21, bb4: i$34) // phi 함수가 추가됨
  x$27: phi(bb3: x$18, bb4: x$31) // phi 함수가 추가됨
  [7] $24 = LoadLocal i$23
  [8] $25 = 10
  [9] $26 = Binary $24 < $25
  [10] Branch (<unknown> $26) then:bb5 else:bb2
bb5 (block):
  predecessor blocks: bb1
  [11] $28 = LoadLocal x$27
  [12] $29 = 1
  [13] $30 = Binary $28 + $29
  [14] $32 = StoreLocal Reassign x$31 = $30
  [15] $33 = LoadLocal x$31
  [16] Goto(Continue) bb4
bb4 (loop):
  predecessor blocks: bb5
  [17] $35 = PostfixUpdate i$34 = i$23 ++
  [18] Goto bb1
bb2 (block):
  predecessor blocks: bb1
  [19] $36 = LoadLocal x$27
  [20] Return $36

적절한 위치에 phi함수가 추가되어 있음을 확인할 수 있습니다.

마무리

이번 글에서는 React Compiler의 SSA 변환과정에 대해서 살펴보았습니다.
SSA 변환은 정적 단일 대입이라는 개념으로, 변수에 대한 대입이 한번만 이루어지게 되는 것을 의미합니다.
그 과정에서 분기에 대한 처리를 위해, phi 함수라는 개념을 도입하게 되었고, 어떻게 phi 함수를 추가하는지 살펴보았습니다.
이를 통해 변수에 대한 대입이 어디서 이루어졌는지 추적할 수 있게 되고, 최적화에도 도움이 됩니다.

그 과정에서 논문을 두편에 걸쳐서 살펴보았는데요.
Cytron 알고리즘과 Braun 알고리즘의 처리 과정과 각각의 장단점도 살펴보았습니다.
그리고 원래 목적이었던, React Compiler의 SSA 변환과정을 살펴보았습니다.

다음 글에서는 이렇게 바꾼 SSA 형태를 통해서 어떤 최적화를 진행하는지 살펴보도록 하겠습니다. 🚀

참고

• https://www.cs.cornell.edu/courses/cs4120/2023sp/notes.html?id=reachdef
• https://groups.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf
• https://pages.cs.wisc.edu/~fischer/cs701.f05/lectures/Lecture22.pdf
• https://www.cs.princeton.edu/courses/archive/spring22/cos320/lectures/ssa.pdf