SSA

* v8에서도 사용됨 (Maglev , Turbofan)

 

 

v8 1-day 분석을 하던 도중 SSA에 관련된 내용이 있길래 공부를 해두면 나중에도 도움이 될 것 같아서 정리해보기로 했다. 

 

위키백과에선 이런식으로 나온다.

 

컴파일러 설계 에서 정적 단일 할당 형식 ( SSA 형식 또는 간단히 SSA 라고 약칭함 ) 은 각 변수가 정확히 한 번만 할당되는 중간 표현 (IR)의 한 유형입니다. SSA는 LLVM , GNU 컴파일러 컬렉션 , 그리고 여러 상용 컴파일러를 포함하여 명령형 언어용 대부분의 고품질 최적화 컴파일러에서 사용됩니다 .

 

즉 SSA에서는 각 변수에 대해서 한번만 값을 할당을 한다. 

새로운 값이 필요할 때마다 기존 변수를 덮어쓰지 않고 새로운 이름의 변수를 생성한다. 

분기(조건문 등)에서 여러 경로로부터 값을 받아야할 때는 ϕ(파이) 함수를 사용한다. 

 

SSA 사용 이유?

변수 정의 / 사용 추적이 쉬움. 

각 변수는 한 번만 정의되므로 , 어떤 값을 사용하는지 정확하게 추적이 가능하다. 

디펜던시 분석 (Dependence Analysis), 레지스터 할당 등이 쉬워진다.

 

즉 최적화를 위해서 사용하고 기계어 코드를 더 간결하고 효율적으로 만드는데 사용

 

최적화 용이

Dead Code Elimination :  사용되지 않는 변수 제거 

Constant Propagation: 상수 값 미리 계산
Common Subexpression Elimination: 동일 계산 제거

 

언제 사용될까?

 

[소스코드] 
   ↓ 파싱
[AST] 
   ↓
[중간 표현 (IR)] 
   ↓
[최적화] ← ★ 이 단계에서 SSA가 사용됨
   ↓
[기계어 코드 생성]

 

최적화 단계에서 프로그램을 SSA 형태로 바꿔서 분석하고 최적화한 다음에 다시 일반 형태로 되돌린 후 기계어로 변환한다. 

 

 

 

예시 

일반적인 중간 표현 (non-SSA) 

a = 1;
if (x > 0) {
    a = 2;
}
print(a);

 

여기에선 a를 2번 할당 했으므로 SSA 형태가 아니다. 

 

이를 SSA로 변환하면 

a1 = 1;
if (x > 0) {
    a2 = 2;
} else {
    a2 = a1;
}
print(a2);

 

또는 파이 함수로 

a1 = 1;
if (x > 0)
    a2 = 2;
else
    a2 = a1;
a3 = φ(a1, a2);
print(a3);

 

 

파이함수란? 

 

파이 함수는 SSA 형태의 중간 표현 (IR)에서 사용되는 가상의 함수로 여러 개의 제어 흐름(브랜치)에서 오는 변수 값을 선택하는 역할을 한다. 

 

SSA에서는 변수를 한번만 할당 가능한데 만약 분기문에서 a = 1 , a = 2이런식으로 나눠진다면 할당을 2번해야하는 경우가 발생한다. 그러므로 파이 함수를 사용하여 이를 해결했다. 

+ 삼항 연산자라고 생각하면 편하

 

코드를 실행하다보면 분기문을 만날 수 있는데 이때 if , switch 등등 다양하게 만날 수 있다. 

그럼  if문 값에 따라서 값이 달라질텐데 예시를 들어 보면 

 

일반적인 코드가 아래와 같다면 

if (x > 0)
    a = 10;
else
    a = 20;
print(a);

 

if (x > 0)
    a1 = 10;
else
    a2 = 20;

a3 = φ(a1, a2);  // x가 0보다 크면 a1, 아니면 a2
print(a3);

 

if문의 값에 따라서 (참 , 거짓) 파이 값에서 전자 (참) , 후자(거짓)으로 a3에 값이 할당이 되게 된다. 

그러면 기존에 있던 값과 똑같이 동작하는 걸 알 수 있다.