주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.
주의 : 번역이 개판이므로 이상하면 원문을 참조하세요.
원문 : Static single assignment form, Wikipedia.
컴퓨터 디자인에서, static single assignment form( 보통 SSA form 이나 단순하게 SSA 로 발음됨 ) 은 중간 표현( intermediate representation, IR )의 속성( property )입니다. 그것은 각 변수들이 정확히 한 번만 할당되고 모든 변수들은 그것이 사용되기 전에 정의될 것을 요구합니다. 원래의 IR 에서 현재 존재하는 변수들은 여러 버전들로 나뉩니다. 새로운 변수들은 일반적으로 텍스트북에서의 서브스크립트( subscript, 아래첨자 )를 원래 이름에 붙여서 식별됩니다. 그래서 모든 정의들은 자신만의 원래 버전을 획득하게 됩니다. SSA 폼에서 use-def chain 들은 명시적( explicit )이며, 각각은 단일 요소를 포함합니다.
SSA 는 Barry K.Rosen, Kark N. Wegman, F. Kenneth Zadeck 에 의해 1988 년에 제안되었습니다. IBM 에서 근무하던 Ron Crytron 과 Jeanne Ferrante 및 이전의 세 연구자들은 SSA 폼을 효율적으로 계산할 수 있는 알고리즘을 개발했습니다.
사람들은 Fortran 이나 C 를 위한 컴파일러에서 SSA 를 검색하는 것을 기대할 수 있습니다. 반면에 Scheme, ML, Haskell 과 같은 함수형 언어( functional language ) 컴파일러들에서는 continuation-passing style 을 일반적으로 사용했습니다. SSA 는 공식적으로는, 중간 표현으로서 사용될 때는 발생하지 않는, non-local control flow 를 제외하고는 잘 동작하는( well-behaved ) CPS 의 서브셋과 동일합니다. So optimizations and transformations formulated in terms of one immediately apply to the other.
Benefits
SSA 의 주요한 유용성은 다양한 컴파일러에서의 최적화의 결과를 동시에 단순화하고 증진시킨다는 것입니다. 이는 변수의 속성들을 단순화함으로써 수행됩니다. 예를 들어, 다음 코드 조각을 살펴 봅시다.
y := 1
y := 2
x := y
인간들은 첫 번째 할당이 불필요하며 세 번째 라인에서 사용되고 있는 y 의 값이 두 번째 y 할당에서 온다고 생각할 수 있습니다. 프로그램은 reaching definition analysis 를 수행해야만 이를 결정할 수 있을 겁니다. 하지만 프로그램이 SSA 폼이라면, 이것들은 둘 다 임시적( intermediate )입니다:
y1 := 1
y2 := 2
x1 = y2
SSA 를 사용하거나 매우 강화된 컴파일러 최적화 알고리즘들은 다음과 같습니다 :
- Constant propagation
- Value range propagation
- Sparse conditional constant propagation
- Dead code elimination
- Global value numbering
- Partial redundancy elimination
- Strength reduction
- Register allocation
Converting to SSA
일반 코드를 SSA 폼으로 변환하는 것은 주로 각각의 할당의 대상을 새로운 변수로 치환하고 각각의 변수의 사용을 그 지점에 도달하는 "버전"의 변수로 치환하는 것입니다. 예를 들어, 다음과 같은 제어 흐름 그래프( control flow graph )를 살펴 봅시다:
"x <-- x - 3" 의 왼쪽에 있는 이름을 변경하고 그 다음에 x 를 사용하는 곳을 그 새로운 이름으로 변경하는 것은 프로그램을 수정하지 않고 종료될 수 있게 할 것입니다. 이것은 SSA 에서 새로운 두 개의 변수들을 생성함으로써 이용될 수 있습니다 : x1, x2. 각각의 변수들은 한 번만 할당됩니다. 이런식으로 차이가 나는 서브스크립트를 제공함으로써 다른 변수들이 만들어집니다:
각각이 사용하는 정의가 무엇을 참조하고 있는지는 명확합니다. 한 가지 경우만을 제외하고는 말이죠: 바닥에 있는 블락에서 y 의 사용은 y1 이나 y2 를 가리킬 수 있으며, 이는 제어 흐름이 타고 왔느냐에 의존합니다.
이를 해결하기 위해서, 마지막 블락에 특별한 구문이 삽입되는데, 이를 파이( Φ, Phi ) 함수라고 부릅니다. 이 구문은 y3 라 불리는 새로운 y 에 대한 정의를 생성하는데, 이는 y1 이나 y2 에 의해 선택됨으로써 생성되고, 과거의 제어 흐름에 의존됩니다.
이제 마지막 블락에서는 단순히 y3 를 사용하며 정확한 값은 두 가지 방식으로 획득될 것입니다. x 에 대한 Φ 함수는 불필요합니다: 한 가지 버전의 x 만이 존재하며, 여기에는 x2 가 도달하고 있습니다. 그래서 문제가 없습니다( 다시 말해, Φ ( x2, x2 ) = x2 입니다 ).
주어진 임의의 제어 흐름 그래프에서, 어디에 Φ 함수가 삽입되어야 하며 그것을 위한 변수가 무엇인지를 이야기하는 것은 어려울 수 있습니다. 이러한 범용적인 문제는 ( 아래에 나오는 ) dominance frontiers 라 불리는 개념을 사용해서 계산될 수 있는 효율적인 해를 가지고 있습니다.
Φ 함수는 거의 대부분의 머신에서 머신 연산으로서 구현되지는 않습니다. 컴파일러가, Φ 함수를 메모리의 같은 위치( 혹은 같은 레지스터 )를 Φ 함수의 입력으로 산출하는 모든 연산을 위한 목적지로서 사용함으로써, Φ 함수를 간단하게 구현할 수 있습니다. 그러나 이러한 접근법은, wide-issue 머신에서 발생할 수 있는 것처럼, 동시적 연산들이 추측에 근거해( speculatively ) Φ 함수의 입력을 산출하고 있을 때는 사용할 수 없습니다. 일반적으로 wide-issue 머신은, Φ 함수를 구현하기 위해서, 그러한 상황들에서 사용되는 컴파일러에 의해 제공되는 선택 명령을 가지고 있습니다.
Kenny Zadeck 에 의하면 Φ 함수들은 SSA 가 IBM 연구소에서 1980 년대에 개발되는 도중에는 원래 phony 함수들이었다고 합니다. Φ 함수의 공식적인 이름은 학술 논문에서 처음 출판될 때 적용되었다고 합니다.
[ 하략 ... 원문( Static single assignment form, Wikipedia. ) 을 참조하세요 ].