Three-Address Code 와 Static Single Assignment (SSA)
컴파일러가 코드를 최적화하려면, 소스 코드를 분석하기 쉬운 형태로 변환하는 과정이 필요하다. 이때 사용되는 대표적인 중간 표현(IR) 기법이 Three-Address Code와 정적 단일 할당(SSA)이다.
Three-Address Code
Three-Address Code(3AC)는 하나의 명령문에 최대 3개의 주소(피연산자 2개 + 결과값 1개)를 가지는 형태로 표현하는 중간 표현이다. 일반적으로 다음과 같은 형태를 가진다.
\[x = y \; \textit{op} \; z\]여기서 $x$는 결과를 저장할 변수, $y$와 $z$는 피연산자, $\textit{op}$는 연산자이다.
예시
아래와 같은 식이 있다고 하자.
\[x = a + b \times c \div d\]이를 Three-Address Code로 변환하면 다음과 같다.
t1 = b * c
t2 = t1 / d
x = a + t2
각 줄이 하나의 연산만 수행하고, 임시 변수($t_1$, $t_2$)를 사용하여 중간 결과를 저장한다. 이렇게 쪼개 놓으면 컴파일러가 레지스터를 할당하거나 최적화를 수행하기가 훨씬 편해진다.
정적 단일 할당 (SSA)
정적 단일 할당(SSA, Static Single Assignment)은 Three-Address Code를 한 단계 더 발전시킨 중간 표현 방식이다.
핵심 규칙
SSA의 핵심 규칙은 단 하나다.
모든 변수는 정확히 한 번만 할당된다.
즉, 같은 변수 이름에 값을 두 번 이상 대입하지 않는다. 재할당이 필요한 경우에는 새로운 이름의 변수를 만든다. 이것이 ‘정적 단일 할당’이라는 이름의 유래이다.
변환 예시
다음 Three-Address Code를 보자.
p = a + b
q = p - c
p = q * d
p = e - p
q = p + q
여기서 $p$와 $q$는 여러 번 재할당되고 있다. 같은 변수 이름 $p$가 서로 다른 값을 가리키기 때문에, 컴파일러가 데이터 흐름을 추적하기 어렵다.
이를 SSA 형식으로 변환하면 다음과 같다.
p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p2
q2 = p3 + q1
모든 할당이 고유한 변수 이름($p_1, p_2, p_3, q_1, q_2$)을 사용하므로, 각 변수의 정의 지점과 사용 지점이 명확해진다.
Phi 함수 ($\phi$)
조건 분기가 있는 경우, 어떤 경로를 통해 왔느냐에 따라 변수의 값이 달라질 수 있다. SSA에서는 이를 $\phi$ 함수(phi function)로 처리한다.
if (condition)
x1 = 1
else
x2 = 2
x3 = φ(x1, x2)
$\phi$ 함수는 실제로 실행되는 명령어가 아니라, “이 지점에서 $x_3$의 값은 어떤 경로로 왔느냐에 따라 $x_1$ 또는 $x_2$이다”라는 것을 표현하는 표기법이다.
장점
SSA 형식을 사용하면 각 변수가 한 번만 정의되므로, 컴파일러가 다양한 최적화를 수행하기 용이해진다.
- 상수 전파(Constant Propagation): 변수의 값이 상수인 경우, 사용 지점에 상수를 직접 대입할 수 있다.
- 죽은 코드 제거(Dead Code Elimination): 정의된 후 한 번도 사용되지 않는 변수를 쉽게 찾아 제거할 수 있다.
- 공통 부분식 제거(Common Subexpression Elimination): 동일한 연산이 반복되는 경우를 쉽게 탐지할 수 있다.
SSA는 LLVM, GCC 등 현대 컴파일러에서 핵심적인 중간 표현으로 널리 사용되고 있다.